| // RB tree implementation -*- C++ -*- |
| |
| // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 |
| // Free Software Foundation, Inc. |
| // |
| // This file is part of the GNU ISO C++ Library. This library is free |
| // software; you can redistribute it and/or modify it under the |
| // terms of the GNU General Public License as published by the |
| // Free Software Foundation; either version 3, or (at your option) |
| // any later version. |
| |
| // This library is distributed in the hope that it will be useful, |
| // but WITHOUT ANY WARRANTY; without even the implied warranty of |
| // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| // GNU General Public License for more details. |
| |
| // Under Section 7 of GPL version 3, you are granted additional |
| // permissions described in the GCC Runtime Library Exception, version |
| // 3.1, as published by the Free Software Foundation. |
| |
| // You should have received a copy of the GNU General Public License and |
| // a copy of the GCC Runtime Library Exception along with this program; |
| // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
| // <http://www.gnu.org/licenses/>. |
| |
| /* |
| * |
| * Copyright (c) 1996,1997 |
| * Silicon Graphics Computer Systems, Inc. |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Silicon Graphics makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| * |
| * |
| * Copyright (c) 1994 |
| * Hewlett-Packard Company |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Hewlett-Packard Company makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| * |
| * |
| */ |
| |
| /** @file stl_tree.h |
| * This is an internal header file, included by other library headers. |
| * You should not attempt to use it directly. |
| */ |
| |
| #ifndef _STL_TREE_H |
| #define _STL_TREE_H 1 |
| |
| #include <bits/stl_algobase.h> |
| #include <bits/allocator.h> |
| #include <bits/stl_function.h> |
| #include <bits/cpp_type_traits.h> |
| |
| _GLIBCXX_BEGIN_NAMESPACE(std) |
| |
| // Red-black tree class, designed for use in implementing STL |
| // associative containers (set, multiset, map, and multimap). The |
| // insertion and deletion algorithms are based on those in Cormen, |
| // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, |
| // 1990), except that |
| // |
| // (1) the header cell is maintained with links not only to the root |
| // but also to the leftmost node of the tree, to enable constant |
| // time begin(), and to the rightmost node of the tree, to enable |
| // linear time performance when used with the generic set algorithms |
| // (set_union, etc.) |
| // |
| // (2) when a node being deleted has two children its successor node |
| // is relinked into its place, rather than copied, so that the only |
| // iterators invalidated are those referring to the deleted node. |
| |
| enum _Rb_tree_color { _S_red = false, _S_black = true }; |
| |
| struct _Rb_tree_node_base |
| { |
| typedef _Rb_tree_node_base* _Base_ptr; |
| typedef const _Rb_tree_node_base* _Const_Base_ptr; |
| |
| _Rb_tree_color _M_color; |
| _Base_ptr _M_parent; |
| _Base_ptr _M_left; |
| _Base_ptr _M_right; |
| |
| static _Base_ptr |
| _S_minimum(_Base_ptr __x) |
| { |
| while (__x->_M_left != 0) __x = __x->_M_left; |
| return __x; |
| } |
| |
| static _Const_Base_ptr |
| _S_minimum(_Const_Base_ptr __x) |
| { |
| while (__x->_M_left != 0) __x = __x->_M_left; |
| return __x; |
| } |
| |
| static _Base_ptr |
| _S_maximum(_Base_ptr __x) |
| { |
| while (__x->_M_right != 0) __x = __x->_M_right; |
| return __x; |
| } |
| |
| static _Const_Base_ptr |
| _S_maximum(_Const_Base_ptr __x) |
| { |
| while (__x->_M_right != 0) __x = __x->_M_right; |
| return __x; |
| } |
| }; |
| |
| template<typename _Val> |
| struct _Rb_tree_node : public _Rb_tree_node_base |
| { |
| typedef _Rb_tree_node<_Val>* _Link_type; |
| _Val _M_value_field; |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| template<typename... _Args> |
| _Rb_tree_node(_Args&&... __args) |
| : _Rb_tree_node_base(), |
| _M_value_field(std::forward<_Args>(__args)...) { } |
| #endif |
| }; |
| |
| _GLIBCXX_PURE _Rb_tree_node_base* |
| _Rb_tree_increment(_Rb_tree_node_base* __x) throw (); |
| |
| _GLIBCXX_PURE const _Rb_tree_node_base* |
| _Rb_tree_increment(const _Rb_tree_node_base* __x) throw (); |
| |
| _GLIBCXX_PURE _Rb_tree_node_base* |
| _Rb_tree_decrement(_Rb_tree_node_base* __x) throw (); |
| |
| _GLIBCXX_PURE const _Rb_tree_node_base* |
| _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw (); |
| |
| template<typename _Tp> |
| struct _Rb_tree_iterator |
| { |
| typedef _Tp value_type; |
| typedef _Tp& reference; |
| typedef _Tp* pointer; |
| |
| typedef bidirectional_iterator_tag iterator_category; |
| typedef ptrdiff_t difference_type; |
| |
| typedef _Rb_tree_iterator<_Tp> _Self; |
| typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; |
| typedef _Rb_tree_node<_Tp>* _Link_type; |
| |
| _Rb_tree_iterator() |
| : _M_node() { } |
| |
| explicit |
| _Rb_tree_iterator(_Link_type __x) |
| : _M_node(__x) { } |
| |
| reference |
| operator*() const |
| { return static_cast<_Link_type>(_M_node)->_M_value_field; } |
| |
| pointer |
| operator->() const |
| { return &static_cast<_Link_type>(_M_node)->_M_value_field; } |
| |
| _Self& |
| operator++() |
| { |
| _M_node = _Rb_tree_increment(_M_node); |
| return *this; |
| } |
| |
| _Self |
| operator++(int) |
| { |
| _Self __tmp = *this; |
| _M_node = _Rb_tree_increment(_M_node); |
| return __tmp; |
| } |
| |
| _Self& |
| operator--() |
| { |
| _M_node = _Rb_tree_decrement(_M_node); |
| return *this; |
| } |
| |
| _Self |
| operator--(int) |
| { |
| _Self __tmp = *this; |
| _M_node = _Rb_tree_decrement(_M_node); |
| return __tmp; |
| } |
| |
| bool |
| operator==(const _Self& __x) const |
| { return _M_node == __x._M_node; } |
| |
| bool |
| operator!=(const _Self& __x) const |
| { return _M_node != __x._M_node; } |
| |
| _Base_ptr _M_node; |
| }; |
| |
| template<typename _Tp> |
| struct _Rb_tree_const_iterator |
| { |
| typedef _Tp value_type; |
| typedef const _Tp& reference; |
| typedef const _Tp* pointer; |
| |
| typedef _Rb_tree_iterator<_Tp> iterator; |
| |
| typedef bidirectional_iterator_tag iterator_category; |
| typedef ptrdiff_t difference_type; |
| |
| typedef _Rb_tree_const_iterator<_Tp> _Self; |
| typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; |
| typedef const _Rb_tree_node<_Tp>* _Link_type; |
| |
| _Rb_tree_const_iterator() |
| : _M_node() { } |
| |
| explicit |
| _Rb_tree_const_iterator(_Link_type __x) |
| : _M_node(__x) { } |
| |
| _Rb_tree_const_iterator(const iterator& __it) |
| : _M_node(__it._M_node) { } |
| |
| reference |
| operator*() const |
| { return static_cast<_Link_type>(_M_node)->_M_value_field; } |
| |
| pointer |
| operator->() const |
| { return &static_cast<_Link_type>(_M_node)->_M_value_field; } |
| |
| _Self& |
| operator++() |
| { |
| _M_node = _Rb_tree_increment(_M_node); |
| return *this; |
| } |
| |
| _Self |
| operator++(int) |
| { |
| _Self __tmp = *this; |
| _M_node = _Rb_tree_increment(_M_node); |
| return __tmp; |
| } |
| |
| _Self& |
| operator--() |
| { |
| _M_node = _Rb_tree_decrement(_M_node); |
| return *this; |
| } |
| |
| _Self |
| operator--(int) |
| { |
| _Self __tmp = *this; |
| _M_node = _Rb_tree_decrement(_M_node); |
| return __tmp; |
| } |
| |
| bool |
| operator==(const _Self& __x) const |
| { return _M_node == __x._M_node; } |
| |
| bool |
| operator!=(const _Self& __x) const |
| { return _M_node != __x._M_node; } |
| |
| _Base_ptr _M_node; |
| }; |
| |
| template<typename _Val> |
| inline bool |
| operator==(const _Rb_tree_iterator<_Val>& __x, |
| const _Rb_tree_const_iterator<_Val>& __y) |
| { return __x._M_node == __y._M_node; } |
| |
| template<typename _Val> |
| inline bool |
| operator!=(const _Rb_tree_iterator<_Val>& __x, |
| const _Rb_tree_const_iterator<_Val>& __y) |
| { return __x._M_node != __y._M_node; } |
| |
| void |
| _Rb_tree_insert_and_rebalance(const bool __insert_left, |
| _Rb_tree_node_base* __x, |
| _Rb_tree_node_base* __p, |
| _Rb_tree_node_base& __header) throw (); |
| |
| _Rb_tree_node_base* |
| _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, |
| _Rb_tree_node_base& __header) throw (); |
| |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc = allocator<_Val> > |
| class _Rb_tree |
| { |
| typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other |
| _Node_allocator; |
| |
| protected: |
| typedef _Rb_tree_node_base* _Base_ptr; |
| typedef const _Rb_tree_node_base* _Const_Base_ptr; |
| |
| public: |
| typedef _Key key_type; |
| typedef _Val value_type; |
| typedef value_type* pointer; |
| typedef const value_type* const_pointer; |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| typedef _Rb_tree_node<_Val>* _Link_type; |
| typedef const _Rb_tree_node<_Val>* _Const_Link_type; |
| typedef size_t size_type; |
| typedef ptrdiff_t difference_type; |
| typedef _Alloc allocator_type; |
| |
| _Node_allocator& |
| _M_get_Node_allocator() |
| { return *static_cast<_Node_allocator*>(&this->_M_impl); } |
| |
| const _Node_allocator& |
| _M_get_Node_allocator() const |
| { return *static_cast<const _Node_allocator*>(&this->_M_impl); } |
| |
| allocator_type |
| get_allocator() const |
| { return allocator_type(_M_get_Node_allocator()); } |
| |
| protected: |
| _Link_type |
| _M_get_node() |
| { return _M_impl._Node_allocator::allocate(1); } |
| |
| void |
| _M_put_node(_Link_type __p) |
| { _M_impl._Node_allocator::deallocate(__p, 1); } |
| |
| #ifndef __GXX_EXPERIMENTAL_CXX0X__ |
| _Link_type |
| _M_create_node(const value_type& __x) |
| { |
| _Link_type __tmp = _M_get_node(); |
| __try |
| { get_allocator().construct(&__tmp->_M_value_field, __x); } |
| __catch(...) |
| { |
| _M_put_node(__tmp); |
| __throw_exception_again; |
| } |
| return __tmp; |
| } |
| |
| void |
| _M_destroy_node(_Link_type __p) |
| { |
| get_allocator().destroy(&__p->_M_value_field); |
| _M_put_node(__p); |
| } |
| #else |
| template<typename... _Args> |
| _Link_type |
| _M_create_node(_Args&&... __args) |
| { |
| _Link_type __tmp = _M_get_node(); |
| __try |
| { |
| _M_get_Node_allocator().construct(__tmp, |
| std::forward<_Args>(__args)...); |
| } |
| __catch(...) |
| { |
| _M_put_node(__tmp); |
| __throw_exception_again; |
| } |
| return __tmp; |
| } |
| |
| void |
| _M_destroy_node(_Link_type __p) |
| { |
| _M_get_Node_allocator().destroy(__p); |
| _M_put_node(__p); |
| } |
| #endif |
| |
| _Link_type |
| _M_clone_node(_Const_Link_type __x) |
| { |
| _Link_type __tmp = _M_create_node(__x->_M_value_field); |
| __tmp->_M_color = __x->_M_color; |
| __tmp->_M_left = 0; |
| __tmp->_M_right = 0; |
| return __tmp; |
| } |
| |
| protected: |
| template<typename _Key_compare, |
| bool _Is_pod_comparator = __is_pod(_Key_compare)> |
| struct _Rb_tree_impl : public _Node_allocator |
| { |
| _Key_compare _M_key_compare; |
| _Rb_tree_node_base _M_header; |
| size_type _M_node_count; // Keeps track of size of tree. |
| |
| _Rb_tree_impl() |
| : _Node_allocator(), _M_key_compare(), _M_header(), |
| _M_node_count(0) |
| { _M_initialize(); } |
| |
| _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a) |
| : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), |
| _M_node_count(0) |
| { _M_initialize(); } |
| |
| private: |
| void |
| _M_initialize() |
| { |
| this->_M_header._M_color = _S_red; |
| this->_M_header._M_parent = 0; |
| this->_M_header._M_left = &this->_M_header; |
| this->_M_header._M_right = &this->_M_header; |
| } |
| }; |
| |
| _Rb_tree_impl<_Compare> _M_impl; |
| |
| protected: |
| _Base_ptr& |
| _M_root() |
| { return this->_M_impl._M_header._M_parent; } |
| |
| _Const_Base_ptr |
| _M_root() const |
| { return this->_M_impl._M_header._M_parent; } |
| |
| _Base_ptr& |
| _M_leftmost() |
| { return this->_M_impl._M_header._M_left; } |
| |
| _Const_Base_ptr |
| _M_leftmost() const |
| { return this->_M_impl._M_header._M_left; } |
| |
| _Base_ptr& |
| _M_rightmost() |
| { return this->_M_impl._M_header._M_right; } |
| |
| _Const_Base_ptr |
| _M_rightmost() const |
| { return this->_M_impl._M_header._M_right; } |
| |
| _Link_type |
| _M_begin() |
| { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } |
| |
| _Const_Link_type |
| _M_begin() const |
| { |
| return static_cast<_Const_Link_type> |
| (this->_M_impl._M_header._M_parent); |
| } |
| |
| _Link_type |
| _M_end() |
| { return static_cast<_Link_type>(&this->_M_impl._M_header); } |
| |
| _Const_Link_type |
| _M_end() const |
| { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } |
| |
| static const_reference |
| _S_value(_Const_Link_type __x) |
| { return __x->_M_value_field; } |
| |
| static const _Key& |
| _S_key(_Const_Link_type __x) |
| { return _KeyOfValue()(_S_value(__x)); } |
| |
| static _Link_type |
| _S_left(_Base_ptr __x) |
| { return static_cast<_Link_type>(__x->_M_left); } |
| |
| static _Const_Link_type |
| _S_left(_Const_Base_ptr __x) |
| { return static_cast<_Const_Link_type>(__x->_M_left); } |
| |
| static _Link_type |
| _S_right(_Base_ptr __x) |
| { return static_cast<_Link_type>(__x->_M_right); } |
| |
| static _Const_Link_type |
| _S_right(_Const_Base_ptr __x) |
| { return static_cast<_Const_Link_type>(__x->_M_right); } |
| |
| static const_reference |
| _S_value(_Const_Base_ptr __x) |
| { return static_cast<_Const_Link_type>(__x)->_M_value_field; } |
| |
| static const _Key& |
| _S_key(_Const_Base_ptr __x) |
| { return _KeyOfValue()(_S_value(__x)); } |
| |
| static _Base_ptr |
| _S_minimum(_Base_ptr __x) |
| { return _Rb_tree_node_base::_S_minimum(__x); } |
| |
| static _Const_Base_ptr |
| _S_minimum(_Const_Base_ptr __x) |
| { return _Rb_tree_node_base::_S_minimum(__x); } |
| |
| static _Base_ptr |
| _S_maximum(_Base_ptr __x) |
| { return _Rb_tree_node_base::_S_maximum(__x); } |
| |
| static _Const_Base_ptr |
| _S_maximum(_Const_Base_ptr __x) |
| { return _Rb_tree_node_base::_S_maximum(__x); } |
| |
| public: |
| typedef _Rb_tree_iterator<value_type> iterator; |
| typedef _Rb_tree_const_iterator<value_type> const_iterator; |
| |
| typedef std::reverse_iterator<iterator> reverse_iterator; |
| typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
| |
| private: |
| iterator |
| _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, |
| const value_type& __v); |
| |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| // 233. Insertion hints in associative containers. |
| iterator |
| _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v); |
| |
| iterator |
| _M_insert_equal_lower(const value_type& __x); |
| |
| _Link_type |
| _M_copy(_Const_Link_type __x, _Link_type __p); |
| |
| void |
| _M_erase(_Link_type __x); |
| |
| iterator |
| _M_lower_bound(_Link_type __x, _Link_type __y, |
| const _Key& __k); |
| |
| const_iterator |
| _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, |
| const _Key& __k) const; |
| |
| iterator |
| _M_upper_bound(_Link_type __x, _Link_type __y, |
| const _Key& __k); |
| |
| const_iterator |
| _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, |
| const _Key& __k) const; |
| |
| public: |
| // allocation/deallocation |
| _Rb_tree() { } |
| |
| _Rb_tree(const _Compare& __comp, |
| const allocator_type& __a = allocator_type()) |
| : _M_impl(__comp, __a) { } |
| |
| _Rb_tree(const _Rb_tree& __x) |
| : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) |
| { |
| if (__x._M_root() != 0) |
| { |
| _M_root() = _M_copy(__x._M_begin(), _M_end()); |
| _M_leftmost() = _S_minimum(_M_root()); |
| _M_rightmost() = _S_maximum(_M_root()); |
| _M_impl._M_node_count = __x._M_impl._M_node_count; |
| } |
| } |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| _Rb_tree(_Rb_tree&& __x); |
| #endif |
| |
| ~_Rb_tree() |
| { _M_erase(_M_begin()); } |
| |
| _Rb_tree& |
| operator=(const _Rb_tree& __x); |
| |
| // Accessors. |
| _Compare |
| key_comp() const |
| { return _M_impl._M_key_compare; } |
| |
| iterator |
| begin() |
| { |
| return iterator(static_cast<_Link_type> |
| (this->_M_impl._M_header._M_left)); |
| } |
| |
| const_iterator |
| begin() const |
| { |
| return const_iterator(static_cast<_Const_Link_type> |
| (this->_M_impl._M_header._M_left)); |
| } |
| |
| iterator |
| end() |
| { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); } |
| |
| const_iterator |
| end() const |
| { |
| return const_iterator(static_cast<_Const_Link_type> |
| (&this->_M_impl._M_header)); |
| } |
| |
| reverse_iterator |
| rbegin() |
| { return reverse_iterator(end()); } |
| |
| const_reverse_iterator |
| rbegin() const |
| { return const_reverse_iterator(end()); } |
| |
| reverse_iterator |
| rend() |
| { return reverse_iterator(begin()); } |
| |
| const_reverse_iterator |
| rend() const |
| { return const_reverse_iterator(begin()); } |
| |
| bool |
| empty() const |
| { return _M_impl._M_node_count == 0; } |
| |
| size_type |
| size() const |
| { return _M_impl._M_node_count; } |
| |
| size_type |
| max_size() const |
| { return _M_get_Node_allocator().max_size(); } |
| |
| void |
| swap(_Rb_tree& __t); |
| |
| // Insert/erase. |
| pair<iterator, bool> |
| _M_insert_unique(const value_type& __x); |
| |
| iterator |
| _M_insert_equal(const value_type& __x); |
| |
| iterator |
| _M_insert_unique_(const_iterator __position, const value_type& __x); |
| |
| iterator |
| _M_insert_equal_(const_iterator __position, const value_type& __x); |
| |
| template<typename _InputIterator> |
| void |
| _M_insert_unique(_InputIterator __first, _InputIterator __last); |
| |
| template<typename _InputIterator> |
| void |
| _M_insert_equal(_InputIterator __first, _InputIterator __last); |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| // DR 130. Associative erase should return an iterator. |
| iterator |
| erase(iterator __position); |
| |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| // DR 130. Associative erase should return an iterator. |
| const_iterator |
| erase(const_iterator __position); |
| #else |
| void |
| erase(iterator __position); |
| |
| void |
| erase(const_iterator __position); |
| #endif |
| size_type |
| erase(const key_type& __x); |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| // DR 130. Associative erase should return an iterator. |
| iterator |
| erase(iterator __first, iterator __last); |
| |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| // DR 130. Associative erase should return an iterator. |
| const_iterator |
| erase(const_iterator __first, const_iterator __last); |
| #else |
| void |
| erase(iterator __first, iterator __last); |
| |
| void |
| erase(const_iterator __first, const_iterator __last); |
| #endif |
| void |
| erase(const key_type* __first, const key_type* __last); |
| |
| void |
| clear() |
| { |
| _M_erase(_M_begin()); |
| _M_leftmost() = _M_end(); |
| _M_root() = 0; |
| _M_rightmost() = _M_end(); |
| _M_impl._M_node_count = 0; |
| } |
| |
| // Set operations. |
| iterator |
| find(const key_type& __k); |
| |
| const_iterator |
| find(const key_type& __k) const; |
| |
| size_type |
| count(const key_type& __k) const; |
| |
| iterator |
| lower_bound(const key_type& __k) |
| { return _M_lower_bound(_M_begin(), _M_end(), __k); } |
| |
| const_iterator |
| lower_bound(const key_type& __k) const |
| { return _M_lower_bound(_M_begin(), _M_end(), __k); } |
| |
| iterator |
| upper_bound(const key_type& __k) |
| { return _M_upper_bound(_M_begin(), _M_end(), __k); } |
| |
| const_iterator |
| upper_bound(const key_type& __k) const |
| { return _M_upper_bound(_M_begin(), _M_end(), __k); } |
| |
| pair<iterator, iterator> |
| equal_range(const key_type& __k); |
| |
| pair<const_iterator, const_iterator> |
| equal_range(const key_type& __k) const; |
| |
| // Debugging. |
| bool |
| __rb_verify() const; |
| }; |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| inline bool |
| operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
| const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) |
| { |
| return __x.size() == __y.size() |
| && std::equal(__x.begin(), __x.end(), __y.begin()); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| inline bool |
| operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
| const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) |
| { |
| return std::lexicographical_compare(__x.begin(), __x.end(), |
| __y.begin(), __y.end()); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| inline bool |
| operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
| const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) |
| { return !(__x == __y); } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| inline bool |
| operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
| const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) |
| { return __y < __x; } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| inline bool |
| operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
| const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) |
| { return !(__y < __x); } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| inline bool |
| operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
| const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) |
| { return !(__x < __y); } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| inline void |
| swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) |
| { __x.swap(__y); } |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x) |
| : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator()) |
| { |
| if (__x._M_root() != 0) |
| { |
| _M_root() = __x._M_root(); |
| _M_leftmost() = __x._M_leftmost(); |
| _M_rightmost() = __x._M_rightmost(); |
| _M_root()->_M_parent = _M_end(); |
| |
| __x._M_root() = 0; |
| __x._M_leftmost() = __x._M_end(); |
| __x._M_rightmost() = __x._M_end(); |
| |
| this->_M_impl._M_node_count = __x._M_impl._M_node_count; |
| __x._M_impl._M_node_count = 0; |
| } |
| } |
| #endif |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) |
| { |
| if (this != &__x) |
| { |
| // Note that _Key may be a constant type. |
| clear(); |
| _M_impl._M_key_compare = __x._M_impl._M_key_compare; |
| if (__x._M_root() != 0) |
| { |
| _M_root() = _M_copy(__x._M_begin(), _M_end()); |
| _M_leftmost() = _S_minimum(_M_root()); |
| _M_rightmost() = _S_maximum(_M_root()); |
| _M_impl._M_node_count = __x._M_impl._M_node_count; |
| } |
| } |
| return *this; |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) |
| { |
| bool __insert_left = (__x != 0 || __p == _M_end() |
| || _M_impl._M_key_compare(_KeyOfValue()(__v), |
| _S_key(__p))); |
| |
| _Link_type __z = _M_create_node(__v); |
| |
| _Rb_tree_insert_and_rebalance(__insert_left, __z, |
| const_cast<_Base_ptr>(__p), |
| this->_M_impl._M_header); |
| ++_M_impl._M_node_count; |
| return iterator(__z); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v) |
| { |
| bool __insert_left = (__x != 0 || __p == _M_end() |
| || !_M_impl._M_key_compare(_S_key(__p), |
| _KeyOfValue()(__v))); |
| |
| _Link_type __z = _M_create_node(__v); |
| |
| _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, |
| this->_M_impl._M_header); |
| ++_M_impl._M_node_count; |
| return iterator(__z); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_insert_equal_lower(const _Val& __v) |
| { |
| _Link_type __x = _M_begin(); |
| _Link_type __y = _M_end(); |
| while (__x != 0) |
| { |
| __y = __x; |
| __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? |
| _S_left(__x) : _S_right(__x); |
| } |
| return _M_insert_lower(__x, __y, __v); |
| } |
| |
| template<typename _Key, typename _Val, typename _KoV, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type |
| _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: |
| _M_copy(_Const_Link_type __x, _Link_type __p) |
| { |
| // Structural copy. __x and __p must be non-null. |
| _Link_type __top = _M_clone_node(__x); |
| __top->_M_parent = __p; |
| |
| __try |
| { |
| if (__x->_M_right) |
| __top->_M_right = _M_copy(_S_right(__x), __top); |
| __p = __top; |
| __x = _S_left(__x); |
| |
| while (__x != 0) |
| { |
| _Link_type __y = _M_clone_node(__x); |
| __p->_M_left = __y; |
| __y->_M_parent = __p; |
| if (__x->_M_right) |
| __y->_M_right = _M_copy(_S_right(__x), __y); |
| __p = __y; |
| __x = _S_left(__x); |
| } |
| } |
| __catch(...) |
| { |
| _M_erase(__top); |
| __throw_exception_again; |
| } |
| return __top; |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| void |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_erase(_Link_type __x) |
| { |
| // Erase without rebalancing. |
| while (__x != 0) |
| { |
| _M_erase(_S_right(__x)); |
| _Link_type __y = _S_left(__x); |
| _M_destroy_node(__x); |
| __x = __y; |
| } |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, |
| _Compare, _Alloc>::iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_lower_bound(_Link_type __x, _Link_type __y, |
| const _Key& __k) |
| { |
| while (__x != 0) |
| if (!_M_impl._M_key_compare(_S_key(__x), __k)) |
| __y = __x, __x = _S_left(__x); |
| else |
| __x = _S_right(__x); |
| return iterator(__y); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, |
| _Compare, _Alloc>::const_iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, |
| const _Key& __k) const |
| { |
| while (__x != 0) |
| if (!_M_impl._M_key_compare(_S_key(__x), __k)) |
| __y = __x, __x = _S_left(__x); |
| else |
| __x = _S_right(__x); |
| return const_iterator(__y); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, |
| _Compare, _Alloc>::iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_upper_bound(_Link_type __x, _Link_type __y, |
| const _Key& __k) |
| { |
| while (__x != 0) |
| if (_M_impl._M_key_compare(__k, _S_key(__x))) |
| __y = __x, __x = _S_left(__x); |
| else |
| __x = _S_right(__x); |
| return iterator(__y); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, |
| _Compare, _Alloc>::const_iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, |
| const _Key& __k) const |
| { |
| while (__x != 0) |
| if (_M_impl._M_key_compare(__k, _S_key(__x))) |
| __y = __x, __x = _S_left(__x); |
| else |
| __x = _S_right(__x); |
| return const_iterator(__y); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, |
| _Compare, _Alloc>::iterator, |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, |
| _Compare, _Alloc>::iterator> |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| equal_range(const _Key& __k) |
| { |
| _Link_type __x = _M_begin(); |
| _Link_type __y = _M_end(); |
| while (__x != 0) |
| { |
| if (_M_impl._M_key_compare(_S_key(__x), __k)) |
| __x = _S_right(__x); |
| else if (_M_impl._M_key_compare(__k, _S_key(__x))) |
| __y = __x, __x = _S_left(__x); |
| else |
| { |
| _Link_type __xu(__x), __yu(__y); |
| __y = __x, __x = _S_left(__x); |
| __xu = _S_right(__xu); |
| return pair<iterator, |
| iterator>(_M_lower_bound(__x, __y, __k), |
| _M_upper_bound(__xu, __yu, __k)); |
| } |
| } |
| return pair<iterator, iterator>(iterator(__y), |
| iterator(__y)); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, |
| _Compare, _Alloc>::const_iterator, |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, |
| _Compare, _Alloc>::const_iterator> |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| equal_range(const _Key& __k) const |
| { |
| _Const_Link_type __x = _M_begin(); |
| _Const_Link_type __y = _M_end(); |
| while (__x != 0) |
| { |
| if (_M_impl._M_key_compare(_S_key(__x), __k)) |
| __x = _S_right(__x); |
| else if (_M_impl._M_key_compare(__k, _S_key(__x))) |
| __y = __x, __x = _S_left(__x); |
| else |
| { |
| _Const_Link_type __xu(__x), __yu(__y); |
| __y = __x, __x = _S_left(__x); |
| __xu = _S_right(__xu); |
| return pair<const_iterator, |
| const_iterator>(_M_lower_bound(__x, __y, __k), |
| _M_upper_bound(__xu, __yu, __k)); |
| } |
| } |
| return pair<const_iterator, const_iterator>(const_iterator(__y), |
| const_iterator(__y)); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| void |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) |
| { |
| if (_M_root() == 0) |
| { |
| if (__t._M_root() != 0) |
| { |
| _M_root() = __t._M_root(); |
| _M_leftmost() = __t._M_leftmost(); |
| _M_rightmost() = __t._M_rightmost(); |
| _M_root()->_M_parent = _M_end(); |
| |
| __t._M_root() = 0; |
| __t._M_leftmost() = __t._M_end(); |
| __t._M_rightmost() = __t._M_end(); |
| } |
| } |
| else if (__t._M_root() == 0) |
| { |
| __t._M_root() = _M_root(); |
| __t._M_leftmost() = _M_leftmost(); |
| __t._M_rightmost() = _M_rightmost(); |
| __t._M_root()->_M_parent = __t._M_end(); |
| |
| _M_root() = 0; |
| _M_leftmost() = _M_end(); |
| _M_rightmost() = _M_end(); |
| } |
| else |
| { |
| std::swap(_M_root(),__t._M_root()); |
| std::swap(_M_leftmost(),__t._M_leftmost()); |
| std::swap(_M_rightmost(),__t._M_rightmost()); |
| |
| _M_root()->_M_parent = _M_end(); |
| __t._M_root()->_M_parent = __t._M_end(); |
| } |
| // No need to swap header's color as it does not change. |
| std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); |
| std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); |
| |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| // 431. Swapping containers with unequal allocators. |
| std::__alloc_swap<_Node_allocator>:: |
| _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator()); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, |
| _Compare, _Alloc>::iterator, bool> |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_insert_unique(const _Val& __v) |
| { |
| _Link_type __x = _M_begin(); |
| _Link_type __y = _M_end(); |
| bool __comp = true; |
| while (__x != 0) |
| { |
| __y = __x; |
| __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); |
| __x = __comp ? _S_left(__x) : _S_right(__x); |
| } |
| iterator __j = iterator(__y); |
| if (__comp) |
| { |
| if (__j == begin()) |
| return pair<iterator, bool>(_M_insert_(__x, __y, __v), true); |
| else |
| --__j; |
| } |
| if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) |
| return pair<iterator, bool>(_M_insert_(__x, __y, __v), true); |
| return pair<iterator, bool>(__j, false); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_insert_equal(const _Val& __v) |
| { |
| _Link_type __x = _M_begin(); |
| _Link_type __y = _M_end(); |
| while (__x != 0) |
| { |
| __y = __x; |
| __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? |
| _S_left(__x) : _S_right(__x); |
| } |
| return _M_insert_(__x, __y, __v); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_insert_unique_(const_iterator __position, const _Val& __v) |
| { |
| // end() |
| if (__position._M_node == _M_end()) |
| { |
| if (size() > 0 |
| && _M_impl._M_key_compare(_S_key(_M_rightmost()), |
| _KeyOfValue()(__v))) |
| return _M_insert_(0, _M_rightmost(), __v); |
| else |
| return _M_insert_unique(__v).first; |
| } |
| else if (_M_impl._M_key_compare(_KeyOfValue()(__v), |
| _S_key(__position._M_node))) |
| { |
| // First, try before... |
| const_iterator __before = __position; |
| if (__position._M_node == _M_leftmost()) // begin() |
| return _M_insert_(_M_leftmost(), _M_leftmost(), __v); |
| else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), |
| _KeyOfValue()(__v))) |
| { |
| if (_S_right(__before._M_node) == 0) |
| return _M_insert_(0, __before._M_node, __v); |
| else |
| return _M_insert_(__position._M_node, |
| __position._M_node, __v); |
| } |
| else |
| return _M_insert_unique(__v).first; |
| } |
| else if (_M_impl._M_key_compare(_S_key(__position._M_node), |
| _KeyOfValue()(__v))) |
| { |
| // ... then try after. |
| const_iterator __after = __position; |
| if (__position._M_node == _M_rightmost()) |
| return _M_insert_(0, _M_rightmost(), __v); |
| else if (_M_impl._M_key_compare(_KeyOfValue()(__v), |
| _S_key((++__after)._M_node))) |
| { |
| if (_S_right(__position._M_node) == 0) |
| return _M_insert_(0, __position._M_node, __v); |
| else |
| return _M_insert_(__after._M_node, __after._M_node, __v); |
| } |
| else |
| return _M_insert_unique(__v).first; |
| } |
| else |
| // Equivalent keys. |
| return iterator(static_cast<_Link_type> |
| (const_cast<_Base_ptr>(__position._M_node))); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| _M_insert_equal_(const_iterator __position, const _Val& __v) |
| { |
| // end() |
| if (__position._M_node == _M_end()) |
| { |
| if (size() > 0 |
| && !_M_impl._M_key_compare(_KeyOfValue()(__v), |
| _S_key(_M_rightmost()))) |
| return _M_insert_(0, _M_rightmost(), __v); |
| else |
| return _M_insert_equal(__v); |
| } |
| else if (!_M_impl._M_key_compare(_S_key(__position._M_node), |
| _KeyOfValue()(__v))) |
| { |
| // First, try before... |
| const_iterator __before = __position; |
| if (__position._M_node == _M_leftmost()) // begin() |
| return _M_insert_(_M_leftmost(), _M_leftmost(), __v); |
| else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), |
| _S_key((--__before)._M_node))) |
| { |
| if (_S_right(__before._M_node) == 0) |
| return _M_insert_(0, __before._M_node, __v); |
| else |
| return _M_insert_(__position._M_node, |
| __position._M_node, __v); |
| } |
| else |
| return _M_insert_equal(__v); |
| } |
| else |
| { |
| // ... then try after. |
| const_iterator __after = __position; |
| if (__position._M_node == _M_rightmost()) |
| return _M_insert_(0, _M_rightmost(), __v); |
| else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), |
| _KeyOfValue()(__v))) |
| { |
| if (_S_right(__position._M_node) == 0) |
| return _M_insert_(0, __position._M_node, __v); |
| else |
| return _M_insert_(__after._M_node, __after._M_node, __v); |
| } |
| else |
| return _M_insert_equal_lower(__v); |
| } |
| } |
| |
| template<typename _Key, typename _Val, typename _KoV, |
| typename _Cmp, typename _Alloc> |
| template<class _II> |
| void |
| _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: |
| _M_insert_unique(_II __first, _II __last) |
| { |
| for (; __first != __last; ++__first) |
| _M_insert_unique_(end(), *__first); |
| } |
| |
| template<typename _Key, typename _Val, typename _KoV, |
| typename _Cmp, typename _Alloc> |
| template<class _II> |
| void |
| _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: |
| _M_insert_equal(_II __first, _II __last) |
| { |
| for (; __first != __last; ++__first) |
| _M_insert_equal_(end(), *__first); |
| } |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| // DR 130. Associative erase should return an iterator. |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| inline typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| erase(iterator __position) |
| { |
| iterator __result = __position; |
| ++__result; |
| _Link_type __y = |
| static_cast<_Link_type>(_Rb_tree_rebalance_for_erase |
| (__position._M_node, |
| this->_M_impl._M_header)); |
| _M_destroy_node(__y); |
| --_M_impl._M_node_count; |
| return __result; |
| } |
| |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| // DR 130. Associative erase should return an iterator. |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| inline typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| erase(const_iterator __position) |
| { |
| const_iterator __result = __position; |
| ++__result; |
| _Link_type __y = |
| static_cast<_Link_type>(_Rb_tree_rebalance_for_erase |
| (const_cast<_Base_ptr>(__position._M_node), |
| this->_M_impl._M_header)); |
| _M_destroy_node(__y); |
| --_M_impl._M_node_count; |
| return __result; |
| } |
| #else |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| inline void |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| erase(iterator __position) |
| { |
| _Link_type __y = |
| static_cast<_Link_type>(_Rb_tree_rebalance_for_erase |
| (__position._M_node, |
| this->_M_impl._M_header)); |
| _M_destroy_node(__y); |
| --_M_impl._M_node_count; |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| inline void |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| erase(const_iterator __position) |
| { |
| _Link_type __y = |
| static_cast<_Link_type>(_Rb_tree_rebalance_for_erase |
| (const_cast<_Base_ptr>(__position._M_node), |
| this->_M_impl._M_header)); |
| _M_destroy_node(__y); |
| --_M_impl._M_node_count; |
| } |
| #endif |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| erase(const _Key& __x) |
| { |
| pair<iterator, iterator> __p = equal_range(__x); |
| const size_type __old_size = size(); |
| erase(__p.first, __p.second); |
| return __old_size - size(); |
| } |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| // DR 130. Associative erase should return an iterator. |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| erase(iterator __first, iterator __last) |
| { |
| if (__first == begin() && __last == end()) |
| { |
| clear(); |
| return end(); |
| } |
| else |
| { |
| while (__first != __last) |
| erase(__first++); |
| return __last; |
| } |
| } |
| |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS |
| // DR 130. Associative erase should return an iterator. |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| erase(const_iterator __first, const_iterator __last) |
| { |
| if (__first == begin() && __last == end()) |
| { |
| clear(); |
| return end(); |
| } |
| else |
| { |
| while (__first != __last) |
| erase(__first++); |
| return __last; |
| } |
| } |
| #else |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| void |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| erase(iterator __first, iterator __last) |
| { |
| if (__first == begin() && __last == end()) |
| clear(); |
| else |
| while (__first != __last) |
| erase(__first++); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| void |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| erase(const_iterator __first, const_iterator __last) |
| { |
| if (__first == begin() && __last == end()) |
| clear(); |
| else |
| while (__first != __last) |
| erase(__first++); |
| } |
| #endif |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| void |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| erase(const _Key* __first, const _Key* __last) |
| { |
| while (__first != __last) |
| erase(*__first++); |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, |
| _Compare, _Alloc>::iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| find(const _Key& __k) |
| { |
| iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); |
| return (__j == end() |
| || _M_impl._M_key_compare(__k, |
| _S_key(__j._M_node))) ? end() : __j; |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, |
| _Compare, _Alloc>::const_iterator |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| find(const _Key& __k) const |
| { |
| const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); |
| return (__j == end() |
| || _M_impl._M_key_compare(__k, |
| _S_key(__j._M_node))) ? end() : __j; |
| } |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type |
| _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
| count(const _Key& __k) const |
| { |
| pair<const_iterator, const_iterator> __p = equal_range(__k); |
| const size_type __n = std::distance(__p.first, __p.second); |
| return __n; |
| } |
| |
| _GLIBCXX_PURE unsigned int |
| _Rb_tree_black_count(const _Rb_tree_node_base* __node, |
| const _Rb_tree_node_base* __root) throw (); |
| |
| template<typename _Key, typename _Val, typename _KeyOfValue, |
| typename _Compare, typename _Alloc> |
| bool |
| _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const |
| { |
| if (_M_impl._M_node_count == 0 || begin() == end()) |
| return _M_impl._M_node_count == 0 && begin() == end() |
| && this->_M_impl._M_header._M_left == _M_end() |
| && this->_M_impl._M_header._M_right == _M_end(); |
| |
| unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); |
| for (const_iterator __it = begin(); __it != end(); ++__it) |
| { |
| _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); |
| _Const_Link_type __L = _S_left(__x); |
| _Const_Link_type __R = _S_right(__x); |
| |
| if (__x->_M_color == _S_red) |
| if ((__L && __L->_M_color == _S_red) |
| || (__R && __R->_M_color == _S_red)) |
| return false; |
| |
| if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) |
| return false; |
| if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) |
| return false; |
| |
| if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) |
| return false; |
| } |
| |
| if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) |
| return false; |
| if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) |
| return false; |
| return true; |
| } |
| |
| _GLIBCXX_END_NAMESPACE |
| |
| #endif |
