68 namespace std _GLIBCXX_VISIBILITY(default)
70 _GLIBCXX_BEGIN_NAMESPACE_VERSION
88 enum _Rb_tree_color { _S_red =
false, _S_black =
true };
90 struct _Rb_tree_node_base
92 typedef _Rb_tree_node_base* _Base_ptr;
93 typedef const _Rb_tree_node_base* _Const_Base_ptr;
95 _Rb_tree_color _M_color;
101 _S_minimum(_Base_ptr __x)
103 while (__x->_M_left != 0) __x = __x->_M_left;
107 static _Const_Base_ptr
108 _S_minimum(_Const_Base_ptr __x)
110 while (__x->_M_left != 0) __x = __x->_M_left;
115 _S_maximum(_Base_ptr __x)
117 while (__x->_M_right != 0) __x = __x->_M_right;
121 static _Const_Base_ptr
122 _S_maximum(_Const_Base_ptr __x)
124 while (__x->_M_right != 0) __x = __x->_M_right;
129 template<
typename _Val>
130 struct _Rb_tree_node :
public _Rb_tree_node_base
132 typedef _Rb_tree_node<_Val>* _Link_type;
135 #ifdef __GXX_EXPERIMENTAL_CXX0X__
136 template<
typename... _Args>
137 _Rb_tree_node(_Args&&... __args)
138 : _Rb_tree_node_base(),
139 _M_value_field(std::
forward<_Args>(__args)...) { }
143 _GLIBCXX_PURE _Rb_tree_node_base*
144 _Rb_tree_increment(_Rb_tree_node_base* __x)
throw ();
146 _GLIBCXX_PURE
const _Rb_tree_node_base*
147 _Rb_tree_increment(
const _Rb_tree_node_base* __x)
throw ();
149 _GLIBCXX_PURE _Rb_tree_node_base*
150 _Rb_tree_decrement(_Rb_tree_node_base* __x)
throw ();
152 _GLIBCXX_PURE
const _Rb_tree_node_base*
153 _Rb_tree_decrement(
const _Rb_tree_node_base* __x)
throw ();
155 template<
typename _Tp>
156 struct _Rb_tree_iterator
158 typedef _Tp value_type;
159 typedef _Tp& reference;
160 typedef _Tp* pointer;
162 typedef bidirectional_iterator_tag iterator_category;
163 typedef ptrdiff_t difference_type;
165 typedef _Rb_tree_iterator<_Tp> _Self;
166 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
167 typedef _Rb_tree_node<_Tp>* _Link_type;
173 _Rb_tree_iterator(_Link_type __x)
178 {
return static_cast<_Link_type
>(_M_node)->_M_value_field; }
183 (_M_node)->_M_value_field); }
188 _M_node = _Rb_tree_increment(_M_node);
196 _M_node = _Rb_tree_increment(_M_node);
203 _M_node = _Rb_tree_decrement(_M_node);
211 _M_node = _Rb_tree_decrement(_M_node);
216 operator==(
const _Self& __x)
const
217 {
return _M_node == __x._M_node; }
220 operator!=(
const _Self& __x)
const
221 {
return _M_node != __x._M_node; }
226 template<
typename _Tp>
227 struct _Rb_tree_const_iterator
229 typedef _Tp value_type;
230 typedef const _Tp& reference;
231 typedef const _Tp* pointer;
233 typedef _Rb_tree_iterator<_Tp> iterator;
235 typedef bidirectional_iterator_tag iterator_category;
236 typedef ptrdiff_t difference_type;
238 typedef _Rb_tree_const_iterator<_Tp> _Self;
239 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
240 typedef const _Rb_tree_node<_Tp>* _Link_type;
242 _Rb_tree_const_iterator()
246 _Rb_tree_const_iterator(_Link_type __x)
249 _Rb_tree_const_iterator(
const iterator& __it)
250 : _M_node(__it._M_node) { }
253 _M_const_cast()
const
254 {
return iterator(static_cast<typename iterator::_Link_type>
255 (const_cast<typename iterator::_Base_ptr>(_M_node))); }
259 {
return static_cast<_Link_type
>(_M_node)->_M_value_field; }
264 (_M_node)->_M_value_field); }
269 _M_node = _Rb_tree_increment(_M_node);
277 _M_node = _Rb_tree_increment(_M_node);
284 _M_node = _Rb_tree_decrement(_M_node);
292 _M_node = _Rb_tree_decrement(_M_node);
297 operator==(
const _Self& __x)
const
298 {
return _M_node == __x._M_node; }
301 operator!=(
const _Self& __x)
const
302 {
return _M_node != __x._M_node; }
307 template<
typename _Val>
309 operator==(
const _Rb_tree_iterator<_Val>& __x,
310 const _Rb_tree_const_iterator<_Val>& __y)
311 {
return __x._M_node == __y._M_node; }
313 template<
typename _Val>
315 operator!=(
const _Rb_tree_iterator<_Val>& __x,
316 const _Rb_tree_const_iterator<_Val>& __y)
317 {
return __x._M_node != __y._M_node; }
320 _Rb_tree_insert_and_rebalance(
const bool __insert_left,
321 _Rb_tree_node_base* __x,
322 _Rb_tree_node_base* __p,
323 _Rb_tree_node_base& __header)
throw ();
326 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base*
const __z,
327 _Rb_tree_node_base& __header)
throw ();
330 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
331 typename _Compare,
typename _Alloc = allocator<_Val> >
334 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
338 typedef _Rb_tree_node_base* _Base_ptr;
339 typedef const _Rb_tree_node_base* _Const_Base_ptr;
342 typedef _Key key_type;
343 typedef _Val value_type;
344 typedef value_type* pointer;
345 typedef const value_type* const_pointer;
346 typedef value_type& reference;
347 typedef const value_type& const_reference;
348 typedef _Rb_tree_node<_Val>* _Link_type;
349 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
350 typedef size_t size_type;
351 typedef ptrdiff_t difference_type;
352 typedef _Alloc allocator_type;
355 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
356 {
return *
static_cast<_Node_allocator*
>(&this->_M_impl); }
358 const _Node_allocator&
359 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
360 {
return *
static_cast<const _Node_allocator*
>(&this->_M_impl); }
363 get_allocator() const _GLIBCXX_NOEXCEPT
364 {
return allocator_type(_M_get_Node_allocator()); }
369 {
return _M_impl._Node_allocator::allocate(1); }
372 _M_put_node(_Link_type __p)
373 { _M_impl._Node_allocator::deallocate(__p, 1); }
375 #ifndef __GXX_EXPERIMENTAL_CXX0X__
377 _M_create_node(
const value_type& __x)
379 _Link_type __tmp = _M_get_node();
381 { get_allocator().construct
386 __throw_exception_again;
392 _M_destroy_node(_Link_type __p)
398 template<
typename... _Args>
400 _M_create_node(_Args&&... __args)
402 _Link_type __tmp = _M_get_node();
405 _M_get_Node_allocator().construct(__tmp,
406 std::forward<_Args>(__args)...);
411 __throw_exception_again;
417 _M_destroy_node(_Link_type __p)
419 _M_get_Node_allocator().destroy(__p);
425 _M_clone_node(_Const_Link_type __x)
427 _Link_type __tmp = _M_create_node(__x->_M_value_field);
428 __tmp->_M_color = __x->_M_color;
435 template<
typename _Key_compare,
436 bool _Is_pod_comparator = __is_pod(_Key_compare)>
437 struct _Rb_tree_impl :
public _Node_allocator
439 _Key_compare _M_key_compare;
440 _Rb_tree_node_base _M_header;
441 size_type _M_node_count;
444 : _Node_allocator(), _M_key_compare(), _M_header(),
448 _Rb_tree_impl(
const _Key_compare& __comp,
const _Node_allocator& __a)
449 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
453 #ifdef __GXX_EXPERIMENTAL_CXX0X__
454 _Rb_tree_impl(
const _Key_compare& __comp, _Node_allocator&& __a)
455 : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
456 _M_header(), _M_node_count(0)
464 this->_M_header._M_color = _S_red;
465 this->_M_header._M_parent = 0;
466 this->_M_header._M_left = &this->_M_header;
467 this->_M_header._M_right = &this->_M_header;
471 _Rb_tree_impl<_Compare> _M_impl;
476 {
return this->_M_impl._M_header._M_parent; }
480 {
return this->_M_impl._M_header._M_parent; }
484 {
return this->_M_impl._M_header._M_left; }
488 {
return this->_M_impl._M_header._M_left; }
492 {
return this->_M_impl._M_header._M_right; }
496 {
return this->_M_impl._M_header._M_right; }
500 {
return static_cast<_Link_type
>(this->_M_impl._M_header._M_parent); }
505 return static_cast<_Const_Link_type
>
506 (this->_M_impl._M_header._M_parent);
511 {
return static_cast<_Link_type
>(&this->_M_impl._M_header); }
515 {
return static_cast<_Const_Link_type
>(&this->_M_impl._M_header); }
517 static const_reference
518 _S_value(_Const_Link_type __x)
519 {
return __x->_M_value_field; }
522 _S_key(_Const_Link_type __x)
523 {
return _KeyOfValue()(_S_value(__x)); }
526 _S_left(_Base_ptr __x)
527 {
return static_cast<_Link_type
>(__x->_M_left); }
529 static _Const_Link_type
530 _S_left(_Const_Base_ptr __x)
531 {
return static_cast<_Const_Link_type
>(__x->_M_left); }
534 _S_right(_Base_ptr __x)
535 {
return static_cast<_Link_type
>(__x->_M_right); }
537 static _Const_Link_type
538 _S_right(_Const_Base_ptr __x)
539 {
return static_cast<_Const_Link_type
>(__x->_M_right); }
541 static const_reference
542 _S_value(_Const_Base_ptr __x)
543 {
return static_cast<_Const_Link_type
>(__x)->_M_value_field; }
546 _S_key(_Const_Base_ptr __x)
547 {
return _KeyOfValue()(_S_value(__x)); }
550 _S_minimum(_Base_ptr __x)
551 {
return _Rb_tree_node_base::_S_minimum(__x); }
553 static _Const_Base_ptr
554 _S_minimum(_Const_Base_ptr __x)
555 {
return _Rb_tree_node_base::_S_minimum(__x); }
558 _S_maximum(_Base_ptr __x)
559 {
return _Rb_tree_node_base::_S_maximum(__x); }
561 static _Const_Base_ptr
562 _S_maximum(_Const_Base_ptr __x)
563 {
return _Rb_tree_node_base::_S_maximum(__x); }
566 typedef _Rb_tree_iterator<value_type> iterator;
567 typedef _Rb_tree_const_iterator<value_type> const_iterator;
573 #ifdef __GXX_EXPERIMENTAL_CXX0X__
574 template<
typename _Arg>
576 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, _Arg&& __v);
578 template<
typename _Arg>
580 _M_insert_lower(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
582 template<
typename _Arg>
584 _M_insert_equal_lower(_Arg&& __x);
587 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
588 const value_type& __v);
593 _M_insert_lower(_Base_ptr __x, _Base_ptr __y,
const value_type& __v);
596 _M_insert_equal_lower(
const value_type& __x);
600 _M_copy(_Const_Link_type __x, _Link_type __p);
603 _M_erase(_Link_type __x);
606 _M_lower_bound(_Link_type __x, _Link_type __y,
610 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
611 const _Key& __k)
const;
614 _M_upper_bound(_Link_type __x, _Link_type __y,
618 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
619 const _Key& __k)
const;
625 _Rb_tree(
const _Compare& __comp,
626 const allocator_type& __a = allocator_type())
627 : _M_impl(__comp, _Node_allocator(__a)) { }
629 _Rb_tree(
const _Rb_tree& __x)
630 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
632 if (__x._M_root() != 0)
634 _M_root() = _M_copy(__x._M_begin(), _M_end());
635 _M_leftmost() = _S_minimum(_M_root());
636 _M_rightmost() = _S_maximum(_M_root());
637 _M_impl._M_node_count = __x._M_impl._M_node_count;
641 #ifdef __GXX_EXPERIMENTAL_CXX0X__
642 _Rb_tree(_Rb_tree&& __x);
645 ~_Rb_tree() _GLIBCXX_NOEXCEPT
646 { _M_erase(_M_begin()); }
649 operator=(
const _Rb_tree& __x);
654 {
return _M_impl._M_key_compare; }
657 begin() _GLIBCXX_NOEXCEPT
659 return iterator(static_cast<_Link_type>
660 (this->_M_impl._M_header._M_left));
664 begin() const _GLIBCXX_NOEXCEPT
666 return const_iterator(static_cast<_Const_Link_type>
667 (this->_M_impl._M_header._M_left));
671 end() _GLIBCXX_NOEXCEPT
672 {
return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
675 end() const _GLIBCXX_NOEXCEPT
677 return const_iterator(static_cast<_Const_Link_type>
678 (&this->_M_impl._M_header));
682 rbegin() _GLIBCXX_NOEXCEPT
683 {
return reverse_iterator(
end()); }
685 const_reverse_iterator
686 rbegin() const _GLIBCXX_NOEXCEPT
687 {
return const_reverse_iterator(
end()); }
690 rend() _GLIBCXX_NOEXCEPT
691 {
return reverse_iterator(
begin()); }
693 const_reverse_iterator
694 rend() const _GLIBCXX_NOEXCEPT
695 {
return const_reverse_iterator(
begin()); }
698 empty() const _GLIBCXX_NOEXCEPT
699 {
return _M_impl._M_node_count == 0; }
702 size() const _GLIBCXX_NOEXCEPT
703 {
return _M_impl._M_node_count; }
706 max_size() const _GLIBCXX_NOEXCEPT
707 {
return _M_get_Node_allocator().max_size(); }
713 #ifdef __GXX_EXPERIMENTAL_CXX0X__
714 template<
typename _Arg>
716 _M_insert_unique(_Arg&& __x);
718 template<
typename _Arg>
720 _M_insert_equal(_Arg&& __x);
722 template<
typename _Arg>
724 _M_insert_unique_(const_iterator __position, _Arg&& __x);
726 template<
typename _Arg>
728 _M_insert_equal_(const_iterator __position, _Arg&& __x);
731 _M_insert_unique(
const value_type& __x);
734 _M_insert_equal(
const value_type& __x);
737 _M_insert_unique_(const_iterator __position,
const value_type& __x);
740 _M_insert_equal_(const_iterator __position,
const value_type& __x);
743 template<
typename _InputIterator>
745 _M_insert_unique(_InputIterator __first, _InputIterator __last);
747 template<
typename _InputIterator>
749 _M_insert_equal(_InputIterator __first, _InputIterator __last);
753 _M_erase_aux(const_iterator __position);
756 _M_erase_aux(const_iterator __first, const_iterator __last);
759 #ifdef __GXX_EXPERIMENTAL_CXX0X__
763 erase(const_iterator __position)
765 const_iterator __result = __position;
767 _M_erase_aux(__position);
768 return __result._M_const_cast();
773 erase(iterator __position)
775 iterator __result = __position;
777 _M_erase_aux(__position);
782 erase(iterator __position)
783 { _M_erase_aux(__position); }
786 erase(const_iterator __position)
787 { _M_erase_aux(__position); }
790 erase(
const key_type& __x);
792 #ifdef __GXX_EXPERIMENTAL_CXX0X__
796 erase(const_iterator __first, const_iterator __last)
798 _M_erase_aux(__first, __last);
799 return __last._M_const_cast();
803 erase(iterator __first, iterator __last)
804 { _M_erase_aux(__first, __last); }
807 erase(const_iterator __first, const_iterator __last)
808 { _M_erase_aux(__first, __last); }
811 erase(
const key_type* __first,
const key_type* __last);
814 clear() _GLIBCXX_NOEXCEPT
816 _M_erase(_M_begin());
817 _M_leftmost() = _M_end();
819 _M_rightmost() = _M_end();
820 _M_impl._M_node_count = 0;
825 find(
const key_type& __k);
828 find(
const key_type& __k)
const;
831 count(
const key_type& __k)
const;
834 lower_bound(
const key_type& __k)
835 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
838 lower_bound(
const key_type& __k)
const
839 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
842 upper_bound(
const key_type& __k)
843 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
846 upper_bound(
const key_type& __k)
const
847 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
849 pair<iterator, iterator>
850 equal_range(
const key_type& __k);
852 pair<const_iterator, const_iterator>
853 equal_range(
const key_type& __k)
const;
860 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
861 typename _Compare,
typename _Alloc>
863 operator==(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
864 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
866 return __x.size() == __y.size()
867 &&
std::equal(__x.begin(), __x.end(), __y.begin());
870 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
871 typename _Compare,
typename _Alloc>
873 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
874 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
877 __y.begin(), __y.end());
880 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
881 typename _Compare,
typename _Alloc>
883 operator!=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
884 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
885 {
return !(__x == __y); }
887 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
888 typename _Compare,
typename _Alloc>
890 operator>(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
891 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
892 {
return __y < __x; }
894 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
895 typename _Compare,
typename _Alloc>
897 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
898 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
899 {
return !(__y < __x); }
901 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
902 typename _Compare,
typename _Alloc>
904 operator>=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
905 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
906 {
return !(__x < __y); }
908 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
909 typename _Compare,
typename _Alloc>
911 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
912 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
915 #ifdef __GXX_EXPERIMENTAL_CXX0X__
916 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
917 typename _Compare,
typename _Alloc>
918 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
919 _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
920 : _M_impl(__x._M_impl._M_key_compare,
921 std::move(__x._M_get_Node_allocator()))
923 if (__x._M_root() != 0)
925 _M_root() = __x._M_root();
926 _M_leftmost() = __x._M_leftmost();
927 _M_rightmost() = __x._M_rightmost();
928 _M_root()->_M_parent = _M_end();
931 __x._M_leftmost() = __x._M_end();
932 __x._M_rightmost() = __x._M_end();
934 this->_M_impl._M_node_count = __x._M_impl._M_node_count;
935 __x._M_impl._M_node_count = 0;
940 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
941 typename _Compare,
typename _Alloc>
942 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
943 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
944 operator=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
950 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
951 if (__x._M_root() != 0)
953 _M_root() = _M_copy(__x._M_begin(), _M_end());
954 _M_leftmost() = _S_minimum(_M_root());
955 _M_rightmost() = _S_maximum(_M_root());
956 _M_impl._M_node_count = __x._M_impl._M_node_count;
962 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
963 typename _Compare,
typename _Alloc>
964 #ifdef __GXX_EXPERIMENTAL_CXX0X__
965 template<
typename _Arg>
967 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
968 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
969 #ifdef __GXX_EXPERIMENTAL_CXX0X__
970 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v)
972 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p,
const _Val& __v)
975 bool __insert_left = (__x != 0 || __p == _M_end()
976 || _M_impl._M_key_compare(_KeyOfValue()(__v),
979 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
981 _Rb_tree_insert_and_rebalance(__insert_left, __z,
982 const_cast<_Base_ptr>(__p),
983 this->_M_impl._M_header);
984 ++_M_impl._M_node_count;
985 return iterator(__z);
988 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
989 typename _Compare,
typename _Alloc>
990 #ifdef __GXX_EXPERIMENTAL_CXX0X__
991 template<
typename _Arg>
993 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
994 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
995 #ifdef __GXX_EXPERIMENTAL_CXX0X__
996 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
998 _M_insert_lower(_Base_ptr __x, _Base_ptr __p,
const _Val& __v)
1001 bool __insert_left = (__x != 0 || __p == _M_end()
1002 || !_M_impl._M_key_compare(_S_key(__p),
1003 _KeyOfValue()(__v)));
1005 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1007 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1008 this->_M_impl._M_header);
1009 ++_M_impl._M_node_count;
1010 return iterator(__z);
1013 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1014 typename _Compare,
typename _Alloc>
1015 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1016 template<
typename _Arg>
1018 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1019 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1020 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1021 _M_insert_equal_lower(_Arg&& __v)
1023 _M_insert_equal_lower(
const _Val& __v)
1026 _Link_type __x = _M_begin();
1027 _Link_type __y = _M_end();
1031 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1032 _S_left(__x) : _S_right(__x);
1034 return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
1037 template<
typename _Key,
typename _Val,
typename _KoV,
1038 typename _Compare,
typename _Alloc>
1039 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1040 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1041 _M_copy(_Const_Link_type __x, _Link_type __p)
1044 _Link_type __top = _M_clone_node(__x);
1045 __top->_M_parent = __p;
1050 __top->_M_right = _M_copy(_S_right(__x), __top);
1056 _Link_type __y = _M_clone_node(__x);
1058 __y->_M_parent = __p;
1060 __y->_M_right = _M_copy(_S_right(__x), __y);
1068 __throw_exception_again;
1073 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1074 typename _Compare,
typename _Alloc>
1076 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1077 _M_erase(_Link_type __x)
1082 _M_erase(_S_right(__x));
1083 _Link_type __y = _S_left(__x);
1084 _M_destroy_node(__x);
1089 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1090 typename _Compare,
typename _Alloc>
1091 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1092 _Compare, _Alloc>::iterator
1093 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1094 _M_lower_bound(_Link_type __x, _Link_type __y,
1098 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1099 __y = __x, __x = _S_left(__x);
1101 __x = _S_right(__x);
1102 return iterator(__y);
1105 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1106 typename _Compare,
typename _Alloc>
1107 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1108 _Compare, _Alloc>::const_iterator
1109 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1110 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1111 const _Key& __k)
const
1114 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1115 __y = __x, __x = _S_left(__x);
1117 __x = _S_right(__x);
1118 return const_iterator(__y);
1121 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1122 typename _Compare,
typename _Alloc>
1123 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1124 _Compare, _Alloc>::iterator
1125 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1126 _M_upper_bound(_Link_type __x, _Link_type __y,
1130 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1131 __y = __x, __x = _S_left(__x);
1133 __x = _S_right(__x);
1134 return iterator(__y);
1137 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1138 typename _Compare,
typename _Alloc>
1139 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1140 _Compare, _Alloc>::const_iterator
1141 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1142 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1143 const _Key& __k)
const
1146 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1147 __y = __x, __x = _S_left(__x);
1149 __x = _S_right(__x);
1150 return const_iterator(__y);
1153 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1154 typename _Compare,
typename _Alloc>
1155 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1156 _Compare, _Alloc>::iterator,
1157 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1158 _Compare, _Alloc>::iterator>
1159 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1160 equal_range(
const _Key& __k)
1162 _Link_type __x = _M_begin();
1163 _Link_type __y = _M_end();
1166 if (_M_impl._M_key_compare(_S_key(__x), __k))
1167 __x = _S_right(__x);
1168 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1169 __y = __x, __x = _S_left(__x);
1172 _Link_type __xu(__x), __yu(__y);
1173 __y = __x, __x = _S_left(__x);
1174 __xu = _S_right(__xu);
1175 return pair<iterator,
1176 iterator>(_M_lower_bound(__x, __y, __k),
1177 _M_upper_bound(__xu, __yu, __k));
1180 return pair<iterator, iterator>(iterator(__y),
1184 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1185 typename _Compare,
typename _Alloc>
1186 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1187 _Compare, _Alloc>::const_iterator,
1188 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1189 _Compare, _Alloc>::const_iterator>
1190 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1191 equal_range(
const _Key& __k)
const
1193 _Const_Link_type __x = _M_begin();
1194 _Const_Link_type __y = _M_end();
1197 if (_M_impl._M_key_compare(_S_key(__x), __k))
1198 __x = _S_right(__x);
1199 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1200 __y = __x, __x = _S_left(__x);
1203 _Const_Link_type __xu(__x), __yu(__y);
1204 __y = __x, __x = _S_left(__x);
1205 __xu = _S_right(__xu);
1206 return pair<const_iterator,
1207 const_iterator>(_M_lower_bound(__x, __y, __k),
1208 _M_upper_bound(__xu, __yu, __k));
1211 return pair<const_iterator, const_iterator>(const_iterator(__y),
1212 const_iterator(__y));
1215 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1216 typename _Compare,
typename _Alloc>
1218 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1219 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1223 if (__t._M_root() != 0)
1225 _M_root() = __t._M_root();
1226 _M_leftmost() = __t._M_leftmost();
1227 _M_rightmost() = __t._M_rightmost();
1228 _M_root()->_M_parent = _M_end();
1231 __t._M_leftmost() = __t._M_end();
1232 __t._M_rightmost() = __t._M_end();
1235 else if (__t._M_root() == 0)
1237 __t._M_root() = _M_root();
1238 __t._M_leftmost() = _M_leftmost();
1239 __t._M_rightmost() = _M_rightmost();
1240 __t._M_root()->_M_parent = __t._M_end();
1243 _M_leftmost() = _M_end();
1244 _M_rightmost() = _M_end();
1248 std::swap(_M_root(),__t._M_root());
1249 std::swap(_M_leftmost(),__t._M_leftmost());
1250 std::swap(_M_rightmost(),__t._M_rightmost());
1252 _M_root()->_M_parent = _M_end();
1253 __t._M_root()->_M_parent = __t._M_end();
1256 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1257 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1261 std::__alloc_swap<_Node_allocator>::
1262 _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
1265 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1266 typename _Compare,
typename _Alloc>
1267 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1268 template<
typename _Arg>
1270 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1271 _Compare, _Alloc>::iterator,
bool>
1272 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1273 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1274 _M_insert_unique(_Arg&& __v)
1276 _M_insert_unique(
const _Val& __v)
1279 _Link_type __x = _M_begin();
1280 _Link_type __y = _M_end();
1285 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1286 __x = __comp ? _S_left(__x) : _S_right(__x);
1288 iterator __j = iterator(__y);
1292 return pair<iterator, bool>
1293 (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)),
true);
1297 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
1298 return pair<iterator, bool>
1299 (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)),
true);
1300 return pair<iterator, bool>(__j,
false);
1303 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1304 typename _Compare,
typename _Alloc>
1305 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1306 template<
typename _Arg>
1308 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1309 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1310 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1311 _M_insert_equal(_Arg&& __v)
1313 _M_insert_equal(
const _Val& __v)
1316 _Link_type __x = _M_begin();
1317 _Link_type __y = _M_end();
1321 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1322 _S_left(__x) : _S_right(__x);
1324 return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
1327 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1328 typename _Compare,
typename _Alloc>
1329 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1330 template<
typename _Arg>
1332 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1333 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1334 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1335 _M_insert_unique_(const_iterator __position, _Arg&& __v)
1337 _M_insert_unique_(const_iterator __position,
const _Val& __v)
1341 if (__position._M_node == _M_end())
1344 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1345 _KeyOfValue()(__v)))
1346 return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v));
1348 return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1350 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1351 _S_key(__position._M_node)))
1354 const_iterator __before = __position;
1355 if (__position._M_node == _M_leftmost())
1356 return _M_insert_(_M_leftmost(), _M_leftmost(),
1357 _GLIBCXX_FORWARD(_Arg, __v));
1358 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1359 _KeyOfValue()(__v)))
1361 if (_S_right(__before._M_node) == 0)
1362 return _M_insert_(0, __before._M_node,
1363 _GLIBCXX_FORWARD(_Arg, __v));
1365 return _M_insert_(__position._M_node,
1367 _GLIBCXX_FORWARD(_Arg, __v));
1370 return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1372 else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1373 _KeyOfValue()(__v)))
1376 const_iterator __after = __position;
1377 if (__position._M_node == _M_rightmost())
1378 return _M_insert_(0, _M_rightmost(),
1379 _GLIBCXX_FORWARD(_Arg, __v));
1380 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1381 _S_key((++__after)._M_node)))
1383 if (_S_right(__position._M_node) == 0)
1384 return _M_insert_(0, __position._M_node,
1385 _GLIBCXX_FORWARD(_Arg, __v));
1387 return _M_insert_(__after._M_node, __after._M_node,
1388 _GLIBCXX_FORWARD(_Arg, __v));
1391 return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1395 return __position._M_const_cast();
1398 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1399 typename _Compare,
typename _Alloc>
1400 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1401 template<
typename _Arg>
1403 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1404 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1405 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1406 _M_insert_equal_(const_iterator __position, _Arg&& __v)
1408 _M_insert_equal_(const_iterator __position,
const _Val& __v)
1412 if (__position._M_node == _M_end())
1415 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1416 _S_key(_M_rightmost())))
1417 return _M_insert_(0, _M_rightmost(),
1418 _GLIBCXX_FORWARD(_Arg, __v));
1420 return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
1422 else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1423 _KeyOfValue()(__v)))
1426 const_iterator __before = __position;
1427 if (__position._M_node == _M_leftmost())
1428 return _M_insert_(_M_leftmost(), _M_leftmost(),
1429 _GLIBCXX_FORWARD(_Arg, __v));
1430 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1431 _S_key((--__before)._M_node)))
1433 if (_S_right(__before._M_node) == 0)
1434 return _M_insert_(0, __before._M_node,
1435 _GLIBCXX_FORWARD(_Arg, __v));
1437 return _M_insert_(__position._M_node,
1439 _GLIBCXX_FORWARD(_Arg, __v));
1442 return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
1447 const_iterator __after = __position;
1448 if (__position._M_node == _M_rightmost())
1449 return _M_insert_(0, _M_rightmost(),
1450 _GLIBCXX_FORWARD(_Arg, __v));
1451 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1452 _KeyOfValue()(__v)))
1454 if (_S_right(__position._M_node) == 0)
1455 return _M_insert_(0, __position._M_node,
1456 _GLIBCXX_FORWARD(_Arg, __v));
1458 return _M_insert_(__after._M_node, __after._M_node,
1459 _GLIBCXX_FORWARD(_Arg, __v));
1462 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
1466 template<
typename _Key,
typename _Val,
typename _KoV,
1467 typename _Cmp,
typename _Alloc>
1470 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1471 _M_insert_unique(_II __first, _II __last)
1473 for (; __first != __last; ++__first)
1474 _M_insert_unique_(
end(), *__first);
1477 template<
typename _Key,
typename _Val,
typename _KoV,
1478 typename _Cmp,
typename _Alloc>
1481 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1482 _M_insert_equal(_II __first, _II __last)
1484 for (; __first != __last; ++__first)
1485 _M_insert_equal_(
end(), *__first);
1488 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1489 typename _Compare,
typename _Alloc>
1491 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1492 _M_erase_aux(const_iterator __position)
1495 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1496 (const_cast<_Base_ptr>(__position._M_node),
1497 this->_M_impl._M_header));
1498 _M_destroy_node(__y);
1499 --_M_impl._M_node_count;
1502 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1503 typename _Compare,
typename _Alloc>
1505 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1506 _M_erase_aux(const_iterator __first, const_iterator __last)
1508 if (__first ==
begin() && __last ==
end())
1511 while (__first != __last)
1515 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1516 typename _Compare,
typename _Alloc>
1517 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1518 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1519 erase(
const _Key& __x)
1521 pair<iterator, iterator> __p = equal_range(__x);
1522 const size_type __old_size =
size();
1523 erase(__p.first, __p.second);
1524 return __old_size -
size();
1527 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1528 typename _Compare,
typename _Alloc>
1530 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1531 erase(
const _Key* __first,
const _Key* __last)
1533 while (__first != __last)
1537 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1538 typename _Compare,
typename _Alloc>
1539 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1540 _Compare, _Alloc>::iterator
1541 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1542 find(
const _Key& __k)
1544 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1545 return (__j ==
end()
1546 || _M_impl._M_key_compare(__k,
1547 _S_key(__j._M_node))) ?
end() : __j;
1550 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1551 typename _Compare,
typename _Alloc>
1552 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1553 _Compare, _Alloc>::const_iterator
1554 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1555 find(
const _Key& __k)
const
1557 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1558 return (__j ==
end()
1559 || _M_impl._M_key_compare(__k,
1560 _S_key(__j._M_node))) ?
end() : __j;
1563 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1564 typename _Compare,
typename _Alloc>
1565 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1567 count(
const _Key& __k)
const
1569 pair<const_iterator, const_iterator> __p = equal_range(__k);
1574 _GLIBCXX_PURE
unsigned int
1575 _Rb_tree_black_count(
const _Rb_tree_node_base* __node,
1576 const _Rb_tree_node_base* __root)
throw ();
1578 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1579 typename _Compare,
typename _Alloc>
1581 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify()
const
1583 if (_M_impl._M_node_count == 0 ||
begin() ==
end())
1584 return _M_impl._M_node_count == 0 &&
begin() ==
end()
1585 && this->_M_impl._M_header._M_left == _M_end()
1586 && this->_M_impl._M_header._M_right == _M_end();
1588 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1589 for (const_iterator __it =
begin(); __it !=
end(); ++__it)
1591 _Const_Link_type __x =
static_cast<_Const_Link_type
>(__it._M_node);
1592 _Const_Link_type __L = _S_left(__x);
1593 _Const_Link_type __R = _S_right(__x);
1595 if (__x->_M_color == _S_red)
1596 if ((__L && __L->_M_color == _S_red)
1597 || (__R && __R->_M_color == _S_red))
1600 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1602 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1605 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1609 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1611 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1616 _GLIBCXX_END_NAMESPACE_VERSION
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
size_t count() const _GLIBCXX_NOEXCEPT
Returns the number of bits which are set.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initilizer_list.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
bool equal(_II1 __first1, _II1 __last1, _II2 __first2)
Tests a range for element-wise equality.
_Tp * __addressof(_Tp &__r) _GLIBCXX_NOEXCEPT
Same as C++11 std::addressof.
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initilizer_list.
constexpr size_t size() const _GLIBCXX_NOEXCEPT
Returns the total number of bits.