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.
68 Red-black tree class, designed for use in implementing STL
69 associative containers (set, multiset, map, and multimap). The
70 insertion and deletion algorithms are based on those in Cormen,
71 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
74 (1) the header cell is maintained with links not only to the root
75 but also to the leftmost node of the tree, to enable constant time
76 begin(), and to the rightmost node of the tree, to enable linear time
77 performance when used with the generic set algorithms (set_union,
80 (2) when a node being deleted has two children its successor node is
81 relinked into its place, rather than copied, so that the only
82 iterators invalidated are those referring to the deleted node.
86 #include <bits/stl_algobase.h>
87 #include <bits/allocator.h>
88 #include <bits/stl_construct.h>
89 #include <bits/stl_function.h>
93 enum _Rb_tree_color
{ _S_red
= false, _S_black
= true };
95 struct _Rb_tree_node_base
97 typedef _Rb_tree_node_base
* _Base_ptr
;
98 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
100 _Rb_tree_color _M_color
;
106 _S_minimum(_Base_ptr __x
)
108 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
112 static _Const_Base_ptr
113 _S_minimum(_Const_Base_ptr __x
)
115 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
120 _S_maximum(_Base_ptr __x
)
122 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
126 static _Const_Base_ptr
127 _S_maximum(_Const_Base_ptr __x
)
129 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
134 template<typename _Val
>
135 struct _Rb_tree_node
: public _Rb_tree_node_base
137 typedef _Rb_tree_node
<_Val
>* _Link_type
;
142 _Rb_tree_increment(_Rb_tree_node_base
* __x
);
144 const _Rb_tree_node_base
*
145 _Rb_tree_increment(const _Rb_tree_node_base
* __x
);
148 _Rb_tree_decrement(_Rb_tree_node_base
* __x
);
150 const _Rb_tree_node_base
*
151 _Rb_tree_decrement(const _Rb_tree_node_base
* __x
);
153 template<typename _Tp
>
154 struct _Rb_tree_iterator
156 typedef _Tp value_type
;
157 typedef _Tp
& reference
;
158 typedef _Tp
* pointer
;
160 typedef bidirectional_iterator_tag iterator_category
;
161 typedef ptrdiff_t difference_type
;
163 typedef _Rb_tree_iterator
<_Tp
> _Self
;
164 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
165 typedef _Rb_tree_node
<_Tp
>* _Link_type
;
167 _Rb_tree_iterator() {}
169 _Rb_tree_iterator(_Link_type __x
)
174 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
178 { return &static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
183 _M_node
= _Rb_tree_increment(_M_node
);
191 _M_node
= _Rb_tree_increment(_M_node
);
198 _M_node
= _Rb_tree_decrement(_M_node
);
206 _M_node
= _Rb_tree_decrement(_M_node
);
211 operator==(const _Self
& __x
) const
212 { return _M_node
== __x
._M_node
; }
215 operator!=(const _Self
& __x
) const
216 { return _M_node
!= __x
._M_node
; }
221 template<typename _Tp
>
222 struct _Rb_tree_const_iterator
224 typedef _Tp value_type
;
225 typedef const _Tp
& reference
;
226 typedef const _Tp
* pointer
;
228 typedef _Rb_tree_iterator
<_Tp
> iterator
;
230 typedef bidirectional_iterator_tag iterator_category
;
231 typedef ptrdiff_t difference_type
;
233 typedef _Rb_tree_const_iterator
<_Tp
> _Self
;
234 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr
;
235 typedef const _Rb_tree_node
<_Tp
>* _Link_type
;
237 _Rb_tree_const_iterator() {}
239 _Rb_tree_const_iterator(_Link_type __x
)
242 _Rb_tree_const_iterator(const iterator
& __it
)
243 : _M_node(__it
._M_node
) {}
247 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
251 { return &static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
256 _M_node
= _Rb_tree_increment(_M_node
);
264 _M_node
= _Rb_tree_increment(_M_node
);
271 _M_node
= _Rb_tree_decrement(_M_node
);
279 _M_node
= _Rb_tree_decrement(_M_node
);
284 operator==(const _Self
& __x
) const
285 { return _M_node
== __x
._M_node
; }
288 operator!=(const _Self
& __x
) const
289 { return _M_node
!= __x
._M_node
; }
294 template<typename _Val
>
296 operator==(const _Rb_tree_iterator
<_Val
>& __x
,
297 const _Rb_tree_const_iterator
<_Val
>& __y
)
298 { return __x
._M_node
== __y
._M_node
; }
300 template<typename _Val
>
302 operator!=(const _Rb_tree_iterator
<_Val
>& __x
,
303 const _Rb_tree_const_iterator
<_Val
>& __y
)
304 { return __x
._M_node
!= __y
._M_node
; }
307 _Rb_tree_rotate_left(_Rb_tree_node_base
* const __x
,
308 _Rb_tree_node_base
*& __root
);
311 _Rb_tree_rotate_right(_Rb_tree_node_base
* const __x
,
312 _Rb_tree_node_base
*& __root
);
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
> >
328 : protected _Alloc::template rebind
<_Rb_tree_node
<_Val
> >::other
330 typedef typename
_Alloc::template rebind
<_Rb_tree_node
<_Val
> >::other
334 typedef _Rb_tree_node_base
* _Base_ptr
;
335 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
336 typedef _Rb_tree_node
<_Val
> _Rb_tree_node
;
339 typedef _Key key_type
;
340 typedef _Val value_type
;
341 typedef value_type
* pointer
;
342 typedef const value_type
* const_pointer
;
343 typedef value_type
& reference
;
344 typedef const value_type
& const_reference
;
345 typedef _Rb_tree_node
* _Link_type
;
346 typedef const _Rb_tree_node
* _Const_Link_type
;
347 typedef size_t size_type
;
348 typedef ptrdiff_t difference_type
;
350 typedef _Alloc allocator_type
;
351 allocator_type
get_allocator() const
352 { return *static_cast<const _Node_allocator
*>(this); }
357 { return _Node_allocator::allocate(1); }
360 _M_put_node(_Rb_tree_node
* __p
)
361 { _Node_allocator::deallocate(__p
, 1); }
364 _M_create_node(const value_type
& __x
)
366 _Link_type __tmp
= _M_get_node();
368 { std::_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 destroy_node(_Link_type __p
)
390 std::_Destroy(&__p
->_M_value_field
);
395 _Rb_tree_node_base _M_header
;
396 size_type _M_node_count
; // keeps track of size of tree
397 _Compare _M_key_compare
;
402 { return this->_M_header
._M_parent
; }
406 { return this->_M_header
._M_parent
; }
410 { return this->_M_header
._M_left
; }
414 { return this->_M_header
._M_left
; }
418 { return this->_M_header
._M_right
; }
422 { return this->_M_header
._M_right
; }
426 { return static_cast<_Link_type
>(this->_M_header
._M_parent
); }
430 { return static_cast<_Const_Link_type
>(this->_M_header
._M_parent
); }
434 { return static_cast<_Link_type
>(&this->_M_header
); }
438 { return static_cast<_Const_Link_type
>(&this->_M_header
); }
440 static const_reference
441 _S_value(_Const_Link_type __x
)
442 { return __x
->_M_value_field
; }
445 _S_key(_Const_Link_type __x
)
446 { return _KeyOfValue()(_S_value(__x
)); }
449 _S_left(_Base_ptr __x
)
450 { return static_cast<_Link_type
>(__x
->_M_left
); }
452 static _Const_Link_type
453 _S_left(_Const_Base_ptr __x
)
454 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
457 _S_right(_Base_ptr __x
)
458 { return static_cast<_Link_type
>(__x
->_M_right
); }
460 static _Const_Link_type
461 _S_right(_Const_Base_ptr __x
)
462 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
464 static const_reference
465 _S_value(_Const_Base_ptr __x
)
466 { return static_cast<_Const_Link_type
>(__x
)->_M_value_field
; }
469 _S_key(_Const_Base_ptr __x
)
470 { return _KeyOfValue()(_S_value(__x
)); }
473 _S_minimum(_Base_ptr __x
)
474 { return _Rb_tree_node_base::_S_minimum(__x
); }
476 static _Const_Base_ptr
477 _S_minimum(_Const_Base_ptr __x
)
478 { return _Rb_tree_node_base::_S_minimum(__x
); }
481 _S_maximum(_Base_ptr __x
)
482 { return _Rb_tree_node_base::_S_maximum(__x
); }
484 static _Const_Base_ptr
485 _S_maximum(_Const_Base_ptr __x
)
486 { return _Rb_tree_node_base::_S_maximum(__x
); }
489 typedef _Rb_tree_iterator
<value_type
> iterator
;
490 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
492 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
493 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
497 _M_insert(_Base_ptr __x
, _Base_ptr __y
, const value_type
& __v
);
500 _M_copy(_Const_Link_type __x
, _Link_type __p
);
503 _M_erase(_Link_type __x
);
506 // allocation/deallocation
508 : _Node_allocator(allocator_type()),
511 { _M_empty_initialize(); }
513 _Rb_tree(const _Compare
& __comp
)
514 : _Node_allocator(allocator_type()),
516 _M_key_compare(__comp
)
517 { _M_empty_initialize(); }
519 _Rb_tree(const _Compare
& __comp
, const allocator_type
& __a
)
520 : _Node_allocator(__a
),
522 _M_key_compare(__comp
)
523 { _M_empty_initialize(); }
525 _Rb_tree(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
)
526 : _Node_allocator(__x
.get_allocator()),
528 _M_key_compare(__x
._M_key_compare
)
530 if (__x
._M_root() == 0)
531 _M_empty_initialize();
534 this->_M_header
._M_color
= _S_red
;
535 _M_root() = _M_copy(__x
._M_begin(), _M_end());
536 _M_leftmost() = _S_minimum(_M_root());
537 _M_rightmost() = _S_maximum(_M_root());
539 _M_node_count
= __x
._M_node_count
;
542 ~_Rb_tree() { _M_erase(_M_begin()); }
544 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>&
545 operator=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
);
548 void _M_empty_initialize()
550 // Used to distinguish header from __root, in iterator.operator++.
551 this->_M_header
._M_color
= _S_red
;
553 _M_leftmost() = _M_end();
554 _M_rightmost() = _M_end();
561 { return _M_key_compare
; }
565 { return static_cast<_Link_type
>(this->_M_header
._M_left
); }
569 { return static_cast<_Const_Link_type
>(this->_M_header
._M_left
); }
573 { return static_cast<_Link_type
>(&this->_M_header
); }
577 { return static_cast<_Const_Link_type
>(&this->_M_header
); }
581 { return reverse_iterator(end()); }
583 const_reverse_iterator
585 { return const_reverse_iterator(end()); }
589 { return reverse_iterator(begin()); }
591 const_reverse_iterator
593 { return const_reverse_iterator(begin()); }
597 { return _M_node_count
== 0; }
601 { return _M_node_count
; }
605 { return size_type(-1); }
608 swap(_Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __t
);
612 insert_unique(const value_type
& __x
);
615 insert_equal(const value_type
& __x
);
618 insert_unique(iterator __position
, const value_type
& __x
);
621 insert_equal(iterator __position
, const value_type
& __x
);
623 template<typename _InputIterator
>
625 insert_unique(_InputIterator __first
, _InputIterator __last
);
627 template<typename _InputIterator
>
629 insert_equal(_InputIterator __first
, _InputIterator __last
);
632 erase(iterator __position
);
635 erase(const key_type
& __x
);
638 erase(iterator __first
, iterator __last
);
641 erase(const key_type
* __first
, const key_type
* __last
);
646 _M_erase(_M_begin());
647 _M_leftmost() = _M_end();
649 _M_rightmost() = _M_end();
655 find(const key_type
& __x
);
658 find(const key_type
& __x
) const;
661 count(const key_type
& __x
) const;
664 lower_bound(const key_type
& __x
);
667 lower_bound(const key_type
& __x
) const;
670 upper_bound(const key_type
& __x
);
673 upper_bound(const key_type
& __x
) const;
675 pair
<iterator
,iterator
>
676 equal_range(const key_type
& __x
);
678 pair
<const_iterator
, const_iterator
>
679 equal_range(const key_type
& __x
) const;
686 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
687 typename _Compare
, typename _Alloc
>
689 operator==(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
690 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
692 return __x
.size() == __y
.size()
693 && equal(__x
.begin(), __x
.end(), __y
.begin());
696 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
697 typename _Compare
, typename _Alloc
>
699 operator<(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
700 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
702 return lexicographical_compare(__x
.begin(), __x
.end(),
703 __y
.begin(), __y
.end());
706 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
707 typename _Compare
, typename _Alloc
>
709 operator!=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
710 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
711 { return !(__x
== __y
); }
713 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
714 typename _Compare
, typename _Alloc
>
716 operator>(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
717 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
718 { return __y
< __x
; }
720 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
721 typename _Compare
, typename _Alloc
>
723 operator<=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
724 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
725 { return !(__y
< __x
); }
727 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
728 typename _Compare
, typename _Alloc
>
730 operator>=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
731 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
732 { return !(__x
< __y
); }
734 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
735 typename _Compare
, typename _Alloc
>
737 swap(_Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
738 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
741 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
742 typename _Compare
, typename _Alloc
>
743 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>&
744 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
745 operator=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
)
749 // Note that _Key may be a constant type.
751 _M_key_compare
= __x
._M_key_compare
;
752 if (__x
._M_root() != 0)
754 _M_root() = _M_copy(__x
._M_begin(), _M_end());
755 _M_leftmost() = _S_minimum(_M_root());
756 _M_rightmost() = _S_maximum(_M_root());
757 _M_node_count
= __x
._M_node_count
;
763 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
764 typename _Compare
, typename _Alloc
>
765 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
766 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
767 _M_insert(_Base_ptr __x
, _Base_ptr __p
, const _Val
& __v
)
769 _Link_type __z
= _M_create_node(__v
);
772 __insert_left
= __x
!= 0 || __p
== _M_end()
773 || _M_key_compare(_KeyOfValue()(__v
), _S_key(__p
));
775 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
, this->_M_header
);
777 return iterator(__z
);
780 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
781 typename _Compare
, typename _Alloc
>
782 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
783 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
784 insert_equal(const _Val
& __v
)
786 _Link_type __x
= _M_begin();
787 _Link_type __y
= _M_end();
791 __x
= _M_key_compare(_KeyOfValue()(__v
), _S_key(__x
)) ?
792 _S_left(__x
) : _S_right(__x
);
794 return _M_insert(__x
, __y
, __v
);
797 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
798 typename _Compare
, typename _Alloc
>
800 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
801 swap(_Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __t
)
805 if (__t
._M_root() != 0)
807 _M_root() = __t
._M_root();
808 _M_leftmost() = __t
._M_leftmost();
809 _M_rightmost() = __t
._M_rightmost();
810 _M_root()->_M_parent
= _M_end();
813 __t
._M_leftmost() = __t
._M_end();
814 __t
._M_rightmost() = __t
._M_end();
817 else if (__t
._M_root() == 0)
819 __t
._M_root() = _M_root();
820 __t
._M_leftmost() = _M_leftmost();
821 __t
._M_rightmost() = _M_rightmost();
822 __t
._M_root()->_M_parent
= __t
._M_end();
825 _M_leftmost() = _M_end();
826 _M_rightmost() = _M_end();
830 std::swap(_M_root(),__t
._M_root());
831 std::swap(_M_leftmost(),__t
._M_leftmost());
832 std::swap(_M_rightmost(),__t
._M_rightmost());
834 _M_root()->_M_parent
= _M_end();
835 __t
._M_root()->_M_parent
= __t
._M_end();
837 // No need to swap header's color as it does not change.
838 std::swap(this->_M_node_count
, __t
._M_node_count
);
839 std::swap(this->_M_key_compare
, __t
._M_key_compare
);
842 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
843 typename _Compare
, typename _Alloc
>
844 pair
<typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
,
846 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
847 insert_unique(const _Val
& __v
)
849 _Link_type __x
= _M_begin();
850 _Link_type __y
= _M_end();
855 __comp
= _M_key_compare(_KeyOfValue()(__v
), _S_key(__x
));
856 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
858 iterator __j
= iterator(__y
);
861 return pair
<iterator
,bool>(_M_insert(__x
, __y
, __v
), true);
864 if (_M_key_compare(_S_key(__j
._M_node
), _KeyOfValue()(__v
)))
865 return pair
<iterator
,bool>(_M_insert(__x
, __y
, __v
), true);
866 return pair
<iterator
,bool>(__j
, false);
869 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
870 typename _Compare
, typename _Alloc
>
871 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
872 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
873 insert_unique(iterator __position
, const _Val
& __v
)
875 if (__position
._M_node
== _M_leftmost())
879 && _M_key_compare(_KeyOfValue()(__v
), _S_key(__position
._M_node
)))
880 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
881 // first argument just needs to be non-null
883 return insert_unique(__v
).first
;
885 else if (__position
._M_node
== _M_end())
888 if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v
)))
889 return _M_insert(0, _M_rightmost(), __v
);
891 return insert_unique(__v
).first
;
895 iterator __before
= __position
;
897 if (_M_key_compare(_S_key(__before
._M_node
), _KeyOfValue()(__v
))
898 && _M_key_compare(_KeyOfValue()(__v
),_S_key(__position
._M_node
)))
900 if (_S_right(__before
._M_node
) == 0)
901 return _M_insert(0, __before
._M_node
, __v
);
903 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
904 // first argument just needs to be non-null
907 return insert_unique(__v
).first
;
911 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
912 typename _Compare
, typename _Alloc
>
913 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
914 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
915 insert_equal(iterator __position
, const _Val
& __v
)
917 if (__position
._M_node
== _M_leftmost())
921 && !_M_key_compare(_S_key(__position
._M_node
),
923 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
924 // first argument just needs to be non-null
926 return insert_equal(__v
);
928 else if (__position
._M_node
== _M_end())
931 if (!_M_key_compare(_KeyOfValue()(__v
), _S_key(_M_rightmost())))
932 return _M_insert(0, _M_rightmost(), __v
);
934 return insert_equal(__v
);
938 iterator __before
= __position
;
940 if (!_M_key_compare(_KeyOfValue()(__v
), _S_key(__before
._M_node
))
941 && !_M_key_compare(_S_key(__position
._M_node
),
944 if (_S_right(__before
._M_node
) == 0)
945 return _M_insert(0, __before
._M_node
, __v
);
947 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
948 // first argument just needs to be non-null
951 return insert_equal(__v
);
955 template<typename _Key
, typename _Val
, typename _KoV
,
956 typename _Cmp
, typename _Alloc
>
959 _Rb_tree
<_Key
,_Val
,_KoV
,_Cmp
,_Alloc
>::
960 insert_equal(_II __first
, _II __last
)
962 for ( ; __first
!= __last
; ++__first
)
963 insert_equal(*__first
);
966 template<typename _Key
, typename _Val
, typename _KoV
,
967 typename _Cmp
, typename _Alloc
>
970 _Rb_tree
<_Key
,_Val
,_KoV
,_Cmp
,_Alloc
>::
971 insert_unique(_II __first
, _II __last
)
973 for ( ; __first
!= __last
; ++__first
)
974 insert_unique(*__first
);
977 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
978 typename _Compare
, typename _Alloc
>
980 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::erase(iterator __position
)
983 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase(__position
._M_node
,
989 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
990 typename _Compare
, typename _Alloc
>
991 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::size_type
992 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::erase(const _Key
& __x
)
994 pair
<iterator
,iterator
> __p
= equal_range(__x
);
995 size_type __n
= std::distance(__p
.first
, __p
.second
);
996 erase(__p
.first
, __p
.second
);
1000 template<typename _Key
, typename _Val
, typename _KoV
,
1001 typename _Compare
, typename _Alloc
>
1002 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1003 _Rb_tree
<_Key
,_Val
,_KoV
,_Compare
,_Alloc
>::
1004 _M_copy(_Const_Link_type __x
, _Link_type __p
)
1006 // Structural copy. __x and __p must be non-null.
1007 _Link_type __top
= _M_clone_node(__x
);
1008 __top
->_M_parent
= __p
;
1013 __top
->_M_right
= _M_copy(_S_right(__x
), __top
);
1019 _Link_type __y
= _M_clone_node(__x
);
1021 __y
->_M_parent
= __p
;
1023 __y
->_M_right
= _M_copy(_S_right(__x
), __y
);
1031 __throw_exception_again
;
1036 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1037 typename _Compare
, typename _Alloc
>
1039 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::_M_erase(_Link_type __x
)
1041 // Erase without rebalancing.
1044 _M_erase(_S_right(__x
));
1045 _Link_type __y
= _S_left(__x
);
1051 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1052 typename _Compare
, typename _Alloc
>
1054 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1055 erase(iterator __first
, iterator __last
)
1057 if (__first
== begin() && __last
== end())
1060 while (__first
!= __last
) erase(__first
++);
1063 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1064 typename _Compare
, typename _Alloc
>
1066 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1067 erase(const _Key
* __first
, const _Key
* __last
)
1069 while (__first
!= __last
)
1073 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1074 typename _Compare
, typename _Alloc
>
1075 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1076 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::find(const _Key
& __k
)
1078 _Link_type __x
= _M_begin(); // Current node.
1079 _Link_type __y
= _M_end(); // Last node which is not less than __k.
1082 if (!_M_key_compare(_S_key(__x
), __k
))
1083 __y
= __x
, __x
= _S_left(__x
);
1085 __x
= _S_right(__x
);
1087 iterator __j
= iterator(__y
);
1088 return (__j
== end() || _M_key_compare(__k
, _S_key(__j
._M_node
))) ?
1092 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1093 typename _Compare
, typename _Alloc
>
1094 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1095 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1096 find(const _Key
& __k
) const
1098 _Const_Link_type __x
= _M_begin(); // Current node.
1099 _Const_Link_type __y
= _M_end(); // Last node which is not less than __k.
1103 if (!_M_key_compare(_S_key(__x
), __k
))
1104 __y
= __x
, __x
= _S_left(__x
);
1106 __x
= _S_right(__x
);
1108 const_iterator __j
= const_iterator(__y
);
1109 return (__j
== end() || _M_key_compare(__k
, _S_key(__j
._M_node
))) ?
1113 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1114 typename _Compare
, typename _Alloc
>
1115 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::size_type
1116 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1117 count(const _Key
& __k
) const
1119 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
1120 const size_type __n
= std::distance(__p
.first
, __p
.second
);
1124 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1125 typename _Compare
, typename _Alloc
>
1126 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1127 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1128 lower_bound(const _Key
& __k
)
1130 _Link_type __x
= _M_begin(); // Current node.
1131 _Link_type __y
= _M_end(); // Last node which is not less than __k.
1134 if (!_M_key_compare(_S_key(__x
), __k
))
1135 __y
= __x
, __x
= _S_left(__x
);
1137 __x
= _S_right(__x
);
1139 return iterator(__y
);
1142 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1143 typename _Compare
, typename _Alloc
>
1144 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1145 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1146 lower_bound(const _Key
& __k
) const
1148 _Const_Link_type __x
= _M_begin(); // Current node.
1149 _Const_Link_type __y
= _M_end(); // Last node which is not less than __k.
1152 if (!_M_key_compare(_S_key(__x
), __k
))
1153 __y
= __x
, __x
= _S_left(__x
);
1155 __x
= _S_right(__x
);
1157 return const_iterator(__y
);
1160 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1161 typename _Compare
, typename _Alloc
>
1162 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1163 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1164 upper_bound(const _Key
& __k
)
1166 _Link_type __x
= _M_begin(); // Current node.
1167 _Link_type __y
= _M_end(); // Last node which is greater than __k.
1170 if (_M_key_compare(__k
, _S_key(__x
)))
1171 __y
= __x
, __x
= _S_left(__x
);
1173 __x
= _S_right(__x
);
1175 return iterator(__y
);
1178 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1179 typename _Compare
, typename _Alloc
>
1180 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1181 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1182 upper_bound(const _Key
& __k
) const
1184 _Const_Link_type __x
= _M_begin(); // Current node.
1185 _Const_Link_type __y
= _M_end(); // Last node which is greater than __k.
1188 if (_M_key_compare(__k
, _S_key(__x
)))
1189 __y
= __x
, __x
= _S_left(__x
);
1191 __x
= _S_right(__x
);
1193 return const_iterator(__y
);
1196 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1197 typename _Compare
, typename _Alloc
>
1199 pair
<typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,
1200 _Compare
,_Alloc
>::iterator
,
1201 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
>
1202 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1203 equal_range(const _Key
& __k
)
1204 { return pair
<iterator
, iterator
>(lower_bound(__k
), upper_bound(__k
)); }
1206 template<typename _Key
, typename _Val
, typename _KoV
,
1207 typename _Compare
, typename _Alloc
>
1209 pair
<typename _Rb_tree
<_Key
, _Val
, _KoV
,
1210 _Compare
, _Alloc
>::const_iterator
,
1211 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::const_iterator
>
1212 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>
1213 ::equal_range(const _Key
& __k
) const
1214 { return pair
<const_iterator
, const_iterator
>(lower_bound(__k
),
1215 upper_bound(__k
)); }
1218 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
1219 const _Rb_tree_node_base
* __root
);
1221 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1222 typename _Compare
, typename _Alloc
>
1224 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
1226 if (_M_node_count
== 0 || begin() == end())
1227 return _M_node_count
== 0 && begin() == end()
1228 && this->_M_header
._M_left
== _M_end()
1229 && this->_M_header
._M_right
== _M_end();
1231 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
1232 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
1234 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
1235 _Const_Link_type __L
= _S_left(__x
);
1236 _Const_Link_type __R
= _S_right(__x
);
1238 if (__x
->_M_color
== _S_red
)
1239 if ((__L
&& __L
->_M_color
== _S_red
)
1240 || (__R
&& __R
->_M_color
== _S_red
))
1243 if (__L
&& _M_key_compare(_S_key(__x
), _S_key(__L
)))
1245 if (__R
&& _M_key_compare(_S_key(__R
), _S_key(__x
)))
1248 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
1252 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1254 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))