1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
5 // Free Software Foundation, Inc.
7 // This file is part of the GNU ISO C++ Library. This library is free
8 // software; you can redistribute it and/or modify it under the
9 // terms of the GNU General Public License as published by the
10 // Free Software Foundation; either version 3, or (at your option)
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 // GNU General Public License for more details.
18 // Under Section 7 of GPL version 3, you are granted additional
19 // permissions described in the GCC Runtime Library Exception, version
20 // 3.1, as published by the Free Software Foundation.
22 // You should have received a copy of the GNU General Public License and
23 // a copy of the GCC Runtime Library Exception along with this program;
24 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
25 // <http://www.gnu.org/licenses/>.
29 * Copyright (c) 1996,1997
30 * Silicon Graphics Computer Systems, Inc.
32 * Permission to use, copy, modify, distribute and sell this software
33 * and its documentation for any purpose is hereby granted without fee,
34 * provided that the above copyright notice appear in all copies and
35 * that both that copyright notice and this permission notice appear
36 * in supporting documentation. Silicon Graphics makes no
37 * representations about the suitability of this software for any
38 * purpose. It is provided "as is" without express or implied warranty.
42 * Hewlett-Packard Company
44 * Permission to use, copy, modify, distribute and sell this software
45 * and its documentation for any purpose is hereby granted without fee,
46 * provided that the above copyright notice appear in all copies and
47 * that both that copyright notice and this permission notice appear
48 * in supporting documentation. Hewlett-Packard Company makes no
49 * representations about the suitability of this software for any
50 * purpose. It is provided "as is" without express or implied warranty.
56 * This is an internal header file, included by other library headers.
57 * You should not attempt to use it directly.
63 #include <bits/stl_algobase.h>
64 #include <bits/allocator.h>
65 #include <bits/stl_function.h>
66 #include <bits/cpp_type_traits.h>
68 _GLIBCXX_BEGIN_NAMESPACE(std
)
70 // Red-black tree class, designed for use in implementing STL
71 // associative containers (set, multiset, map, and multimap). The
72 // insertion and deletion algorithms are based on those in Cormen,
73 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
76 // (1) the header cell is maintained with links not only to the root
77 // but also to the leftmost node of the tree, to enable constant
78 // time begin(), and to the rightmost node of the tree, to enable
79 // linear time performance when used with the generic set algorithms
82 // (2) when a node being deleted has two children its successor node
83 // is relinked into its place, rather than copied, so that the only
84 // iterators invalidated are those referring to the deleted node.
86 enum _Rb_tree_color
{ _S_red
= false, _S_black
= true };
88 struct _Rb_tree_node_base
90 typedef _Rb_tree_node_base
* _Base_ptr
;
91 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
93 _Rb_tree_color _M_color
;
99 _S_minimum(_Base_ptr __x
)
101 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
105 static _Const_Base_ptr
106 _S_minimum(_Const_Base_ptr __x
)
108 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
113 _S_maximum(_Base_ptr __x
)
115 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
119 static _Const_Base_ptr
120 _S_maximum(_Const_Base_ptr __x
)
122 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
127 template<typename _Val
>
128 struct _Rb_tree_node
: public _Rb_tree_node_base
130 typedef _Rb_tree_node
<_Val
>* _Link_type
;
133 #ifdef __GXX_EXPERIMENTAL_CXX0X__
134 template<typename
... _Args
>
135 _Rb_tree_node(_Args
&&... __args
)
136 : _Rb_tree_node_base(),
137 _M_value_field(std::forward
<_Args
>(__args
)...) { }
141 _GLIBCXX_PURE _Rb_tree_node_base
*
142 _Rb_tree_increment(_Rb_tree_node_base
* __x
) throw ();
144 _GLIBCXX_PURE
const _Rb_tree_node_base
*
145 _Rb_tree_increment(const _Rb_tree_node_base
* __x
) throw ();
147 _GLIBCXX_PURE _Rb_tree_node_base
*
148 _Rb_tree_decrement(_Rb_tree_node_base
* __x
) throw ();
150 _GLIBCXX_PURE
const _Rb_tree_node_base
*
151 _Rb_tree_decrement(const _Rb_tree_node_base
* __x
) throw ();
153 template<typename _Tp
>
154 struct _Rb_tree_iterator
156 typedef _Tp value_type
;
157 typedef _Tp
& reference
;
158 typedef _Tp
* pointer
;
160 typedef bidirectional_iterator_tag iterator_category
;
161 typedef ptrdiff_t difference_type
;
163 typedef _Rb_tree_iterator
<_Tp
> _Self
;
164 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
165 typedef _Rb_tree_node
<_Tp
>* _Link_type
;
171 _Rb_tree_iterator(_Link_type __x
)
176 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
180 { return std::__addressof(static_cast<_Link_type
>
181 (_M_node
)->_M_value_field
); }
186 _M_node
= _Rb_tree_increment(_M_node
);
194 _M_node
= _Rb_tree_increment(_M_node
);
201 _M_node
= _Rb_tree_decrement(_M_node
);
209 _M_node
= _Rb_tree_decrement(_M_node
);
214 operator==(const _Self
& __x
) const
215 { return _M_node
== __x
._M_node
; }
218 operator!=(const _Self
& __x
) const
219 { return _M_node
!= __x
._M_node
; }
224 template<typename _Tp
>
225 struct _Rb_tree_const_iterator
227 typedef _Tp value_type
;
228 typedef const _Tp
& reference
;
229 typedef const _Tp
* pointer
;
231 typedef _Rb_tree_iterator
<_Tp
> iterator
;
233 typedef bidirectional_iterator_tag iterator_category
;
234 typedef ptrdiff_t difference_type
;
236 typedef _Rb_tree_const_iterator
<_Tp
> _Self
;
237 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr
;
238 typedef const _Rb_tree_node
<_Tp
>* _Link_type
;
240 _Rb_tree_const_iterator()
244 _Rb_tree_const_iterator(_Link_type __x
)
247 _Rb_tree_const_iterator(const iterator
& __it
)
248 : _M_node(__it
._M_node
) { }
252 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
256 { return std::__addressof(static_cast<_Link_type
>
257 (_M_node
)->_M_value_field
); }
262 _M_node
= _Rb_tree_increment(_M_node
);
270 _M_node
= _Rb_tree_increment(_M_node
);
277 _M_node
= _Rb_tree_decrement(_M_node
);
285 _M_node
= _Rb_tree_decrement(_M_node
);
290 operator==(const _Self
& __x
) const
291 { return _M_node
== __x
._M_node
; }
294 operator!=(const _Self
& __x
) const
295 { return _M_node
!= __x
._M_node
; }
300 template<typename _Val
>
302 operator==(const _Rb_tree_iterator
<_Val
>& __x
,
303 const _Rb_tree_const_iterator
<_Val
>& __y
)
304 { return __x
._M_node
== __y
._M_node
; }
306 template<typename _Val
>
308 operator!=(const _Rb_tree_iterator
<_Val
>& __x
,
309 const _Rb_tree_const_iterator
<_Val
>& __y
)
310 { return __x
._M_node
!= __y
._M_node
; }
313 _Rb_tree_insert_and_rebalance(const bool __insert_left
,
314 _Rb_tree_node_base
* __x
,
315 _Rb_tree_node_base
* __p
,
316 _Rb_tree_node_base
& __header
) throw ();
319 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
320 _Rb_tree_node_base
& __header
) throw ();
323 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
324 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
327 typedef typename
_Alloc::template rebind
<_Rb_tree_node
<_Val
> >::other
331 typedef _Rb_tree_node_base
* _Base_ptr
;
332 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
335 typedef _Key key_type
;
336 typedef _Val value_type
;
337 typedef value_type
* pointer
;
338 typedef const value_type
* const_pointer
;
339 typedef value_type
& reference
;
340 typedef const value_type
& const_reference
;
341 typedef _Rb_tree_node
<_Val
>* _Link_type
;
342 typedef const _Rb_tree_node
<_Val
>* _Const_Link_type
;
343 typedef size_t size_type
;
344 typedef ptrdiff_t difference_type
;
345 typedef _Alloc allocator_type
;
348 _M_get_Node_allocator()
349 { return *static_cast<_Node_allocator
*>(&this->_M_impl
); }
351 const _Node_allocator
&
352 _M_get_Node_allocator() const
353 { return *static_cast<const _Node_allocator
*>(&this->_M_impl
); }
356 get_allocator() const
357 { return allocator_type(_M_get_Node_allocator()); }
362 { return _M_impl
._Node_allocator::allocate(1); }
365 _M_put_node(_Link_type __p
)
366 { _M_impl
._Node_allocator::deallocate(__p
, 1); }
368 #ifndef __GXX_EXPERIMENTAL_CXX0X__
370 _M_create_node(const value_type
& __x
)
372 _Link_type __tmp
= _M_get_node();
374 { get_allocator().construct
375 (std::__addressof(__tmp
->_M_value_field
), __x
); }
379 __throw_exception_again
;
385 _M_destroy_node(_Link_type __p
)
387 get_allocator().destroy(std::__addressof(__p
->_M_value_field
));
391 template<typename
... _Args
>
393 _M_create_node(_Args
&&... __args
)
395 _Link_type __tmp
= _M_get_node();
398 _M_get_Node_allocator().construct(__tmp
,
399 std::forward
<_Args
>(__args
)...);
404 __throw_exception_again
;
410 _M_destroy_node(_Link_type __p
)
412 _M_get_Node_allocator().destroy(__p
);
418 _M_clone_node(_Const_Link_type __x
)
420 _Link_type __tmp
= _M_create_node(__x
->_M_value_field
);
421 __tmp
->_M_color
= __x
->_M_color
;
428 template<typename _Key_compare
,
429 bool _Is_pod_comparator
= __is_pod(_Key_compare
)>
430 struct _Rb_tree_impl
: public _Node_allocator
432 _Key_compare _M_key_compare
;
433 _Rb_tree_node_base _M_header
;
434 size_type _M_node_count
; // Keeps track of size of tree.
437 : _Node_allocator(), _M_key_compare(), _M_header(),
441 _Rb_tree_impl(const _Key_compare
& __comp
, const _Node_allocator
& __a
)
442 : _Node_allocator(__a
), _M_key_compare(__comp
), _M_header(),
450 this->_M_header
._M_color
= _S_red
;
451 this->_M_header
._M_parent
= 0;
452 this->_M_header
._M_left
= &this->_M_header
;
453 this->_M_header
._M_right
= &this->_M_header
;
457 _Rb_tree_impl
<_Compare
> _M_impl
;
462 { return this->_M_impl
._M_header
._M_parent
; }
466 { return this->_M_impl
._M_header
._M_parent
; }
470 { return this->_M_impl
._M_header
._M_left
; }
474 { return this->_M_impl
._M_header
._M_left
; }
478 { return this->_M_impl
._M_header
._M_right
; }
482 { return this->_M_impl
._M_header
._M_right
; }
486 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
491 return static_cast<_Const_Link_type
>
492 (this->_M_impl
._M_header
._M_parent
);
497 { return static_cast<_Link_type
>(&this->_M_impl
._M_header
); }
501 { return static_cast<_Const_Link_type
>(&this->_M_impl
._M_header
); }
503 static const_reference
504 _S_value(_Const_Link_type __x
)
505 { return __x
->_M_value_field
; }
508 _S_key(_Const_Link_type __x
)
509 { return _KeyOfValue()(_S_value(__x
)); }
512 _S_left(_Base_ptr __x
)
513 { return static_cast<_Link_type
>(__x
->_M_left
); }
515 static _Const_Link_type
516 _S_left(_Const_Base_ptr __x
)
517 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
520 _S_right(_Base_ptr __x
)
521 { return static_cast<_Link_type
>(__x
->_M_right
); }
523 static _Const_Link_type
524 _S_right(_Const_Base_ptr __x
)
525 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
527 static const_reference
528 _S_value(_Const_Base_ptr __x
)
529 { return static_cast<_Const_Link_type
>(__x
)->_M_value_field
; }
532 _S_key(_Const_Base_ptr __x
)
533 { return _KeyOfValue()(_S_value(__x
)); }
536 _S_minimum(_Base_ptr __x
)
537 { return _Rb_tree_node_base::_S_minimum(__x
); }
539 static _Const_Base_ptr
540 _S_minimum(_Const_Base_ptr __x
)
541 { return _Rb_tree_node_base::_S_minimum(__x
); }
544 _S_maximum(_Base_ptr __x
)
545 { return _Rb_tree_node_base::_S_maximum(__x
); }
547 static _Const_Base_ptr
548 _S_maximum(_Const_Base_ptr __x
)
549 { return _Rb_tree_node_base::_S_maximum(__x
); }
552 typedef _Rb_tree_iterator
<value_type
> iterator
;
553 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
555 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
556 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
560 _M_insert_(_Const_Base_ptr __x
, _Const_Base_ptr __y
,
561 const value_type
& __v
);
563 // _GLIBCXX_RESOLVE_LIB_DEFECTS
564 // 233. Insertion hints in associative containers.
566 _M_insert_lower(_Base_ptr __x
, _Base_ptr __y
, const value_type
& __v
);
569 _M_insert_equal_lower(const value_type
& __x
);
572 _M_copy(_Const_Link_type __x
, _Link_type __p
);
575 _M_erase(_Link_type __x
);
578 _M_lower_bound(_Link_type __x
, _Link_type __y
,
582 _M_lower_bound(_Const_Link_type __x
, _Const_Link_type __y
,
583 const _Key
& __k
) const;
586 _M_upper_bound(_Link_type __x
, _Link_type __y
,
590 _M_upper_bound(_Const_Link_type __x
, _Const_Link_type __y
,
591 const _Key
& __k
) const;
594 // allocation/deallocation
597 _Rb_tree(const _Compare
& __comp
,
598 const allocator_type
& __a
= allocator_type())
599 : _M_impl(__comp
, __a
) { }
601 _Rb_tree(const _Rb_tree
& __x
)
602 : _M_impl(__x
._M_impl
._M_key_compare
, __x
._M_get_Node_allocator())
604 if (__x
._M_root() != 0)
606 _M_root() = _M_copy(__x
._M_begin(), _M_end());
607 _M_leftmost() = _S_minimum(_M_root());
608 _M_rightmost() = _S_maximum(_M_root());
609 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
613 #ifdef __GXX_EXPERIMENTAL_CXX0X__
614 _Rb_tree(_Rb_tree
&& __x
);
618 { _M_erase(_M_begin()); }
621 operator=(const _Rb_tree
& __x
);
626 { return _M_impl
._M_key_compare
; }
631 return iterator(static_cast<_Link_type
>
632 (this->_M_impl
._M_header
._M_left
));
638 return const_iterator(static_cast<_Const_Link_type
>
639 (this->_M_impl
._M_header
._M_left
));
644 { return iterator(static_cast<_Link_type
>(&this->_M_impl
._M_header
)); }
649 return const_iterator(static_cast<_Const_Link_type
>
650 (&this->_M_impl
._M_header
));
655 { return reverse_iterator(end()); }
657 const_reverse_iterator
659 { return const_reverse_iterator(end()); }
663 { return reverse_iterator(begin()); }
665 const_reverse_iterator
667 { return const_reverse_iterator(begin()); }
671 { return _M_impl
._M_node_count
== 0; }
675 { return _M_impl
._M_node_count
; }
679 { return _M_get_Node_allocator().max_size(); }
686 _M_insert_unique(const value_type
& __x
);
689 _M_insert_equal(const value_type
& __x
);
692 _M_insert_unique_(const_iterator __position
, const value_type
& __x
);
695 _M_insert_equal_(const_iterator __position
, const value_type
& __x
);
697 template<typename _InputIterator
>
699 _M_insert_unique(_InputIterator __first
, _InputIterator __last
);
701 template<typename _InputIterator
>
703 _M_insert_equal(_InputIterator __first
, _InputIterator __last
);
705 #ifdef __GXX_EXPERIMENTAL_CXX0X__
706 // _GLIBCXX_RESOLVE_LIB_DEFECTS
707 // DR 130. Associative erase should return an iterator.
709 erase(iterator __position
);
711 // _GLIBCXX_RESOLVE_LIB_DEFECTS
712 // DR 130. Associative erase should return an iterator.
714 erase(const_iterator __position
);
717 erase(iterator __position
);
720 erase(const_iterator __position
);
723 erase(const key_type
& __x
);
725 #ifdef __GXX_EXPERIMENTAL_CXX0X__
726 // _GLIBCXX_RESOLVE_LIB_DEFECTS
727 // DR 130. Associative erase should return an iterator.
729 erase(iterator __first
, iterator __last
);
731 // _GLIBCXX_RESOLVE_LIB_DEFECTS
732 // DR 130. Associative erase should return an iterator.
734 erase(const_iterator __first
, const_iterator __last
);
737 erase(iterator __first
, iterator __last
);
740 erase(const_iterator __first
, const_iterator __last
);
743 erase(const key_type
* __first
, const key_type
* __last
);
748 _M_erase(_M_begin());
749 _M_leftmost() = _M_end();
751 _M_rightmost() = _M_end();
752 _M_impl
._M_node_count
= 0;
757 find(const key_type
& __k
);
760 find(const key_type
& __k
) const;
763 count(const key_type
& __k
) const;
766 lower_bound(const key_type
& __k
)
767 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
770 lower_bound(const key_type
& __k
) const
771 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
774 upper_bound(const key_type
& __k
)
775 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
778 upper_bound(const key_type
& __k
) const
779 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
781 pair
<iterator
, iterator
>
782 equal_range(const key_type
& __k
);
784 pair
<const_iterator
, const_iterator
>
785 equal_range(const key_type
& __k
) const;
792 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
793 typename _Compare
, typename _Alloc
>
795 operator==(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
796 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
798 return __x
.size() == __y
.size()
799 && std::equal(__x
.begin(), __x
.end(), __y
.begin());
802 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
803 typename _Compare
, typename _Alloc
>
805 operator<(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
806 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
808 return std::lexicographical_compare(__x
.begin(), __x
.end(),
809 __y
.begin(), __y
.end());
812 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
813 typename _Compare
, typename _Alloc
>
815 operator!=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
816 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
817 { return !(__x
== __y
); }
819 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
820 typename _Compare
, typename _Alloc
>
822 operator>(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
823 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
824 { return __y
< __x
; }
826 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
827 typename _Compare
, typename _Alloc
>
829 operator<=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
830 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
831 { return !(__y
< __x
); }
833 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
834 typename _Compare
, typename _Alloc
>
836 operator>=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
837 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
838 { return !(__x
< __y
); }
840 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
841 typename _Compare
, typename _Alloc
>
843 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
844 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
847 #ifdef __GXX_EXPERIMENTAL_CXX0X__
848 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
849 typename _Compare
, typename _Alloc
>
850 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
851 _Rb_tree(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&& __x
)
852 : _M_impl(__x
._M_impl
._M_key_compare
, __x
._M_get_Node_allocator())
854 if (__x
._M_root() != 0)
856 _M_root() = __x
._M_root();
857 _M_leftmost() = __x
._M_leftmost();
858 _M_rightmost() = __x
._M_rightmost();
859 _M_root()->_M_parent
= _M_end();
862 __x
._M_leftmost() = __x
._M_end();
863 __x
._M_rightmost() = __x
._M_end();
865 this->_M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
866 __x
._M_impl
._M_node_count
= 0;
871 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
872 typename _Compare
, typename _Alloc
>
873 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
874 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
875 operator=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
)
879 // Note that _Key may be a constant type.
881 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
882 if (__x
._M_root() != 0)
884 _M_root() = _M_copy(__x
._M_begin(), _M_end());
885 _M_leftmost() = _S_minimum(_M_root());
886 _M_rightmost() = _S_maximum(_M_root());
887 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
893 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
894 typename _Compare
, typename _Alloc
>
895 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
896 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
897 _M_insert_(_Const_Base_ptr __x
, _Const_Base_ptr __p
, const _Val
& __v
)
899 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
900 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
903 _Link_type __z
= _M_create_node(__v
);
905 _Rb_tree_insert_and_rebalance(__insert_left
, __z
,
906 const_cast<_Base_ptr
>(__p
),
907 this->_M_impl
._M_header
);
908 ++_M_impl
._M_node_count
;
909 return iterator(__z
);
912 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
913 typename _Compare
, typename _Alloc
>
914 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
915 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
916 _M_insert_lower(_Base_ptr __x
, _Base_ptr __p
, const _Val
& __v
)
918 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
919 || !_M_impl
._M_key_compare(_S_key(__p
),
920 _KeyOfValue()(__v
)));
922 _Link_type __z
= _M_create_node(__v
);
924 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
925 this->_M_impl
._M_header
);
926 ++_M_impl
._M_node_count
;
927 return iterator(__z
);
930 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
931 typename _Compare
, typename _Alloc
>
932 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
933 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
934 _M_insert_equal_lower(const _Val
& __v
)
936 _Link_type __x
= _M_begin();
937 _Link_type __y
= _M_end();
941 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _KeyOfValue()(__v
)) ?
942 _S_left(__x
) : _S_right(__x
);
944 return _M_insert_lower(__x
, __y
, __v
);
947 template<typename _Key
, typename _Val
, typename _KoV
,
948 typename _Compare
, typename _Alloc
>
949 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
950 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
951 _M_copy(_Const_Link_type __x
, _Link_type __p
)
953 // Structural copy. __x and __p must be non-null.
954 _Link_type __top
= _M_clone_node(__x
);
955 __top
->_M_parent
= __p
;
960 __top
->_M_right
= _M_copy(_S_right(__x
), __top
);
966 _Link_type __y
= _M_clone_node(__x
);
968 __y
->_M_parent
= __p
;
970 __y
->_M_right
= _M_copy(_S_right(__x
), __y
);
978 __throw_exception_again
;
983 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
984 typename _Compare
, typename _Alloc
>
986 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
987 _M_erase(_Link_type __x
)
989 // Erase without rebalancing.
992 _M_erase(_S_right(__x
));
993 _Link_type __y
= _S_left(__x
);
994 _M_destroy_node(__x
);
999 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1000 typename _Compare
, typename _Alloc
>
1001 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1002 _Compare
, _Alloc
>::iterator
1003 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1004 _M_lower_bound(_Link_type __x
, _Link_type __y
,
1008 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1009 __y
= __x
, __x
= _S_left(__x
);
1011 __x
= _S_right(__x
);
1012 return iterator(__y
);
1015 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1016 typename _Compare
, typename _Alloc
>
1017 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1018 _Compare
, _Alloc
>::const_iterator
1019 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1020 _M_lower_bound(_Const_Link_type __x
, _Const_Link_type __y
,
1021 const _Key
& __k
) const
1024 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1025 __y
= __x
, __x
= _S_left(__x
);
1027 __x
= _S_right(__x
);
1028 return const_iterator(__y
);
1031 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1032 typename _Compare
, typename _Alloc
>
1033 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1034 _Compare
, _Alloc
>::iterator
1035 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1036 _M_upper_bound(_Link_type __x
, _Link_type __y
,
1040 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1041 __y
= __x
, __x
= _S_left(__x
);
1043 __x
= _S_right(__x
);
1044 return iterator(__y
);
1047 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1048 typename _Compare
, typename _Alloc
>
1049 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1050 _Compare
, _Alloc
>::const_iterator
1051 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1052 _M_upper_bound(_Const_Link_type __x
, _Const_Link_type __y
,
1053 const _Key
& __k
) const
1056 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1057 __y
= __x
, __x
= _S_left(__x
);
1059 __x
= _S_right(__x
);
1060 return const_iterator(__y
);
1063 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1064 typename _Compare
, typename _Alloc
>
1065 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1066 _Compare
, _Alloc
>::iterator
,
1067 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1068 _Compare
, _Alloc
>::iterator
>
1069 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1070 equal_range(const _Key
& __k
)
1072 _Link_type __x
= _M_begin();
1073 _Link_type __y
= _M_end();
1076 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1077 __x
= _S_right(__x
);
1078 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1079 __y
= __x
, __x
= _S_left(__x
);
1082 _Link_type
__xu(__x
), __yu(__y
);
1083 __y
= __x
, __x
= _S_left(__x
);
1084 __xu
= _S_right(__xu
);
1085 return pair
<iterator
,
1086 iterator
>(_M_lower_bound(__x
, __y
, __k
),
1087 _M_upper_bound(__xu
, __yu
, __k
));
1090 return pair
<iterator
, iterator
>(iterator(__y
),
1094 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1095 typename _Compare
, typename _Alloc
>
1096 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1097 _Compare
, _Alloc
>::const_iterator
,
1098 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1099 _Compare
, _Alloc
>::const_iterator
>
1100 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1101 equal_range(const _Key
& __k
) const
1103 _Const_Link_type __x
= _M_begin();
1104 _Const_Link_type __y
= _M_end();
1107 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1108 __x
= _S_right(__x
);
1109 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1110 __y
= __x
, __x
= _S_left(__x
);
1113 _Const_Link_type
__xu(__x
), __yu(__y
);
1114 __y
= __x
, __x
= _S_left(__x
);
1115 __xu
= _S_right(__xu
);
1116 return pair
<const_iterator
,
1117 const_iterator
>(_M_lower_bound(__x
, __y
, __k
),
1118 _M_upper_bound(__xu
, __yu
, __k
));
1121 return pair
<const_iterator
, const_iterator
>(const_iterator(__y
),
1122 const_iterator(__y
));
1125 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1126 typename _Compare
, typename _Alloc
>
1128 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1129 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __t
)
1133 if (__t
._M_root() != 0)
1135 _M_root() = __t
._M_root();
1136 _M_leftmost() = __t
._M_leftmost();
1137 _M_rightmost() = __t
._M_rightmost();
1138 _M_root()->_M_parent
= _M_end();
1141 __t
._M_leftmost() = __t
._M_end();
1142 __t
._M_rightmost() = __t
._M_end();
1145 else if (__t
._M_root() == 0)
1147 __t
._M_root() = _M_root();
1148 __t
._M_leftmost() = _M_leftmost();
1149 __t
._M_rightmost() = _M_rightmost();
1150 __t
._M_root()->_M_parent
= __t
._M_end();
1153 _M_leftmost() = _M_end();
1154 _M_rightmost() = _M_end();
1158 std::swap(_M_root(),__t
._M_root());
1159 std::swap(_M_leftmost(),__t
._M_leftmost());
1160 std::swap(_M_rightmost(),__t
._M_rightmost());
1162 _M_root()->_M_parent
= _M_end();
1163 __t
._M_root()->_M_parent
= __t
._M_end();
1165 // No need to swap header's color as it does not change.
1166 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
1167 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
1169 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1170 // 431. Swapping containers with unequal allocators.
1171 std::__alloc_swap
<_Node_allocator
>::
1172 _S_do_it(_M_get_Node_allocator(), __t
._M_get_Node_allocator());
1175 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1176 typename _Compare
, typename _Alloc
>
1177 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1178 _Compare
, _Alloc
>::iterator
, bool>
1179 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1180 _M_insert_unique(const _Val
& __v
)
1182 _Link_type __x
= _M_begin();
1183 _Link_type __y
= _M_end();
1188 __comp
= _M_impl
._M_key_compare(_KeyOfValue()(__v
), _S_key(__x
));
1189 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
1191 iterator __j
= iterator(__y
);
1195 return pair
<iterator
, bool>(_M_insert_(__x
, __y
, __v
), true);
1199 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), _KeyOfValue()(__v
)))
1200 return pair
<iterator
, bool>(_M_insert_(__x
, __y
, __v
), true);
1201 return pair
<iterator
, bool>(__j
, false);
1204 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1205 typename _Compare
, typename _Alloc
>
1206 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1207 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1208 _M_insert_equal(const _Val
& __v
)
1210 _Link_type __x
= _M_begin();
1211 _Link_type __y
= _M_end();
1215 __x
= _M_impl
._M_key_compare(_KeyOfValue()(__v
), _S_key(__x
)) ?
1216 _S_left(__x
) : _S_right(__x
);
1218 return _M_insert_(__x
, __y
, __v
);
1221 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1222 typename _Compare
, typename _Alloc
>
1223 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1224 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1225 _M_insert_unique_(const_iterator __position
, const _Val
& __v
)
1228 if (__position
._M_node
== _M_end())
1231 && _M_impl
._M_key_compare(_S_key(_M_rightmost()),
1232 _KeyOfValue()(__v
)))
1233 return _M_insert_(0, _M_rightmost(), __v
);
1235 return _M_insert_unique(__v
).first
;
1237 else if (_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1238 _S_key(__position
._M_node
)))
1240 // First, try before...
1241 const_iterator __before
= __position
;
1242 if (__position
._M_node
== _M_leftmost()) // begin()
1243 return _M_insert_(_M_leftmost(), _M_leftmost(), __v
);
1244 else if (_M_impl
._M_key_compare(_S_key((--__before
)._M_node
),
1245 _KeyOfValue()(__v
)))
1247 if (_S_right(__before
._M_node
) == 0)
1248 return _M_insert_(0, __before
._M_node
, __v
);
1250 return _M_insert_(__position
._M_node
,
1251 __position
._M_node
, __v
);
1254 return _M_insert_unique(__v
).first
;
1256 else if (_M_impl
._M_key_compare(_S_key(__position
._M_node
),
1257 _KeyOfValue()(__v
)))
1259 // ... then try after.
1260 const_iterator __after
= __position
;
1261 if (__position
._M_node
== _M_rightmost())
1262 return _M_insert_(0, _M_rightmost(), __v
);
1263 else if (_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1264 _S_key((++__after
)._M_node
)))
1266 if (_S_right(__position
._M_node
) == 0)
1267 return _M_insert_(0, __position
._M_node
, __v
);
1269 return _M_insert_(__after
._M_node
, __after
._M_node
, __v
);
1272 return _M_insert_unique(__v
).first
;
1276 return iterator(static_cast<_Link_type
>
1277 (const_cast<_Base_ptr
>(__position
._M_node
)));
1280 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1281 typename _Compare
, typename _Alloc
>
1282 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1283 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1284 _M_insert_equal_(const_iterator __position
, const _Val
& __v
)
1287 if (__position
._M_node
== _M_end())
1290 && !_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1291 _S_key(_M_rightmost())))
1292 return _M_insert_(0, _M_rightmost(), __v
);
1294 return _M_insert_equal(__v
);
1296 else if (!_M_impl
._M_key_compare(_S_key(__position
._M_node
),
1297 _KeyOfValue()(__v
)))
1299 // First, try before...
1300 const_iterator __before
= __position
;
1301 if (__position
._M_node
== _M_leftmost()) // begin()
1302 return _M_insert_(_M_leftmost(), _M_leftmost(), __v
);
1303 else if (!_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1304 _S_key((--__before
)._M_node
)))
1306 if (_S_right(__before
._M_node
) == 0)
1307 return _M_insert_(0, __before
._M_node
, __v
);
1309 return _M_insert_(__position
._M_node
,
1310 __position
._M_node
, __v
);
1313 return _M_insert_equal(__v
);
1317 // ... then try after.
1318 const_iterator __after
= __position
;
1319 if (__position
._M_node
== _M_rightmost())
1320 return _M_insert_(0, _M_rightmost(), __v
);
1321 else if (!_M_impl
._M_key_compare(_S_key((++__after
)._M_node
),
1322 _KeyOfValue()(__v
)))
1324 if (_S_right(__position
._M_node
) == 0)
1325 return _M_insert_(0, __position
._M_node
, __v
);
1327 return _M_insert_(__after
._M_node
, __after
._M_node
, __v
);
1330 return _M_insert_equal_lower(__v
);
1334 template<typename _Key
, typename _Val
, typename _KoV
,
1335 typename _Cmp
, typename _Alloc
>
1338 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
1339 _M_insert_unique(_II __first
, _II __last
)
1341 for (; __first
!= __last
; ++__first
)
1342 _M_insert_unique_(end(), *__first
);
1345 template<typename _Key
, typename _Val
, typename _KoV
,
1346 typename _Cmp
, typename _Alloc
>
1349 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
1350 _M_insert_equal(_II __first
, _II __last
)
1352 for (; __first
!= __last
; ++__first
)
1353 _M_insert_equal_(end(), *__first
);
1356 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1357 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1358 // DR 130. Associative erase should return an iterator.
1359 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1360 typename _Compare
, typename _Alloc
>
1361 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1362 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1363 erase(iterator __position
)
1365 iterator __result
= __position
;
1368 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1369 (__position
._M_node
,
1370 this->_M_impl
._M_header
));
1371 _M_destroy_node(__y
);
1372 --_M_impl
._M_node_count
;
1376 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1377 // DR 130. Associative erase should return an iterator.
1378 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1379 typename _Compare
, typename _Alloc
>
1380 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::const_iterator
1381 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1382 erase(const_iterator __position
)
1384 const_iterator __result
= __position
;
1387 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1388 (const_cast<_Base_ptr
>(__position
._M_node
),
1389 this->_M_impl
._M_header
));
1390 _M_destroy_node(__y
);
1391 --_M_impl
._M_node_count
;
1395 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1396 typename _Compare
, typename _Alloc
>
1398 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1399 erase(iterator __position
)
1402 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1403 (__position
._M_node
,
1404 this->_M_impl
._M_header
));
1405 _M_destroy_node(__y
);
1406 --_M_impl
._M_node_count
;
1409 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1410 typename _Compare
, typename _Alloc
>
1412 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1413 erase(const_iterator __position
)
1416 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1417 (const_cast<_Base_ptr
>(__position
._M_node
),
1418 this->_M_impl
._M_header
));
1419 _M_destroy_node(__y
);
1420 --_M_impl
._M_node_count
;
1424 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1425 typename _Compare
, typename _Alloc
>
1426 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
1427 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1428 erase(const _Key
& __x
)
1430 pair
<iterator
, iterator
> __p
= equal_range(__x
);
1431 const size_type __old_size
= size();
1432 erase(__p
.first
, __p
.second
);
1433 return __old_size
- size();
1436 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1437 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1438 // DR 130. Associative erase should return an iterator.
1439 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1440 typename _Compare
, typename _Alloc
>
1441 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1442 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1443 erase(iterator __first
, iterator __last
)
1445 if (__first
== begin() && __last
== end())
1452 while (__first
!= __last
)
1458 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1459 // DR 130. Associative erase should return an iterator.
1460 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1461 typename _Compare
, typename _Alloc
>
1462 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::const_iterator
1463 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1464 erase(const_iterator __first
, const_iterator __last
)
1466 if (__first
== begin() && __last
== end())
1473 while (__first
!= __last
)
1479 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1480 typename _Compare
, typename _Alloc
>
1482 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1483 erase(iterator __first
, iterator __last
)
1485 if (__first
== begin() && __last
== end())
1488 while (__first
!= __last
)
1492 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1493 typename _Compare
, typename _Alloc
>
1495 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1496 erase(const_iterator __first
, const_iterator __last
)
1498 if (__first
== begin() && __last
== end())
1501 while (__first
!= __last
)
1506 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1507 typename _Compare
, typename _Alloc
>
1509 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1510 erase(const _Key
* __first
, const _Key
* __last
)
1512 while (__first
!= __last
)
1516 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1517 typename _Compare
, typename _Alloc
>
1518 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1519 _Compare
, _Alloc
>::iterator
1520 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1521 find(const _Key
& __k
)
1523 iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
1524 return (__j
== end()
1525 || _M_impl
._M_key_compare(__k
,
1526 _S_key(__j
._M_node
))) ? end() : __j
;
1529 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1530 typename _Compare
, typename _Alloc
>
1531 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1532 _Compare
, _Alloc
>::const_iterator
1533 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1534 find(const _Key
& __k
) const
1536 const_iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
1537 return (__j
== end()
1538 || _M_impl
._M_key_compare(__k
,
1539 _S_key(__j
._M_node
))) ? end() : __j
;
1542 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1543 typename _Compare
, typename _Alloc
>
1544 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
1545 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1546 count(const _Key
& __k
) const
1548 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
1549 const size_type __n
= std::distance(__p
.first
, __p
.second
);
1553 _GLIBCXX_PURE
unsigned int
1554 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
1555 const _Rb_tree_node_base
* __root
) throw ();
1557 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1558 typename _Compare
, typename _Alloc
>
1560 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
1562 if (_M_impl
._M_node_count
== 0 || begin() == end())
1563 return _M_impl
._M_node_count
== 0 && begin() == end()
1564 && this->_M_impl
._M_header
._M_left
== _M_end()
1565 && this->_M_impl
._M_header
._M_right
== _M_end();
1567 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
1568 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
1570 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
1571 _Const_Link_type __L
= _S_left(__x
);
1572 _Const_Link_type __R
= _S_right(__x
);
1574 if (__x
->_M_color
== _S_red
)
1575 if ((__L
&& __L
->_M_color
== _S_red
)
1576 || (__R
&& __R
->_M_color
== _S_red
))
1579 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
1581 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
1584 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
1588 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1590 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1595 _GLIBCXX_END_NAMESPACE