1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
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
;
139 _Rb_tree_increment(_Rb_tree_node_base
* __x
);
141 const _Rb_tree_node_base
*
142 _Rb_tree_increment(const _Rb_tree_node_base
* __x
);
145 _Rb_tree_decrement(_Rb_tree_node_base
* __x
);
147 const _Rb_tree_node_base
*
148 _Rb_tree_decrement(const _Rb_tree_node_base
* __x
);
150 template<typename _Tp
>
151 struct _Rb_tree_iterator
153 typedef _Tp value_type
;
154 typedef _Tp
& reference
;
155 typedef _Tp
* pointer
;
157 typedef bidirectional_iterator_tag iterator_category
;
158 typedef ptrdiff_t difference_type
;
160 typedef _Rb_tree_iterator
<_Tp
> _Self
;
161 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
162 typedef _Rb_tree_node
<_Tp
>* _Link_type
;
168 _Rb_tree_iterator(_Link_type __x
)
173 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
177 { return &static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
182 _M_node
= _Rb_tree_increment(_M_node
);
190 _M_node
= _Rb_tree_increment(_M_node
);
197 _M_node
= _Rb_tree_decrement(_M_node
);
205 _M_node
= _Rb_tree_decrement(_M_node
);
210 operator==(const _Self
& __x
) const
211 { return _M_node
== __x
._M_node
; }
214 operator!=(const _Self
& __x
) const
215 { return _M_node
!= __x
._M_node
; }
220 template<typename _Tp
>
221 struct _Rb_tree_const_iterator
223 typedef _Tp value_type
;
224 typedef const _Tp
& reference
;
225 typedef const _Tp
* pointer
;
227 typedef _Rb_tree_iterator
<_Tp
> iterator
;
229 typedef bidirectional_iterator_tag iterator_category
;
230 typedef ptrdiff_t difference_type
;
232 typedef _Rb_tree_const_iterator
<_Tp
> _Self
;
233 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr
;
234 typedef const _Rb_tree_node
<_Tp
>* _Link_type
;
236 _Rb_tree_const_iterator()
240 _Rb_tree_const_iterator(_Link_type __x
)
243 _Rb_tree_const_iterator(const iterator
& __it
)
244 : _M_node(__it
._M_node
) { }
248 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
252 { return &static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
257 _M_node
= _Rb_tree_increment(_M_node
);
265 _M_node
= _Rb_tree_increment(_M_node
);
272 _M_node
= _Rb_tree_decrement(_M_node
);
280 _M_node
= _Rb_tree_decrement(_M_node
);
285 operator==(const _Self
& __x
) const
286 { return _M_node
== __x
._M_node
; }
289 operator!=(const _Self
& __x
) const
290 { return _M_node
!= __x
._M_node
; }
295 template<typename _Val
>
297 operator==(const _Rb_tree_iterator
<_Val
>& __x
,
298 const _Rb_tree_const_iterator
<_Val
>& __y
)
299 { return __x
._M_node
== __y
._M_node
; }
301 template<typename _Val
>
303 operator!=(const _Rb_tree_iterator
<_Val
>& __x
,
304 const _Rb_tree_const_iterator
<_Val
>& __y
)
305 { return __x
._M_node
!= __y
._M_node
; }
308 _Rb_tree_insert_and_rebalance(const bool __insert_left
,
309 _Rb_tree_node_base
* __x
,
310 _Rb_tree_node_base
* __p
,
311 _Rb_tree_node_base
& __header
);
314 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
315 _Rb_tree_node_base
& __header
);
318 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
319 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
322 typedef typename
_Alloc::template rebind
<_Rb_tree_node
<_Val
> >::other
326 typedef _Rb_tree_node_base
* _Base_ptr
;
327 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
330 typedef _Key key_type
;
331 typedef _Val value_type
;
332 typedef value_type
* pointer
;
333 typedef const value_type
* const_pointer
;
334 typedef value_type
& reference
;
335 typedef const value_type
& const_reference
;
336 typedef _Rb_tree_node
<_Val
>* _Link_type
;
337 typedef const _Rb_tree_node
<_Val
>* _Const_Link_type
;
338 typedef size_t size_type
;
339 typedef ptrdiff_t difference_type
;
340 typedef _Alloc allocator_type
;
343 _M_get_Node_allocator()
344 { return *static_cast<_Node_allocator
*>(&this->_M_impl
); }
346 const _Node_allocator
&
347 _M_get_Node_allocator() const
348 { return *static_cast<const _Node_allocator
*>(&this->_M_impl
); }
351 get_allocator() const
352 { return allocator_type(_M_get_Node_allocator()); }
357 { return _M_impl
._Node_allocator::allocate(1); }
360 _M_put_node(_Link_type __p
)
361 { _M_impl
._Node_allocator::deallocate(__p
, 1); }
364 _M_create_node(const value_type
& __x
)
366 _Link_type __tmp
= _M_get_node();
368 { get_allocator().construct(&__tmp
->_M_value_field
, __x
); }
372 __throw_exception_again
;
378 _M_clone_node(_Const_Link_type __x
)
380 _Link_type __tmp
= _M_create_node(__x
->_M_value_field
);
381 __tmp
->_M_color
= __x
->_M_color
;
388 _M_destroy_node(_Link_type __p
)
390 get_allocator().destroy(&__p
->_M_value_field
);
395 template<typename _Key_compare
,
396 bool _Is_pod_comparator
= __is_pod(_Key_compare
)>
397 struct _Rb_tree_impl
: public _Node_allocator
399 _Key_compare _M_key_compare
;
400 _Rb_tree_node_base _M_header
;
401 size_type _M_node_count
; // Keeps track of size of tree.
404 : _Node_allocator(), _M_key_compare(), _M_header(),
408 _Rb_tree_impl(const _Key_compare
& __comp
, const _Node_allocator
& __a
)
409 : _Node_allocator(__a
), _M_key_compare(__comp
), _M_header(),
417 this->_M_header
._M_color
= _S_red
;
418 this->_M_header
._M_parent
= 0;
419 this->_M_header
._M_left
= &this->_M_header
;
420 this->_M_header
._M_right
= &this->_M_header
;
424 _Rb_tree_impl
<_Compare
> _M_impl
;
429 { return this->_M_impl
._M_header
._M_parent
; }
433 { return this->_M_impl
._M_header
._M_parent
; }
437 { return this->_M_impl
._M_header
._M_left
; }
441 { return this->_M_impl
._M_header
._M_left
; }
445 { return this->_M_impl
._M_header
._M_right
; }
449 { return this->_M_impl
._M_header
._M_right
; }
453 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
458 return static_cast<_Const_Link_type
>
459 (this->_M_impl
._M_header
._M_parent
);
464 { return static_cast<_Link_type
>(&this->_M_impl
._M_header
); }
468 { return static_cast<_Const_Link_type
>(&this->_M_impl
._M_header
); }
470 static const_reference
471 _S_value(_Const_Link_type __x
)
472 { return __x
->_M_value_field
; }
475 _S_key(_Const_Link_type __x
)
476 { return _KeyOfValue()(_S_value(__x
)); }
479 _S_left(_Base_ptr __x
)
480 { return static_cast<_Link_type
>(__x
->_M_left
); }
482 static _Const_Link_type
483 _S_left(_Const_Base_ptr __x
)
484 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
487 _S_right(_Base_ptr __x
)
488 { return static_cast<_Link_type
>(__x
->_M_right
); }
490 static _Const_Link_type
491 _S_right(_Const_Base_ptr __x
)
492 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
494 static const_reference
495 _S_value(_Const_Base_ptr __x
)
496 { return static_cast<_Const_Link_type
>(__x
)->_M_value_field
; }
499 _S_key(_Const_Base_ptr __x
)
500 { return _KeyOfValue()(_S_value(__x
)); }
503 _S_minimum(_Base_ptr __x
)
504 { return _Rb_tree_node_base::_S_minimum(__x
); }
506 static _Const_Base_ptr
507 _S_minimum(_Const_Base_ptr __x
)
508 { return _Rb_tree_node_base::_S_minimum(__x
); }
511 _S_maximum(_Base_ptr __x
)
512 { return _Rb_tree_node_base::_S_maximum(__x
); }
514 static _Const_Base_ptr
515 _S_maximum(_Const_Base_ptr __x
)
516 { return _Rb_tree_node_base::_S_maximum(__x
); }
519 typedef _Rb_tree_iterator
<value_type
> iterator
;
520 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
522 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
523 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
527 _M_insert_(_Const_Base_ptr __x
, _Const_Base_ptr __y
,
528 const value_type
& __v
);
530 // _GLIBCXX_RESOLVE_LIB_DEFECTS
531 // 233. Insertion hints in associative containers.
533 _M_insert_lower(_Base_ptr __x
, _Base_ptr __y
, const value_type
& __v
);
536 _M_insert_equal_lower(const value_type
& __x
);
539 _M_copy(_Const_Link_type __x
, _Link_type __p
);
542 _M_erase(_Link_type __x
);
545 _M_lower_bound(_Link_type __x
, _Link_type __y
,
549 _M_lower_bound(_Const_Link_type __x
, _Const_Link_type __y
,
550 const _Key
& __k
) const;
553 _M_upper_bound(_Link_type __x
, _Link_type __y
,
557 _M_upper_bound(_Const_Link_type __x
, _Const_Link_type __y
,
558 const _Key
& __k
) const;
561 // allocation/deallocation
564 _Rb_tree(const _Compare
& __comp
,
565 const allocator_type
& __a
= allocator_type())
566 : _M_impl(__comp
, __a
) { }
568 _Rb_tree(const _Rb_tree
& __x
)
569 : _M_impl(__x
._M_impl
._M_key_compare
, __x
._M_get_Node_allocator())
571 if (__x
._M_root() != 0)
573 _M_root() = _M_copy(__x
._M_begin(), _M_end());
574 _M_leftmost() = _S_minimum(_M_root());
575 _M_rightmost() = _S_maximum(_M_root());
576 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
580 #ifdef __GXX_EXPERIMENTAL_CXX0X__
581 _Rb_tree(_Rb_tree
&& __x
);
585 { _M_erase(_M_begin()); }
588 operator=(const _Rb_tree
& __x
);
593 { return _M_impl
._M_key_compare
; }
598 return iterator(static_cast<_Link_type
>
599 (this->_M_impl
._M_header
._M_left
));
605 return const_iterator(static_cast<_Const_Link_type
>
606 (this->_M_impl
._M_header
._M_left
));
611 { return iterator(static_cast<_Link_type
>(&this->_M_impl
._M_header
)); }
616 return const_iterator(static_cast<_Const_Link_type
>
617 (&this->_M_impl
._M_header
));
622 { return reverse_iterator(end()); }
624 const_reverse_iterator
626 { return const_reverse_iterator(end()); }
630 { return reverse_iterator(begin()); }
632 const_reverse_iterator
634 { return const_reverse_iterator(begin()); }
638 { return _M_impl
._M_node_count
== 0; }
642 { return _M_impl
._M_node_count
; }
646 { return _M_get_Node_allocator().max_size(); }
649 #ifdef __GXX_EXPERIMENTAL_CXX0X__
650 swap(_Rb_tree
&& __t
);
657 _M_insert_unique(const value_type
& __x
);
660 _M_insert_equal(const value_type
& __x
);
663 _M_insert_unique_(const_iterator __position
, const value_type
& __x
);
666 _M_insert_equal_(const_iterator __position
, const value_type
& __x
);
668 template<typename _InputIterator
>
670 _M_insert_unique(_InputIterator __first
, _InputIterator __last
);
672 template<typename _InputIterator
>
674 _M_insert_equal(_InputIterator __first
, _InputIterator __last
);
677 erase(iterator __position
);
680 erase(const_iterator __position
);
683 erase(const key_type
& __x
);
686 erase(iterator __first
, iterator __last
);
689 erase(const_iterator __first
, const_iterator __last
);
692 erase(const key_type
* __first
, const key_type
* __last
);
697 _M_erase(_M_begin());
698 _M_leftmost() = _M_end();
700 _M_rightmost() = _M_end();
701 _M_impl
._M_node_count
= 0;
706 find(const key_type
& __k
);
709 find(const key_type
& __k
) const;
712 count(const key_type
& __k
) const;
715 lower_bound(const key_type
& __k
)
716 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
719 lower_bound(const key_type
& __k
) const
720 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
723 upper_bound(const key_type
& __k
)
724 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
727 upper_bound(const key_type
& __k
) const
728 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
730 pair
<iterator
, iterator
>
731 equal_range(const key_type
& __k
);
733 pair
<const_iterator
, const_iterator
>
734 equal_range(const key_type
& __k
) const;
741 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
742 typename _Compare
, typename _Alloc
>
744 operator==(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
745 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
747 return __x
.size() == __y
.size()
748 && std::equal(__x
.begin(), __x
.end(), __y
.begin());
751 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
752 typename _Compare
, typename _Alloc
>
754 operator<(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
755 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
757 return std::lexicographical_compare(__x
.begin(), __x
.end(),
758 __y
.begin(), __y
.end());
761 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
762 typename _Compare
, typename _Alloc
>
764 operator!=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
765 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
766 { return !(__x
== __y
); }
768 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
769 typename _Compare
, typename _Alloc
>
771 operator>(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
772 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
773 { return __y
< __x
; }
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
)
780 { return !(__y
< __x
); }
782 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
783 typename _Compare
, typename _Alloc
>
785 operator>=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
786 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
787 { return !(__x
< __y
); }
789 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
790 typename _Compare
, typename _Alloc
>
792 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
793 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
796 #ifdef __GXX_EXPERIMENTAL_CXX0X__
797 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
798 typename _Compare
, typename _Alloc
>
799 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
800 _Rb_tree(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&& __x
)
801 : _M_impl(__x
._M_impl
._M_key_compare
, __x
._M_get_Node_allocator())
803 if (__x
._M_root() != 0)
805 _M_root() = __x
._M_root();
806 _M_leftmost() = __x
._M_leftmost();
807 _M_rightmost() = __x
._M_rightmost();
808 _M_root()->_M_parent
= _M_end();
811 __x
._M_leftmost() = __x
._M_end();
812 __x
._M_rightmost() = __x
._M_end();
814 this->_M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
815 __x
._M_impl
._M_node_count
= 0;
820 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
821 typename _Compare
, typename _Alloc
>
822 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
823 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
824 operator=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
)
828 // Note that _Key may be a constant type.
830 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
831 if (__x
._M_root() != 0)
833 _M_root() = _M_copy(__x
._M_begin(), _M_end());
834 _M_leftmost() = _S_minimum(_M_root());
835 _M_rightmost() = _S_maximum(_M_root());
836 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
842 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
843 typename _Compare
, typename _Alloc
>
844 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
845 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
846 _M_insert_(_Const_Base_ptr __x
, _Const_Base_ptr __p
, const _Val
& __v
)
848 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
849 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
852 _Link_type __z
= _M_create_node(__v
);
854 _Rb_tree_insert_and_rebalance(__insert_left
, __z
,
855 const_cast<_Base_ptr
>(__p
),
856 this->_M_impl
._M_header
);
857 ++_M_impl
._M_node_count
;
858 return iterator(__z
);
861 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
862 typename _Compare
, typename _Alloc
>
863 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
864 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
865 _M_insert_lower(_Base_ptr __x
, _Base_ptr __p
, const _Val
& __v
)
867 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
868 || !_M_impl
._M_key_compare(_S_key(__p
),
869 _KeyOfValue()(__v
)));
871 _Link_type __z
= _M_create_node(__v
);
873 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
874 this->_M_impl
._M_header
);
875 ++_M_impl
._M_node_count
;
876 return iterator(__z
);
879 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
880 typename _Compare
, typename _Alloc
>
881 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
882 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
883 _M_insert_equal_lower(const _Val
& __v
)
885 _Link_type __x
= _M_begin();
886 _Link_type __y
= _M_end();
890 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _KeyOfValue()(__v
)) ?
891 _S_left(__x
) : _S_right(__x
);
893 return _M_insert_lower(__x
, __y
, __v
);
896 template<typename _Key
, typename _Val
, typename _KoV
,
897 typename _Compare
, typename _Alloc
>
898 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
899 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
900 _M_copy(_Const_Link_type __x
, _Link_type __p
)
902 // Structural copy. __x and __p must be non-null.
903 _Link_type __top
= _M_clone_node(__x
);
904 __top
->_M_parent
= __p
;
909 __top
->_M_right
= _M_copy(_S_right(__x
), __top
);
915 _Link_type __y
= _M_clone_node(__x
);
917 __y
->_M_parent
= __p
;
919 __y
->_M_right
= _M_copy(_S_right(__x
), __y
);
927 __throw_exception_again
;
932 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
933 typename _Compare
, typename _Alloc
>
935 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
936 _M_erase(_Link_type __x
)
938 // Erase without rebalancing.
941 _M_erase(_S_right(__x
));
942 _Link_type __y
= _S_left(__x
);
943 _M_destroy_node(__x
);
948 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
949 typename _Compare
, typename _Alloc
>
950 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
951 _Compare
, _Alloc
>::iterator
952 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
953 _M_lower_bound(_Link_type __x
, _Link_type __y
,
957 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
958 __y
= __x
, __x
= _S_left(__x
);
961 return iterator(__y
);
964 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
965 typename _Compare
, typename _Alloc
>
966 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
967 _Compare
, _Alloc
>::const_iterator
968 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
969 _M_lower_bound(_Const_Link_type __x
, _Const_Link_type __y
,
970 const _Key
& __k
) const
973 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
974 __y
= __x
, __x
= _S_left(__x
);
977 return const_iterator(__y
);
980 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
981 typename _Compare
, typename _Alloc
>
982 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
983 _Compare
, _Alloc
>::iterator
984 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
985 _M_upper_bound(_Link_type __x
, _Link_type __y
,
989 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
990 __y
= __x
, __x
= _S_left(__x
);
993 return iterator(__y
);
996 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
997 typename _Compare
, typename _Alloc
>
998 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
999 _Compare
, _Alloc
>::const_iterator
1000 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1001 _M_upper_bound(_Const_Link_type __x
, _Const_Link_type __y
,
1002 const _Key
& __k
) const
1005 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1006 __y
= __x
, __x
= _S_left(__x
);
1008 __x
= _S_right(__x
);
1009 return const_iterator(__y
);
1012 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1013 typename _Compare
, typename _Alloc
>
1014 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1015 _Compare
, _Alloc
>::iterator
,
1016 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1017 _Compare
, _Alloc
>::iterator
>
1018 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1019 equal_range(const _Key
& __k
)
1021 _Link_type __x
= _M_begin();
1022 _Link_type __y
= _M_end();
1025 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1026 __x
= _S_right(__x
);
1027 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1028 __y
= __x
, __x
= _S_left(__x
);
1031 _Link_type
__xu(__x
), __yu(__y
);
1032 __y
= __x
, __x
= _S_left(__x
);
1033 __xu
= _S_right(__xu
);
1034 return pair
<iterator
,
1035 iterator
>(_M_lower_bound(__x
, __y
, __k
),
1036 _M_upper_bound(__xu
, __yu
, __k
));
1039 return pair
<iterator
, iterator
>(iterator(__y
),
1043 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1044 typename _Compare
, typename _Alloc
>
1045 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1046 _Compare
, _Alloc
>::const_iterator
,
1047 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1048 _Compare
, _Alloc
>::const_iterator
>
1049 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1050 equal_range(const _Key
& __k
) const
1052 _Const_Link_type __x
= _M_begin();
1053 _Const_Link_type __y
= _M_end();
1056 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1057 __x
= _S_right(__x
);
1058 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1059 __y
= __x
, __x
= _S_left(__x
);
1062 _Const_Link_type
__xu(__x
), __yu(__y
);
1063 __y
= __x
, __x
= _S_left(__x
);
1064 __xu
= _S_right(__xu
);
1065 return pair
<const_iterator
,
1066 const_iterator
>(_M_lower_bound(__x
, __y
, __k
),
1067 _M_upper_bound(__xu
, __yu
, __k
));
1070 return pair
<const_iterator
, const_iterator
>(const_iterator(__y
),
1071 const_iterator(__y
));
1074 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1075 typename _Compare
, typename _Alloc
>
1077 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1078 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1079 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&& __t
)
1081 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __t
)
1086 if (__t
._M_root() != 0)
1088 _M_root() = __t
._M_root();
1089 _M_leftmost() = __t
._M_leftmost();
1090 _M_rightmost() = __t
._M_rightmost();
1091 _M_root()->_M_parent
= _M_end();
1094 __t
._M_leftmost() = __t
._M_end();
1095 __t
._M_rightmost() = __t
._M_end();
1098 else if (__t
._M_root() == 0)
1100 __t
._M_root() = _M_root();
1101 __t
._M_leftmost() = _M_leftmost();
1102 __t
._M_rightmost() = _M_rightmost();
1103 __t
._M_root()->_M_parent
= __t
._M_end();
1106 _M_leftmost() = _M_end();
1107 _M_rightmost() = _M_end();
1111 std::swap(_M_root(),__t
._M_root());
1112 std::swap(_M_leftmost(),__t
._M_leftmost());
1113 std::swap(_M_rightmost(),__t
._M_rightmost());
1115 _M_root()->_M_parent
= _M_end();
1116 __t
._M_root()->_M_parent
= __t
._M_end();
1118 // No need to swap header's color as it does not change.
1119 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
1120 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
1122 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1123 // 431. Swapping containers with unequal allocators.
1124 std::__alloc_swap
<_Node_allocator
>::
1125 _S_do_it(_M_get_Node_allocator(), __t
._M_get_Node_allocator());
1128 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1129 typename _Compare
, typename _Alloc
>
1130 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1131 _Compare
, _Alloc
>::iterator
, bool>
1132 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1133 _M_insert_unique(const _Val
& __v
)
1135 _Link_type __x
= _M_begin();
1136 _Link_type __y
= _M_end();
1141 __comp
= _M_impl
._M_key_compare(_KeyOfValue()(__v
), _S_key(__x
));
1142 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
1144 iterator __j
= iterator(__y
);
1148 return pair
<iterator
, bool>(_M_insert_(__x
, __y
, __v
), true);
1152 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), _KeyOfValue()(__v
)))
1153 return pair
<iterator
, bool>(_M_insert_(__x
, __y
, __v
), true);
1154 return pair
<iterator
, bool>(__j
, false);
1157 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1158 typename _Compare
, typename _Alloc
>
1159 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1160 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1161 _M_insert_equal(const _Val
& __v
)
1163 _Link_type __x
= _M_begin();
1164 _Link_type __y
= _M_end();
1168 __x
= _M_impl
._M_key_compare(_KeyOfValue()(__v
), _S_key(__x
)) ?
1169 _S_left(__x
) : _S_right(__x
);
1171 return _M_insert_(__x
, __y
, __v
);
1174 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1175 typename _Compare
, typename _Alloc
>
1176 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1177 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1178 _M_insert_unique_(const_iterator __position
, const _Val
& __v
)
1181 if (__position
._M_node
== _M_end())
1184 && _M_impl
._M_key_compare(_S_key(_M_rightmost()),
1185 _KeyOfValue()(__v
)))
1186 return _M_insert_(0, _M_rightmost(), __v
);
1188 return _M_insert_unique(__v
).first
;
1190 else if (_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1191 _S_key(__position
._M_node
)))
1193 // First, try before...
1194 const_iterator __before
= __position
;
1195 if (__position
._M_node
== _M_leftmost()) // begin()
1196 return _M_insert_(_M_leftmost(), _M_leftmost(), __v
);
1197 else if (_M_impl
._M_key_compare(_S_key((--__before
)._M_node
),
1198 _KeyOfValue()(__v
)))
1200 if (_S_right(__before
._M_node
) == 0)
1201 return _M_insert_(0, __before
._M_node
, __v
);
1203 return _M_insert_(__position
._M_node
,
1204 __position
._M_node
, __v
);
1207 return _M_insert_unique(__v
).first
;
1209 else if (_M_impl
._M_key_compare(_S_key(__position
._M_node
),
1210 _KeyOfValue()(__v
)))
1212 // ... then try after.
1213 const_iterator __after
= __position
;
1214 if (__position
._M_node
== _M_rightmost())
1215 return _M_insert_(0, _M_rightmost(), __v
);
1216 else if (_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1217 _S_key((++__after
)._M_node
)))
1219 if (_S_right(__position
._M_node
) == 0)
1220 return _M_insert_(0, __position
._M_node
, __v
);
1222 return _M_insert_(__after
._M_node
, __after
._M_node
, __v
);
1225 return _M_insert_unique(__v
).first
;
1229 return iterator(static_cast<_Link_type
>
1230 (const_cast<_Base_ptr
>(__position
._M_node
)));
1233 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1234 typename _Compare
, typename _Alloc
>
1235 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1236 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1237 _M_insert_equal_(const_iterator __position
, const _Val
& __v
)
1240 if (__position
._M_node
== _M_end())
1243 && !_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1244 _S_key(_M_rightmost())))
1245 return _M_insert_(0, _M_rightmost(), __v
);
1247 return _M_insert_equal(__v
);
1249 else if (!_M_impl
._M_key_compare(_S_key(__position
._M_node
),
1250 _KeyOfValue()(__v
)))
1252 // First, try before...
1253 const_iterator __before
= __position
;
1254 if (__position
._M_node
== _M_leftmost()) // begin()
1255 return _M_insert_(_M_leftmost(), _M_leftmost(), __v
);
1256 else if (!_M_impl
._M_key_compare(_KeyOfValue()(__v
),
1257 _S_key((--__before
)._M_node
)))
1259 if (_S_right(__before
._M_node
) == 0)
1260 return _M_insert_(0, __before
._M_node
, __v
);
1262 return _M_insert_(__position
._M_node
,
1263 __position
._M_node
, __v
);
1266 return _M_insert_equal(__v
);
1270 // ... then try after.
1271 const_iterator __after
= __position
;
1272 if (__position
._M_node
== _M_rightmost())
1273 return _M_insert_(0, _M_rightmost(), __v
);
1274 else if (!_M_impl
._M_key_compare(_S_key((++__after
)._M_node
),
1275 _KeyOfValue()(__v
)))
1277 if (_S_right(__position
._M_node
) == 0)
1278 return _M_insert_(0, __position
._M_node
, __v
);
1280 return _M_insert_(__after
._M_node
, __after
._M_node
, __v
);
1283 return _M_insert_equal_lower(__v
);
1287 template<typename _Key
, typename _Val
, typename _KoV
,
1288 typename _Cmp
, typename _Alloc
>
1291 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
1292 _M_insert_unique(_II __first
, _II __last
)
1294 for (; __first
!= __last
; ++__first
)
1295 _M_insert_unique_(end(), *__first
);
1298 template<typename _Key
, typename _Val
, typename _KoV
,
1299 typename _Cmp
, typename _Alloc
>
1302 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
1303 _M_insert_equal(_II __first
, _II __last
)
1305 for (; __first
!= __last
; ++__first
)
1306 _M_insert_equal_(end(), *__first
);
1309 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1310 typename _Compare
, typename _Alloc
>
1312 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1313 erase(iterator __position
)
1316 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1317 (__position
._M_node
,
1318 this->_M_impl
._M_header
));
1319 _M_destroy_node(__y
);
1320 --_M_impl
._M_node_count
;
1323 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1324 typename _Compare
, typename _Alloc
>
1326 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1327 erase(const_iterator __position
)
1330 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1331 (const_cast<_Base_ptr
>(__position
._M_node
),
1332 this->_M_impl
._M_header
));
1333 _M_destroy_node(__y
);
1334 --_M_impl
._M_node_count
;
1337 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1338 typename _Compare
, typename _Alloc
>
1339 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
1340 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1341 erase(const _Key
& __x
)
1343 pair
<iterator
, iterator
> __p
= equal_range(__x
);
1344 const size_type __old_size
= size();
1345 erase(__p
.first
, __p
.second
);
1346 return __old_size
- size();
1349 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1350 typename _Compare
, typename _Alloc
>
1352 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1353 erase(iterator __first
, iterator __last
)
1355 if (__first
== begin() && __last
== end())
1358 while (__first
!= __last
)
1362 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1363 typename _Compare
, typename _Alloc
>
1365 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1366 erase(const_iterator __first
, const_iterator __last
)
1368 if (__first
== begin() && __last
== end())
1371 while (__first
!= __last
)
1375 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1376 typename _Compare
, typename _Alloc
>
1378 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1379 erase(const _Key
* __first
, const _Key
* __last
)
1381 while (__first
!= __last
)
1385 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1386 typename _Compare
, typename _Alloc
>
1387 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1388 _Compare
, _Alloc
>::iterator
1389 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1390 find(const _Key
& __k
)
1392 iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
1393 return (__j
== end()
1394 || _M_impl
._M_key_compare(__k
,
1395 _S_key(__j
._M_node
))) ? end() : __j
;
1398 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1399 typename _Compare
, typename _Alloc
>
1400 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1401 _Compare
, _Alloc
>::const_iterator
1402 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1403 find(const _Key
& __k
) const
1405 const_iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
1406 return (__j
== end()
1407 || _M_impl
._M_key_compare(__k
,
1408 _S_key(__j
._M_node
))) ? end() : __j
;
1411 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1412 typename _Compare
, typename _Alloc
>
1413 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
1414 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1415 count(const _Key
& __k
) const
1417 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
1418 const size_type __n
= std::distance(__p
.first
, __p
.second
);
1423 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
1424 const _Rb_tree_node_base
* __root
);
1426 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1427 typename _Compare
, typename _Alloc
>
1429 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
1431 if (_M_impl
._M_node_count
== 0 || begin() == end())
1432 return _M_impl
._M_node_count
== 0 && begin() == end()
1433 && this->_M_impl
._M_header
._M_left
== _M_end()
1434 && this->_M_impl
._M_header
._M_right
== _M_end();
1436 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
1437 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
1439 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
1440 _Const_Link_type __L
= _S_left(__x
);
1441 _Const_Link_type __R
= _S_right(__x
);
1443 if (__x
->_M_color
== _S_red
)
1444 if ((__L
&& __L
->_M_color
== _S_red
)
1445 || (__R
&& __R
->_M_color
== _S_red
))
1448 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
1450 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
1453 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
1457 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1459 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1464 _GLIBCXX_END_NAMESPACE