67 _GLIBCXX_BEGIN_NAMESPACE(std)
85 enum _Rb_tree_color { _S_red =
false, _S_black =
true };
87 struct _Rb_tree_node_base
89 typedef _Rb_tree_node_base* _Base_ptr;
90 typedef const _Rb_tree_node_base* _Const_Base_ptr;
92 _Rb_tree_color _M_color;
98 _S_minimum(_Base_ptr __x)
100 while (__x->_M_left != 0) __x = __x->_M_left;
104 static _Const_Base_ptr
105 _S_minimum(_Const_Base_ptr __x)
107 while (__x->_M_left != 0) __x = __x->_M_left;
112 _S_maximum(_Base_ptr __x)
114 while (__x->_M_right != 0) __x = __x->_M_right;
118 static _Const_Base_ptr
119 _S_maximum(_Const_Base_ptr __x)
121 while (__x->_M_right != 0) __x = __x->_M_right;
126 template<
typename _Val>
127 struct _Rb_tree_node :
public _Rb_tree_node_base
129 typedef _Rb_tree_node<_Val>* _Link_type;
132 #ifdef __GXX_EXPERIMENTAL_CXX0X__
133 template<
typename... _Args>
134 _Rb_tree_node(_Args&&... __args)
135 : _Rb_tree_node_base(),
136 _M_value_field(std::forward<_Args>(__args)...) { }
141 _Rb_tree_increment(_Rb_tree_node_base* __x);
143 const _Rb_tree_node_base*
144 _Rb_tree_increment(
const _Rb_tree_node_base* __x);
147 _Rb_tree_decrement(_Rb_tree_node_base* __x);
149 const _Rb_tree_node_base*
150 _Rb_tree_decrement(
const _Rb_tree_node_base* __x);
152 template<
typename _Tp>
153 struct _Rb_tree_iterator
155 typedef _Tp value_type;
156 typedef _Tp& reference;
157 typedef _Tp* pointer;
159 typedef bidirectional_iterator_tag iterator_category;
160 typedef ptrdiff_t difference_type;
162 typedef _Rb_tree_iterator<_Tp> _Self;
163 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
164 typedef _Rb_tree_node<_Tp>* _Link_type;
170 _Rb_tree_iterator(_Link_type __x)
175 {
return static_cast<_Link_type
>(_M_node)->_M_value_field; }
179 {
return &
static_cast<_Link_type
>(_M_node)->_M_value_field; }
184 _M_node = _Rb_tree_increment(_M_node);
192 _M_node = _Rb_tree_increment(_M_node);
199 _M_node = _Rb_tree_decrement(_M_node);
207 _M_node = _Rb_tree_decrement(_M_node);
212 operator==(
const _Self& __x)
const
213 {
return _M_node == __x._M_node; }
216 operator!=(
const _Self& __x)
const
217 {
return _M_node != __x._M_node; }
222 template<
typename _Tp>
223 struct _Rb_tree_const_iterator
225 typedef _Tp value_type;
226 typedef const _Tp& reference;
227 typedef const _Tp* pointer;
229 typedef _Rb_tree_iterator<_Tp> iterator;
231 typedef bidirectional_iterator_tag iterator_category;
232 typedef ptrdiff_t difference_type;
234 typedef _Rb_tree_const_iterator<_Tp> _Self;
235 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
236 typedef const _Rb_tree_node<_Tp>* _Link_type;
238 _Rb_tree_const_iterator()
242 _Rb_tree_const_iterator(_Link_type __x)
245 _Rb_tree_const_iterator(
const iterator& __it)
246 : _M_node(__it._M_node) { }
250 {
return static_cast<_Link_type
>(_M_node)->_M_value_field; }
254 {
return &
static_cast<_Link_type
>(_M_node)->_M_value_field; }
259 _M_node = _Rb_tree_increment(_M_node);
267 _M_node = _Rb_tree_increment(_M_node);
274 _M_node = _Rb_tree_decrement(_M_node);
282 _M_node = _Rb_tree_decrement(_M_node);
287 operator==(
const _Self& __x)
const
288 {
return _M_node == __x._M_node; }
291 operator!=(
const _Self& __x)
const
292 {
return _M_node != __x._M_node; }
297 template<
typename _Val>
299 operator==(
const _Rb_tree_iterator<_Val>& __x,
300 const _Rb_tree_const_iterator<_Val>& __y)
301 {
return __x._M_node == __y._M_node; }
303 template<
typename _Val>
305 operator!=(
const _Rb_tree_iterator<_Val>& __x,
306 const _Rb_tree_const_iterator<_Val>& __y)
307 {
return __x._M_node != __y._M_node; }
310 _Rb_tree_insert_and_rebalance(
const bool __insert_left,
311 _Rb_tree_node_base* __x,
312 _Rb_tree_node_base* __p,
313 _Rb_tree_node_base& __header);
316 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base*
const __z,
317 _Rb_tree_node_base& __header);
320 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
321 typename _Compare,
typename _Alloc = allocator<_Val> >
324 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
328 typedef _Rb_tree_node_base* _Base_ptr;
329 typedef const _Rb_tree_node_base* _Const_Base_ptr;
332 typedef _Key key_type;
333 typedef _Val value_type;
334 typedef value_type* pointer;
335 typedef const value_type* const_pointer;
336 typedef value_type& reference;
337 typedef const value_type& const_reference;
338 typedef _Rb_tree_node<_Val>* _Link_type;
339 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
340 typedef size_t size_type;
341 typedef ptrdiff_t difference_type;
342 typedef _Alloc allocator_type;
345 _M_get_Node_allocator()
346 {
return *
static_cast<_Node_allocator*
>(&this->_M_impl); }
348 const _Node_allocator&
349 _M_get_Node_allocator()
const
350 {
return *
static_cast<const _Node_allocator*
>(&this->_M_impl); }
353 get_allocator()
const
354 {
return allocator_type(_M_get_Node_allocator()); }
359 {
return _M_impl._Node_allocator::allocate(1); }
362 _M_put_node(_Link_type __p)
363 { _M_impl._Node_allocator::deallocate(__p, 1); }
365 #ifndef __GXX_EXPERIMENTAL_CXX0X__
367 _M_create_node(
const value_type& __x)
369 _Link_type __tmp = _M_get_node();
371 { get_allocator().construct(&__tmp->_M_value_field, __x); }
375 __throw_exception_again;
381 _M_destroy_node(_Link_type __p)
383 get_allocator().destroy(&__p->_M_value_field);
387 template<
typename... _Args>
389 _M_create_node(_Args&&... __args)
391 _Link_type __tmp = _M_get_node();
394 _M_get_Node_allocator().construct(__tmp,
395 std::forward<_Args>(__args)...);
400 __throw_exception_again;
406 _M_destroy_node(_Link_type __p)
408 _M_get_Node_allocator().destroy(__p);
414 _M_clone_node(_Const_Link_type __x)
416 _Link_type __tmp = _M_create_node(__x->_M_value_field);
417 __tmp->_M_color = __x->_M_color;
424 template<
typename _Key_compare,
425 bool _Is_pod_comparator = __is_pod(_Key_compare)>
426 struct _Rb_tree_impl :
public _Node_allocator
428 _Key_compare _M_key_compare;
429 _Rb_tree_node_base _M_header;
430 size_type _M_node_count;
433 : _Node_allocator(), _M_key_compare(), _M_header(),
437 _Rb_tree_impl(
const _Key_compare& __comp,
const _Node_allocator& __a)
438 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
446 this->_M_header._M_color = _S_red;
447 this->_M_header._M_parent = 0;
448 this->_M_header._M_left = &this->_M_header;
449 this->_M_header._M_right = &this->_M_header;
453 _Rb_tree_impl<_Compare> _M_impl;
458 {
return this->_M_impl._M_header._M_parent; }
462 {
return this->_M_impl._M_header._M_parent; }
466 {
return this->_M_impl._M_header._M_left; }
470 {
return this->_M_impl._M_header._M_left; }
474 {
return this->_M_impl._M_header._M_right; }
478 {
return this->_M_impl._M_header._M_right; }
482 {
return static_cast<_Link_type
>(this->_M_impl._M_header._M_parent); }
487 return static_cast<_Const_Link_type
>
488 (this->_M_impl._M_header._M_parent);
493 {
return static_cast<_Link_type
>(&this->_M_impl._M_header); }
497 {
return static_cast<_Const_Link_type
>(&this->_M_impl._M_header); }
499 static const_reference
500 _S_value(_Const_Link_type __x)
501 {
return __x->_M_value_field; }
504 _S_key(_Const_Link_type __x)
505 {
return _KeyOfValue()(_S_value(__x)); }
508 _S_left(_Base_ptr __x)
509 {
return static_cast<_Link_type
>(__x->_M_left); }
511 static _Const_Link_type
512 _S_left(_Const_Base_ptr __x)
513 {
return static_cast<_Const_Link_type
>(__x->_M_left); }
516 _S_right(_Base_ptr __x)
517 {
return static_cast<_Link_type
>(__x->_M_right); }
519 static _Const_Link_type
520 _S_right(_Const_Base_ptr __x)
521 {
return static_cast<_Const_Link_type
>(__x->_M_right); }
523 static const_reference
524 _S_value(_Const_Base_ptr __x)
525 {
return static_cast<_Const_Link_type
>(__x)->_M_value_field; }
528 _S_key(_Const_Base_ptr __x)
529 {
return _KeyOfValue()(_S_value(__x)); }
532 _S_minimum(_Base_ptr __x)
533 {
return _Rb_tree_node_base::_S_minimum(__x); }
535 static _Const_Base_ptr
536 _S_minimum(_Const_Base_ptr __x)
537 {
return _Rb_tree_node_base::_S_minimum(__x); }
540 _S_maximum(_Base_ptr __x)
541 {
return _Rb_tree_node_base::_S_maximum(__x); }
543 static _Const_Base_ptr
544 _S_maximum(_Const_Base_ptr __x)
545 {
return _Rb_tree_node_base::_S_maximum(__x); }
548 typedef _Rb_tree_iterator<value_type> iterator;
549 typedef _Rb_tree_const_iterator<value_type> const_iterator;
556 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
557 const value_type& __v);
562 _M_insert_lower(_Base_ptr __x, _Base_ptr __y,
const value_type& __v);
565 _M_insert_equal_lower(
const value_type& __x);
568 _M_copy(_Const_Link_type __x, _Link_type __p);
571 _M_erase(_Link_type __x);
574 _M_lower_bound(_Link_type __x, _Link_type __y,
578 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
579 const _Key& __k)
const;
582 _M_upper_bound(_Link_type __x, _Link_type __y,
586 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
587 const _Key& __k)
const;
593 _Rb_tree(
const _Compare& __comp,
594 const allocator_type& __a = allocator_type())
595 : _M_impl(__comp, __a) { }
597 _Rb_tree(
const _Rb_tree& __x)
598 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
600 if (__x._M_root() != 0)
602 _M_root() = _M_copy(__x._M_begin(), _M_end());
603 _M_leftmost() = _S_minimum(_M_root());
604 _M_rightmost() = _S_maximum(_M_root());
605 _M_impl._M_node_count = __x._M_impl._M_node_count;
609 #ifdef __GXX_EXPERIMENTAL_CXX0X__
610 _Rb_tree(_Rb_tree&& __x);
614 { _M_erase(_M_begin()); }
617 operator=(
const _Rb_tree& __x);
622 {
return _M_impl._M_key_compare; }
627 return iterator(static_cast<_Link_type>
628 (this->_M_impl._M_header._M_left));
634 return const_iterator(static_cast<_Const_Link_type>
635 (this->_M_impl._M_header._M_left));
640 {
return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
645 return const_iterator(static_cast<_Const_Link_type>
646 (&this->_M_impl._M_header));
651 {
return reverse_iterator(end()); }
653 const_reverse_iterator
655 {
return const_reverse_iterator(end()); }
659 {
return reverse_iterator(begin()); }
661 const_reverse_iterator
663 {
return const_reverse_iterator(begin()); }
667 {
return _M_impl._M_node_count == 0; }
671 {
return _M_impl._M_node_count; }
675 {
return _M_get_Node_allocator().max_size(); }
678 #ifdef __GXX_EXPERIMENTAL_CXX0X__
679 swap(_Rb_tree&& __t);
686 _M_insert_unique(
const value_type& __x);
689 _M_insert_equal(
const value_type& __x);
692 _M_insert_unique_(const_iterator __position,
const value_type& __x);
695 _M_insert_equal_(const_iterator __position,
const value_type& __x);
697 template<
typename _InputIterator>
699 _M_insert_unique(_InputIterator __first, _InputIterator __last);
701 template<
typename _InputIterator>
703 _M_insert_equal(_InputIterator __first, _InputIterator __last);
706 erase(iterator __position);
709 erase(const_iterator __position);
712 erase(
const key_type& __x);
715 erase(iterator __first, iterator __last);
718 erase(const_iterator __first, const_iterator __last);
721 erase(
const key_type* __first,
const key_type* __last);
726 _M_erase(_M_begin());
727 _M_leftmost() = _M_end();
729 _M_rightmost() = _M_end();
730 _M_impl._M_node_count = 0;
735 find(
const key_type& __k);
738 find(
const key_type& __k)
const;
741 count(
const key_type& __k)
const;
744 lower_bound(
const key_type& __k)
745 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
748 lower_bound(
const key_type& __k)
const
749 {
return _M_lower_bound(_M_begin(), _M_end(), __k); }
752 upper_bound(
const key_type& __k)
753 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
756 upper_bound(
const key_type& __k)
const
757 {
return _M_upper_bound(_M_begin(), _M_end(), __k); }
759 pair<iterator, iterator>
760 equal_range(
const key_type& __k);
762 pair<const_iterator, const_iterator>
763 equal_range(
const key_type& __k)
const;
770 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
771 typename _Compare,
typename _Alloc>
773 operator==(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
774 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
776 return __x.size() == __y.size()
777 &&
std::equal(__x.begin(), __x.end(), __y.begin());
780 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
781 typename _Compare,
typename _Alloc>
783 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
784 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
787 __y.begin(), __y.end());
790 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
791 typename _Compare,
typename _Alloc>
793 operator!=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
794 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
795 {
return !(__x == __y); }
797 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
798 typename _Compare,
typename _Alloc>
800 operator>(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
801 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
802 {
return __y < __x; }
804 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
805 typename _Compare,
typename _Alloc>
807 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
808 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
809 {
return !(__y < __x); }
811 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
812 typename _Compare,
typename _Alloc>
814 operator>=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
815 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
816 {
return !(__x < __y); }
818 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
819 typename _Compare,
typename _Alloc>
821 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
822 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
825 #ifdef __GXX_EXPERIMENTAL_CXX0X__
826 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
827 typename _Compare,
typename _Alloc>
828 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
829 _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
830 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
832 if (__x._M_root() != 0)
834 _M_root() = __x._M_root();
835 _M_leftmost() = __x._M_leftmost();
836 _M_rightmost() = __x._M_rightmost();
837 _M_root()->_M_parent = _M_end();
840 __x._M_leftmost() = __x._M_end();
841 __x._M_rightmost() = __x._M_end();
843 this->_M_impl._M_node_count = __x._M_impl._M_node_count;
844 __x._M_impl._M_node_count = 0;
849 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
850 typename _Compare,
typename _Alloc>
851 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
852 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
853 operator=(
const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
859 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
860 if (__x._M_root() != 0)
862 _M_root() = _M_copy(__x._M_begin(), _M_end());
863 _M_leftmost() = _S_minimum(_M_root());
864 _M_rightmost() = _S_maximum(_M_root());
865 _M_impl._M_node_count = __x._M_impl._M_node_count;
871 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
872 typename _Compare,
typename _Alloc>
873 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
874 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
875 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p,
const _Val& __v)
877 bool __insert_left = (__x != 0 || __p == _M_end()
878 || _M_impl._M_key_compare(_KeyOfValue()(__v),
881 _Link_type __z = _M_create_node(__v);
883 _Rb_tree_insert_and_rebalance(__insert_left, __z,
884 const_cast<_Base_ptr>(__p),
885 this->_M_impl._M_header);
886 ++_M_impl._M_node_count;
887 return iterator(__z);
890 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
891 typename _Compare,
typename _Alloc>
892 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
893 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
894 _M_insert_lower(_Base_ptr __x, _Base_ptr __p,
const _Val& __v)
896 bool __insert_left = (__x != 0 || __p == _M_end()
897 || !_M_impl._M_key_compare(_S_key(__p),
898 _KeyOfValue()(__v)));
900 _Link_type __z = _M_create_node(__v);
902 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
903 this->_M_impl._M_header);
904 ++_M_impl._M_node_count;
905 return iterator(__z);
908 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
909 typename _Compare,
typename _Alloc>
910 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
911 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
912 _M_insert_equal_lower(
const _Val& __v)
914 _Link_type __x = _M_begin();
915 _Link_type __y = _M_end();
919 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
920 _S_left(__x) : _S_right(__x);
922 return _M_insert_lower(__x, __y, __v);
925 template<
typename _Key,
typename _Val,
typename _KoV,
926 typename _Compare,
typename _Alloc>
927 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
928 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
929 _M_copy(_Const_Link_type __x, _Link_type __p)
932 _Link_type __top = _M_clone_node(__x);
933 __top->_M_parent = __p;
938 __top->_M_right = _M_copy(_S_right(__x), __top);
944 _Link_type __y = _M_clone_node(__x);
946 __y->_M_parent = __p;
948 __y->_M_right = _M_copy(_S_right(__x), __y);
956 __throw_exception_again;
961 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
962 typename _Compare,
typename _Alloc>
964 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
965 _M_erase(_Link_type __x)
970 _M_erase(_S_right(__x));
971 _Link_type __y = _S_left(__x);
972 _M_destroy_node(__x);
977 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
978 typename _Compare,
typename _Alloc>
979 typename _Rb_tree<_Key, _Val, _KeyOfValue,
980 _Compare, _Alloc>::iterator
981 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
982 _M_lower_bound(_Link_type __x, _Link_type __y,
986 if (!_M_impl._M_key_compare(_S_key(__x), __k))
987 __y = __x, __x = _S_left(__x);
990 return iterator(__y);
993 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
994 typename _Compare,
typename _Alloc>
995 typename _Rb_tree<_Key, _Val, _KeyOfValue,
996 _Compare, _Alloc>::const_iterator
997 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
998 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
999 const _Key& __k)
const
1002 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1003 __y = __x, __x = _S_left(__x);
1005 __x = _S_right(__x);
1006 return const_iterator(__y);
1009 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1010 typename _Compare,
typename _Alloc>
1011 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1012 _Compare, _Alloc>::iterator
1013 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1014 _M_upper_bound(_Link_type __x, _Link_type __y,
1018 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1019 __y = __x, __x = _S_left(__x);
1021 __x = _S_right(__x);
1022 return iterator(__y);
1025 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1026 typename _Compare,
typename _Alloc>
1027 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1028 _Compare, _Alloc>::const_iterator
1029 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1030 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1031 const _Key& __k)
const
1034 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1035 __y = __x, __x = _S_left(__x);
1037 __x = _S_right(__x);
1038 return const_iterator(__y);
1041 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1042 typename _Compare,
typename _Alloc>
1043 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1044 _Compare, _Alloc>::iterator,
1045 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1046 _Compare, _Alloc>::iterator>
1047 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1048 equal_range(
const _Key& __k)
1050 _Link_type __x = _M_begin();
1051 _Link_type __y = _M_end();
1054 if (_M_impl._M_key_compare(_S_key(__x), __k))
1055 __x = _S_right(__x);
1056 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1057 __y = __x, __x = _S_left(__x);
1060 _Link_type __xu(__x), __yu(__y);
1061 __y = __x, __x = _S_left(__x);
1062 __xu = _S_right(__xu);
1063 return pair<iterator,
1064 iterator>(_M_lower_bound(__x, __y, __k),
1065 _M_upper_bound(__xu, __yu, __k));
1068 return pair<iterator, iterator>(iterator(__y),
1072 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1073 typename _Compare,
typename _Alloc>
1074 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1075 _Compare, _Alloc>::const_iterator,
1076 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1077 _Compare, _Alloc>::const_iterator>
1078 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1079 equal_range(
const _Key& __k)
const
1081 _Const_Link_type __x = _M_begin();
1082 _Const_Link_type __y = _M_end();
1085 if (_M_impl._M_key_compare(_S_key(__x), __k))
1086 __x = _S_right(__x);
1087 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1088 __y = __x, __x = _S_left(__x);
1091 _Const_Link_type __xu(__x), __yu(__y);
1092 __y = __x, __x = _S_left(__x);
1093 __xu = _S_right(__xu);
1094 return pair<const_iterator,
1095 const_iterator>(_M_lower_bound(__x, __y, __k),
1096 _M_upper_bound(__xu, __yu, __k));
1099 return pair<const_iterator, const_iterator>(const_iterator(__y),
1100 const_iterator(__y));
1103 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1104 typename _Compare,
typename _Alloc>
1106 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1107 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1108 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __t)
1110 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1115 if (__t._M_root() != 0)
1117 _M_root() = __t._M_root();
1118 _M_leftmost() = __t._M_leftmost();
1119 _M_rightmost() = __t._M_rightmost();
1120 _M_root()->_M_parent = _M_end();
1123 __t._M_leftmost() = __t._M_end();
1124 __t._M_rightmost() = __t._M_end();
1127 else if (__t._M_root() == 0)
1129 __t._M_root() = _M_root();
1130 __t._M_leftmost() = _M_leftmost();
1131 __t._M_rightmost() = _M_rightmost();
1132 __t._M_root()->_M_parent = __t._M_end();
1135 _M_leftmost() = _M_end();
1136 _M_rightmost() = _M_end();
1140 std::swap(_M_root(),__t._M_root());
1141 std::swap(_M_leftmost(),__t._M_leftmost());
1142 std::swap(_M_rightmost(),__t._M_rightmost());
1144 _M_root()->_M_parent = _M_end();
1145 __t._M_root()->_M_parent = __t._M_end();
1148 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1149 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1153 std::__alloc_swap<_Node_allocator>::
1154 _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
1157 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1158 typename _Compare,
typename _Alloc>
1159 pair<
typename _Rb_tree<_Key, _Val, _KeyOfValue,
1160 _Compare, _Alloc>::iterator,
bool>
1161 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1162 _M_insert_unique(
const _Val& __v)
1164 _Link_type __x = _M_begin();
1165 _Link_type __y = _M_end();
1170 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1171 __x = __comp ? _S_left(__x) : _S_right(__x);
1173 iterator __j = iterator(__y);
1177 return pair<iterator, bool>(_M_insert_(__x, __y, __v),
true);
1181 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
1182 return pair<iterator, bool>(_M_insert_(__x, __y, __v),
true);
1183 return pair<iterator, bool>(__j,
false);
1186 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1187 typename _Compare,
typename _Alloc>
1188 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1189 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1190 _M_insert_equal(
const _Val& __v)
1192 _Link_type __x = _M_begin();
1193 _Link_type __y = _M_end();
1197 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1198 _S_left(__x) : _S_right(__x);
1200 return _M_insert_(__x, __y, __v);
1203 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1204 typename _Compare,
typename _Alloc>
1205 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1206 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1207 _M_insert_unique_(const_iterator __position,
const _Val& __v)
1210 if (__position._M_node == _M_end())
1213 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1214 _KeyOfValue()(__v)))
1215 return _M_insert_(0, _M_rightmost(), __v);
1217 return _M_insert_unique(__v).first;
1219 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1220 _S_key(__position._M_node)))
1223 const_iterator __before = __position;
1224 if (__position._M_node == _M_leftmost())
1225 return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
1226 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1227 _KeyOfValue()(__v)))
1229 if (_S_right(__before._M_node) == 0)
1230 return _M_insert_(0, __before._M_node, __v);
1232 return _M_insert_(__position._M_node,
1233 __position._M_node, __v);
1236 return _M_insert_unique(__v).first;
1238 else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1239 _KeyOfValue()(__v)))
1242 const_iterator __after = __position;
1243 if (__position._M_node == _M_rightmost())
1244 return _M_insert_(0, _M_rightmost(), __v);
1245 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1246 _S_key((++__after)._M_node)))
1248 if (_S_right(__position._M_node) == 0)
1249 return _M_insert_(0, __position._M_node, __v);
1251 return _M_insert_(__after._M_node, __after._M_node, __v);
1254 return _M_insert_unique(__v).first;
1258 return iterator(static_cast<_Link_type>
1259 (const_cast<_Base_ptr>(__position._M_node)));
1262 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1263 typename _Compare,
typename _Alloc>
1264 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1265 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1266 _M_insert_equal_(const_iterator __position,
const _Val& __v)
1269 if (__position._M_node == _M_end())
1272 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1273 _S_key(_M_rightmost())))
1274 return _M_insert_(0, _M_rightmost(), __v);
1276 return _M_insert_equal(__v);
1278 else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1279 _KeyOfValue()(__v)))
1282 const_iterator __before = __position;
1283 if (__position._M_node == _M_leftmost())
1284 return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
1285 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1286 _S_key((--__before)._M_node)))
1288 if (_S_right(__before._M_node) == 0)
1289 return _M_insert_(0, __before._M_node, __v);
1291 return _M_insert_(__position._M_node,
1292 __position._M_node, __v);
1295 return _M_insert_equal(__v);
1300 const_iterator __after = __position;
1301 if (__position._M_node == _M_rightmost())
1302 return _M_insert_(0, _M_rightmost(), __v);
1303 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1304 _KeyOfValue()(__v)))
1306 if (_S_right(__position._M_node) == 0)
1307 return _M_insert_(0, __position._M_node, __v);
1309 return _M_insert_(__after._M_node, __after._M_node, __v);
1312 return _M_insert_equal_lower(__v);
1316 template<
typename _Key,
typename _Val,
typename _KoV,
1317 typename _Cmp,
typename _Alloc>
1320 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1321 _M_insert_unique(_II __first, _II __last)
1323 for (; __first != __last; ++__first)
1324 _M_insert_unique_(end(), *__first);
1327 template<
typename _Key,
typename _Val,
typename _KoV,
1328 typename _Cmp,
typename _Alloc>
1331 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1332 _M_insert_equal(_II __first, _II __last)
1334 for (; __first != __last; ++__first)
1335 _M_insert_equal_(end(), *__first);
1338 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1339 typename _Compare,
typename _Alloc>
1341 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1342 erase(iterator __position)
1345 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1346 (__position._M_node,
1347 this->_M_impl._M_header));
1348 _M_destroy_node(__y);
1349 --_M_impl._M_node_count;
1352 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1353 typename _Compare,
typename _Alloc>
1355 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1356 erase(const_iterator __position)
1359 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1360 (const_cast<_Base_ptr>(__position._M_node),
1361 this->_M_impl._M_header));
1362 _M_destroy_node(__y);
1363 --_M_impl._M_node_count;
1366 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1367 typename _Compare,
typename _Alloc>
1368 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1369 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1370 erase(
const _Key& __x)
1372 pair<iterator, iterator> __p = equal_range(__x);
1373 const size_type __old_size = size();
1374 erase(__p.first, __p.second);
1375 return __old_size - size();
1378 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1379 typename _Compare,
typename _Alloc>
1381 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1382 erase(iterator __first, iterator __last)
1384 if (__first == begin() && __last == end())
1387 while (__first != __last)
1391 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1392 typename _Compare,
typename _Alloc>
1394 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1395 erase(const_iterator __first, const_iterator __last)
1397 if (__first == begin() && __last == end())
1400 while (__first != __last)
1404 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1405 typename _Compare,
typename _Alloc>
1407 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1408 erase(
const _Key* __first,
const _Key* __last)
1410 while (__first != __last)
1414 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1415 typename _Compare,
typename _Alloc>
1416 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1417 _Compare, _Alloc>::iterator
1418 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1419 find(
const _Key& __k)
1421 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1422 return (__j == end()
1423 || _M_impl._M_key_compare(__k,
1424 _S_key(__j._M_node))) ? end() : __j;
1427 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1428 typename _Compare,
typename _Alloc>
1429 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1430 _Compare, _Alloc>::const_iterator
1431 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1432 find(
const _Key& __k)
const
1434 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1435 return (__j == end()
1436 || _M_impl._M_key_compare(__k,
1437 _S_key(__j._M_node))) ? end() : __j;
1440 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1441 typename _Compare,
typename _Alloc>
1442 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1443 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1444 count(
const _Key& __k)
const
1446 pair<const_iterator, const_iterator> __p = equal_range(__k);
1452 _Rb_tree_black_count(
const _Rb_tree_node_base* __node,
1453 const _Rb_tree_node_base* __root);
1455 template<
typename _Key,
typename _Val,
typename _KeyOfValue,
1456 typename _Compare,
typename _Alloc>
1458 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify()
const
1460 if (_M_impl._M_node_count == 0 || begin() == end())
1461 return _M_impl._M_node_count == 0 && begin() == end()
1462 && this->_M_impl._M_header._M_left == _M_end()
1463 && this->_M_impl._M_header._M_right == _M_end();
1465 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1466 for (const_iterator __it = begin(); __it != end(); ++__it)
1468 _Const_Link_type __x =
static_cast<_Const_Link_type
>(__it._M_node);
1469 _Const_Link_type __L = _S_left(__x);
1470 _Const_Link_type __R = _S_right(__x);
1472 if (__x->_M_color == _S_red)
1473 if ((__L && __L->_M_color == _S_red)
1474 || (__R && __R->_M_color == _S_red))
1477 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1479 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1482 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1486 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1488 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1493 _GLIBCXX_END_NAMESPACE
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.
bool equal(_II1 __first1, _II1 __last1, _II2 __first2)
Tests a range for element-wise equality.