1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
32 * Copyright (c) 1996,1997
33 * Silicon Graphics Computer Systems, Inc.
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Silicon Graphics makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
45 * Hewlett-Packard Company
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Hewlett-Packard Company makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
59 * This is an internal header file, included by other library headers.
60 * You should not attempt to use it directly.
66 #include <bits/stl_algobase.h>
67 #include <bits/allocator.h>
68 #include <bits/stl_construct.h>
69 #include <bits/stl_function.h>
70 #include <bits/cpp_type_traits.h>
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
;
164 _Rb_tree_iterator() { }
166 _Rb_tree_iterator(_Link_type __x
)
171 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
175 { return &static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
180 _M_node
= _Rb_tree_increment(_M_node
);
188 _M_node
= _Rb_tree_increment(_M_node
);
195 _M_node
= _Rb_tree_decrement(_M_node
);
203 _M_node
= _Rb_tree_decrement(_M_node
);
208 operator==(const _Self
& __x
) const
209 { return _M_node
== __x
._M_node
; }
212 operator!=(const _Self
& __x
) const
213 { return _M_node
!= __x
._M_node
; }
218 template<typename _Tp
>
219 struct _Rb_tree_const_iterator
221 typedef _Tp value_type
;
222 typedef const _Tp
& reference
;
223 typedef const _Tp
* pointer
;
225 typedef _Rb_tree_iterator
<_Tp
> iterator
;
227 typedef bidirectional_iterator_tag iterator_category
;
228 typedef ptrdiff_t difference_type
;
230 typedef _Rb_tree_const_iterator
<_Tp
> _Self
;
231 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr
;
232 typedef const _Rb_tree_node
<_Tp
>* _Link_type
;
234 _Rb_tree_const_iterator() { }
236 _Rb_tree_const_iterator(_Link_type __x
)
239 _Rb_tree_const_iterator(const iterator
& __it
)
240 : _M_node(__it
._M_node
) { }
244 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
248 { return &static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
253 _M_node
= _Rb_tree_increment(_M_node
);
261 _M_node
= _Rb_tree_increment(_M_node
);
268 _M_node
= _Rb_tree_decrement(_M_node
);
276 _M_node
= _Rb_tree_decrement(_M_node
);
281 operator==(const _Self
& __x
) const
282 { return _M_node
== __x
._M_node
; }
285 operator!=(const _Self
& __x
) const
286 { return _M_node
!= __x
._M_node
; }
291 template<typename _Val
>
293 operator==(const _Rb_tree_iterator
<_Val
>& __x
,
294 const _Rb_tree_const_iterator
<_Val
>& __y
)
295 { return __x
._M_node
== __y
._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
; }
304 _Rb_tree_rotate_left(_Rb_tree_node_base
* const __x
,
305 _Rb_tree_node_base
*& __root
);
308 _Rb_tree_rotate_right(_Rb_tree_node_base
* const __x
,
309 _Rb_tree_node_base
*& __root
);
312 _Rb_tree_insert_and_rebalance(const bool __insert_left
,
313 _Rb_tree_node_base
* __x
,
314 _Rb_tree_node_base
* __p
,
315 _Rb_tree_node_base
& __header
);
318 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
319 _Rb_tree_node_base
& __header
);
322 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
323 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
326 typedef typename
_Alloc::template rebind
<_Rb_tree_node
<_Val
> >::other
330 typedef _Rb_tree_node_base
* _Base_ptr
;
331 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
332 typedef _Rb_tree_node
<_Val
> _Rb_tree_node
;
335 typedef _Key key_type
;
336 typedef _Val value_type
;
337 typedef value_type
* pointer
;
338 typedef const value_type
* const_pointer
;
339 typedef value_type
& reference
;
340 typedef const value_type
& const_reference
;
341 typedef _Rb_tree_node
* _Link_type
;
342 typedef const _Rb_tree_node
* _Const_Link_type
;
343 typedef size_t size_type
;
344 typedef ptrdiff_t difference_type
;
345 typedef _Alloc allocator_type
;
348 get_allocator() const
349 { return *static_cast<const _Node_allocator
*>(&this->_M_impl
); }
354 { return _M_impl
._Node_allocator::allocate(1); }
357 _M_put_node(_Rb_tree_node
* __p
)
358 { _M_impl
._Node_allocator::deallocate(__p
, 1); }
361 _M_create_node(const value_type
& __x
)
363 _Link_type __tmp
= _M_get_node();
365 { get_allocator().construct(&__tmp
->_M_value_field
, __x
); }
369 __throw_exception_again
;
375 _M_clone_node(_Const_Link_type __x
)
377 _Link_type __tmp
= _M_create_node(__x
->_M_value_field
);
378 __tmp
->_M_color
= __x
->_M_color
;
385 destroy_node(_Link_type __p
)
387 get_allocator().destroy(&__p
->_M_value_field
);
392 template<typename _Key_compare
,
393 bool _Is_pod_comparator
= std::__is_pod
<_Key_compare
>::_M_type
>
394 struct _Rb_tree_impl
: public _Node_allocator
396 _Key_compare _M_key_compare
;
397 _Rb_tree_node_base _M_header
;
398 size_type _M_node_count
; // Keeps track of size of tree.
400 _Rb_tree_impl(const _Node_allocator
& __a
= _Node_allocator(),
401 const _Key_compare
& __comp
= _Key_compare())
402 : _Node_allocator(__a
), _M_key_compare(__comp
), _M_node_count(0)
404 this->_M_header
._M_color
= _S_red
;
405 this->_M_header
._M_parent
= 0;
406 this->_M_header
._M_left
= &this->_M_header
;
407 this->_M_header
._M_right
= &this->_M_header
;
411 // Specialization for _Comparison types that are not capable of
412 // being base classes / super classes.
413 template<typename _Key_compare
>
414 struct _Rb_tree_impl
<_Key_compare
, true> : public _Node_allocator
416 _Key_compare _M_key_compare
;
417 _Rb_tree_node_base _M_header
;
418 size_type _M_node_count
; // Keeps track of size of tree.
420 _Rb_tree_impl(const _Node_allocator
& __a
= _Node_allocator(),
421 const _Key_compare
& __comp
= _Key_compare())
422 : _Node_allocator(__a
), _M_key_compare(__comp
), _M_node_count(0)
424 this->_M_header
._M_color
= _S_red
;
425 this->_M_header
._M_parent
= 0;
426 this->_M_header
._M_left
= &this->_M_header
;
427 this->_M_header
._M_right
= &this->_M_header
;
431 _Rb_tree_impl
<_Compare
> _M_impl
;
436 { return this->_M_impl
._M_header
._M_parent
; }
440 { return this->_M_impl
._M_header
._M_parent
; }
444 { return this->_M_impl
._M_header
._M_left
; }
448 { return this->_M_impl
._M_header
._M_left
; }
452 { return this->_M_impl
._M_header
._M_right
; }
456 { return this->_M_impl
._M_header
._M_right
; }
460 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
465 return static_cast<_Const_Link_type
>
466 (this->_M_impl
._M_header
._M_parent
);
471 { return static_cast<_Link_type
>(&this->_M_impl
._M_header
); }
475 { return static_cast<_Const_Link_type
>(&this->_M_impl
._M_header
); }
477 static const_reference
478 _S_value(_Const_Link_type __x
)
479 { return __x
->_M_value_field
; }
482 _S_key(_Const_Link_type __x
)
483 { return _KeyOfValue()(_S_value(__x
)); }
486 _S_left(_Base_ptr __x
)
487 { return static_cast<_Link_type
>(__x
->_M_left
); }
489 static _Const_Link_type
490 _S_left(_Const_Base_ptr __x
)
491 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
494 _S_right(_Base_ptr __x
)
495 { return static_cast<_Link_type
>(__x
->_M_right
); }
497 static _Const_Link_type
498 _S_right(_Const_Base_ptr __x
)
499 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
501 static const_reference
502 _S_value(_Const_Base_ptr __x
)
503 { return static_cast<_Const_Link_type
>(__x
)->_M_value_field
; }
506 _S_key(_Const_Base_ptr __x
)
507 { return _KeyOfValue()(_S_value(__x
)); }
510 _S_minimum(_Base_ptr __x
)
511 { return _Rb_tree_node_base::_S_minimum(__x
); }
513 static _Const_Base_ptr
514 _S_minimum(_Const_Base_ptr __x
)
515 { return _Rb_tree_node_base::_S_minimum(__x
); }
518 _S_maximum(_Base_ptr __x
)
519 { return _Rb_tree_node_base::_S_maximum(__x
); }
521 static _Const_Base_ptr
522 _S_maximum(_Const_Base_ptr __x
)
523 { return _Rb_tree_node_base::_S_maximum(__x
); }
526 typedef _Rb_tree_iterator
<value_type
> iterator
;
527 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
529 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
530 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
534 _M_insert(_Base_ptr __x
, _Base_ptr __y
, const value_type
& __v
);
537 _M_copy(_Const_Link_type __x
, _Link_type __p
);
540 _M_erase(_Link_type __x
);
543 // allocation/deallocation
547 _Rb_tree(const _Compare
& __comp
)
548 : _M_impl(allocator_type(), __comp
)
551 _Rb_tree(const _Compare
& __comp
, const allocator_type
& __a
)
552 : _M_impl(__a
, __comp
)
555 _Rb_tree(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
)
556 : _M_impl(__x
.get_allocator(), __x
._M_impl
._M_key_compare
)
558 if (__x
._M_root() != 0)
560 _M_root() = _M_copy(__x
._M_begin(), _M_end());
561 _M_leftmost() = _S_minimum(_M_root());
562 _M_rightmost() = _S_maximum(_M_root());
563 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
568 { _M_erase(_M_begin()); }
570 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
571 operator=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
);
576 { return _M_impl
._M_key_compare
; }
580 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_left
); }
585 return static_cast<_Const_Link_type
>
586 (this->_M_impl
._M_header
._M_left
);
591 { return static_cast<_Link_type
>(&this->_M_impl
._M_header
); }
595 { return static_cast<_Const_Link_type
>(&this->_M_impl
._M_header
); }
599 { return reverse_iterator(end()); }
601 const_reverse_iterator
603 { return const_reverse_iterator(end()); }
607 { return reverse_iterator(begin()); }
609 const_reverse_iterator
611 { return const_reverse_iterator(begin()); }
615 { return _M_impl
._M_node_count
== 0; }
619 { return _M_impl
._M_node_count
; }
623 { return size_type(-1); }
626 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __t
);
630 insert_unique(const value_type
& __x
);
633 insert_equal(const value_type
& __x
);
636 insert_unique(iterator __position
, const value_type
& __x
);
639 insert_equal(iterator __position
, const value_type
& __x
);
641 template<typename _InputIterator
>
643 insert_unique(_InputIterator __first
, _InputIterator __last
);
645 template<typename _InputIterator
>
647 insert_equal(_InputIterator __first
, _InputIterator __last
);
650 erase(iterator __position
);
653 erase(const key_type
& __x
);
656 erase(iterator __first
, iterator __last
);
659 erase(const key_type
* __first
, const key_type
* __last
);
664 _M_erase(_M_begin());
665 _M_leftmost() = _M_end();
667 _M_rightmost() = _M_end();
668 _M_impl
._M_node_count
= 0;
673 find(const key_type
& __x
);
676 find(const key_type
& __x
) const;
679 count(const key_type
& __x
) const;
682 lower_bound(const key_type
& __x
);
685 lower_bound(const key_type
& __x
) const;
688 upper_bound(const key_type
& __x
);
691 upper_bound(const key_type
& __x
) const;
693 pair
<iterator
,iterator
>
694 equal_range(const key_type
& __x
);
696 pair
<const_iterator
, const_iterator
>
697 equal_range(const key_type
& __x
) const;
704 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
705 typename _Compare
, typename _Alloc
>
707 operator==(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
708 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
710 return __x
.size() == __y
.size()
711 && equal(__x
.begin(), __x
.end(), __y
.begin());
714 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
715 typename _Compare
, typename _Alloc
>
717 operator<(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
718 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
720 return lexicographical_compare(__x
.begin(), __x
.end(),
721 __y
.begin(), __y
.end());
724 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
725 typename _Compare
, typename _Alloc
>
727 operator!=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
728 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
729 { return !(__x
== __y
); }
731 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
732 typename _Compare
, typename _Alloc
>
734 operator>(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
735 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
736 { return __y
< __x
; }
738 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
739 typename _Compare
, typename _Alloc
>
741 operator<=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
742 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
743 { return !(__y
< __x
); }
745 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
746 typename _Compare
, typename _Alloc
>
748 operator>=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
749 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
750 { return !(__x
< __y
); }
752 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
753 typename _Compare
, typename _Alloc
>
755 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
756 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
759 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
760 typename _Compare
, typename _Alloc
>
761 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
762 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
763 operator=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
)
767 // Note that _Key may be a constant type.
769 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
770 if (__x
._M_root() != 0)
772 _M_root() = _M_copy(__x
._M_begin(), _M_end());
773 _M_leftmost() = _S_minimum(_M_root());
774 _M_rightmost() = _S_maximum(_M_root());
775 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
781 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
782 typename _Compare
, typename _Alloc
>
783 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
784 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
785 _M_insert(_Base_ptr __x
, _Base_ptr __p
, const _Val
& __v
)
787 _Link_type __z
= _M_create_node(__v
);
790 __insert_left
= (__x
!= 0 || __p
== _M_end()
791 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
794 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
795 this->_M_impl
._M_header
);
796 ++_M_impl
._M_node_count
;
797 return iterator(__z
);
800 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
801 typename _Compare
, typename _Alloc
>
802 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
803 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
804 insert_equal(const _Val
& __v
)
806 _Link_type __x
= _M_begin();
807 _Link_type __y
= _M_end();
811 __x
= _M_impl
._M_key_compare(_KeyOfValue()(__v
), _S_key(__x
)) ?
812 _S_left(__x
) : _S_right(__x
);
814 return _M_insert(__x
, __y
, __v
);
817 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
818 typename _Compare
, typename _Alloc
>
820 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
821 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __t
)
825 if (__t
._M_root() != 0)
827 _M_root() = __t
._M_root();
828 _M_leftmost() = __t
._M_leftmost();
829 _M_rightmost() = __t
._M_rightmost();
830 _M_root()->_M_parent
= _M_end();
833 __t
._M_leftmost() = __t
._M_end();
834 __t
._M_rightmost() = __t
._M_end();
837 else if (__t
._M_root() == 0)
839 __t
._M_root() = _M_root();
840 __t
._M_leftmost() = _M_leftmost();
841 __t
._M_rightmost() = _M_rightmost();
842 __t
._M_root()->_M_parent
= __t
._M_end();
845 _M_leftmost() = _M_end();
846 _M_rightmost() = _M_end();
850 std::swap(_M_root(),__t
._M_root());
851 std::swap(_M_leftmost(),__t
._M_leftmost());
852 std::swap(_M_rightmost(),__t
._M_rightmost());
854 _M_root()->_M_parent
= _M_end();
855 __t
._M_root()->_M_parent
= __t
._M_end();
857 // No need to swap header's color as it does not change.
858 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
859 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
862 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
863 typename _Compare
, typename _Alloc
>
864 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
865 _Compare
, _Alloc
>::iterator
, bool>
866 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
867 insert_unique(const _Val
& __v
)
869 _Link_type __x
= _M_begin();
870 _Link_type __y
= _M_end();
875 __comp
= _M_impl
._M_key_compare(_KeyOfValue()(__v
), _S_key(__x
));
876 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
878 iterator __j
= iterator(__y
);
881 return pair
<iterator
,bool>(_M_insert(__x
, __y
, __v
), true);
884 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), _KeyOfValue()(__v
)))
885 return pair
<iterator
, bool>(_M_insert(__x
, __y
, __v
), true);
886 return pair
<iterator
, bool>(__j
, false);
889 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
890 typename _Compare
, typename _Alloc
>
891 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
892 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
893 insert_unique(iterator __position
, const _Val
& __v
)
895 if (__position
._M_node
== _M_leftmost())
899 && _M_impl
._M_key_compare(_KeyOfValue()(__v
),
900 _S_key(__position
._M_node
)))
901 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
902 // First argument just needs to be non-null.
904 return insert_unique(__v
).first
;
906 else if (__position
._M_node
== _M_end())
909 if (_M_impl
._M_key_compare(_S_key(_M_rightmost()),
911 return _M_insert(0, _M_rightmost(), __v
);
913 return insert_unique(__v
).first
;
917 iterator __before
= __position
;
919 if (_M_impl
._M_key_compare(_S_key(__before
._M_node
),
921 && _M_impl
._M_key_compare(_KeyOfValue()(__v
),
922 _S_key(__position
._M_node
)))
924 if (_S_right(__before
._M_node
) == 0)
925 return _M_insert(0, __before
._M_node
, __v
);
927 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
928 // First argument just needs to be non-null.
931 return insert_unique(__v
).first
;
935 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
936 typename _Compare
, typename _Alloc
>
937 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
938 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
939 insert_equal(iterator __position
, const _Val
& __v
)
941 if (__position
._M_node
== _M_leftmost())
945 && !_M_impl
._M_key_compare(_S_key(__position
._M_node
),
947 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
948 // first argument just needs to be non-null
950 return insert_equal(__v
);
952 else if (__position
._M_node
== _M_end())
955 if (!_M_impl
._M_key_compare(_KeyOfValue()(__v
),
956 _S_key(_M_rightmost())))
957 return _M_insert(0, _M_rightmost(), __v
);
959 return insert_equal(__v
);
963 iterator __before
= __position
;
965 if (!_M_impl
._M_key_compare(_KeyOfValue()(__v
),
966 _S_key(__before
._M_node
))
967 && !_M_impl
._M_key_compare(_S_key(__position
._M_node
),
970 if (_S_right(__before
._M_node
) == 0)
971 return _M_insert(0, __before
._M_node
, __v
);
973 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
974 // First argument just needs to be non-null.
977 return insert_equal(__v
);
981 template<typename _Key
, typename _Val
, typename _KoV
,
982 typename _Cmp
, typename _Alloc
>
985 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
986 insert_equal(_II __first
, _II __last
)
988 for (; __first
!= __last
; ++__first
)
989 insert_equal(*__first
);
992 template<typename _Key
, typename _Val
, typename _KoV
,
993 typename _Cmp
, typename _Alloc
>
996 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
997 insert_unique(_II __first
, _II __last
)
999 for (; __first
!= __last
; ++__first
)
1000 insert_unique(*__first
);
1003 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1004 typename _Compare
, typename _Alloc
>
1006 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1007 erase(iterator __position
)
1010 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1011 (__position
._M_node
,
1012 this->_M_impl
._M_header
));
1014 --_M_impl
._M_node_count
;
1017 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1018 typename _Compare
, typename _Alloc
>
1019 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
1020 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1021 erase(const _Key
& __x
)
1023 pair
<iterator
,iterator
> __p
= equal_range(__x
);
1024 size_type __n
= std::distance(__p
.first
, __p
.second
);
1025 erase(__p
.first
, __p
.second
);
1029 template<typename _Key
, typename _Val
, typename _KoV
,
1030 typename _Compare
, typename _Alloc
>
1031 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1032 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
1033 _M_copy(_Const_Link_type __x
, _Link_type __p
)
1035 // Structural copy. __x and __p must be non-null.
1036 _Link_type __top
= _M_clone_node(__x
);
1037 __top
->_M_parent
= __p
;
1042 __top
->_M_right
= _M_copy(_S_right(__x
), __top
);
1048 _Link_type __y
= _M_clone_node(__x
);
1050 __y
->_M_parent
= __p
;
1052 __y
->_M_right
= _M_copy(_S_right(__x
), __y
);
1060 __throw_exception_again
;
1065 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1066 typename _Compare
, typename _Alloc
>
1068 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1069 _M_erase(_Link_type __x
)
1071 // Erase without rebalancing.
1074 _M_erase(_S_right(__x
));
1075 _Link_type __y
= _S_left(__x
);
1081 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1082 typename _Compare
, typename _Alloc
>
1084 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1085 erase(iterator __first
, iterator __last
)
1087 if (__first
== begin() && __last
== end())
1090 while (__first
!= __last
) erase(__first
++);
1093 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1094 typename _Compare
, typename _Alloc
>
1096 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1097 erase(const _Key
* __first
, const _Key
* __last
)
1099 while (__first
!= __last
)
1103 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1104 typename _Compare
, typename _Alloc
>
1105 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1106 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1107 find(const _Key
& __k
)
1109 _Link_type __x
= _M_begin(); // Current node.
1110 _Link_type __y
= _M_end(); // Last node which is not less than __k.
1113 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1114 __y
= __x
, __x
= _S_left(__x
);
1116 __x
= _S_right(__x
);
1118 iterator __j
= iterator(__y
);
1119 return (__j
== end()
1120 || _M_impl
._M_key_compare(__k
,
1121 _S_key(__j
._M_node
))) ? end() : __j
;
1124 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1125 typename _Compare
, typename _Alloc
>
1126 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::const_iterator
1127 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1128 find(const _Key
& __k
) const
1130 _Const_Link_type __x
= _M_begin(); // Current node.
1131 _Const_Link_type __y
= _M_end(); // Last node which is not less than __k.
1135 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1136 __y
= __x
, __x
= _S_left(__x
);
1138 __x
= _S_right(__x
);
1140 const_iterator __j
= const_iterator(__y
);
1141 return (__j
== end()
1142 || _M_impl
._M_key_compare(__k
,
1143 _S_key(__j
._M_node
))) ? end() : __j
;
1146 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1147 typename _Compare
, typename _Alloc
>
1148 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
1149 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1150 count(const _Key
& __k
) const
1152 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
1153 const size_type __n
= std::distance(__p
.first
, __p
.second
);
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 lower_bound(const _Key
& __k
)
1163 _Link_type __x
= _M_begin(); // Current node.
1164 _Link_type __y
= _M_end(); // Last node which is not less than __k.
1167 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1168 __y
= __x
, __x
= _S_left(__x
);
1170 __x
= _S_right(__x
);
1172 return iterator(__y
);
1175 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1176 typename _Compare
, typename _Alloc
>
1177 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::const_iterator
1178 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1179 lower_bound(const _Key
& __k
) const
1181 _Const_Link_type __x
= _M_begin(); // Current node.
1182 _Const_Link_type __y
= _M_end(); // Last node which is not less than __k.
1185 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1186 __y
= __x
, __x
= _S_left(__x
);
1188 __x
= _S_right(__x
);
1190 return const_iterator(__y
);
1193 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1194 typename _Compare
, typename _Alloc
>
1195 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1196 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1197 upper_bound(const _Key
& __k
)
1199 _Link_type __x
= _M_begin(); // Current node.
1200 _Link_type __y
= _M_end(); // Last node which is greater than __k.
1203 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1204 __y
= __x
, __x
= _S_left(__x
);
1206 __x
= _S_right(__x
);
1208 return iterator(__y
);
1211 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1212 typename _Compare
, typename _Alloc
>
1213 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::const_iterator
1214 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1215 upper_bound(const _Key
& __k
) const
1217 _Const_Link_type __x
= _M_begin(); // Current node.
1218 _Const_Link_type __y
= _M_end(); // Last node which is greater than __k.
1221 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1222 __y
= __x
, __x
= _S_left(__x
);
1224 __x
= _S_right(__x
);
1226 return const_iterator(__y
);
1229 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1230 typename _Compare
, typename _Alloc
>
1232 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1233 _Compare
, _Alloc
>::iterator
,
1234 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
>
1235 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1236 equal_range(const _Key
& __k
)
1237 { return pair
<iterator
, iterator
>(lower_bound(__k
), upper_bound(__k
)); }
1239 template<typename _Key
, typename _Val
, typename _KoV
,
1240 typename _Compare
, typename _Alloc
>
1242 pair
<typename _Rb_tree
<_Key
, _Val
, _KoV
,
1243 _Compare
, _Alloc
>::const_iterator
,
1244 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::const_iterator
>
1245 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
1246 equal_range(const _Key
& __k
) const
1247 { return pair
<const_iterator
, const_iterator
>(lower_bound(__k
),
1248 upper_bound(__k
)); }
1251 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
1252 const _Rb_tree_node_base
* __root
);
1254 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1255 typename _Compare
, typename _Alloc
>
1257 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
1259 if (_M_impl
._M_node_count
== 0 || begin() == end())
1260 return _M_impl
._M_node_count
== 0 && begin() == end()
1261 && this->_M_impl
._M_header
._M_left
== _M_end()
1262 && this->_M_impl
._M_header
._M_right
== _M_end();
1264 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
1265 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
1267 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
1268 _Const_Link_type __L
= _S_left(__x
);
1269 _Const_Link_type __R
= _S_right(__x
);
1271 if (__x
->_M_color
== _S_red
)
1272 if ((__L
&& __L
->_M_color
== _S_red
)
1273 || (__R
&& __R
->_M_color
== _S_red
))
1276 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
1278 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
1281 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
1285 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1287 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))