61 #pragma GCC system_header 68 #if __cplusplus >= 201103L 71 #if __cplusplus > 201402L 75 namespace std _GLIBCXX_VISIBILITY(default)
77 _GLIBCXX_BEGIN_NAMESPACE_VERSION
79 #if __cplusplus > 201103L 80 # define __cpp_lib_generic_associative_lookup 201304 99 enum _Rb_tree_color { _S_red =
false, _S_black =
true };
101 struct _Rb_tree_node_base
103 typedef _Rb_tree_node_base* _Base_ptr;
104 typedef const _Rb_tree_node_base* _Const_Base_ptr;
106 _Rb_tree_color _M_color;
112 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
114 while (__x->_M_left != 0) __x = __x->_M_left;
118 static _Const_Base_ptr
119 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
121 while (__x->_M_left != 0) __x = __x->_M_left;
126 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
128 while (__x->_M_right != 0) __x = __x->_M_right;
132 static _Const_Base_ptr
133 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
135 while (__x->_M_right != 0) __x = __x->_M_right;
141 template<
typename _Key_compare>
142 struct _Rb_tree_key_compare
144 _Key_compare _M_key_compare;
146 _Rb_tree_key_compare()
147 _GLIBCXX_NOEXCEPT_IF(
148 is_nothrow_default_constructible<_Key_compare>::value)
152 _Rb_tree_key_compare(
const _Key_compare& __comp)
153 : _M_key_compare(__comp)
156 #if __cplusplus >= 201103L 158 _Rb_tree_key_compare(
const _Rb_tree_key_compare&) =
default;
160 _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
161 noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
162 : _M_key_compare(__x._M_key_compare)
168 struct _Rb_tree_header
170 _Rb_tree_node_base _M_header;
171 size_t _M_node_count;
173 _Rb_tree_header() _GLIBCXX_NOEXCEPT
175 _M_header._M_color = _S_red;
179 #if __cplusplus >= 201103L 180 _Rb_tree_header(_Rb_tree_header&& __x) noexcept
182 if (__x._M_header._M_parent !=
nullptr)
186 _M_header._M_color = _S_red;
193 _M_move_data(_Rb_tree_header& __from)
195 _M_header._M_parent = __from._M_header._M_parent;
196 _M_header._M_left = __from._M_header._M_left;
197 _M_header._M_right = __from._M_header._M_right;
198 _M_header._M_parent->_M_parent = &_M_header;
199 _M_node_count = __from._M_node_count;
207 _M_header._M_parent = 0;
208 _M_header._M_left = &_M_header;
209 _M_header._M_right = &_M_header;
214 template<
typename _Val>
215 struct _Rb_tree_node :
public _Rb_tree_node_base
217 typedef _Rb_tree_node<_Val>* _Link_type;
219 #if __cplusplus < 201103L 230 __gnu_cxx::__aligned_membuf<_Val> _M_storage;
234 {
return _M_storage._M_ptr(); }
238 {
return _M_storage._M_ptr(); }
242 _GLIBCXX_PURE _Rb_tree_node_base*
243 _Rb_tree_increment(_Rb_tree_node_base* __x)
throw ();
245 _GLIBCXX_PURE
const _Rb_tree_node_base*
246 _Rb_tree_increment(
const _Rb_tree_node_base* __x)
throw ();
248 _GLIBCXX_PURE _Rb_tree_node_base*
249 _Rb_tree_decrement(_Rb_tree_node_base* __x)
throw ();
251 _GLIBCXX_PURE
const _Rb_tree_node_base*
252 _Rb_tree_decrement(
const _Rb_tree_node_base* __x)
throw ();
254 template<
typename _Tp>
255 struct _Rb_tree_iterator
257 typedef _Tp value_type;
258 typedef _Tp& reference;
259 typedef _Tp* pointer;
261 typedef bidirectional_iterator_tag iterator_category;
262 typedef ptrdiff_t difference_type;
264 typedef _Rb_tree_iterator<_Tp> _Self;
265 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
266 typedef _Rb_tree_node<_Tp>* _Link_type;
268 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
272 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
277 {
return *
static_cast<_Link_type
>(_M_node)->_M_valptr(); }
280 operator->() const _GLIBCXX_NOEXCEPT
281 {
return static_cast<_Link_type
> (_M_node)->_M_valptr(); }
284 operator++() _GLIBCXX_NOEXCEPT
286 _M_node = _Rb_tree_increment(_M_node);
291 operator++(
int) _GLIBCXX_NOEXCEPT
294 _M_node = _Rb_tree_increment(_M_node);
299 operator--() _GLIBCXX_NOEXCEPT
301 _M_node = _Rb_tree_decrement(_M_node);
306 operator--(
int) _GLIBCXX_NOEXCEPT
309 _M_node = _Rb_tree_decrement(_M_node);
314 operator==(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
315 {
return _M_node == __x._M_node; }
318 operator!=(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
319 {
return _M_node != __x._M_node; }
324 template<
typename _Tp>
325 struct _Rb_tree_const_iterator
327 typedef _Tp value_type;
328 typedef const _Tp& reference;
329 typedef const _Tp* pointer;
331 typedef _Rb_tree_iterator<_Tp> iterator;
333 typedef bidirectional_iterator_tag iterator_category;
334 typedef ptrdiff_t difference_type;
336 typedef _Rb_tree_const_iterator<_Tp> _Self;
337 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
338 typedef const _Rb_tree_node<_Tp>* _Link_type;
340 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
344 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
347 _Rb_tree_const_iterator(
const iterator& __it) _GLIBCXX_NOEXCEPT
348 : _M_node(__it._M_node) { }
351 _M_const_cast() const _GLIBCXX_NOEXCEPT
352 {
return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
356 {
return *
static_cast<_Link_type
>(_M_node)->_M_valptr(); }
359 operator->() const _GLIBCXX_NOEXCEPT
360 {
return static_cast<_Link_type
>(_M_node)->_M_valptr(); }
363 operator++() _GLIBCXX_NOEXCEPT
365 _M_node = _Rb_tree_increment(_M_node);
370 operator++(
int) _GLIBCXX_NOEXCEPT
373 _M_node = _Rb_tree_increment(_M_node);
378 operator--() _GLIBCXX_NOEXCEPT
380 _M_node = _Rb_tree_decrement(_M_node);
385 operator--(
int) _GLIBCXX_NOEXCEPT
388 _M_node = _Rb_tree_decrement(_M_node);
393 operator==(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
394 {
return _M_node == __x._M_node; }
397 operator!=(
const _Self& __x)
const _GLIBCXX_NOEXCEPT
398 {
return _M_node != __x._M_node; }
403 template<
typename _Val>
405 operator==(
const _Rb_tree_iterator<_Val>& __x,
406 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
407 {
return __x._M_node == __y._M_node; }
409 template<
typename _Val>
411 operator!=(
const _Rb_tree_iterator<_Val>& __x,
412 const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
413 {
return __x._M_node != __y._M_node; }
416 _Rb_tree_insert_and_rebalance(
const bool __insert_left,
417 _Rb_tree_node_base* __x,
418 _Rb_tree_node_base* __p,
419 _Rb_tree_node_base& __header)
throw ();
422 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base*
const __z,
423 _Rb_tree_node_base& __header)
throw ();
425 #if __cplusplus > 201103L 426 template<
typename _Cmp,
typename _SfinaeType,
typename = __
void_t<>>
427 struct __has_is_transparent
430 template<
typename _Cmp,
typename _SfinaeType>
431 struct __has_is_transparent<_Cmp, _SfinaeType,
432 __void_t<typename _Cmp::is_transparent>>
433 {
typedef void type; };
436 #if __cplusplus > 201402L 437 template<
typename _Tree1,
typename _Cmp2>
438 struct _Rb_tree_merge_helper { };
441 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
442 typename _Compare,
typename _Alloc = allocator<_Val> >
446 rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
451 typedef _Rb_tree_node_base* _Base_ptr;
452 typedef const _Rb_tree_node_base* _Const_Base_ptr;
453 typedef _Rb_tree_node<_Val>* _Link_type;
454 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
459 struct _Reuse_or_alloc_node
461 _Reuse_or_alloc_node(_Rb_tree& __t)
462 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
466 _M_root->_M_parent = 0;
468 if (_M_nodes->_M_left)
469 _M_nodes = _M_nodes->_M_left;
475 #if __cplusplus >= 201103L 476 _Reuse_or_alloc_node(
const _Reuse_or_alloc_node&) =
delete;
479 ~_Reuse_or_alloc_node()
480 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
482 template<
typename _Arg>
484 #if __cplusplus < 201103L 485 operator()(
const _Arg& __arg)
487 operator()(_Arg&& __arg)
490 _Link_type __node =
static_cast<_Link_type
>(_M_extract());
493 _M_t._M_destroy_node(__node);
494 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
498 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
508 _Base_ptr __node = _M_nodes;
509 _M_nodes = _M_nodes->_M_parent;
512 if (_M_nodes->_M_right == __node)
514 _M_nodes->_M_right = 0;
516 if (_M_nodes->_M_left)
518 _M_nodes = _M_nodes->_M_left;
520 while (_M_nodes->_M_right)
521 _M_nodes = _M_nodes->_M_right;
523 if (_M_nodes->_M_left)
524 _M_nodes = _M_nodes->_M_left;
528 _M_nodes->_M_left = 0;
545 _Alloc_node(_Rb_tree& __t)
548 template<
typename _Arg>
550 #if __cplusplus < 201103L 551 operator()(
const _Arg& __arg)
const 553 operator()(_Arg&& __arg)
const 555 {
return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
562 typedef _Key key_type;
563 typedef _Val value_type;
564 typedef value_type* pointer;
565 typedef const value_type* const_pointer;
566 typedef value_type& reference;
567 typedef const value_type& const_reference;
568 typedef size_t size_type;
569 typedef ptrdiff_t difference_type;
570 typedef _Alloc allocator_type;
573 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
574 {
return *
static_cast<_Node_allocator*
>(&this->_M_impl); }
576 const _Node_allocator&
577 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
578 {
return *
static_cast<const _Node_allocator*
>(&this->_M_impl); }
581 get_allocator() const _GLIBCXX_NOEXCEPT
582 {
return allocator_type(_M_get_Node_allocator()); }
587 {
return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
590 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
591 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
593 #if __cplusplus < 201103L 595 _M_construct_node(_Link_type __node,
const value_type& __x)
598 { get_allocator().construct(__node->_M_valptr(), __x); }
602 __throw_exception_again;
607 _M_create_node(
const value_type& __x)
609 _Link_type __tmp = _M_get_node();
610 _M_construct_node(__tmp, __x);
615 _M_destroy_node(_Link_type __p)
616 { get_allocator().destroy(__p->_M_valptr()); }
618 template<
typename... _Args>
620 _M_construct_node(_Link_type __node, _Args&&... __args)
624 ::new(__node) _Rb_tree_node<_Val>;
625 _Alloc_traits::construct(_M_get_Node_allocator(),
627 std::forward<_Args>(__args)...);
631 __node->~_Rb_tree_node<_Val>();
633 __throw_exception_again;
637 template<
typename... _Args>
639 _M_create_node(_Args&&... __args)
641 _Link_type __tmp = _M_get_node();
642 _M_construct_node(__tmp, std::forward<_Args>(__args)...);
647 _M_destroy_node(_Link_type __p) noexcept
649 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
650 __p->~_Rb_tree_node<_Val>();
655 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
657 _M_destroy_node(__p);
661 template<
typename _NodeGen>
663 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
665 _Link_type __tmp = __node_gen(*__x->_M_valptr());
666 __tmp->_M_color = __x->_M_color;
674 template<
typename _Key_compare,
675 bool = __is_pod(_Key_compare)>
677 :
public _Node_allocator
678 ,
public _Rb_tree_key_compare<_Key_compare>
679 ,
public _Rb_tree_header
681 typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
683 #if __cplusplus < 201103L 687 _Rb_tree_impl() =
default;
688 _Rb_tree_impl(_Rb_tree_impl&&) =
default;
691 _Rb_tree_impl(
const _Rb_tree_impl& __x)
692 : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
693 , _Base_key_compare(__x._M_key_compare)
696 #if __cplusplus < 201103L 697 _Rb_tree_impl(
const _Key_compare& __comp,
const _Node_allocator& __a)
698 : _Node_allocator(__a), _Base_key_compare(__comp)
701 _Rb_tree_impl(
const _Key_compare& __comp, _Node_allocator&& __a)
702 : _Node_allocator(
std::move(__a)), _Base_key_compare(__comp)
707 _Rb_tree_impl<_Compare> _M_impl;
711 _M_root() _GLIBCXX_NOEXCEPT
712 {
return this->_M_impl._M_header._M_parent; }
715 _M_root() const _GLIBCXX_NOEXCEPT
716 {
return this->_M_impl._M_header._M_parent; }
719 _M_leftmost() _GLIBCXX_NOEXCEPT
720 {
return this->_M_impl._M_header._M_left; }
723 _M_leftmost() const _GLIBCXX_NOEXCEPT
724 {
return this->_M_impl._M_header._M_left; }
727 _M_rightmost() _GLIBCXX_NOEXCEPT
728 {
return this->_M_impl._M_header._M_right; }
731 _M_rightmost() const _GLIBCXX_NOEXCEPT
732 {
return this->_M_impl._M_header._M_right; }
735 _M_begin() _GLIBCXX_NOEXCEPT
736 {
return static_cast<_Link_type
>(this->_M_impl._M_header._M_parent); }
739 _M_begin() const _GLIBCXX_NOEXCEPT
741 return static_cast<_Const_Link_type
> 742 (this->_M_impl._M_header._M_parent);
746 _M_end() _GLIBCXX_NOEXCEPT
747 {
return &this->_M_impl._M_header; }
750 _M_end() const _GLIBCXX_NOEXCEPT
751 {
return &this->_M_impl._M_header; }
753 static const_reference
754 _S_value(_Const_Link_type __x)
755 {
return *__x->_M_valptr(); }
758 _S_key(_Const_Link_type __x)
759 {
return _KeyOfValue()(_S_value(__x)); }
762 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
763 {
return static_cast<_Link_type
>(__x->_M_left); }
765 static _Const_Link_type
766 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
767 {
return static_cast<_Const_Link_type
>(__x->_M_left); }
770 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
771 {
return static_cast<_Link_type
>(__x->_M_right); }
773 static _Const_Link_type
774 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
775 {
return static_cast<_Const_Link_type
>(__x->_M_right); }
777 static const_reference
778 _S_value(_Const_Base_ptr __x)
779 {
return *
static_cast<_Const_Link_type
>(__x)->_M_valptr(); }
782 _S_key(_Const_Base_ptr __x)
783 {
return _KeyOfValue()(_S_value(__x)); }
786 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
787 {
return _Rb_tree_node_base::_S_minimum(__x); }
789 static _Const_Base_ptr
790 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
791 {
return _Rb_tree_node_base::_S_minimum(__x); }
794 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
795 {
return _Rb_tree_node_base::_S_maximum(__x); }
797 static _Const_Base_ptr
798 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
799 {
return _Rb_tree_node_base::_S_maximum(__x); }
802 typedef _Rb_tree_iterator<value_type> iterator;
803 typedef _Rb_tree_const_iterator<value_type> const_iterator;
808 #if __cplusplus > 201402L 809 using node_type = _Node_handle<_Key, _Val, _Node_allocator>;
810 using insert_return_type = _Node_insert_return<iterator, node_type>;
813 pair<_Base_ptr, _Base_ptr>
814 _M_get_insert_unique_pos(
const key_type& __k);
816 pair<_Base_ptr, _Base_ptr>
817 _M_get_insert_equal_pos(
const key_type& __k);
819 pair<_Base_ptr, _Base_ptr>
820 _M_get_insert_hint_unique_pos(const_iterator __pos,
821 const key_type& __k);
823 pair<_Base_ptr, _Base_ptr>
824 _M_get_insert_hint_equal_pos(const_iterator __pos,
825 const key_type& __k);
828 #if __cplusplus >= 201103L 829 template<
typename _Arg,
typename _NodeGen>
831 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
834 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
836 template<
typename _Arg>
838 _M_insert_lower(_Base_ptr __y, _Arg&& __v);
840 template<
typename _Arg>
842 _M_insert_equal_lower(_Arg&& __x);
845 _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
848 _M_insert_equal_lower_node(_Link_type __z);
850 template<
typename _NodeGen>
852 _M_insert_(_Base_ptr __x, _Base_ptr __y,
853 const value_type& __v, _NodeGen&);
858 _M_insert_lower(_Base_ptr __y,
const value_type& __v);
861 _M_insert_equal_lower(
const value_type& __x);
864 template<
typename _NodeGen>
866 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
868 template<
typename _NodeGen>
870 _M_copy(
const _Rb_tree& __x, _NodeGen& __gen)
872 _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
873 _M_leftmost() = _S_minimum(__root);
874 _M_rightmost() = _S_maximum(__root);
875 _M_impl._M_node_count = __x._M_impl._M_node_count;
880 _M_copy(
const _Rb_tree& __x)
882 _Alloc_node __an(*
this);
883 return _M_copy(__x, __an);
887 _M_erase(_Link_type __x);
890 _M_lower_bound(_Link_type __x, _Base_ptr __y,
894 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
895 const _Key& __k)
const;
898 _M_upper_bound(_Link_type __x, _Base_ptr __y,
902 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
903 const _Key& __k)
const;
907 #if __cplusplus < 201103L 910 _Rb_tree() =
default;
913 _Rb_tree(
const _Compare& __comp,
914 const allocator_type& __a = allocator_type())
915 : _M_impl(__comp, _Node_allocator(__a)) { }
917 _Rb_tree(
const _Rb_tree& __x)
918 : _M_impl(__x._M_impl)
920 if (__x._M_root() != 0)
921 _M_root() = _M_copy(__x);
924 #if __cplusplus >= 201103L 925 _Rb_tree(
const allocator_type& __a)
926 : _M_impl(_Compare(), _Node_allocator(__a))
929 _Rb_tree(
const _Rb_tree& __x,
const allocator_type& __a)
930 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
932 if (__x._M_root() !=
nullptr)
933 _M_root() = _M_copy(__x);
936 _Rb_tree(_Rb_tree&&) =
default;
938 _Rb_tree(_Rb_tree&& __x,
const allocator_type& __a)
939 : _Rb_tree(
std::move(__x), _Node_allocator(__a))
942 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
945 ~_Rb_tree() _GLIBCXX_NOEXCEPT
946 { _M_erase(_M_begin()); }
949 operator=(
const _Rb_tree& __x);
954 {
return _M_impl._M_key_compare; }
957 begin() _GLIBCXX_NOEXCEPT
958 {
return iterator(this->_M_impl._M_header._M_left); }
961 begin() const _GLIBCXX_NOEXCEPT
962 {
return const_iterator(this->_M_impl._M_header._M_left); }
965 end() _GLIBCXX_NOEXCEPT
966 {
return iterator(&this->_M_impl._M_header); }
969 end() const _GLIBCXX_NOEXCEPT
970 {
return const_iterator(&this->_M_impl._M_header); }
973 rbegin() _GLIBCXX_NOEXCEPT
974 {
return reverse_iterator(
end()); }
976 const_reverse_iterator
977 rbegin() const _GLIBCXX_NOEXCEPT
978 {
return const_reverse_iterator(
end()); }
981 rend() _GLIBCXX_NOEXCEPT
982 {
return reverse_iterator(
begin()); }
984 const_reverse_iterator
985 rend() const _GLIBCXX_NOEXCEPT
986 {
return const_reverse_iterator(
begin()); }
989 empty() const _GLIBCXX_NOEXCEPT
990 {
return _M_impl._M_node_count == 0; }
993 size() const _GLIBCXX_NOEXCEPT
994 {
return _M_impl._M_node_count; }
997 max_size() const _GLIBCXX_NOEXCEPT
998 {
return _Alloc_traits::max_size(_M_get_Node_allocator()); }
1002 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
1005 #if __cplusplus >= 201103L 1006 template<
typename _Arg>
1007 pair<iterator, bool>
1008 _M_insert_unique(_Arg&& __x);
1010 template<
typename _Arg>
1012 _M_insert_equal(_Arg&& __x);
1014 template<
typename _Arg,
typename _NodeGen>
1016 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1018 template<
typename _Arg>
1020 _M_insert_unique_(const_iterator __pos, _Arg&& __x)
1022 _Alloc_node __an(*
this);
1023 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
1026 template<
typename _Arg,
typename _NodeGen>
1028 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1030 template<
typename _Arg>
1032 _M_insert_equal_(const_iterator __pos, _Arg&& __x)
1034 _Alloc_node __an(*
this);
1035 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
1038 template<
typename... _Args>
1039 pair<iterator, bool>
1040 _M_emplace_unique(_Args&&... __args);
1042 template<
typename... _Args>
1044 _M_emplace_equal(_Args&&... __args);
1046 template<
typename... _Args>
1048 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
1050 template<
typename... _Args>
1052 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
1054 pair<iterator, bool>
1055 _M_insert_unique(
const value_type& __x);
1058 _M_insert_equal(
const value_type& __x);
1060 template<
typename _NodeGen>
1062 _M_insert_unique_(const_iterator __pos,
const value_type& __x,
1066 _M_insert_unique_(const_iterator __pos,
const value_type& __x)
1068 _Alloc_node __an(*
this);
1069 return _M_insert_unique_(__pos, __x, __an);
1072 template<
typename _NodeGen>
1074 _M_insert_equal_(const_iterator __pos,
const value_type& __x,
1077 _M_insert_equal_(const_iterator __pos,
const value_type& __x)
1079 _Alloc_node __an(*
this);
1080 return _M_insert_equal_(__pos, __x, __an);
1084 template<
typename _InputIterator>
1086 _M_insert_unique(_InputIterator __first, _InputIterator __last);
1088 template<
typename _InputIterator>
1090 _M_insert_equal(_InputIterator __first, _InputIterator __last);
1094 _M_erase_aux(const_iterator __position);
1097 _M_erase_aux(const_iterator __first, const_iterator __last);
1100 #if __cplusplus >= 201103L 1103 _GLIBCXX_ABI_TAG_CXX11
1105 erase(const_iterator __position)
1107 __glibcxx_assert(__position !=
end());
1108 const_iterator __result = __position;
1110 _M_erase_aux(__position);
1111 return __result._M_const_cast();
1115 _GLIBCXX_ABI_TAG_CXX11
1117 erase(iterator __position)
1119 __glibcxx_assert(__position !=
end());
1120 iterator __result = __position;
1122 _M_erase_aux(__position);
1127 erase(iterator __position)
1129 __glibcxx_assert(__position !=
end());
1130 _M_erase_aux(__position);
1134 erase(const_iterator __position)
1136 __glibcxx_assert(__position !=
end());
1137 _M_erase_aux(__position);
1141 erase(
const key_type& __x);
1143 #if __cplusplus >= 201103L 1146 _GLIBCXX_ABI_TAG_CXX11
1148 erase(const_iterator __first, const_iterator __last)
1150 _M_erase_aux(__first, __last);
1151 return __last._M_const_cast();
1155 erase(iterator __first, iterator __last)
1156 { _M_erase_aux(__first, __last); }
1159 erase(const_iterator __first, const_iterator __last)
1160 { _M_erase_aux(__first, __last); }
1163 erase(
const key_type* __first,
const key_type* __last);
1166 clear() _GLIBCXX_NOEXCEPT
1168 _M_erase(_M_begin());
1174 find(
const key_type& __k);
1177 find(
const key_type& __k)
const;
1180 count(
const key_type& __k)
const;
1183 lower_bound(
const key_type& __k)
1184 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
1187 lower_bound(
const key_type& __k)
const 1188 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
1191 upper_bound(
const key_type& __k)
1192 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
1195 upper_bound(
const key_type& __k)
const 1196 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
1198 pair<iterator, iterator>
1199 equal_range(
const key_type& __k);
1201 pair<const_iterator, const_iterator>
1202 equal_range(
const key_type& __k)
const;
1204 #if __cplusplus > 201103L 1205 template<
typename _Kt,
1207 typename __has_is_transparent<_Compare, _Kt>::type>
1209 _M_find_tr(
const _Kt& __k)
1211 const _Rb_tree* __const_this =
this;
1212 return __const_this->_M_find_tr(__k)._M_const_cast();
1215 template<
typename _Kt,
1217 typename __has_is_transparent<_Compare, _Kt>::type>
1219 _M_find_tr(
const _Kt& __k)
const 1221 auto __j = _M_lower_bound_tr(__k);
1222 if (__j !=
end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1227 template<
typename _Kt,
1229 typename __has_is_transparent<_Compare, _Kt>::type>
1231 _M_count_tr(
const _Kt& __k)
const 1233 auto __p = _M_equal_range_tr(__k);
1237 template<
typename _Kt,
1239 typename __has_is_transparent<_Compare, _Kt>::type>
1241 _M_lower_bound_tr(
const _Kt& __k)
1243 const _Rb_tree* __const_this =
this;
1244 return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
1247 template<
typename _Kt,
1249 typename __has_is_transparent<_Compare, _Kt>::type>
1251 _M_lower_bound_tr(
const _Kt& __k)
const 1253 auto __x = _M_begin();
1254 auto __y = _M_end();
1256 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1262 __x = _S_right(__x);
1263 return const_iterator(__y);
1266 template<
typename _Kt,
1268 typename __has_is_transparent<_Compare, _Kt>::type>
1270 _M_upper_bound_tr(
const _Kt& __k)
1272 const _Rb_tree* __const_this =
this;
1273 return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
1276 template<
typename _Kt,
1278 typename __has_is_transparent<_Compare, _Kt>::type>
1280 _M_upper_bound_tr(
const _Kt& __k)
const 1282 auto __x = _M_begin();
1283 auto __y = _M_end();
1285 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1291 __x = _S_right(__x);
1292 return const_iterator(__y);
1295 template<
typename _Kt,
1297 typename __has_is_transparent<_Compare, _Kt>::type>
1298 pair<iterator, iterator>
1299 _M_equal_range_tr(
const _Kt& __k)
1301 const _Rb_tree* __const_this =
this;
1302 auto __ret = __const_this->_M_equal_range_tr(__k);
1303 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
1306 template<
typename _Kt,
1308 typename __has_is_transparent<_Compare, _Kt>::type>
1309 pair<const_iterator, const_iterator>
1310 _M_equal_range_tr(
const _Kt& __k)
const 1312 auto __low = _M_lower_bound_tr(__k);
1313 auto __high = __low;
1314 auto& __cmp = _M_impl._M_key_compare;
1315 while (__high !=
end() && !__cmp(__k, _S_key(__high._M_node)))
1317 return { __low, __high };
1323 __rb_verify()
const;
1325 #if __cplusplus >= 201103L 1327 operator=(_Rb_tree&&)
1328 noexcept(_Alloc_traits::_S_nothrow_move()
1329 && is_nothrow_move_assignable<_Compare>::value);
1331 template<typename _Iterator>
1333 _M_assign_unique(_Iterator, _Iterator);
1335 template<typename _Iterator>
1337 _M_assign_equal(_Iterator, _Iterator);
1343 { _M_impl._M_move_data(__x._M_impl); }
1360 #if __cplusplus > 201402L 1364 _M_reinsert_node_unique(node_type&& __nh)
1366 insert_return_type __ret;
1368 __ret.position =
end();
1371 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1373 auto __res = _M_get_insert_unique_pos(__nh._M_key());
1377 = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1378 __nh._M_ptr =
nullptr;
1379 __ret.inserted =
true;
1383 __ret.node = std::move(__nh);
1384 __ret.position = iterator(__res.first);
1385 __ret.inserted =
false;
1393 _M_reinsert_node_equal(node_type&& __nh)
1400 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1401 auto __res = _M_get_insert_equal_pos(__nh._M_key());
1403 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1405 __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1406 __nh._M_ptr =
nullptr;
1413 _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
1420 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1421 auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
1424 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1425 __nh._M_ptr =
nullptr;
1428 __ret = iterator(__res.first);
1435 _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
1442 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1443 auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
1445 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1447 __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1448 __nh._M_ptr =
nullptr;
1455 extract(const_iterator __pos)
1457 auto __ptr = _Rb_tree_rebalance_for_erase(
1458 __pos._M_const_cast()._M_node, _M_impl._M_header);
1459 --_M_impl._M_node_count;
1460 return {
static_cast<_Link_type
>(__ptr), _M_get_Node_allocator() };
1465 extract(
const key_type& __k)
1468 auto __pos = find(__k);
1470 __nh = extract(const_iterator(__pos));
1474 template<
typename _Compare2>
1475 using _Compatible_tree
1476 = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
1478 template<
typename,
typename>
1479 friend class _Rb_tree_merge_helper;
1482 template<
typename _Compare2>
1484 _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept
1486 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1487 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1490 auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos));
1493 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1494 auto __ptr = _Rb_tree_rebalance_for_erase(
1495 __pos._M_node, __src_impl._M_header);
1496 --__src_impl._M_node_count;
1497 _M_insert_node(__res.first, __res.second,
1498 static_cast<_Link_type>(__ptr));
1504 template<
typename _Compare2>
1506 _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept
1508 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1509 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1512 auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos));
1515 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1516 auto __ptr = _Rb_tree_rebalance_for_erase(
1517 __pos._M_node, __src_impl._M_header);
1518 --__src_impl._M_node_count;
1519 _M_insert_node(__res.first, __res.second,
1520 static_cast<_Link_type>(__ptr));
1527 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1528 typename _Compare,
typename _Alloc>
1530 operator==(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1531 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1533 return __x.size() == __y.size()
1534 &&
std::equal(__x.begin(), __x.end(), __y.begin());
1537 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1538 typename _Compare,
typename _Alloc>
1540 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1541 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1544 __y.begin(), __y.end());
1547 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1548 typename _Compare,
typename _Alloc>
1550 operator!=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1551 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1552 {
return !(__x == __y); }
1554 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1555 typename _Compare,
typename _Alloc>
1557 operator>(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1558 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1559 {
return __y < __x; }
1561 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1562 typename _Compare,
typename _Alloc>
1564 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1565 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1566 {
return !(__y < __x); }
1568 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1569 typename _Compare,
typename _Alloc>
1571 operator>=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1572 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1573 {
return !(__x < __y); }
1575 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1576 typename _Compare,
typename _Alloc>
1578 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1579 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1582 #if __cplusplus >= 201103L 1583 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1584 typename _Compare,
typename _Alloc>
1585 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1586 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1587 : _M_impl(__x._M_impl._M_key_compare,
std::move(__a))
1589 using __eq =
typename _Alloc_traits::is_always_equal;
1590 if (__x._M_root() !=
nullptr)
1591 _M_move_data(__x, __eq());
1594 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1595 typename _Compare,
typename _Alloc>
1597 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1600 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1604 _Alloc_node __an(*
this);
1606 [&__an](
const value_type& __cval)
1608 auto& __val =
const_cast<value_type&
>(__cval);
1611 _M_root() = _M_copy(__x, __lbd);
1615 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1616 typename _Compare,
typename _Alloc>
1618 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1619 _M_move_assign(_Rb_tree& __x, true_type)
1622 if (__x._M_root() !=
nullptr)
1624 std::__alloc_on_move(_M_get_Node_allocator(),
1625 __x._M_get_Node_allocator());
1628 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1629 typename _Compare,
typename _Alloc>
1631 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1634 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1635 return _M_move_assign(__x, true_type{});
1639 _Reuse_or_alloc_node __roan(*
this);
1641 if (__x._M_root() !=
nullptr)
1644 [&__roan](
const value_type& __cval)
1646 auto& __val =
const_cast<value_type&
>(__cval);
1649 _M_root() = _M_copy(__x, __lbd);
1654 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1655 typename _Compare,
typename _Alloc>
1656 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1657 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1658 operator=(_Rb_tree&& __x)
1659 noexcept(_Alloc_traits::_S_nothrow_move()
1660 && is_nothrow_move_assignable<_Compare>::value)
1662 _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
1663 _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());
1667 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1668 typename _Compare,
typename _Alloc>
1669 template<
typename _Iterator>
1671 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1672 _M_assign_unique(_Iterator __first, _Iterator __last)
1674 _Reuse_or_alloc_node __roan(*
this);
1676 for (; __first != __last; ++__first)
1677 _M_insert_unique_(
end(), *__first, __roan);
1680 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1681 typename _Compare,
typename _Alloc>
1682 template<
typename _Iterator>
1684 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1685 _M_assign_equal(_Iterator __first, _Iterator __last)
1687 _Reuse_or_alloc_node __roan(*
this);
1689 for (; __first != __last; ++__first)
1690 _M_insert_equal_(
end(), *__first, __roan);
1694 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1695 typename _Compare,
typename _Alloc>
1696 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1697 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1698 operator=(
const _Rb_tree& __x)
1703 #if __cplusplus >= 201103L 1704 if (_Alloc_traits::_S_propagate_on_copy_assign())
1706 auto& __this_alloc = this->_M_get_Node_allocator();
1707 auto& __that_alloc = __x._M_get_Node_allocator();
1708 if (!_Alloc_traits::_S_always_equal()
1709 && __this_alloc != __that_alloc)
1714 std::__alloc_on_copy(__this_alloc, __that_alloc);
1719 _Reuse_or_alloc_node __roan(*
this);
1721 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1722 if (__x._M_root() != 0)
1723 _M_root() = _M_copy(__x, __roan);
1729 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1730 typename _Compare,
typename _Alloc>
1731 #if __cplusplus >= 201103L 1732 template<
typename _Arg,
typename _NodeGen>
1734 template<
typename _NodeGen>
1736 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1737 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1738 _M_insert_(_Base_ptr __x, _Base_ptr __p,
1739 #
if __cplusplus >= 201103L
1744 _NodeGen& __node_gen)
1746 bool __insert_left = (__x != 0 || __p == _M_end()
1747 || _M_impl._M_key_compare(_KeyOfValue()(__v),
1750 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1752 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1753 this->_M_impl._M_header);
1754 ++_M_impl._M_node_count;
1755 return iterator(__z);
1758 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1759 typename _Compare,
typename _Alloc>
1760 #if __cplusplus >= 201103L 1761 template<
typename _Arg>
1763 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1764 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1765 #if __cplusplus >= 201103L 1766 _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1768 _M_insert_lower(_Base_ptr __p,
const _Val& __v)
1771 bool __insert_left = (__p == _M_end()
1772 || !_M_impl._M_key_compare(_S_key(__p),
1773 _KeyOfValue()(__v)));
1775 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1777 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1778 this->_M_impl._M_header);
1779 ++_M_impl._M_node_count;
1780 return iterator(__z);
1783 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1784 typename _Compare,
typename _Alloc>
1785 #if __cplusplus >= 201103L 1786 template<
typename _Arg>
1788 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1789 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1790 #if __cplusplus >= 201103L 1791 _M_insert_equal_lower(_Arg&& __v)
1793 _M_insert_equal_lower(
const _Val& __v)
1796 _Link_type __x = _M_begin();
1797 _Base_ptr __y = _M_end();
1801 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1802 _S_left(__x) : _S_right(__x);
1804 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1807 template<
typename _Key,
typename _Val,
typename _KoV,
1808 typename _Compare,
typename _Alloc>
1809 template<
typename _NodeGen>
1810 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1811 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1812 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
1815 _Link_type __top = _M_clone_node(__x, __node_gen);
1816 __top->_M_parent = __p;
1821 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1827 _Link_type __y = _M_clone_node(__x, __node_gen);
1829 __y->_M_parent = __p;
1831 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1839 __throw_exception_again;
1844 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1845 typename _Compare,
typename _Alloc>
1847 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1848 _M_erase(_Link_type __x)
1853 _M_erase(_S_right(__x));
1854 _Link_type __y = _S_left(__x);
1860 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1861 typename _Compare,
typename _Alloc>
1862 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1863 _Compare, _Alloc>::iterator
1864 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1865 _M_lower_bound(_Link_type __x, _Base_ptr __y,
1869 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1870 __y = __x, __x = _S_left(__x);
1872 __x = _S_right(__x);
1873 return iterator(__y);
1876 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1877 typename _Compare,
typename _Alloc>
1878 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1879 _Compare, _Alloc>::const_iterator
1880 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1881 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1882 const _Key& __k)
const 1885 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1886 __y = __x, __x = _S_left(__x);
1888 __x = _S_right(__x);
1889 return const_iterator(__y);
1892 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1893 typename _Compare,
typename _Alloc>
1894 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1895 _Compare, _Alloc>::iterator
1896 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1897 _M_upper_bound(_Link_type __x, _Base_ptr __y,
1901 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1902 __y = __x, __x = _S_left(__x);
1904 __x = _S_right(__x);
1905 return iterator(__y);
1908 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1909 typename _Compare,
typename _Alloc>
1910 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1911 _Compare, _Alloc>::const_iterator
1912 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1913 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1914 const _Key& __k)
const 1917 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1918 __y = __x, __x = _S_left(__x);
1920 __x = _S_right(__x);
1921 return const_iterator(__y);
1924 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1925 typename _Compare,
typename _Alloc>
1926 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1927 _Compare, _Alloc>::iterator,
1928 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1929 _Compare, _Alloc>::iterator>
1930 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1931 equal_range(
const _Key& __k)
1933 _Link_type __x = _M_begin();
1934 _Base_ptr __y = _M_end();
1937 if (_M_impl._M_key_compare(_S_key(__x), __k))
1938 __x = _S_right(__x);
1939 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1940 __y = __x, __x = _S_left(__x);
1943 _Link_type __xu(__x);
1944 _Base_ptr __yu(__y);
1945 __y = __x, __x = _S_left(__x);
1946 __xu = _S_right(__xu);
1947 return pair<iterator,
1948 iterator>(_M_lower_bound(__x, __y, __k),
1949 _M_upper_bound(__xu, __yu, __k));
1952 return pair<iterator, iterator>(iterator(__y),
1956 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1957 typename _Compare,
typename _Alloc>
1958 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1959 _Compare, _Alloc>::const_iterator,
1960 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1961 _Compare, _Alloc>::const_iterator>
1962 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1963 equal_range(
const _Key& __k)
const 1965 _Const_Link_type __x = _M_begin();
1966 _Const_Base_ptr __y = _M_end();
1969 if (_M_impl._M_key_compare(_S_key(__x), __k))
1970 __x = _S_right(__x);
1971 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1972 __y = __x, __x = _S_left(__x);
1975 _Const_Link_type __xu(__x);
1976 _Const_Base_ptr __yu(__y);
1977 __y = __x, __x = _S_left(__x);
1978 __xu = _S_right(__xu);
1979 return pair<const_iterator,
1980 const_iterator>(_M_lower_bound(__x, __y, __k),
1981 _M_upper_bound(__xu, __yu, __k));
1984 return pair<const_iterator, const_iterator>(const_iterator(__y),
1985 const_iterator(__y));
1988 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1989 typename _Compare,
typename _Alloc>
1991 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1993 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
1997 if (__t._M_root() != 0)
1998 _M_impl._M_move_data(__t._M_impl);
2000 else if (__t._M_root() == 0)
2001 __t._M_impl._M_move_data(_M_impl);
2004 std::swap(_M_root(),__t._M_root());
2005 std::swap(_M_leftmost(),__t._M_leftmost());
2006 std::swap(_M_rightmost(),__t._M_rightmost());
2008 _M_root()->_M_parent = _M_end();
2009 __t._M_root()->_M_parent = __t._M_end();
2010 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
2013 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
2015 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2016 __t._M_get_Node_allocator());
2019 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2020 typename _Compare,
typename _Alloc>
2021 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2022 _Compare, _Alloc>::_Base_ptr,
2023 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2024 _Compare, _Alloc>::_Base_ptr>
2025 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2026 _M_get_insert_unique_pos(
const key_type& __k)
2028 typedef pair<_Base_ptr, _Base_ptr> _Res;
2029 _Link_type __x = _M_begin();
2030 _Base_ptr __y = _M_end();
2035 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
2036 __x = __comp ? _S_left(__x) : _S_right(__x);
2038 iterator __j = iterator(__y);
2042 return _Res(__x, __y);
2046 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
2047 return _Res(__x, __y);
2048 return _Res(__j._M_node, 0);
2051 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2052 typename _Compare,
typename _Alloc>
2053 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2054 _Compare, _Alloc>::_Base_ptr,
2055 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2056 _Compare, _Alloc>::_Base_ptr>
2057 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2058 _M_get_insert_equal_pos(
const key_type& __k)
2060 typedef pair<_Base_ptr, _Base_ptr> _Res;
2061 _Link_type __x = _M_begin();
2062 _Base_ptr __y = _M_end();
2066 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
2067 _S_left(__x) : _S_right(__x);
2069 return _Res(__x, __y);
2072 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2073 typename _Compare,
typename _Alloc>
2074 #if __cplusplus >= 201103L 2075 template<
typename _Arg>
2077 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2078 _Compare, _Alloc>::iterator,
bool>
2079 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2080 #if __cplusplus >= 201103L 2081 _M_insert_unique(_Arg&& __v)
2083 _M_insert_unique(
const _Val& __v)
2086 typedef pair<iterator, bool> _Res;
2087 pair<_Base_ptr, _Base_ptr> __res
2088 = _M_get_insert_unique_pos(_KeyOfValue()(__v));
2092 _Alloc_node __an(*
this);
2093 return _Res(_M_insert_(__res.first, __res.second,
2094 _GLIBCXX_FORWARD(_Arg, __v), __an),
2098 return _Res(iterator(__res.first),
false);
2101 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2102 typename _Compare,
typename _Alloc>
2103 #if __cplusplus >= 201103L 2104 template<
typename _Arg>
2106 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2107 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2108 #if __cplusplus >= 201103L 2109 _M_insert_equal(_Arg&& __v)
2111 _M_insert_equal(
const _Val& __v)
2114 pair<_Base_ptr, _Base_ptr> __res
2115 = _M_get_insert_equal_pos(_KeyOfValue()(__v));
2116 _Alloc_node __an(*
this);
2117 return _M_insert_(__res.first, __res.second,
2118 _GLIBCXX_FORWARD(_Arg, __v), __an);
2121 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2122 typename _Compare,
typename _Alloc>
2123 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2124 _Compare, _Alloc>::_Base_ptr,
2125 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2126 _Compare, _Alloc>::_Base_ptr>
2127 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2128 _M_get_insert_hint_unique_pos(const_iterator __position,
2129 const key_type& __k)
2131 iterator __pos = __position._M_const_cast();
2132 typedef pair<_Base_ptr, _Base_ptr> _Res;
2135 if (__pos._M_node == _M_end())
2138 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
2139 return _Res(0, _M_rightmost());
2141 return _M_get_insert_unique_pos(__k);
2143 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
2146 iterator __before = __pos;
2147 if (__pos._M_node == _M_leftmost())
2148 return _Res(_M_leftmost(), _M_leftmost());
2149 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
2151 if (_S_right(__before._M_node) == 0)
2152 return _Res(0, __before._M_node);
2154 return _Res(__pos._M_node, __pos._M_node);
2157 return _M_get_insert_unique_pos(__k);
2159 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2162 iterator __after = __pos;
2163 if (__pos._M_node == _M_rightmost())
2164 return _Res(0, _M_rightmost());
2165 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
2167 if (_S_right(__pos._M_node) == 0)
2168 return _Res(0, __pos._M_node);
2170 return _Res(__after._M_node, __after._M_node);
2173 return _M_get_insert_unique_pos(__k);
2177 return _Res(__pos._M_node, 0);
2180 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2181 typename _Compare,
typename _Alloc>
2182 #if __cplusplus >= 201103L 2183 template<
typename _Arg,
typename _NodeGen>
2185 template<
typename _NodeGen>
2187 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2188 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2189 _M_insert_unique_(const_iterator __position,
2190 #
if __cplusplus >= 201103L
2195 _NodeGen& __node_gen)
2197 pair<_Base_ptr, _Base_ptr> __res
2198 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
2201 return _M_insert_(__res.first, __res.second,
2202 _GLIBCXX_FORWARD(_Arg, __v),
2204 return iterator(__res.first);
2207 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2208 typename _Compare,
typename _Alloc>
2209 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2210 _Compare, _Alloc>::_Base_ptr,
2211 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2212 _Compare, _Alloc>::_Base_ptr>
2213 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2214 _M_get_insert_hint_equal_pos(const_iterator __position,
const key_type& __k)
2216 iterator __pos = __position._M_const_cast();
2217 typedef pair<_Base_ptr, _Base_ptr> _Res;
2220 if (__pos._M_node == _M_end())
2223 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2224 return _Res(0, _M_rightmost());
2226 return _M_get_insert_equal_pos(__k);
2228 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2231 iterator __before = __pos;
2232 if (__pos._M_node == _M_leftmost())
2233 return _Res(_M_leftmost(), _M_leftmost());
2234 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2236 if (_S_right(__before._M_node) == 0)
2237 return _Res(0, __before._M_node);
2239 return _Res(__pos._M_node, __pos._M_node);
2242 return _M_get_insert_equal_pos(__k);
2247 iterator __after = __pos;
2248 if (__pos._M_node == _M_rightmost())
2249 return _Res(0, _M_rightmost());
2250 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2252 if (_S_right(__pos._M_node) == 0)
2253 return _Res(0, __pos._M_node);
2255 return _Res(__after._M_node, __after._M_node);
2262 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2263 typename _Compare,
typename _Alloc>
2264 #if __cplusplus >= 201103L 2265 template<
typename _Arg,
typename _NodeGen>
2267 template<
typename _NodeGen>
2269 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2270 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2271 _M_insert_equal_(const_iterator __position,
2272 #
if __cplusplus >= 201103L
2277 _NodeGen& __node_gen)
2279 pair<_Base_ptr, _Base_ptr> __res
2280 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2283 return _M_insert_(__res.first, __res.second,
2284 _GLIBCXX_FORWARD(_Arg, __v),
2287 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2290 #if __cplusplus >= 201103L 2291 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2292 typename _Compare,
typename _Alloc>
2293 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2294 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2295 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2297 bool __insert_left = (__x != 0 || __p == _M_end()
2298 || _M_impl._M_key_compare(_S_key(__z),
2301 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2302 this->_M_impl._M_header);
2303 ++_M_impl._M_node_count;
2304 return iterator(__z);
2307 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2308 typename _Compare,
typename _Alloc>
2309 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2310 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2311 _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2313 bool __insert_left = (__p == _M_end()
2314 || !_M_impl._M_key_compare(_S_key(__p),
2317 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2318 this->_M_impl._M_header);
2319 ++_M_impl._M_node_count;
2320 return iterator(__z);
2323 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2324 typename _Compare,
typename _Alloc>
2325 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2326 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2327 _M_insert_equal_lower_node(_Link_type __z)
2329 _Link_type __x = _M_begin();
2330 _Base_ptr __y = _M_end();
2334 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2335 _S_left(__x) : _S_right(__x);
2337 return _M_insert_lower_node(__y, __z);
2340 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2341 typename _Compare,
typename _Alloc>
2342 template<
typename... _Args>
2343 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
2344 _Compare, _Alloc>::iterator,
bool>
2345 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2346 _M_emplace_unique(_Args&&... __args)
2348 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2352 typedef pair<iterator, bool> _Res;
2353 auto __res = _M_get_insert_unique_pos(_S_key(__z));
2355 return _Res(_M_insert_node(__res.first, __res.second, __z),
true);
2358 return _Res(iterator(__res.first),
false);
2363 __throw_exception_again;
2367 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2368 typename _Compare,
typename _Alloc>
2369 template<
typename... _Args>
2370 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2371 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2372 _M_emplace_equal(_Args&&... __args)
2374 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2378 auto __res = _M_get_insert_equal_pos(_S_key(__z));
2379 return _M_insert_node(__res.first, __res.second, __z);
2384 __throw_exception_again;
2388 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2389 typename _Compare,
typename _Alloc>
2390 template<
typename... _Args>
2391 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2392 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2393 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2395 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2399 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2402 return _M_insert_node(__res.first, __res.second, __z);
2405 return iterator(__res.first);
2410 __throw_exception_again;
2414 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2415 typename _Compare,
typename _Alloc>
2416 template<
typename... _Args>
2417 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2418 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2419 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2421 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2425 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2428 return _M_insert_node(__res.first, __res.second, __z);
2430 return _M_insert_equal_lower_node(__z);
2435 __throw_exception_again;
2440 template<
typename _Key,
typename _Val,
typename _KoV,
2441 typename _Cmp,
typename _Alloc>
2444 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2445 _M_insert_unique(_II __first, _II __last)
2447 _Alloc_node __an(*
this);
2448 for (; __first != __last; ++__first)
2449 _M_insert_unique_(
end(), *__first, __an);
2452 template<
typename _Key,
typename _Val,
typename _KoV,
2453 typename _Cmp,
typename _Alloc>
2456 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2457 _M_insert_equal(_II __first, _II __last)
2459 _Alloc_node __an(*
this);
2460 for (; __first != __last; ++__first)
2461 _M_insert_equal_(
end(), *__first, __an);
2464 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2465 typename _Compare,
typename _Alloc>
2467 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2468 _M_erase_aux(const_iterator __position)
2471 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
2472 (const_cast<_Base_ptr>(__position._M_node),
2473 this->_M_impl._M_header));
2475 --_M_impl._M_node_count;
2478 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2479 typename _Compare,
typename _Alloc>
2481 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2482 _M_erase_aux(const_iterator __first, const_iterator __last)
2484 if (__first ==
begin() && __last ==
end())
2487 while (__first != __last)
2488 _M_erase_aux(__first++);
2491 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2492 typename _Compare,
typename _Alloc>
2493 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2494 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2495 erase(
const _Key& __x)
2497 pair<iterator, iterator> __p = equal_range(__x);
2498 const size_type __old_size =
size();
2499 _M_erase_aux(__p.first, __p.second);
2500 return __old_size -
size();
2503 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2504 typename _Compare,
typename _Alloc>
2506 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2507 erase(
const _Key* __first,
const _Key* __last)
2509 while (__first != __last)
2513 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2514 typename _Compare,
typename _Alloc>
2515 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2516 _Compare, _Alloc>::iterator
2517 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2518 find(
const _Key& __k)
2520 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2521 return (__j ==
end()
2522 || _M_impl._M_key_compare(__k,
2523 _S_key(__j._M_node))) ?
end() : __j;
2526 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2527 typename _Compare,
typename _Alloc>
2528 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2529 _Compare, _Alloc>::const_iterator
2530 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2531 find(
const _Key& __k)
const 2533 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2534 return (__j ==
end()
2535 || _M_impl._M_key_compare(__k,
2536 _S_key(__j._M_node))) ?
end() : __j;
2539 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2540 typename _Compare,
typename _Alloc>
2541 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2542 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2543 count(
const _Key& __k)
const 2545 pair<const_iterator, const_iterator> __p = equal_range(__k);
2550 _GLIBCXX_PURE
unsigned int 2551 _Rb_tree_black_count(
const _Rb_tree_node_base* __node,
2552 const _Rb_tree_node_base* __root)
throw ();
2554 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
2555 typename _Compare,
typename _Alloc>
2557 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify()
const 2559 if (_M_impl._M_node_count == 0 ||
begin() ==
end())
2560 return _M_impl._M_node_count == 0 &&
begin() ==
end()
2561 && this->_M_impl._M_header._M_left == _M_end()
2562 && this->_M_impl._M_header._M_right == _M_end();
2564 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2565 for (const_iterator __it =
begin(); __it !=
end(); ++__it)
2567 _Const_Link_type __x =
static_cast<_Const_Link_type
>(__it._M_node);
2568 _Const_Link_type __L = _S_left(__x);
2569 _Const_Link_type __R = _S_right(__x);
2571 if (__x->_M_color == _S_red)
2572 if ((__L && __L->_M_color == _S_red)
2573 || (__R && __R->_M_color == _S_red))
2576 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2578 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2581 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2585 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2587 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2592 #if __cplusplus > 201402L 2594 template<
typename _Key,
typename _Val,
typename _Sel,
typename _Cmp1,
2595 typename _Alloc,
typename _Cmp2>
2596 struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
2600 friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;
2603 _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
2604 {
return __tree._M_impl; }
2608 _GLIBCXX_END_NAMESPACE_VERSION
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
ISO C++ entities toplevel namespace is std.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
_GLIBCXX17_CONSTEXPR auto rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
iterator begin()
As per Table mumble.
_GLIBCXX17_CONSTEXPR auto rend(_Container &__cont) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
iterator end()
As per Table mumble.
constexpr conditional< __move_if_noexcept_cond< _Tp >::value, const _Tp &, _Tp && >::type move_if_noexcept(_Tp &__x) noexcept
Conditionally convert a value to an rvalue.
size_type size() const
As per Table mumble.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Uniform interface to C++98 and C++11 allocators.
bool equal(_IIter1 __first1, _IIter1 __last1, _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
Tests a range for element-wise equality.