1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001-2014 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
27 * Copyright (c) 1996,1997
28 * Silicon Graphics Computer Systems, Inc.
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Silicon Graphics makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
40 * Hewlett-Packard Company
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Hewlett-Packard Company makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
53 /** @file bits/stl_tree.h
54 * This is an internal header file, included by other library headers.
55 * Do not attempt to use it directly. @headername{map,set}
61 #pragma GCC system_header
63 #include <bits/stl_algobase.h>
64 #include <bits/allocator.h>
65 #include <bits/stl_function.h>
66 #include <bits/cpp_type_traits.h>
67 #include <ext/alloc_traits.h>
68 #if __cplusplus >= 201103L
69 #include <ext/aligned_buffer.h>
72 namespace std
_GLIBCXX_VISIBILITY(default)
74 _GLIBCXX_BEGIN_NAMESPACE_VERSION
76 // Red-black tree class, designed for use in implementing STL
77 // associative containers (set, multiset, map, and multimap). The
78 // insertion and deletion algorithms are based on those in Cormen,
79 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
82 // (1) the header cell is maintained with links not only to the root
83 // but also to the leftmost node of the tree, to enable constant
84 // time begin(), and to the rightmost node of the tree, to enable
85 // linear time performance when used with the generic set algorithms
88 // (2) when a node being deleted has two children its successor node
89 // is relinked into its place, rather than copied, so that the only
90 // iterators invalidated are those referring to the deleted node.
92 enum _Rb_tree_color
{ _S_red
= false, _S_black
= true };
94 struct _Rb_tree_node_base
96 typedef _Rb_tree_node_base
* _Base_ptr
;
97 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
99 _Rb_tree_color _M_color
;
105 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
107 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
111 static _Const_Base_ptr
112 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
114 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
119 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
121 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
125 static _Const_Base_ptr
126 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
128 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
133 template<typename _Val
>
134 struct _Rb_tree_node
: public _Rb_tree_node_base
136 typedef _Rb_tree_node
<_Val
>* _Link_type
;
138 #if __cplusplus < 201103L
143 { return std::__addressof(_M_value_field
); }
147 { return std::__addressof(_M_value_field
); }
149 __gnu_cxx::__aligned_buffer
<_Val
> _M_storage
;
153 { return _M_storage
._M_ptr(); }
157 { return _M_storage
._M_ptr(); }
161 _GLIBCXX_PURE _Rb_tree_node_base
*
162 _Rb_tree_increment(_Rb_tree_node_base
* __x
) throw ();
164 _GLIBCXX_PURE
const _Rb_tree_node_base
*
165 _Rb_tree_increment(const _Rb_tree_node_base
* __x
) throw ();
167 _GLIBCXX_PURE _Rb_tree_node_base
*
168 _Rb_tree_decrement(_Rb_tree_node_base
* __x
) throw ();
170 _GLIBCXX_PURE
const _Rb_tree_node_base
*
171 _Rb_tree_decrement(const _Rb_tree_node_base
* __x
) throw ();
173 template<typename _Tp
>
174 struct _Rb_tree_iterator
176 typedef _Tp value_type
;
177 typedef _Tp
& reference
;
178 typedef _Tp
* pointer
;
180 typedef bidirectional_iterator_tag iterator_category
;
181 typedef ptrdiff_t difference_type
;
183 typedef _Rb_tree_iterator
<_Tp
> _Self
;
184 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
185 typedef _Rb_tree_node
<_Tp
>* _Link_type
;
187 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
191 _Rb_tree_iterator(_Link_type __x
) _GLIBCXX_NOEXCEPT
195 operator*() const _GLIBCXX_NOEXCEPT
196 { return *static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
199 operator->() const _GLIBCXX_NOEXCEPT
200 { return static_cast<_Link_type
> (_M_node
)->_M_valptr(); }
203 operator++() _GLIBCXX_NOEXCEPT
205 _M_node
= _Rb_tree_increment(_M_node
);
210 operator++(int) _GLIBCXX_NOEXCEPT
213 _M_node
= _Rb_tree_increment(_M_node
);
218 operator--() _GLIBCXX_NOEXCEPT
220 _M_node
= _Rb_tree_decrement(_M_node
);
225 operator--(int) _GLIBCXX_NOEXCEPT
228 _M_node
= _Rb_tree_decrement(_M_node
);
233 operator==(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
234 { return _M_node
== __x
._M_node
; }
237 operator!=(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
238 { return _M_node
!= __x
._M_node
; }
243 template<typename _Tp
>
244 struct _Rb_tree_const_iterator
246 typedef _Tp value_type
;
247 typedef const _Tp
& reference
;
248 typedef const _Tp
* pointer
;
250 typedef _Rb_tree_iterator
<_Tp
> iterator
;
252 typedef bidirectional_iterator_tag iterator_category
;
253 typedef ptrdiff_t difference_type
;
255 typedef _Rb_tree_const_iterator
<_Tp
> _Self
;
256 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr
;
257 typedef const _Rb_tree_node
<_Tp
>* _Link_type
;
259 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
263 _Rb_tree_const_iterator(_Link_type __x
) _GLIBCXX_NOEXCEPT
266 _Rb_tree_const_iterator(const iterator
& __it
) _GLIBCXX_NOEXCEPT
267 : _M_node(__it
._M_node
) { }
270 _M_const_cast() const _GLIBCXX_NOEXCEPT
271 { return iterator(static_cast<typename
iterator::_Link_type
>
272 (const_cast<typename
iterator::_Base_ptr
>(_M_node
))); }
275 operator*() const _GLIBCXX_NOEXCEPT
276 { return *static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
279 operator->() const _GLIBCXX_NOEXCEPT
280 { return static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
283 operator++() _GLIBCXX_NOEXCEPT
285 _M_node
= _Rb_tree_increment(_M_node
);
290 operator++(int) _GLIBCXX_NOEXCEPT
293 _M_node
= _Rb_tree_increment(_M_node
);
298 operator--() _GLIBCXX_NOEXCEPT
300 _M_node
= _Rb_tree_decrement(_M_node
);
305 operator--(int) _GLIBCXX_NOEXCEPT
308 _M_node
= _Rb_tree_decrement(_M_node
);
313 operator==(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
314 { return _M_node
== __x
._M_node
; }
317 operator!=(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
318 { return _M_node
!= __x
._M_node
; }
323 template<typename _Val
>
325 operator==(const _Rb_tree_iterator
<_Val
>& __x
,
326 const _Rb_tree_const_iterator
<_Val
>& __y
) _GLIBCXX_NOEXCEPT
327 { return __x
._M_node
== __y
._M_node
; }
329 template<typename _Val
>
331 operator!=(const _Rb_tree_iterator
<_Val
>& __x
,
332 const _Rb_tree_const_iterator
<_Val
>& __y
) _GLIBCXX_NOEXCEPT
333 { return __x
._M_node
!= __y
._M_node
; }
336 _Rb_tree_insert_and_rebalance(const bool __insert_left
,
337 _Rb_tree_node_base
* __x
,
338 _Rb_tree_node_base
* __p
,
339 _Rb_tree_node_base
& __header
) throw ();
342 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
343 _Rb_tree_node_base
& __header
) throw ();
346 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
347 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
350 typedef typename
__gnu_cxx::__alloc_traits
<_Alloc
>::template
351 rebind
<_Rb_tree_node
<_Val
> >::other _Node_allocator
;
353 typedef __gnu_cxx::__alloc_traits
<_Node_allocator
> _Alloc_traits
;
356 typedef _Rb_tree_node_base
* _Base_ptr
;
357 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
358 typedef _Rb_tree_node
<_Val
>* _Link_type
;
359 typedef const _Rb_tree_node
<_Val
>* _Const_Link_type
;
362 // Functor recycling a pool of nodes and using allocation once the pool is
364 struct _Reuse_or_alloc_node
366 _Reuse_or_alloc_node(const _Rb_tree_node_base
& __header
,
368 : _M_root(__header
._M_parent
), _M_nodes(__header
._M_right
), _M_t(__t
)
371 _M_root
->_M_parent
= 0;
376 #if __cplusplus >= 201103L
377 _Reuse_or_alloc_node(const _Reuse_or_alloc_node
&) = delete;
380 ~_Reuse_or_alloc_node()
381 { _M_t
._M_erase(static_cast<_Link_type
>(_M_root
)); }
383 template<typename _Arg
>
385 #if __cplusplus < 201103L
386 operator()(const _Arg
& __arg
)
388 operator()(_Arg
&& __arg
)
391 _Link_type __node
= static_cast<_Link_type
>(_M_extract());
394 _M_t
._M_destroy_node(__node
);
395 _M_t
._M_construct_node(__node
, _GLIBCXX_FORWARD(_Arg
, __arg
));
399 return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
));
409 _Base_ptr __node
= _M_nodes
;
410 _M_nodes
= _M_nodes
->_M_parent
;
413 if (_M_nodes
->_M_right
== __node
)
415 _M_nodes
->_M_right
= 0;
417 if (_M_nodes
->_M_left
)
419 _M_nodes
= _M_nodes
->_M_left
;
421 while (_M_nodes
->_M_right
)
422 _M_nodes
= _M_nodes
->_M_right
;
425 else // __node is on the left.
426 _M_nodes
->_M_left
= 0;
439 // Functor similar to the previous one but without any pool of node to
443 _Alloc_node(_Rb_tree
& __t
)
446 template<typename _Arg
>
448 #if __cplusplus < 201103L
449 operator()(const _Arg
& __arg
) const
451 operator()(_Arg
&& __arg
) const
453 { return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
)); }
460 typedef _Key key_type
;
461 typedef _Val value_type
;
462 typedef value_type
* pointer
;
463 typedef const value_type
* const_pointer
;
464 typedef value_type
& reference
;
465 typedef const value_type
& const_reference
;
466 typedef size_t size_type
;
467 typedef ptrdiff_t difference_type
;
468 typedef _Alloc allocator_type
;
471 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
472 { return *static_cast<_Node_allocator
*>(&this->_M_impl
); }
474 const _Node_allocator
&
475 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
476 { return *static_cast<const _Node_allocator
*>(&this->_M_impl
); }
479 get_allocator() const _GLIBCXX_NOEXCEPT
480 { return allocator_type(_M_get_Node_allocator()); }
485 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
488 _M_put_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
489 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p
, 1); }
491 #if __cplusplus < 201103L
493 _M_construct_node(_Link_type __node
, const value_type
& __x
)
496 { get_allocator().construct(__node
->_M_valptr(), __x
); }
500 __throw_exception_again
;
505 _M_create_node(const value_type
& __x
)
507 _Link_type __tmp
= _M_get_node();
508 _M_construct_node(__tmp
, __x
);
513 _M_destroy_node(_Link_type __p
)
514 { get_allocator().destroy(__p
->_M_valptr()); }
516 template<typename
... _Args
>
518 _M_construct_node(_Link_type __node
, _Args
&&... __args
)
522 ::new(__node
) _Rb_tree_node
<_Val
>;
523 _Alloc_traits::construct(_M_get_Node_allocator(),
525 std::forward
<_Args
>(__args
)...);
529 __node
->~_Rb_tree_node
<_Val
>();
531 __throw_exception_again
;
535 template<typename
... _Args
>
537 _M_create_node(_Args
&&... __args
)
539 _Link_type __tmp
= _M_get_node();
540 _M_construct_node(__tmp
, std::forward
<_Args
>(__args
)...);
545 _M_destroy_node(_Link_type __p
) noexcept
547 _Alloc_traits::destroy(_M_get_Node_allocator(), __p
->_M_valptr());
548 __p
->~_Rb_tree_node
<_Val
>();
553 _M_drop_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
555 _M_destroy_node(__p
);
559 template<typename _NodeGen
>
561 _M_clone_node(_Const_Link_type __x
, _NodeGen
& __node_gen
)
563 _Link_type __tmp
= __node_gen(*__x
->_M_valptr());
564 __tmp
->_M_color
= __x
->_M_color
;
571 // Unused _Is_pod_comparator is kept as it is part of mangled name.
572 template<typename _Key_compare
,
573 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare
)>
574 struct _Rb_tree_impl
: public _Node_allocator
576 _Key_compare _M_key_compare
;
577 _Rb_tree_node_base _M_header
;
578 size_type _M_node_count
; // Keeps track of size of tree.
581 : _Node_allocator(), _M_key_compare(), _M_header(),
585 _Rb_tree_impl(const _Key_compare
& __comp
, const _Node_allocator
& __a
)
586 : _Node_allocator(__a
), _M_key_compare(__comp
), _M_header(),
590 #if __cplusplus >= 201103L
591 _Rb_tree_impl(const _Key_compare
& __comp
, _Node_allocator
&& __a
)
592 : _Node_allocator(std::move(__a
)), _M_key_compare(__comp
),
593 _M_header(), _M_node_count(0)
600 this->_M_header
._M_parent
= 0;
601 this->_M_header
._M_left
= &this->_M_header
;
602 this->_M_header
._M_right
= &this->_M_header
;
603 this->_M_node_count
= 0;
610 this->_M_header
._M_color
= _S_red
;
611 this->_M_header
._M_parent
= 0;
612 this->_M_header
._M_left
= &this->_M_header
;
613 this->_M_header
._M_right
= &this->_M_header
;
617 _Rb_tree_impl
<_Compare
> _M_impl
;
621 _M_root() _GLIBCXX_NOEXCEPT
622 { return this->_M_impl
._M_header
._M_parent
; }
625 _M_root() const _GLIBCXX_NOEXCEPT
626 { return this->_M_impl
._M_header
._M_parent
; }
629 _M_leftmost() _GLIBCXX_NOEXCEPT
630 { return this->_M_impl
._M_header
._M_left
; }
633 _M_leftmost() const _GLIBCXX_NOEXCEPT
634 { return this->_M_impl
._M_header
._M_left
; }
637 _M_rightmost() _GLIBCXX_NOEXCEPT
638 { return this->_M_impl
._M_header
._M_right
; }
641 _M_rightmost() const _GLIBCXX_NOEXCEPT
642 { return this->_M_impl
._M_header
._M_right
; }
645 _M_begin() _GLIBCXX_NOEXCEPT
646 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
649 _M_begin() const _GLIBCXX_NOEXCEPT
651 return static_cast<_Const_Link_type
>
652 (this->_M_impl
._M_header
._M_parent
);
656 _M_end() _GLIBCXX_NOEXCEPT
657 { return reinterpret_cast<_Link_type
>(&this->_M_impl
._M_header
); }
660 _M_end() const _GLIBCXX_NOEXCEPT
661 { return reinterpret_cast<_Const_Link_type
>(&this->_M_impl
._M_header
); }
663 static const_reference
664 _S_value(_Const_Link_type __x
)
665 { return *__x
->_M_valptr(); }
668 _S_key(_Const_Link_type __x
)
669 { return _KeyOfValue()(_S_value(__x
)); }
672 _S_left(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
673 { return static_cast<_Link_type
>(__x
->_M_left
); }
675 static _Const_Link_type
676 _S_left(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
677 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
680 _S_right(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
681 { return static_cast<_Link_type
>(__x
->_M_right
); }
683 static _Const_Link_type
684 _S_right(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
685 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
687 static const_reference
688 _S_value(_Const_Base_ptr __x
)
689 { return *static_cast<_Const_Link_type
>(__x
)->_M_valptr(); }
692 _S_key(_Const_Base_ptr __x
)
693 { return _KeyOfValue()(_S_value(__x
)); }
696 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
697 { return _Rb_tree_node_base::_S_minimum(__x
); }
699 static _Const_Base_ptr
700 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
701 { return _Rb_tree_node_base::_S_minimum(__x
); }
704 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
705 { return _Rb_tree_node_base::_S_maximum(__x
); }
707 static _Const_Base_ptr
708 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
709 { return _Rb_tree_node_base::_S_maximum(__x
); }
712 typedef _Rb_tree_iterator
<value_type
> iterator
;
713 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
715 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
716 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
719 pair
<_Base_ptr
, _Base_ptr
>
720 _M_get_insert_unique_pos(const key_type
& __k
);
722 pair
<_Base_ptr
, _Base_ptr
>
723 _M_get_insert_equal_pos(const key_type
& __k
);
725 pair
<_Base_ptr
, _Base_ptr
>
726 _M_get_insert_hint_unique_pos(const_iterator __pos
,
727 const key_type
& __k
);
729 pair
<_Base_ptr
, _Base_ptr
>
730 _M_get_insert_hint_equal_pos(const_iterator __pos
,
731 const key_type
& __k
);
733 #if __cplusplus >= 201103L
734 template<typename _Arg
, typename _NodeGen
>
736 _M_insert_(_Base_ptr __x
, _Base_ptr __y
, _Arg
&& __v
, _NodeGen
&);
739 _M_insert_node(_Base_ptr __x
, _Base_ptr __y
, _Link_type __z
);
741 template<typename _Arg
>
743 _M_insert_lower(_Base_ptr __y
, _Arg
&& __v
);
745 template<typename _Arg
>
747 _M_insert_equal_lower(_Arg
&& __x
);
750 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
);
753 _M_insert_equal_lower_node(_Link_type __z
);
755 template<typename _NodeGen
>
757 _M_insert_(_Base_ptr __x
, _Base_ptr __y
,
758 const value_type
& __v
, _NodeGen
&);
760 // _GLIBCXX_RESOLVE_LIB_DEFECTS
761 // 233. Insertion hints in associative containers.
763 _M_insert_lower(_Base_ptr __y
, const value_type
& __v
);
766 _M_insert_equal_lower(const value_type
& __x
);
769 template<typename _NodeGen
>
771 _M_copy(_Const_Link_type __x
, _Link_type __p
, _NodeGen
&);
774 _M_copy(_Const_Link_type __x
, _Link_type __p
)
776 _Alloc_node
__an(*this);
777 return _M_copy(__x
, __p
, __an
);
781 _M_erase(_Link_type __x
);
784 _M_lower_bound(_Link_type __x
, _Link_type __y
,
788 _M_lower_bound(_Const_Link_type __x
, _Const_Link_type __y
,
789 const _Key
& __k
) const;
792 _M_upper_bound(_Link_type __x
, _Link_type __y
,
796 _M_upper_bound(_Const_Link_type __x
, _Const_Link_type __y
,
797 const _Key
& __k
) const;
800 // allocation/deallocation
803 _Rb_tree(const _Compare
& __comp
,
804 const allocator_type
& __a
= allocator_type())
805 : _M_impl(__comp
, _Node_allocator(__a
)) { }
807 _Rb_tree(const _Rb_tree
& __x
)
808 : _M_impl(__x
._M_impl
._M_key_compare
,
809 _Alloc_traits::_S_select_on_copy(__x
._M_get_Node_allocator()))
811 if (__x
._M_root() != 0)
813 _M_root() = _M_copy(__x
._M_begin(), _M_end());
814 _M_leftmost() = _S_minimum(_M_root());
815 _M_rightmost() = _S_maximum(_M_root());
816 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
820 #if __cplusplus >= 201103L
821 _Rb_tree(const allocator_type
& __a
)
822 : _M_impl(_Compare(), _Node_allocator(__a
))
825 _Rb_tree(const _Rb_tree
& __x
, const allocator_type
& __a
)
826 : _M_impl(__x
._M_impl
._M_key_compare
, _Node_allocator(__a
))
828 if (__x
._M_root() != nullptr)
830 _M_root() = _M_copy(__x
._M_begin(), _M_end());
831 _M_leftmost() = _S_minimum(_M_root());
832 _M_rightmost() = _S_maximum(_M_root());
833 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
837 _Rb_tree(_Rb_tree
&& __x
)
838 : _M_impl(__x
._M_impl
._M_key_compare
, __x
._M_get_Node_allocator())
840 if (__x
._M_root() != 0)
841 _M_move_data(__x
, std::true_type());
844 _Rb_tree(_Rb_tree
&& __x
, const allocator_type
& __a
)
845 : _Rb_tree(std::move(__x
), _Node_allocator(__a
))
848 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
);
851 ~_Rb_tree() _GLIBCXX_NOEXCEPT
852 { _M_erase(_M_begin()); }
855 operator=(const _Rb_tree
& __x
);
860 { return _M_impl
._M_key_compare
; }
863 begin() _GLIBCXX_NOEXCEPT
865 return iterator(static_cast<_Link_type
>
866 (this->_M_impl
._M_header
._M_left
));
870 begin() const _GLIBCXX_NOEXCEPT
872 return const_iterator(static_cast<_Const_Link_type
>
873 (this->_M_impl
._M_header
._M_left
));
877 end() _GLIBCXX_NOEXCEPT
878 { return iterator(static_cast<_Link_type
>(&this->_M_impl
._M_header
)); }
881 end() const _GLIBCXX_NOEXCEPT
883 return const_iterator(static_cast<_Const_Link_type
>
884 (&this->_M_impl
._M_header
));
888 rbegin() _GLIBCXX_NOEXCEPT
889 { return reverse_iterator(end()); }
891 const_reverse_iterator
892 rbegin() const _GLIBCXX_NOEXCEPT
893 { return const_reverse_iterator(end()); }
896 rend() _GLIBCXX_NOEXCEPT
897 { return reverse_iterator(begin()); }
899 const_reverse_iterator
900 rend() const _GLIBCXX_NOEXCEPT
901 { return const_reverse_iterator(begin()); }
904 empty() const _GLIBCXX_NOEXCEPT
905 { return _M_impl
._M_node_count
== 0; }
908 size() const _GLIBCXX_NOEXCEPT
909 { return _M_impl
._M_node_count
; }
912 max_size() const _GLIBCXX_NOEXCEPT
913 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
916 #if __cplusplus >= 201103L
917 swap(_Rb_tree
& __t
) noexcept(_Alloc_traits::_S_nothrow_swap());
923 #if __cplusplus >= 201103L
924 template<typename _Arg
>
926 _M_insert_unique(_Arg
&& __x
);
928 template<typename _Arg
>
930 _M_insert_equal(_Arg
&& __x
);
932 template<typename _Arg
, typename _NodeGen
>
934 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
936 template<typename _Arg
>
938 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
)
940 _Alloc_node
__an(*this);
941 return _M_insert_unique_(__pos
, std::forward
<_Arg
>(__x
), __an
);
944 template<typename _Arg
, typename _NodeGen
>
946 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
948 template<typename _Arg
>
950 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
)
952 _Alloc_node
__an(*this);
953 return _M_insert_equal_(__pos
, std::forward
<_Arg
>(__x
), __an
);
956 template<typename
... _Args
>
958 _M_emplace_unique(_Args
&&... __args
);
960 template<typename
... _Args
>
962 _M_emplace_equal(_Args
&&... __args
);
964 template<typename
... _Args
>
966 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
);
968 template<typename
... _Args
>
970 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
);
973 _M_insert_unique(const value_type
& __x
);
976 _M_insert_equal(const value_type
& __x
);
978 template<typename _NodeGen
>
980 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
,
984 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
)
986 _Alloc_node
__an(*this);
987 return _M_insert_unique_(__pos
, __x
, __an
);
990 template<typename _NodeGen
>
992 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
,
995 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
)
997 _Alloc_node
__an(*this);
998 return _M_insert_equal_(__pos
, __x
, __an
);
1002 template<typename _InputIterator
>
1004 _M_insert_unique(_InputIterator __first
, _InputIterator __last
);
1006 template<typename _InputIterator
>
1008 _M_insert_equal(_InputIterator __first
, _InputIterator __last
);
1012 _M_erase_aux(const_iterator __position
);
1015 _M_erase_aux(const_iterator __first
, const_iterator __last
);
1018 #if __cplusplus >= 201103L
1019 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1020 // DR 130. Associative erase should return an iterator.
1021 _GLIBCXX_ABI_TAG_CXX11
1023 erase(const_iterator __position
)
1025 const_iterator __result
= __position
;
1027 _M_erase_aux(__position
);
1028 return __result
._M_const_cast();
1032 _GLIBCXX_ABI_TAG_CXX11
1034 erase(iterator __position
)
1036 iterator __result
= __position
;
1038 _M_erase_aux(__position
);
1043 erase(iterator __position
)
1044 { _M_erase_aux(__position
); }
1047 erase(const_iterator __position
)
1048 { _M_erase_aux(__position
); }
1051 erase(const key_type
& __x
);
1053 #if __cplusplus >= 201103L
1054 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1055 // DR 130. Associative erase should return an iterator.
1056 _GLIBCXX_ABI_TAG_CXX11
1058 erase(const_iterator __first
, const_iterator __last
)
1060 _M_erase_aux(__first
, __last
);
1061 return __last
._M_const_cast();
1065 erase(iterator __first
, iterator __last
)
1066 { _M_erase_aux(__first
, __last
); }
1069 erase(const_iterator __first
, const_iterator __last
)
1070 { _M_erase_aux(__first
, __last
); }
1073 erase(const key_type
* __first
, const key_type
* __last
);
1076 clear() _GLIBCXX_NOEXCEPT
1078 _M_erase(_M_begin());
1084 find(const key_type
& __k
);
1087 find(const key_type
& __k
) const;
1090 count(const key_type
& __k
) const;
1093 lower_bound(const key_type
& __k
)
1094 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1097 lower_bound(const key_type
& __k
) const
1098 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1101 upper_bound(const key_type
& __k
)
1102 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1105 upper_bound(const key_type
& __k
) const
1106 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1108 pair
<iterator
, iterator
>
1109 equal_range(const key_type
& __k
);
1111 pair
<const_iterator
, const_iterator
>
1112 equal_range(const key_type
& __k
) const;
1116 __rb_verify() const;
1118 #if __cplusplus >= 201103L
1120 operator=(_Rb_tree
&&) noexcept(_Alloc_traits::_S_nothrow_move());
1122 template<typename _Iterator
>
1124 _M_assign_unique(_Iterator
, _Iterator
);
1126 template<typename _Iterator
>
1128 _M_assign_equal(_Iterator
, _Iterator
);
1131 // Move elements from container with equal allocator.
1133 _M_move_data(_Rb_tree
&, std::true_type
);
1135 // Move elements from container with possibly non-equal allocator,
1136 // which might result in a copy not a move.
1138 _M_move_data(_Rb_tree
&, std::false_type
);
1142 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1143 typename _Compare
, typename _Alloc
>
1145 operator==(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1146 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1148 return __x
.size() == __y
.size()
1149 && std::equal(__x
.begin(), __x
.end(), __y
.begin());
1152 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1153 typename _Compare
, typename _Alloc
>
1155 operator<(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1156 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1158 return std::lexicographical_compare(__x
.begin(), __x
.end(),
1159 __y
.begin(), __y
.end());
1162 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1163 typename _Compare
, typename _Alloc
>
1165 operator!=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1166 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1167 { return !(__x
== __y
); }
1169 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1170 typename _Compare
, typename _Alloc
>
1172 operator>(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1173 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1174 { return __y
< __x
; }
1176 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1177 typename _Compare
, typename _Alloc
>
1179 operator<=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1180 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1181 { return !(__y
< __x
); }
1183 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1184 typename _Compare
, typename _Alloc
>
1186 operator>=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1187 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1188 { return !(__x
< __y
); }
1190 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1191 typename _Compare
, typename _Alloc
>
1193 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1194 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1197 #if __cplusplus >= 201103L
1198 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1199 typename _Compare
, typename _Alloc
>
1200 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1201 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
)
1202 : _M_impl(__x
._M_impl
._M_key_compare
, std::move(__a
))
1204 using __eq
= integral_constant
<bool, _Alloc_traits::_S_always_equal()>;
1205 if (__x
._M_root() != nullptr)
1206 _M_move_data(__x
, __eq());
1209 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1210 typename _Compare
, typename _Alloc
>
1212 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1213 _M_move_data(_Rb_tree
& __x
, std::true_type
)
1215 _M_root() = __x
._M_root();
1216 _M_leftmost() = __x
._M_leftmost();
1217 _M_rightmost() = __x
._M_rightmost();
1218 _M_root()->_M_parent
= _M_end();
1221 __x
._M_leftmost() = __x
._M_end();
1222 __x
._M_rightmost() = __x
._M_end();
1224 this->_M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1225 __x
._M_impl
._M_node_count
= 0;
1228 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1229 typename _Compare
, typename _Alloc
>
1231 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1232 _M_move_data(_Rb_tree
& __x
, std::false_type
)
1234 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1235 _M_move_data(__x
, std::true_type());
1238 _Alloc_node
__an(*this);
1240 [&__an
](const value_type
& __cval
)
1242 auto& __val
= const_cast<value_type
&>(__cval
);
1243 return __an(std::move_if_noexcept(__val
));
1245 _M_root() = _M_copy(__x
._M_begin(), _M_end(), __lbd
);
1246 _M_leftmost() = _S_minimum(_M_root());
1247 _M_rightmost() = _S_maximum(_M_root());
1248 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1252 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1253 typename _Compare
, typename _Alloc
>
1254 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1255 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1256 operator=(_Rb_tree
&& __x
)
1257 noexcept(_Alloc_traits::_S_nothrow_move())
1259 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
1260 if (_Alloc_traits::_S_propagate_on_move_assign()
1261 || _Alloc_traits::_S_always_equal()
1262 || _M_get_Node_allocator() == __x
._M_get_Node_allocator())
1265 if (__x
._M_root() != nullptr)
1266 _M_move_data(__x
, std::true_type());
1267 std::__alloc_on_move(_M_get_Node_allocator(),
1268 __x
._M_get_Node_allocator());
1272 // Try to move each node reusing existing nodes and copying __x nodes
1274 _Reuse_or_alloc_node
__roan(_M_impl
._M_header
, *this);
1276 if (__x
._M_root() != nullptr)
1279 [&__roan
](const value_type
& __cval
)
1281 auto& __val
= const_cast<value_type
&>(__cval
);
1282 return __roan(std::move_if_noexcept(__val
));
1284 _M_root() = _M_copy(__x
._M_begin(), _M_end(), __lbd
);
1285 _M_leftmost() = _S_minimum(_M_root());
1286 _M_rightmost() = _S_maximum(_M_root());
1287 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1293 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1294 typename _Compare
, typename _Alloc
>
1295 template<typename _Iterator
>
1297 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1298 _M_assign_unique(_Iterator __first
, _Iterator __last
)
1300 _Reuse_or_alloc_node
__roan(this->_M_impl
._M_header
, *this);
1302 for (; __first
!= __last
; ++__first
)
1303 _M_insert_unique_(end(), *__first
, __roan
);
1306 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1307 typename _Compare
, typename _Alloc
>
1308 template<typename _Iterator
>
1310 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1311 _M_assign_equal(_Iterator __first
, _Iterator __last
)
1313 _Reuse_or_alloc_node
__roan(this->_M_impl
._M_header
, *this);
1315 for (; __first
!= __last
; ++__first
)
1316 _M_insert_equal_(end(), *__first
, __roan
);
1320 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1321 typename _Compare
, typename _Alloc
>
1322 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1323 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1324 operator=(const _Rb_tree
& __x
)
1328 // Note that _Key may be a constant type.
1329 #if __cplusplus >= 201103L
1330 if (_Alloc_traits::_S_propagate_on_copy_assign())
1332 auto& __this_alloc
= this->_M_get_Node_allocator();
1333 auto& __that_alloc
= __x
._M_get_Node_allocator();
1334 if (!_Alloc_traits::_S_always_equal()
1335 && __this_alloc
!= __that_alloc
)
1337 // Replacement allocator cannot free existing storage, we need
1338 // to erase nodes first.
1340 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1345 _Reuse_or_alloc_node
__roan(this->_M_impl
._M_header
, *this);
1347 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
1348 if (__x
._M_root() != 0)
1350 _M_root() = _M_copy(__x
._M_begin(), _M_end(), __roan
);
1351 _M_leftmost() = _S_minimum(_M_root());
1352 _M_rightmost() = _S_maximum(_M_root());
1353 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1360 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1361 typename _Compare
, typename _Alloc
>
1362 #if __cplusplus >= 201103L
1363 template<typename _Arg
, typename _NodeGen
>
1365 template<typename _NodeGen
>
1367 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1368 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1369 _M_insert_(_Base_ptr __x
, _Base_ptr __p
,
1370 #if __cplusplus >= 201103L
1375 _NodeGen
& __node_gen
)
1377 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
1378 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
1381 _Link_type __z
= __node_gen(_GLIBCXX_FORWARD(_Arg
, __v
));
1383 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1384 this->_M_impl
._M_header
);
1385 ++_M_impl
._M_node_count
;
1386 return iterator(__z
);
1389 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1390 typename _Compare
, typename _Alloc
>
1391 #if __cplusplus >= 201103L
1392 template<typename _Arg
>
1394 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1395 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1396 #if __cplusplus >= 201103L
1397 _M_insert_lower(_Base_ptr __p
, _Arg
&& __v
)
1399 _M_insert_lower(_Base_ptr __p
, const _Val
& __v
)
1402 bool __insert_left
= (__p
== _M_end()
1403 || !_M_impl
._M_key_compare(_S_key(__p
),
1404 _KeyOfValue()(__v
)));
1406 _Link_type __z
= _M_create_node(_GLIBCXX_FORWARD(_Arg
, __v
));
1408 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1409 this->_M_impl
._M_header
);
1410 ++_M_impl
._M_node_count
;
1411 return iterator(__z
);
1414 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1415 typename _Compare
, typename _Alloc
>
1416 #if __cplusplus >= 201103L
1417 template<typename _Arg
>
1419 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1420 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1421 #if __cplusplus >= 201103L
1422 _M_insert_equal_lower(_Arg
&& __v
)
1424 _M_insert_equal_lower(const _Val
& __v
)
1427 _Link_type __x
= _M_begin();
1428 _Link_type __y
= _M_end();
1432 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _KeyOfValue()(__v
)) ?
1433 _S_left(__x
) : _S_right(__x
);
1435 return _M_insert_lower(__y
, _GLIBCXX_FORWARD(_Arg
, __v
));
1438 template<typename _Key
, typename _Val
, typename _KoV
,
1439 typename _Compare
, typename _Alloc
>
1440 template<typename _NodeGen
>
1441 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1442 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
1443 _M_copy(_Const_Link_type __x
, _Link_type __p
, _NodeGen
& __node_gen
)
1445 // Structural copy. __x and __p must be non-null.
1446 _Link_type __top
= _M_clone_node(__x
, __node_gen
);
1447 __top
->_M_parent
= __p
;
1452 __top
->_M_right
= _M_copy(_S_right(__x
), __top
, __node_gen
);
1458 _Link_type __y
= _M_clone_node(__x
, __node_gen
);
1460 __y
->_M_parent
= __p
;
1462 __y
->_M_right
= _M_copy(_S_right(__x
), __y
, __node_gen
);
1470 __throw_exception_again
;
1475 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1476 typename _Compare
, typename _Alloc
>
1478 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1479 _M_erase(_Link_type __x
)
1481 // Erase without rebalancing.
1484 _M_erase(_S_right(__x
));
1485 _Link_type __y
= _S_left(__x
);
1491 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1492 typename _Compare
, typename _Alloc
>
1493 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1494 _Compare
, _Alloc
>::iterator
1495 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1496 _M_lower_bound(_Link_type __x
, _Link_type __y
,
1500 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1501 __y
= __x
, __x
= _S_left(__x
);
1503 __x
= _S_right(__x
);
1504 return iterator(__y
);
1507 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1508 typename _Compare
, typename _Alloc
>
1509 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1510 _Compare
, _Alloc
>::const_iterator
1511 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1512 _M_lower_bound(_Const_Link_type __x
, _Const_Link_type __y
,
1513 const _Key
& __k
) const
1516 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1517 __y
= __x
, __x
= _S_left(__x
);
1519 __x
= _S_right(__x
);
1520 return const_iterator(__y
);
1523 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1524 typename _Compare
, typename _Alloc
>
1525 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1526 _Compare
, _Alloc
>::iterator
1527 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1528 _M_upper_bound(_Link_type __x
, _Link_type __y
,
1532 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1533 __y
= __x
, __x
= _S_left(__x
);
1535 __x
= _S_right(__x
);
1536 return iterator(__y
);
1539 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1540 typename _Compare
, typename _Alloc
>
1541 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1542 _Compare
, _Alloc
>::const_iterator
1543 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1544 _M_upper_bound(_Const_Link_type __x
, _Const_Link_type __y
,
1545 const _Key
& __k
) const
1548 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1549 __y
= __x
, __x
= _S_left(__x
);
1551 __x
= _S_right(__x
);
1552 return const_iterator(__y
);
1555 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1556 typename _Compare
, typename _Alloc
>
1557 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1558 _Compare
, _Alloc
>::iterator
,
1559 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1560 _Compare
, _Alloc
>::iterator
>
1561 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1562 equal_range(const _Key
& __k
)
1564 _Link_type __x
= _M_begin();
1565 _Link_type __y
= _M_end();
1568 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1569 __x
= _S_right(__x
);
1570 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1571 __y
= __x
, __x
= _S_left(__x
);
1574 _Link_type
__xu(__x
), __yu(__y
);
1575 __y
= __x
, __x
= _S_left(__x
);
1576 __xu
= _S_right(__xu
);
1577 return pair
<iterator
,
1578 iterator
>(_M_lower_bound(__x
, __y
, __k
),
1579 _M_upper_bound(__xu
, __yu
, __k
));
1582 return pair
<iterator
, iterator
>(iterator(__y
),
1586 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1587 typename _Compare
, typename _Alloc
>
1588 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1589 _Compare
, _Alloc
>::const_iterator
,
1590 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1591 _Compare
, _Alloc
>::const_iterator
>
1592 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1593 equal_range(const _Key
& __k
) const
1595 _Const_Link_type __x
= _M_begin();
1596 _Const_Link_type __y
= _M_end();
1599 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1600 __x
= _S_right(__x
);
1601 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1602 __y
= __x
, __x
= _S_left(__x
);
1605 _Const_Link_type
__xu(__x
), __yu(__y
);
1606 __y
= __x
, __x
= _S_left(__x
);
1607 __xu
= _S_right(__xu
);
1608 return pair
<const_iterator
,
1609 const_iterator
>(_M_lower_bound(__x
, __y
, __k
),
1610 _M_upper_bound(__xu
, __yu
, __k
));
1613 return pair
<const_iterator
, const_iterator
>(const_iterator(__y
),
1614 const_iterator(__y
));
1617 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1618 typename _Compare
, typename _Alloc
>
1620 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1621 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __t
)
1622 #if __cplusplus >= 201103L
1623 noexcept(_Alloc_traits::_S_nothrow_swap())
1628 if (__t
._M_root() != 0)
1630 _M_root() = __t
._M_root();
1631 _M_leftmost() = __t
._M_leftmost();
1632 _M_rightmost() = __t
._M_rightmost();
1633 _M_root()->_M_parent
= _M_end();
1634 _M_impl
._M_node_count
= __t
._M_impl
._M_node_count
;
1636 __t
._M_impl
._M_reset();
1639 else if (__t
._M_root() == 0)
1641 __t
._M_root() = _M_root();
1642 __t
._M_leftmost() = _M_leftmost();
1643 __t
._M_rightmost() = _M_rightmost();
1644 __t
._M_root()->_M_parent
= __t
._M_end();
1645 __t
._M_impl
._M_node_count
= _M_impl
._M_node_count
;
1651 std::swap(_M_root(),__t
._M_root());
1652 std::swap(_M_leftmost(),__t
._M_leftmost());
1653 std::swap(_M_rightmost(),__t
._M_rightmost());
1655 _M_root()->_M_parent
= _M_end();
1656 __t
._M_root()->_M_parent
= __t
._M_end();
1657 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
1659 // No need to swap header's color as it does not change.
1660 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
1662 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
1663 __t
._M_get_Node_allocator());
1666 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1667 typename _Compare
, typename _Alloc
>
1668 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1669 _Compare
, _Alloc
>::_Base_ptr
,
1670 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1671 _Compare
, _Alloc
>::_Base_ptr
>
1672 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1673 _M_get_insert_unique_pos(const key_type
& __k
)
1675 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
1676 _Link_type __x
= _M_begin();
1677 _Link_type __y
= _M_end();
1682 __comp
= _M_impl
._M_key_compare(__k
, _S_key(__x
));
1683 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
1685 iterator __j
= iterator(__y
);
1689 return _Res(__x
, __y
);
1693 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), __k
))
1694 return _Res(__x
, __y
);
1695 return _Res(__j
._M_node
, 0);
1698 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1699 typename _Compare
, typename _Alloc
>
1700 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1701 _Compare
, _Alloc
>::_Base_ptr
,
1702 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1703 _Compare
, _Alloc
>::_Base_ptr
>
1704 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1705 _M_get_insert_equal_pos(const key_type
& __k
)
1707 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
1708 _Link_type __x
= _M_begin();
1709 _Link_type __y
= _M_end();
1713 __x
= _M_impl
._M_key_compare(__k
, _S_key(__x
)) ?
1714 _S_left(__x
) : _S_right(__x
);
1716 return _Res(__x
, __y
);
1719 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1720 typename _Compare
, typename _Alloc
>
1721 #if __cplusplus >= 201103L
1722 template<typename _Arg
>
1724 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1725 _Compare
, _Alloc
>::iterator
, bool>
1726 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1727 #if __cplusplus >= 201103L
1728 _M_insert_unique(_Arg
&& __v
)
1730 _M_insert_unique(const _Val
& __v
)
1733 typedef pair
<iterator
, bool> _Res
;
1734 pair
<_Base_ptr
, _Base_ptr
> __res
1735 = _M_get_insert_unique_pos(_KeyOfValue()(__v
));
1739 _Alloc_node
__an(*this);
1740 return _Res(_M_insert_(__res
.first
, __res
.second
,
1741 _GLIBCXX_FORWARD(_Arg
, __v
), __an
),
1745 return _Res(iterator(static_cast<_Link_type
>(__res
.first
)), false);
1748 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1749 typename _Compare
, typename _Alloc
>
1750 #if __cplusplus >= 201103L
1751 template<typename _Arg
>
1753 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1754 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1755 #if __cplusplus >= 201103L
1756 _M_insert_equal(_Arg
&& __v
)
1758 _M_insert_equal(const _Val
& __v
)
1761 pair
<_Base_ptr
, _Base_ptr
> __res
1762 = _M_get_insert_equal_pos(_KeyOfValue()(__v
));
1763 _Alloc_node
__an(*this);
1764 return _M_insert_(__res
.first
, __res
.second
,
1765 _GLIBCXX_FORWARD(_Arg
, __v
), __an
);
1768 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1769 typename _Compare
, typename _Alloc
>
1770 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1771 _Compare
, _Alloc
>::_Base_ptr
,
1772 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1773 _Compare
, _Alloc
>::_Base_ptr
>
1774 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1775 _M_get_insert_hint_unique_pos(const_iterator __position
,
1776 const key_type
& __k
)
1778 iterator __pos
= __position
._M_const_cast();
1779 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
1782 if (__pos
._M_node
== _M_end())
1785 && _M_impl
._M_key_compare(_S_key(_M_rightmost()), __k
))
1786 return _Res(0, _M_rightmost());
1788 return _M_get_insert_unique_pos(__k
);
1790 else if (_M_impl
._M_key_compare(__k
, _S_key(__pos
._M_node
)))
1792 // First, try before...
1793 iterator __before
= __pos
;
1794 if (__pos
._M_node
== _M_leftmost()) // begin()
1795 return _Res(_M_leftmost(), _M_leftmost());
1796 else if (_M_impl
._M_key_compare(_S_key((--__before
)._M_node
), __k
))
1798 if (_S_right(__before
._M_node
) == 0)
1799 return _Res(0, __before
._M_node
);
1801 return _Res(__pos
._M_node
, __pos
._M_node
);
1804 return _M_get_insert_unique_pos(__k
);
1806 else if (_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
1808 // ... then try after.
1809 iterator __after
= __pos
;
1810 if (__pos
._M_node
== _M_rightmost())
1811 return _Res(0, _M_rightmost());
1812 else if (_M_impl
._M_key_compare(__k
, _S_key((++__after
)._M_node
)))
1814 if (_S_right(__pos
._M_node
) == 0)
1815 return _Res(0, __pos
._M_node
);
1817 return _Res(__after
._M_node
, __after
._M_node
);
1820 return _M_get_insert_unique_pos(__k
);
1824 return _Res(__pos
._M_node
, 0);
1827 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1828 typename _Compare
, typename _Alloc
>
1829 #if __cplusplus >= 201103L
1830 template<typename _Arg
, typename _NodeGen
>
1832 template<typename _NodeGen
>
1834 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1835 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1836 _M_insert_unique_(const_iterator __position
,
1837 #if __cplusplus >= 201103L
1842 _NodeGen
& __node_gen
)
1844 pair
<_Base_ptr
, _Base_ptr
> __res
1845 = _M_get_insert_hint_unique_pos(__position
, _KeyOfValue()(__v
));
1848 return _M_insert_(__res
.first
, __res
.second
,
1849 _GLIBCXX_FORWARD(_Arg
, __v
),
1851 return iterator(static_cast<_Link_type
>(__res
.first
));
1854 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1855 typename _Compare
, typename _Alloc
>
1856 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1857 _Compare
, _Alloc
>::_Base_ptr
,
1858 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1859 _Compare
, _Alloc
>::_Base_ptr
>
1860 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1861 _M_get_insert_hint_equal_pos(const_iterator __position
, const key_type
& __k
)
1863 iterator __pos
= __position
._M_const_cast();
1864 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
1867 if (__pos
._M_node
== _M_end())
1870 && !_M_impl
._M_key_compare(__k
, _S_key(_M_rightmost())))
1871 return _Res(0, _M_rightmost());
1873 return _M_get_insert_equal_pos(__k
);
1875 else if (!_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
1877 // First, try before...
1878 iterator __before
= __pos
;
1879 if (__pos
._M_node
== _M_leftmost()) // begin()
1880 return _Res(_M_leftmost(), _M_leftmost());
1881 else if (!_M_impl
._M_key_compare(__k
, _S_key((--__before
)._M_node
)))
1883 if (_S_right(__before
._M_node
) == 0)
1884 return _Res(0, __before
._M_node
);
1886 return _Res(__pos
._M_node
, __pos
._M_node
);
1889 return _M_get_insert_equal_pos(__k
);
1893 // ... then try after.
1894 iterator __after
= __pos
;
1895 if (__pos
._M_node
== _M_rightmost())
1896 return _Res(0, _M_rightmost());
1897 else if (!_M_impl
._M_key_compare(_S_key((++__after
)._M_node
), __k
))
1899 if (_S_right(__pos
._M_node
) == 0)
1900 return _Res(0, __pos
._M_node
);
1902 return _Res(__after
._M_node
, __after
._M_node
);
1909 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1910 typename _Compare
, typename _Alloc
>
1911 #if __cplusplus >= 201103L
1912 template<typename _Arg
, typename _NodeGen
>
1914 template<typename _NodeGen
>
1916 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1917 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1918 _M_insert_equal_(const_iterator __position
,
1919 #if __cplusplus >= 201103L
1924 _NodeGen
& __node_gen
)
1926 pair
<_Base_ptr
, _Base_ptr
> __res
1927 = _M_get_insert_hint_equal_pos(__position
, _KeyOfValue()(__v
));
1930 return _M_insert_(__res
.first
, __res
.second
,
1931 _GLIBCXX_FORWARD(_Arg
, __v
),
1934 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg
, __v
));
1937 #if __cplusplus >= 201103L
1938 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1939 typename _Compare
, typename _Alloc
>
1940 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1941 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1942 _M_insert_node(_Base_ptr __x
, _Base_ptr __p
, _Link_type __z
)
1944 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
1945 || _M_impl
._M_key_compare(_S_key(__z
),
1948 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1949 this->_M_impl
._M_header
);
1950 ++_M_impl
._M_node_count
;
1951 return iterator(__z
);
1954 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1955 typename _Compare
, typename _Alloc
>
1956 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1957 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1958 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
)
1960 bool __insert_left
= (__p
== _M_end()
1961 || !_M_impl
._M_key_compare(_S_key(__p
),
1964 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1965 this->_M_impl
._M_header
);
1966 ++_M_impl
._M_node_count
;
1967 return iterator(__z
);
1970 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1971 typename _Compare
, typename _Alloc
>
1972 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1973 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1974 _M_insert_equal_lower_node(_Link_type __z
)
1976 _Link_type __x
= _M_begin();
1977 _Link_type __y
= _M_end();
1981 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _S_key(__z
)) ?
1982 _S_left(__x
) : _S_right(__x
);
1984 return _M_insert_lower_node(__y
, __z
);
1987 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1988 typename _Compare
, typename _Alloc
>
1989 template<typename
... _Args
>
1990 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1991 _Compare
, _Alloc
>::iterator
, bool>
1992 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1993 _M_emplace_unique(_Args
&&... __args
)
1995 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
1999 typedef pair
<iterator
, bool> _Res
;
2000 auto __res
= _M_get_insert_unique_pos(_S_key(__z
));
2002 return _Res(_M_insert_node(__res
.first
, __res
.second
, __z
), true);
2005 return _Res(iterator(static_cast<_Link_type
>(__res
.first
)), false);
2010 __throw_exception_again
;
2014 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2015 typename _Compare
, typename _Alloc
>
2016 template<typename
... _Args
>
2017 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2018 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2019 _M_emplace_equal(_Args
&&... __args
)
2021 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2025 auto __res
= _M_get_insert_equal_pos(_S_key(__z
));
2026 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2031 __throw_exception_again
;
2035 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2036 typename _Compare
, typename _Alloc
>
2037 template<typename
... _Args
>
2038 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2039 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2040 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
)
2042 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2046 auto __res
= _M_get_insert_hint_unique_pos(__pos
, _S_key(__z
));
2049 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2052 return iterator(static_cast<_Link_type
>(__res
.first
));
2057 __throw_exception_again
;
2061 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2062 typename _Compare
, typename _Alloc
>
2063 template<typename
... _Args
>
2064 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2065 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2066 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
)
2068 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2072 auto __res
= _M_get_insert_hint_equal_pos(__pos
, _S_key(__z
));
2075 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2077 return _M_insert_equal_lower_node(__z
);
2082 __throw_exception_again
;
2087 template<typename _Key
, typename _Val
, typename _KoV
,
2088 typename _Cmp
, typename _Alloc
>
2091 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
2092 _M_insert_unique(_II __first
, _II __last
)
2094 _Alloc_node
__an(*this);
2095 for (; __first
!= __last
; ++__first
)
2096 _M_insert_unique_(end(), *__first
, __an
);
2099 template<typename _Key
, typename _Val
, typename _KoV
,
2100 typename _Cmp
, typename _Alloc
>
2103 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
2104 _M_insert_equal(_II __first
, _II __last
)
2106 _Alloc_node
__an(*this);
2107 for (; __first
!= __last
; ++__first
)
2108 _M_insert_equal_(end(), *__first
, __an
);
2111 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2112 typename _Compare
, typename _Alloc
>
2114 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2115 _M_erase_aux(const_iterator __position
)
2118 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
2119 (const_cast<_Base_ptr
>(__position
._M_node
),
2120 this->_M_impl
._M_header
));
2122 --_M_impl
._M_node_count
;
2125 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2126 typename _Compare
, typename _Alloc
>
2128 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2129 _M_erase_aux(const_iterator __first
, const_iterator __last
)
2131 if (__first
== begin() && __last
== end())
2134 while (__first
!= __last
)
2138 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2139 typename _Compare
, typename _Alloc
>
2140 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2141 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2142 erase(const _Key
& __x
)
2144 pair
<iterator
, iterator
> __p
= equal_range(__x
);
2145 const size_type __old_size
= size();
2146 erase(__p
.first
, __p
.second
);
2147 return __old_size
- size();
2150 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2151 typename _Compare
, typename _Alloc
>
2153 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2154 erase(const _Key
* __first
, const _Key
* __last
)
2156 while (__first
!= __last
)
2160 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2161 typename _Compare
, typename _Alloc
>
2162 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2163 _Compare
, _Alloc
>::iterator
2164 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2165 find(const _Key
& __k
)
2167 iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2168 return (__j
== end()
2169 || _M_impl
._M_key_compare(__k
,
2170 _S_key(__j
._M_node
))) ? end() : __j
;
2173 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2174 typename _Compare
, typename _Alloc
>
2175 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2176 _Compare
, _Alloc
>::const_iterator
2177 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2178 find(const _Key
& __k
) const
2180 const_iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2181 return (__j
== end()
2182 || _M_impl
._M_key_compare(__k
,
2183 _S_key(__j
._M_node
))) ? end() : __j
;
2186 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2187 typename _Compare
, typename _Alloc
>
2188 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2189 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2190 count(const _Key
& __k
) const
2192 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
2193 const size_type __n
= std::distance(__p
.first
, __p
.second
);
2197 _GLIBCXX_PURE
unsigned int
2198 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
2199 const _Rb_tree_node_base
* __root
) throw ();
2201 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2202 typename _Compare
, typename _Alloc
>
2204 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
2206 if (_M_impl
._M_node_count
== 0 || begin() == end())
2207 return _M_impl
._M_node_count
== 0 && begin() == end()
2208 && this->_M_impl
._M_header
._M_left
== _M_end()
2209 && this->_M_impl
._M_header
._M_right
== _M_end();
2211 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
2212 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
2214 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
2215 _Const_Link_type __L
= _S_left(__x
);
2216 _Const_Link_type __R
= _S_right(__x
);
2218 if (__x
->_M_color
== _S_red
)
2219 if ((__L
&& __L
->_M_color
== _S_red
)
2220 || (__R
&& __R
->_M_color
== _S_red
))
2223 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
2225 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
2228 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
2232 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2234 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2239 _GLIBCXX_END_NAMESPACE_VERSION