1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 2, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
33 * Copyright (c) 1996,1997
34 * Silicon Graphics Computer Systems, Inc.
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation. Silicon Graphics makes no
41 * representations about the suitability of this software for any
42 * purpose. It is provided "as is" without express or implied warranty.
46 * Hewlett-Packard Company
48 * Permission to use, copy, modify, distribute and sell this software
49 * and its documentation for any purpose is hereby granted without fee,
50 * provided that the above copyright notice appear in all copies and
51 * that both that copyright notice and this permission notice appear
52 * in supporting documentation. Hewlett-Packard Company makes no
53 * representations about the suitability of this software for any
54 * purpose. It is provided "as is" without express or implied warranty.
60 * This is an internal header file, included by other library headers.
61 * You should not attempt to use it directly.
67 #include <bits/stl_algobase.h>
68 #include <bits/allocator.h>
69 #include <bits/stl_function.h>
70 #include <bits/cpp_type_traits.h>
72 _GLIBCXX_BEGIN_NAMESPACE(std
)
74 // Red-black tree class, designed for use in implementing STL
75 // associative containers (set, multiset, map, and multimap). The
76 // insertion and deletion algorithms are based on those in Cormen,
77 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
80 // (1) the header cell is maintained with links not only to the root
81 // but also to the leftmost node of the tree, to enable constant
82 // time begin(), and to the rightmost node of the tree, to enable
83 // linear time performance when used with the generic set algorithms
86 // (2) when a node being deleted has two children its successor node
87 // is relinked into its place, rather than copied, so that the only
88 // iterators invalidated are those referring to the deleted node.
90 enum _Rb_tree_color
{ _S_red
= false, _S_black
= true };
92 struct _Rb_tree_node_base
94 typedef _Rb_tree_node_base
* _Base_ptr
;
95 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
97 _Rb_tree_color _M_color
;
103 _S_minimum(_Base_ptr __x
)
105 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
109 static _Const_Base_ptr
110 _S_minimum(_Const_Base_ptr __x
)
112 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
117 _S_maximum(_Base_ptr __x
)
119 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
123 static _Const_Base_ptr
124 _S_maximum(_Const_Base_ptr __x
)
126 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
131 template<typename _Val
>
132 struct _Rb_tree_node
: public _Rb_tree_node_base
134 typedef _Rb_tree_node
<_Val
>* _Link_type
;
137 #ifdef __GXX_EXPERIMENTAL_CXX0X__
138 template<typename
... _Args
>
139 _Rb_tree_node(_Args
&&... __args
)
140 : _Rb_tree_node_base(),
141 _M_value_field(std::forward
<_Args
>(__args
)...) { }
146 _Rb_tree_increment(_Rb_tree_node_base
* __x
);
148 const _Rb_tree_node_base
*
149 _Rb_tree_increment(const _Rb_tree_node_base
* __x
);
152 _Rb_tree_decrement(_Rb_tree_node_base
* __x
);
154 const _Rb_tree_node_base
*
155 _Rb_tree_decrement(const _Rb_tree_node_base
* __x
);
157 template<typename _Tp
>
158 struct _Rb_tree_iterator
160 typedef _Tp value_type
;
161 typedef _Tp
& reference
;
162 typedef _Tp
* pointer
;
164 typedef bidirectional_iterator_tag iterator_category
;
165 typedef ptrdiff_t difference_type
;
167 typedef _Rb_tree_iterator
<_Tp
> _Self
;
168 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
169 typedef _Rb_tree_node
<_Tp
>* _Link_type
;
175 _Rb_tree_iterator(_Link_type __x
)
180 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
184 { return &static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
189 _M_node
= _Rb_tree_increment(_M_node
);
197 _M_node
= _Rb_tree_increment(_M_node
);
204 _M_node
= _Rb_tree_decrement(_M_node
);
212 _M_node
= _Rb_tree_decrement(_M_node
);
217 operator==(const _Self
& __x
) const
218 { return _M_node
== __x
._M_node
; }
221 operator!=(const _Self
& __x
) const
222 { return _M_node
!= __x
._M_node
; }
227 template<typename _Tp
>
228 struct _Rb_tree_const_iterator
230 typedef _Tp value_type
;
231 typedef const _Tp
& reference
;
232 typedef const _Tp
* pointer
;
234 typedef _Rb_tree_iterator
<_Tp
> iterator
;
236 typedef bidirectional_iterator_tag iterator_category
;
237 typedef ptrdiff_t difference_type
;
239 typedef _Rb_tree_const_iterator
<_Tp
> _Self
;
240 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr
;
241 typedef const _Rb_tree_node
<_Tp
>* _Link_type
;
243 _Rb_tree_const_iterator()
247 _Rb_tree_const_iterator(_Link_type __x
)
250 _Rb_tree_const_iterator(const iterator
& __it
)
251 : _M_node(__it
._M_node
) { }
255 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
259 { return &static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
264 _M_node
= _Rb_tree_increment(_M_node
);
272 _M_node
= _Rb_tree_increment(_M_node
);
279 _M_node
= _Rb_tree_decrement(_M_node
);
287 _M_node
= _Rb_tree_decrement(_M_node
);
292 operator==(const _Self
& __x
) const
293 { return _M_node
== __x
._M_node
; }
296 operator!=(const _Self
& __x
) const
297 { return _M_node
!= __x
._M_node
; }
302 template<typename _Val
>
304 operator==(const _Rb_tree_iterator
<_Val
>& __x
,
305 const _Rb_tree_const_iterator
<_Val
>& __y
)
306 { return __x
._M_node
== __y
._M_node
; }
308 template<typename _Val
>
310 operator!=(const _Rb_tree_iterator
<_Val
>& __x
,
311 const _Rb_tree_const_iterator
<_Val
>& __y
)
312 { return __x
._M_node
!= __y
._M_node
; }
315 _Rb_tree_insert_and_rebalance(const bool __insert_left
,
316 _Rb_tree_node_base
* __x
,
317 _Rb_tree_node_base
* __p
,
318 _Rb_tree_node_base
& __header
);
321 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
322 _Rb_tree_node_base
& __header
);
325 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
326 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
329 typedef typename
_Alloc::template rebind
<_Rb_tree_node
<_Val
> >::other
333 typedef _Rb_tree_node_base
* _Base_ptr
;
334 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
337 typedef _Key key_type
;
338 typedef _Val value_type
;
339 typedef value_type
* pointer
;
340 typedef const value_type
* const_pointer
;
341 typedef value_type
& reference
;
342 typedef const value_type
& const_reference
;
343 typedef _Rb_tree_node
<_Val
>* _Link_type
;
344 typedef const _Rb_tree_node
<_Val
>* _Const_Link_type
;
345 typedef size_t size_type
;
346 typedef ptrdiff_t difference_type
;
347 typedef _Alloc allocator_type
;
350 _M_get_Node_allocator()
351 { return *static_cast<_Node_allocator
*>(&this->_M_impl
); }
353 const _Node_allocator
&
354 _M_get_Node_allocator() const
355 { return *static_cast<const _Node_allocator
*>(&this->_M_impl
); }
358 get_allocator() const
359 { return allocator_type(_M_get_Node_allocator()); }
364 { return _M_impl
._Node_allocator::allocate(1); }
367 _M_put_node(_Link_type __p
)
368 { _M_impl
._Node_allocator::deallocate(__p
, 1); }
370 #ifndef __GXX_EXPERIMENTAL_CXX0X__
372 _M_create_node(const value_type
& __x
)
374 _Link_type __tmp
= _M_get_node();
376 { get_allocator().construct(&__tmp
->_M_value_field
, __x
); }
380 __throw_exception_again
;
386 _M_destroy_node(_Link_type __p
)
388 get_allocator().destroy(&__p
->_M_value_field
);
392 template<typename
... _Args
>
394 _M_create_node(_Args
&&... __args
)
396 _Link_type __tmp
= _M_get_node();
399 _M_get_Node_allocator().construct(__tmp
,
400 std::forward
<_Args
>(__args
)...);
405 __throw_exception_again
;
411 _M_destroy_node(_Link_type __p
)
413 _M_get_Node_allocator().destroy(__p
);
419 _M_clone_node(_Const_Link_type __x
)
421 _Link_type __tmp
= _M_create_node(__x
->_M_value_field
);
422 __tmp
->_M_color
= __x
->_M_color
;
429 template<typename _Key_compare
,
430 bool _Is_pod_comparator
= __is_pod(_Key_compare
)>
431 struct _Rb_tree_impl
: public _Node_allocator
433 _Key_compare _M_key_compare
;
434 _Rb_tree_node_base _M_header
;
435 size_type _M_node_count
; // Keeps track of size of tree.
438 : _Node_allocator(), _M_key_compare(), _M_header(),
442 _Rb_tree_impl(const _Key_compare
& __comp
, const _Node_allocator
& __a
)
443 : _Node_allocator(__a
), _M_key_compare(__comp
), _M_header(),
451 this->_M_header
._M_color
= _S_red
;
452 this->_M_header
._M_parent
= 0;
453 this->_M_header
._M_left
= &this->_M_header
;
454 this->_M_header
._M_right
= &this->_M_header
;
458 _Rb_tree_impl
<_Compare
> _M_impl
;
463 { return this->_M_impl
._M_header
._M_parent
; }
467 { return this->_M_impl
._M_header
._M_parent
; }
471 { return this->_M_impl
._M_header
._M_left
; }
475 { return this->_M_impl
._M_header
._M_left
; }
479 { return this->_M_impl
._M_header
._M_right
; }
483 { return this->_M_impl
._M_header
._M_right
; }
487 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
492 return static_cast<_Const_Link_type
>
493 (this->_M_impl
._M_header
._M_parent
);
498 { return static_cast<_Link_type
>(&this->_M_impl
._M_header
); }
502 { return static_cast<_Const_Link_type
>(&this->_M_impl
._M_header
); }
504 static const_reference
505 _S_value(_Const_Link_type __x
)
506 { return __x
->_M_value_field
; }
509 _S_key(_Const_Link_type __x
)
510 { return _KeyOfValue()(_S_value(__x
)); }
513 _S_left(_Base_ptr __x
)
514 { return static_cast<_Link_type
>(__x
->_M_left
); }
516 static _Const_Link_type
517 _S_left(_Const_Base_ptr __x
)
518 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
521 _S_right(_Base_ptr __x
)
522 { return static_cast<_Link_type
>(__x
->_M_right
); }
524 static _Const_Link_type
525 _S_right(_Const_Base_ptr __x
)
526 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
528 static const_reference
529 _S_value(_Const_Base_ptr __x
)
530 { return static_cast<_Const_Link_type
>(__x
)->_M_value_field
; }
533 _S_key(_Const_Base_ptr __x
)
534 { return _KeyOfValue()(_S_value(__x
)); }
537 _S_minimum(_Base_ptr __x
)
538 { return _Rb_tree_node_base::_S_minimum(__x
); }
540 static _Const_Base_ptr
541 _S_minimum(_Const_Base_ptr __x
)
542 { return _Rb_tree_node_base::_S_minimum(__x
); }
545 _S_maximum(_Base_ptr __x
)
546 { return _Rb_tree_node_base::_S_maximum(__x
); }
548 static _Const_Base_ptr
549 _S_maximum(_Const_Base_ptr __x
)
550 { return _Rb_tree_node_base::_S_maximum(__x
); }
553 typedef _Rb_tree_iterator
<value_type
> iterator
;
554 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
556 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
557 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
561 _M_insert_(_Const_Base_ptr __x
, _Const_Base_ptr __y
,
562 const value_type
& __v
);
564 // _GLIBCXX_RESOLVE_LIB_DEFECTS
565 // 233. Insertion hints in associative containers.
567 _M_insert_lower(_Base_ptr __x
, _Base_ptr __y
, const value_type
& __v
);
570 _M_insert_equal_lower(const value_type
& __x
);
573 _M_copy(_Const_Link_type __x
, _Link_type __p
);
576 _M_erase(_Link_type __x
);
579 _M_lower_bound(_Link_type __x
, _Link_type __y
,
583 _M_lower_bound(_Const_Link_type __x
, _Const_Link_type __y
,
584 const _Key
& __k
) const;
587 _M_upper_bound(_Link_type __x
, _Link_type __y
,
591 _M_upper_bound(_Const_Link_type __x
, _Const_Link_type __y
,
592 const _Key
& __k
) const;
595 // allocation/deallocation
598 _Rb_tree(const _Compare
& __comp
,
599 const allocator_type
& __a
= allocator_type())
600 : _M_impl(__comp
, __a
) { }
602 _Rb_tree(const _Rb_tree
& __x
)
603 : _M_impl(__x
._M_impl
._M_key_compare
, __x
._M_get_Node_allocator())
605 if (__x
._M_root() != 0)
607 _M_root() = _M_copy(__x
._M_begin(), _M_end());
608 _M_leftmost() = _S_minimum(_M_root());
609 _M_rightmost() = _S_maximum(_M_root());
610 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
614 #ifdef __GXX_EXPERIMENTAL_CXX0X__
615 _Rb_tree(_Rb_tree
&& __x
);
619 { _M_erase(_M_begin()); }
622 operator=(const _Rb_tree
& __x
);
627 { return _M_impl
._M_key_compare
; }
632 return iterator(static_cast<_Link_type
>
633 (this->_M_impl
._M_header
._M_left
));
639 return const_iterator(static_cast<_Const_Link_type
>
640 (this->_M_impl
._M_header
._M_left
));
645 { return iterator(static_cast<_Link_type
>(&this->_M_impl
._M_header
)); }
650 return const_iterator(static_cast<_Const_Link_type
>
651 (&this->_M_impl
._M_header
));
656 { return reverse_iterator(end()); }
658 const_reverse_iterator
660 { return const_reverse_iterator(end()); }
664 { return reverse_iterator(begin()); }
666 const_reverse_iterator
668 { return const_reverse_iterator(begin()); }
672 { return _M_impl
._M_node_count
== 0; }
676 { return _M_impl
._M_node_count
; }
680 { return _M_get_Node_allocator().max_size(); }
683 #ifdef __GXX_EXPERIMENTAL_CXX0X__
684 swap(_Rb_tree
&& __t
);
691 _M_insert_unique(const value_type
& __x
);
694 _M_insert_equal(const value_type
& __x
);
697 _M_insert_unique_(const_iterator __position
, const value_type
& __x
);
700 _M_insert_equal_(const_iterator __position
, const value_type
& __x
);
702 template<typename _InputIterator
>
704 _M_insert_unique(_InputIterator __first
, _InputIterator __last
);
706 template<typename _InputIterator
>
708 _M_insert_equal(_InputIterator __first
, _InputIterator __last
);
711 erase(iterator __position
);
714 erase(const_iterator __position
);
717 erase(const key_type
& __x
);
720 erase(iterator __first
, iterator __last
);
723 erase(const_iterator __first
, const_iterator __last
);
726 erase(const key_type
* __first
, const key_type
* __last
);
731 _M_erase(_M_begin());
732 _M_leftmost() = _M_end();
734 _M_rightmost() = _M_end();
735 _M_impl
._M_node_count
= 0;
740 find(const key_type
& __k
);
743 find(const key_type
& __k
) const;
746 count(const key_type
& __k
) const;
749 lower_bound(const key_type
& __k
)
750 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
753 lower_bound(const key_type
& __k
) const
754 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
757 upper_bound(const key_type
& __k
)
758 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
761 upper_bound(const key_type
& __k
) const
762 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
764 pair
<iterator
, iterator
>
765 equal_range(const key_type
& __k
);
767 pair
<const_iterator
, const_iterator
>
768 equal_range(const key_type
& __k
) const;
775 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
776 typename _Compare
, typename _Alloc
>
778 operator==(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
779 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
781 return __x
.size() == __y
.size()
782 && std::equal(__x
.begin(), __x
.end(), __y
.begin());
785 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
786 typename _Compare
, typename _Alloc
>
788 operator<(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
789 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
791 return std::lexicographical_compare(__x
.begin(), __x
.end(),
792 __y
.begin(), __y
.end());
795 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
796 typename _Compare
, typename _Alloc
>
798 operator!=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
799 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
800 { return !(__x
== __y
); }
802 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
803 typename _Compare
, typename _Alloc
>
805 operator>(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
806 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
807 { return __y
< __x
; }
809 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
810 typename _Compare
, typename _Alloc
>
812 operator<=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
813 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
814 { return !(__y
< __x
); }
816 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
817 typename _Compare
, typename _Alloc
>
819 operator>=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
820 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
821 { return !(__x
< __y
); }
823 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
824 typename _Compare
, typename _Alloc
>
826 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
827 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
830 #ifdef __GXX_EXPERIMENTAL_CXX0X__
831 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
832 typename _Compare
, typename _Alloc
>
833 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
834 _Rb_tree(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&& __x
)
835 : _M_impl(__x
._M_impl
._M_key_compare
, __x
._M_get_Node_allocator())
837 if (__x
._M_root() != 0)
839 _M_root() = __x
._M_root();
840 _M_leftmost() = __x
._M_leftmost();
841 _M_rightmost() = __x
._M_rightmost();
842 _M_root()->_M_parent
= _M_end();
845 __x
._M_leftmost() = __x
._M_end();
846 __x
._M_rightmost() = __x
._M_end();
848 this->_M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
849 __x
._M_impl
._M_node_count
= 0;
854 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
855 typename _Compare
, typename _Alloc
>
856 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
857 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
858 operator=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
)
862 // Note that _Key may be a constant type.
864 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
865 if (__x
._M_root() != 0)
867 _M_root() = _M_copy(__x
._M_begin(), _M_end());
868 _M_leftmost() = _S_minimum(_M_root());
869 _M_rightmost() = _S_maximum(_M_root());
870 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
876 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
877 typename _Compare
, typename _Alloc
>
878 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
879 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
880 _M_insert_(_Const_Base_ptr __x
, _Const_Base_ptr __p
, const _Val
& __v
)
882 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
883 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
886 _Link_type __z
= _M_create_node(__v
);
888 _Rb_tree_insert_and_rebalance(__insert_left
, __z
,
889 const_cast<_Base_ptr
>(__p
),
890 this->_M_impl
._M_header
);
891 ++_M_impl
._M_node_count
;
892 return iterator(__z
);
895 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
896 typename _Compare
, typename _Alloc
>
897 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
898 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
899 _M_insert_lower(_Base_ptr __x
, _Base_ptr __p
, const _Val
& __v
)
901 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
902 || !_M_impl
._M_key_compare(_S_key(__p
),
903 _KeyOfValue()(__v
)));
905 _Link_type __z
= _M_create_node(__v
);
907 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
908 this->_M_impl
._M_header
);
909 ++_M_impl
._M_node_count
;
910 return iterator(__z
);
913 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
914 typename _Compare
, typename _Alloc
>
915 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
916 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
917 _M_insert_equal_lower(const _Val
& __v
)
919 _Link_type __x
= _M_begin();
920 _Link_type __y
= _M_end();
924 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _KeyOfValue()(__v
)) ?
925 _S_left(__x
) : _S_right(__x
);
927 return _M_insert_lower(__x
, __y
, __v
);
930 template<typename _Key
, typename _Val
, typename _KoV
,
931 typename _Compare
, typename _Alloc
>
932 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
933 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
934 _M_copy(_Const_Link_type __x
, _Link_type __p
)
936 // Structural copy. __x and __p must be non-null.
937 _Link_type __top
= _M_clone_node(__x
);
938 __top
->_M_parent
= __p
;
943 __top
->_M_right
= _M_copy(_S_right(__x
), __top
);
949 _Link_type __y
= _M_clone_node(__x
);
951 __y
->_M_parent
= __p
;
953 __y
->_M_right
= _M_copy(_S_right(__x
), __y
);
961 __throw_exception_again
;
966 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
967 typename _Compare
, typename _Alloc
>
969 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
970 _M_erase(_Link_type __x
)
972 // Erase without rebalancing.
975 _M_erase(_S_right(__x
));
976 _Link_type __y
= _S_left(__x
);
977 _M_destroy_node(__x
);
982 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
983 typename _Compare
, typename _Alloc
>
984 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
985 _Compare
, _Alloc
>::iterator
986 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
987 _M_lower_bound(_Link_type __x
, _Link_type __y
,
991 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
992 __y
= __x
, __x
= _S_left(__x
);
995 return iterator(__y
);
998 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
999 typename _Compare
, typename _Alloc
>
1000 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1001 _Compare
, _Alloc
>::const_iterator
1002 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1003 _M_lower_bound(_Const_Link_type __x
, _Const_Link_type __y
,
1004 const _Key
& __k
) const
1007 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1008 __y
= __x
, __x
= _S_left(__x
);
1010 __x
= _S_right(__x
);
1011 return const_iterator(__y
);
1014 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1015 typename _Compare
, typename _Alloc
>
1016 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1017 _Compare
, _Alloc
>::iterator
1018 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1019 _M_upper_bound(_Link_type __x
, _Link_type __y
,
1023 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1024 __y
= __x
, __x
= _S_left(__x
);
1026 __x
= _S_right(__x
);
1027 return iterator(__y
);
1030 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1031 typename _Compare
, typename _Alloc
>
1032 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1033 _Compare
, _Alloc
>::const_iterator
1034 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1035 _M_upper_bound(_Const_Link_type __x
, _Const_Link_type __y
,
1036 const _Key
& __k
) const
1039 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1040 __y
= __x
, __x
= _S_left(__x
);
1042 __x
= _S_right(__x
);
1043 return const_iterator(__y
);
1046 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1047 typename _Compare
, typename _Alloc
>
1048 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1049 _Compare
, _Alloc
>::iterator
,
1050 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1051 _Compare
, _Alloc
>::iterator
>
1052 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1053 equal_range(const _Key
& __k
)
1055 _Link_type __x
= _M_begin();
1056 _Link_type __y
= _M_end();
1059 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1060 __x
= _S_right(__x
);
1061 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1062 __y
= __x
, __x
= _S_left(__x
);
1065 _Link_type
__xu(__x
), __yu(__y
);
1066 __y
= __x
, __x
= _S_left(__x
);
1067 __xu
= _S_right(__xu
);
1068 return pair
<iterator
,
1069 iterator
>(_M_lower_bound(__x
, __y
, __k
),
1070 _M_upper_bound(__xu
, __yu
, __k
));
1073 return pair
<iterator
, iterator
>(iterator(__y
),
1077 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1078 typename _Compare
, typename _Alloc
>
1079 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1080 _Compare
, _Alloc
>::const_iterator
,
1081 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1082 _Compare
, _Alloc
>::const_iterator
>
1083 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1084 equal_range(const _Key
& __k
) const
1086 _Const_Link_type __x
= _M_begin();
1087 _Const_Link_type __y
= _M_end();
1090 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1091 __x
= _S_right(__x
);
1092 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1093 __y
= __x
, __x
= _S_left(__x
);
1096 _Const_Link_type
__xu(__x
), __yu(__y
);
1097 __y
= __x
, __x
= _S_left(__x
);
1098 __xu
= _S_right(__xu
);
1099 return pair
<const_iterator
,
1100 const_iterator
>(_M_lower_bound(__x
, __y
, __k
),
1101 _M_upper_bound(__xu
, __yu
, __k
));
1104 return pair
<const_iterator
, const_iterator
>(const_iterator(__y
),
1105 const_iterator(__y
));
1108 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1109 typename _Compare
, typename _Alloc
>
1111 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1112 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1113 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&& __t
)
1115 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __t
)
1120 if (__t
._M_root() != 0)
1122 _M_root() = __t
._M_root();
1123 _M_leftmost() = __t
._M_leftmost();
1124 _M_rightmost() = __t
._M_rightmost();
1125 _M_root()->_M_parent
= _M_end();
1128 __t
._M_leftmost() = __t
._M_end();
1129 __t
._M_rightmost() = __t
._M_end();
1132 else if (__t
._M_root() == 0)
1134 __t
._M_root() = _M_root();
1135 __t
._M_leftmost() = _M_leftmost();
1136 __t
._M_rightmost() = _M_rightmost();
1137 __t
._M_root()->_M_parent
= __t
._M_end();
1140 _M_leftmost() = _M_end();
1141 _M_rightmost() = _M_end();
1145 std::swap(_M_root(),__t
._M_root());
1146 std::swap(_M_leftmost(),__t
._M_leftmost());
1147 std::swap(_M_rightmost(),__t
._M_rightmost());
1149 _M_root()->_M_parent
= _M_end();
1150 __t
._M_root()->_M_parent
= __t
._M_end();
1152 // No need to swap header's color as it does not change.
1153 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
1154 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
1156 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1157 // 431. Swapping containers with unequal allocators.
1158 std::__alloc_swap
<_Node_allocator
>::
1159 _S_do_it(_M_get_Node_allocator(), __t
._M_get_Node_allocator());
1162 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1163 typename _Compare
, typename _Alloc
>
1164 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1165 _Compare
, _Alloc
>::iterator
, bool>
1166 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1167 _M_insert_unique(const _Val
& __v
)
1169 _Link_type __x
= _M_begin();
1170 _Link_type __y
= _M_end();
1175 __comp
= _M_impl
._M_key_compare(_KeyOfValue()(__v
), _S_key(__x
));
1176 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
1178 iterator __j
= iterator(__y
);
1182 return pair
<iterator
, bool>(_M_insert_(__x
, __y
, __v
), true);
1186 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), _KeyOfValue()(__v
)))
1187 return pair
<iterator
, bool>(_M_insert_(__x
, __y
, __v
), true);
1188 return pair
<iterator
, bool>(__j
, false);
1191 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1192 typename _Compare
, typename _Alloc
>
1193 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1194 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1195 _M_insert_equal(const _Val
& __v
)
1197 _Link_type __x
= _M_begin();
1198 _Link_type __y
= _M_end();
1202 __x
= _M_impl
._M_key_compare(_KeyOfValue()(__v
), _S_key(__x
)) ?
1203 _S_left(__x
) : _S_right(__x
);
1205 return _M_insert_(__x
, __y
, __v
);
1208 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1209 typename _Compare
, typename _Alloc
>
1210 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1211 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1212 _M_insert_unique_(const_iterator __position
, const _Val
& __v
)
1215 if (__position
._M_node
== _M_end())
1218 && _M_impl
._M_key_compare(_S_key(_M_rightmost()),
1219 _KeyOfValue()(__v
)))
1220 return _M_insert_(0, _M_rightmost(), __v
);
1222 return _M_insert_unique(__v
).first
;
1224 else if (_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1225 _S_key(__position
._M_node
)))
1227 // First, try before...
1228 const_iterator __before
= __position
;
1229 if (__position
._M_node
== _M_leftmost()) // begin()
1230 return _M_insert_(_M_leftmost(), _M_leftmost(), __v
);
1231 else if (_M_impl
._M_key_compare(_S_key((--__before
)._M_node
),
1232 _KeyOfValue()(__v
)))
1234 if (_S_right(__before
._M_node
) == 0)
1235 return _M_insert_(0, __before
._M_node
, __v
);
1237 return _M_insert_(__position
._M_node
,
1238 __position
._M_node
, __v
);
1241 return _M_insert_unique(__v
).first
;
1243 else if (_M_impl
._M_key_compare(_S_key(__position
._M_node
),
1244 _KeyOfValue()(__v
)))
1246 // ... then try after.
1247 const_iterator __after
= __position
;
1248 if (__position
._M_node
== _M_rightmost())
1249 return _M_insert_(0, _M_rightmost(), __v
);
1250 else if (_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1251 _S_key((++__after
)._M_node
)))
1253 if (_S_right(__position
._M_node
) == 0)
1254 return _M_insert_(0, __position
._M_node
, __v
);
1256 return _M_insert_(__after
._M_node
, __after
._M_node
, __v
);
1259 return _M_insert_unique(__v
).first
;
1263 return iterator(static_cast<_Link_type
>
1264 (const_cast<_Base_ptr
>(__position
._M_node
)));
1267 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1268 typename _Compare
, typename _Alloc
>
1269 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1270 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1271 _M_insert_equal_(const_iterator __position
, const _Val
& __v
)
1274 if (__position
._M_node
== _M_end())
1277 && !_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1278 _S_key(_M_rightmost())))
1279 return _M_insert_(0, _M_rightmost(), __v
);
1281 return _M_insert_equal(__v
);
1283 else if (!_M_impl
._M_key_compare(_S_key(__position
._M_node
),
1284 _KeyOfValue()(__v
)))
1286 // First, try before...
1287 const_iterator __before
= __position
;
1288 if (__position
._M_node
== _M_leftmost()) // begin()
1289 return _M_insert_(_M_leftmost(), _M_leftmost(), __v
);
1290 else if (!_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1291 _S_key((--__before
)._M_node
)))
1293 if (_S_right(__before
._M_node
) == 0)
1294 return _M_insert_(0, __before
._M_node
, __v
);
1296 return _M_insert_(__position
._M_node
,
1297 __position
._M_node
, __v
);
1300 return _M_insert_equal(__v
);
1304 // ... then try after.
1305 const_iterator __after
= __position
;
1306 if (__position
._M_node
== _M_rightmost())
1307 return _M_insert_(0, _M_rightmost(), __v
);
1308 else if (!_M_impl
._M_key_compare(_S_key((++__after
)._M_node
),
1309 _KeyOfValue()(__v
)))
1311 if (_S_right(__position
._M_node
) == 0)
1312 return _M_insert_(0, __position
._M_node
, __v
);
1314 return _M_insert_(__after
._M_node
, __after
._M_node
, __v
);
1317 return _M_insert_equal_lower(__v
);
1321 template<typename _Key
, typename _Val
, typename _KoV
,
1322 typename _Cmp
, typename _Alloc
>
1325 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
1326 _M_insert_unique(_II __first
, _II __last
)
1328 for (; __first
!= __last
; ++__first
)
1329 _M_insert_unique_(end(), *__first
);
1332 template<typename _Key
, typename _Val
, typename _KoV
,
1333 typename _Cmp
, typename _Alloc
>
1336 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
1337 _M_insert_equal(_II __first
, _II __last
)
1339 for (; __first
!= __last
; ++__first
)
1340 _M_insert_equal_(end(), *__first
);
1343 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1344 typename _Compare
, typename _Alloc
>
1346 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1347 erase(iterator __position
)
1350 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1351 (__position
._M_node
,
1352 this->_M_impl
._M_header
));
1353 _M_destroy_node(__y
);
1354 --_M_impl
._M_node_count
;
1357 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1358 typename _Compare
, typename _Alloc
>
1360 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1361 erase(const_iterator __position
)
1364 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1365 (const_cast<_Base_ptr
>(__position
._M_node
),
1366 this->_M_impl
._M_header
));
1367 _M_destroy_node(__y
);
1368 --_M_impl
._M_node_count
;
1371 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1372 typename _Compare
, typename _Alloc
>
1373 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
1374 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1375 erase(const _Key
& __x
)
1377 pair
<iterator
, iterator
> __p
= equal_range(__x
);
1378 const size_type __old_size
= size();
1379 erase(__p
.first
, __p
.second
);
1380 return __old_size
- size();
1383 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1384 typename _Compare
, typename _Alloc
>
1386 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1387 erase(iterator __first
, iterator __last
)
1389 if (__first
== begin() && __last
== end())
1392 while (__first
!= __last
)
1396 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1397 typename _Compare
, typename _Alloc
>
1399 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1400 erase(const_iterator __first
, const_iterator __last
)
1402 if (__first
== begin() && __last
== end())
1405 while (__first
!= __last
)
1409 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1410 typename _Compare
, typename _Alloc
>
1412 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1413 erase(const _Key
* __first
, const _Key
* __last
)
1415 while (__first
!= __last
)
1419 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1420 typename _Compare
, typename _Alloc
>
1421 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1422 _Compare
, _Alloc
>::iterator
1423 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1424 find(const _Key
& __k
)
1426 iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
1427 return (__j
== end()
1428 || _M_impl
._M_key_compare(__k
,
1429 _S_key(__j
._M_node
))) ? end() : __j
;
1432 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1433 typename _Compare
, typename _Alloc
>
1434 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1435 _Compare
, _Alloc
>::const_iterator
1436 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1437 find(const _Key
& __k
) const
1439 const_iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
1440 return (__j
== end()
1441 || _M_impl
._M_key_compare(__k
,
1442 _S_key(__j
._M_node
))) ? end() : __j
;
1445 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1446 typename _Compare
, typename _Alloc
>
1447 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
1448 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1449 count(const _Key
& __k
) const
1451 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
1452 const size_type __n
= std::distance(__p
.first
, __p
.second
);
1457 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
1458 const _Rb_tree_node_base
* __root
);
1460 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1461 typename _Compare
, typename _Alloc
>
1463 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
1465 if (_M_impl
._M_node_count
== 0 || begin() == end())
1466 return _M_impl
._M_node_count
== 0 && begin() == end()
1467 && this->_M_impl
._M_header
._M_left
== _M_end()
1468 && this->_M_impl
._M_header
._M_right
== _M_end();
1470 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
1471 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
1473 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
1474 _Const_Link_type __L
= _S_left(__x
);
1475 _Const_Link_type __R
= _S_right(__x
);
1477 if (__x
->_M_color
== _S_red
)
1478 if ((__L
&& __L
->_M_color
== _S_red
)
1479 || (__R
&& __R
->_M_color
== _S_red
))
1482 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
1484 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
1487 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
1491 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1493 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1498 _GLIBCXX_END_NAMESPACE