1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003 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
);
145 _Rb_tree_decrement(_Rb_tree_node_base
* __x
);
147 template<typename _Val
, typename _Ref
, typename _Ptr
>
148 struct _Rb_tree_iterator
150 typedef _Val value_type
;
151 typedef _Ref reference
;
152 typedef _Ptr pointer
;
153 typedef _Rb_tree_iterator
<_Val
, _Val
&, _Val
*> iterator
;
154 typedef _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>
156 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
157 typedef bidirectional_iterator_tag iterator_category
;
158 typedef ptrdiff_t difference_type
;
159 typedef _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
> _Self
;
160 typedef _Rb_tree_node
<_Val
>* _Link_type
;
161 typedef const _Rb_tree_node
<_Val
>* _Const_Link_type
;
163 _Rb_tree_iterator() {}
165 _Rb_tree_iterator(_Link_type __x
)
168 _Rb_tree_iterator(_Const_Link_type __x
)
169 : _M_node(const_cast<_Link_type
>(__x
)) {}
171 _Rb_tree_iterator(const iterator
& __it
)
172 : _M_node(__it
._M_node
) {}
176 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
180 { return &static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
185 _M_node
= _Rb_tree_increment(_M_node
);
193 _M_node
= _Rb_tree_increment(_M_node
);
200 _M_node
= _Rb_tree_decrement(_M_node
);
208 _M_node
= _Rb_tree_decrement(_M_node
);
215 template<typename _Val
, typename _Ref
, typename _Ptr
>
217 operator==(const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __x
,
218 const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __y
)
219 { return __x
._M_node
== __y
._M_node
; }
221 template<typename _Val
>
223 operator==(const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __x
,
224 const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __y
)
225 { return __x
._M_node
== __y
._M_node
; }
227 template<typename _Val
>
229 operator==(const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __x
,
230 const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __y
)
231 { return __x
._M_node
== __y
._M_node
; }
233 template<typename _Val
, typename _Ref
, typename _Ptr
>
235 operator!=(const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __x
,
236 const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __y
)
237 { return __x
._M_node
!= __y
._M_node
; }
239 template<typename _Val
>
241 operator!=(const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __x
,
242 const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __y
)
243 { return __x
._M_node
!= __y
._M_node
; }
245 template<typename _Val
>
247 operator!=(const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __x
,
248 const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __y
)
249 { return __x
._M_node
!= __y
._M_node
; }
252 _Rb_tree_rotate_left(_Rb_tree_node_base
* const __x
, _Rb_tree_node_base
*& __root
);
255 _Rb_tree_rotate_right(_Rb_tree_node_base
* const __x
, _Rb_tree_node_base
*& __root
);
258 _Rb_tree_rebalance(_Rb_tree_node_base
* __x
, _Rb_tree_node_base
*& __root
);
261 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
262 _Rb_tree_node_base
& __header
);
264 // Base class to encapsulate the differences between old SGI-style
265 // allocators and standard-conforming allocators. In order to avoid
266 // having an empty base class, we arbitrarily move one of rb_tree's
267 // data members into the base class.
269 // _Base for general standard-conforming allocators.
270 template<typename _Tp
, typename _Alloc
, bool _S_instanceless
>
271 class _Rb_tree_alloc_base
274 typedef typename _Alloc_traits
<_Tp
, _Alloc
>::allocator_type allocator_type
;
277 get_allocator() const { return _M_node_allocator
; }
279 _Rb_tree_alloc_base(const allocator_type
& __a
)
280 : _M_node_allocator(__a
) {}
283 typename _Alloc_traits
<_Rb_tree_node
<_Tp
>, _Alloc
>::allocator_type
286 _Rb_tree_node_base _M_header
;
289 _M_get_node() { return _M_node_allocator
.allocate(1); }
292 _M_put_node(_Rb_tree_node
<_Tp
>* __p
)
293 { _M_node_allocator
.deallocate(__p
, 1); }
296 // Specialization for instanceless allocators.
297 template<typename _Tp
, typename _Alloc
>
298 class _Rb_tree_alloc_base
<_Tp
, _Alloc
, true>
301 typedef typename _Alloc_traits
<_Tp
, _Alloc
>::allocator_type allocator_type
;
302 allocator_type
get_allocator() const { return allocator_type(); }
304 _Rb_tree_alloc_base(const allocator_type
&) {}
307 _Rb_tree_node_base _M_header
;
309 typedef typename _Alloc_traits
<_Rb_tree_node
<_Tp
>, _Alloc
>::_Alloc_type
313 _M_get_node() { return _Alloc_type::allocate(1); }
316 _M_put_node(_Rb_tree_node
<_Tp
>* __p
) { _Alloc_type::deallocate(__p
, 1); }
319 template<typename _Tp
, typename _Alloc
>
320 struct _Rb_tree_base
: public _Rb_tree_alloc_base
<_Tp
, _Alloc
,
321 _Alloc_traits
<_Tp
, _Alloc
>::_S_instanceless
>
323 typedef _Rb_tree_alloc_base
<_Tp
,
324 _Alloc
, _Alloc_traits
<_Tp
, _Alloc
>::_S_instanceless
> _Base
;
325 typedef typename
_Base::allocator_type allocator_type
;
327 _Rb_tree_base(const allocator_type
& __a
)
332 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
333 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
334 class _Rb_tree
: protected _Rb_tree_base
<_Val
, _Alloc
>
336 typedef _Rb_tree_base
<_Val
, _Alloc
> _Base
;
339 typedef _Rb_tree_node_base
* _Base_ptr
;
340 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
341 typedef _Rb_tree_node
<_Val
> _Rb_tree_node
;
344 typedef _Key key_type
;
345 typedef _Val value_type
;
346 typedef value_type
* pointer
;
347 typedef const value_type
* const_pointer
;
348 typedef value_type
& reference
;
349 typedef const value_type
& const_reference
;
350 typedef _Rb_tree_node
* _Link_type
;
351 typedef const _Rb_tree_node
* _Const_Link_type
;
352 typedef size_t size_type
;
353 typedef ptrdiff_t difference_type
;
355 typedef typename
_Base::allocator_type allocator_type
;
356 allocator_type
get_allocator() const { return _Base::get_allocator(); }
359 using _Base::_M_get_node
;
360 using _Base::_M_put_node
;
361 using _Base::_M_header
;
364 _M_create_node(const value_type
& __x
)
366 _Link_type __tmp
= this->_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
);
394 size_type _M_node_count
; // keeps track of size of tree
395 _Compare _M_key_compare
;
398 _M_root() { return this->_M_header
._M_parent
; }
401 _M_root() const { return this->_M_header
._M_parent
; }
404 _M_leftmost() { return this->_M_header
._M_left
; }
407 _M_leftmost() const { return this->_M_header
._M_left
; }
410 _M_rightmost() { return this->_M_header
._M_right
; }
413 _M_rightmost() const { return this->_M_header
._M_right
; }
416 _M_begin() { return static_cast<_Link_type
>(this->_M_header
._M_parent
); }
419 _M_begin() const { return static_cast<_Const_Link_type
>(this->_M_header
._M_parent
); }
422 _M_end() { return static_cast<_Link_type
>(&this->_M_header
); }
425 _M_end() const { return static_cast<_Const_Link_type
>(&this->_M_header
); }
427 static const_reference
428 _S_value(_Const_Link_type __x
) { return __x
->_M_value_field
; }
431 _S_key(_Const_Link_type __x
) { return _KeyOfValue()(_S_value(__x
)); }
434 _S_left(_Base_ptr __x
) { return static_cast<_Link_type
>(__x
->_M_left
); }
436 static _Const_Link_type
437 _S_left(_Const_Base_ptr __x
) { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
440 _S_right(_Base_ptr __x
) { return static_cast<_Link_type
>(__x
->_M_right
); }
442 static _Const_Link_type
443 _S_right(_Const_Base_ptr __x
) { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
445 static const_reference
446 _S_value(_Const_Base_ptr __x
) { return static_cast<_Const_Link_type
>(__x
)->_M_value_field
; }
449 _S_key(_Const_Base_ptr __x
) { return _KeyOfValue()(_S_value(__x
)); }
452 _S_minimum(_Base_ptr __x
)
453 { return _Rb_tree_node_base::_S_minimum(__x
); }
455 static _Const_Base_ptr
456 _S_minimum(_Const_Base_ptr __x
)
457 { return _Rb_tree_node_base::_S_minimum(__x
); }
460 _S_maximum(_Base_ptr __x
)
461 { return _Rb_tree_node_base::_S_maximum(__x
); }
463 static _Const_Base_ptr
464 _S_maximum(_Const_Base_ptr __x
)
465 { return _Rb_tree_node_base::_S_maximum(__x
); }
468 typedef _Rb_tree_iterator
<value_type
, reference
, pointer
> iterator
;
469 typedef _Rb_tree_iterator
<value_type
, const_reference
, const_pointer
>
472 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
473 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
477 _M_insert(_Base_ptr __x
, _Base_ptr __y
, const value_type
& __v
);
480 _M_copy(_Const_Link_type __x
, _Link_type __p
);
483 _M_erase(_Link_type __x
);
486 // allocation/deallocation
488 : _Base(allocator_type()), _M_node_count(0), _M_key_compare()
489 { _M_empty_initialize(); }
491 _Rb_tree(const _Compare
& __comp
)
492 : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp
)
493 { _M_empty_initialize(); }
495 _Rb_tree(const _Compare
& __comp
, const allocator_type
& __a
)
496 : _Base(__a
), _M_node_count(0), _M_key_compare(__comp
)
497 { _M_empty_initialize(); }
499 _Rb_tree(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
)
500 : _Base(__x
.get_allocator()), _M_node_count(0),
501 _M_key_compare(__x
._M_key_compare
)
503 if (__x
._M_root() == 0)
504 _M_empty_initialize();
507 this->_M_header
._M_color
= _S_red
;
508 _M_root() = _M_copy(__x
._M_begin(), _M_end());
509 _M_leftmost() = _S_minimum(_M_root());
510 _M_rightmost() = _S_maximum(_M_root());
512 _M_node_count
= __x
._M_node_count
;
515 ~_Rb_tree() { clear(); }
517 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>&
518 operator=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
);
521 void _M_empty_initialize()
523 // Used to distinguish header from __root, in iterator.operator++.
524 this->_M_header
._M_color
= _S_red
;
526 _M_leftmost() = _M_end();
527 _M_rightmost() = _M_end();
533 key_comp() const { return _M_key_compare
; }
536 begin() { return static_cast<_Link_type
>(this->_M_header
._M_left
); }
539 begin() const { return static_cast<_Const_Link_type
>(this->_M_header
._M_left
); }
542 end() { return static_cast<_Link_type
>(&this->_M_header
); }
545 end() const { return static_cast<_Const_Link_type
>(&this->_M_header
); }
548 rbegin() { return reverse_iterator(end()); }
550 const_reverse_iterator
551 rbegin() const { return const_reverse_iterator(end()); }
554 rend() { return reverse_iterator(begin()); }
556 const_reverse_iterator
557 rend() const { return const_reverse_iterator(begin()); }
560 empty() const { return _M_node_count
== 0; }
563 size() const { return _M_node_count
; }
566 max_size() const { return size_type(-1); }
569 swap(_Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __t
);
573 insert_unique(const value_type
& __x
);
576 insert_equal(const value_type
& __x
);
579 insert_unique(iterator __position
, const value_type
& __x
);
582 insert_equal(iterator __position
, const value_type
& __x
);
584 template<typename _InputIterator
>
586 insert_unique(_InputIterator __first
, _InputIterator __last
);
588 template<typename _InputIterator
>
590 insert_equal(_InputIterator __first
, _InputIterator __last
);
593 erase(iterator __position
);
596 erase(const key_type
& __x
);
599 erase(iterator __first
, iterator __last
);
602 erase(const key_type
* __first
, const key_type
* __last
);
607 if (_M_node_count
!= 0)
609 _M_erase(_M_begin());
610 _M_leftmost() = _M_end();
612 _M_rightmost() = _M_end();
619 find(const key_type
& __x
);
622 find(const key_type
& __x
) const;
625 count(const key_type
& __x
) const;
628 lower_bound(const key_type
& __x
);
631 lower_bound(const key_type
& __x
) const;
634 upper_bound(const key_type
& __x
);
637 upper_bound(const key_type
& __x
) const;
639 pair
<iterator
,iterator
>
640 equal_range(const key_type
& __x
);
642 pair
<const_iterator
, const_iterator
>
643 equal_range(const key_type
& __x
) const;
650 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
651 typename _Compare
, typename _Alloc
>
653 operator==(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
654 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
656 return __x
.size() == __y
.size() &&
657 equal(__x
.begin(), __x
.end(), __y
.begin());
660 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
661 typename _Compare
, typename _Alloc
>
663 operator<(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
664 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
666 return lexicographical_compare(__x
.begin(), __x
.end(),
667 __y
.begin(), __y
.end());
670 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
671 typename _Compare
, typename _Alloc
>
673 operator!=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
674 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
675 { return !(__x
== __y
); }
677 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
678 typename _Compare
, typename _Alloc
>
680 operator>(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
681 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
682 { return __y
< __x
; }
684 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
685 typename _Compare
, typename _Alloc
>
687 operator<=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
688 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
689 { return !(__y
< __x
); }
691 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
692 typename _Compare
, typename _Alloc
>
694 operator>=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
695 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
696 { return !(__x
< __y
); }
698 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
699 typename _Compare
, typename _Alloc
>
701 swap(_Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
702 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
705 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
706 typename _Compare
, typename _Alloc
>
707 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>&
708 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
709 operator=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
)
713 // Note that _Key may be a constant type.
716 _M_key_compare
= __x
._M_key_compare
;
717 if (__x
._M_root() == 0)
720 _M_leftmost() = _M_end();
721 _M_rightmost() = _M_end();
725 _M_root() = _M_copy(__x
._M_begin(), _M_end());
726 _M_leftmost() = _S_minimum(_M_root());
727 _M_rightmost() = _S_maximum(_M_root());
728 _M_node_count
= __x
._M_node_count
;
734 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
735 typename _Compare
, typename _Alloc
>
736 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
737 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
738 _M_insert(_Base_ptr __x_
, _Base_ptr __y_
, const _Val
& __v
)
740 _Link_type __x
= static_cast<_Link_type
>(__x_
);
741 _Link_type __y
= static_cast<_Link_type
>(__y_
);
744 if (__y
== &this->_M_header
|| __x
!= 0 ||
745 _M_key_compare(_KeyOfValue()(__v
), _S_key(__y
)))
747 __z
= _M_create_node(__v
);
748 __y
->_M_left
= __z
; // also makes _M_leftmost() = __z
749 // when __y == &_M_header
750 if (__y
== &this->_M_header
)
753 _M_rightmost() = __z
;
755 else if (__y
== _M_leftmost())
756 _M_leftmost() = __z
; // maintain _M_leftmost() pointing to min node
760 __z
= _M_create_node(__v
);
762 // Maintain _M_rightmost() pointing to max node.
763 if (__y
== _M_rightmost())
764 _M_rightmost() = __z
;
766 __z
->_M_parent
= __y
;
769 _Rb_tree_rebalance(__z
, this->_M_header
._M_parent
);
771 return iterator(__z
);
774 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
775 typename _Compare
, typename _Alloc
>
776 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
777 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
778 insert_equal(const _Val
& __v
)
780 _Link_type __x
= _M_begin();
781 _Link_type __y
= _M_end();
785 __x
= _M_key_compare(_KeyOfValue()(__v
), _S_key(__x
)) ?
786 _S_left(__x
) : _S_right(__x
);
788 return _M_insert(__x
, __y
, __v
);
791 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
792 typename _Compare
, typename _Alloc
>
794 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
795 swap(_Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __t
)
799 if (__t
._M_root() != 0)
801 _M_root() = __t
._M_root();
802 _M_leftmost() = __t
._M_leftmost();
803 _M_rightmost() = __t
._M_rightmost();
804 _M_root()->_M_parent
= _M_end();
807 __t
._M_leftmost() = __t
._M_end();
808 __t
._M_rightmost() = __t
._M_end();
811 else if (__t
._M_root() == 0)
813 __t
._M_root() = _M_root();
814 __t
._M_leftmost() = _M_leftmost();
815 __t
._M_rightmost() = _M_rightmost();
816 __t
._M_root()->_M_parent
= __t
._M_end();
819 _M_leftmost() = _M_end();
820 _M_rightmost() = _M_end();
824 std::swap(_M_root(),__t
._M_root());
825 std::swap(_M_leftmost(),__t
._M_leftmost());
826 std::swap(_M_rightmost(),__t
._M_rightmost());
828 _M_root()->_M_parent
= _M_end();
829 __t
._M_root()->_M_parent
= __t
._M_end();
831 // No need to swap header's color as it does not change.
832 std::swap(this->_M_node_count
, __t
._M_node_count
);
833 std::swap(this->_M_key_compare
, __t
._M_key_compare
);
836 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
837 typename _Compare
, typename _Alloc
>
838 pair
<typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
,
840 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
841 insert_unique(const _Val
& __v
)
843 _Link_type __x
= _M_begin();
844 _Link_type __y
= _M_end();
849 __comp
= _M_key_compare(_KeyOfValue()(__v
), _S_key(__x
));
850 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
852 iterator __j
= iterator(__y
);
855 return pair
<iterator
,bool>(_M_insert(__x
, __y
, __v
), true);
858 if (_M_key_compare(_S_key(__j
._M_node
), _KeyOfValue()(__v
)))
859 return pair
<iterator
,bool>(_M_insert(__x
, __y
, __v
), true);
860 return pair
<iterator
,bool>(__j
, false);
864 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
865 typename _Compare
, typename _Alloc
>
866 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
867 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
868 insert_unique(iterator __position
, const _Val
& __v
)
870 if (__position
._M_node
== this->_M_header
._M_left
)
874 _M_key_compare(_KeyOfValue()(__v
), _S_key(__position
._M_node
)))
875 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
876 // first argument just needs to be non-null
878 return insert_unique(__v
).first
;
880 else if (__position
._M_node
== &this->_M_header
)
883 if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v
)))
884 return _M_insert(0, _M_rightmost(), __v
);
886 return insert_unique(__v
).first
;
890 iterator __before
= __position
;
892 if (_M_key_compare(_S_key(__before
._M_node
), _KeyOfValue()(__v
))
893 && _M_key_compare(_KeyOfValue()(__v
),_S_key(__position
._M_node
)))
895 if (_S_right(__before
._M_node
) == 0)
896 return _M_insert(0, __before
._M_node
, __v
);
898 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
899 // first argument just needs to be non-null
902 return insert_unique(__v
).first
;
906 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
907 typename _Compare
, typename _Alloc
>
908 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
909 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
910 insert_equal(iterator __position
, const _Val
& __v
)
912 if (__position
._M_node
== this->_M_header
._M_left
)
916 !_M_key_compare(_S_key(__position
._M_node
), _KeyOfValue()(__v
)))
917 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
918 // first argument just needs to be non-null
920 return insert_equal(__v
);
922 else if (__position
._M_node
== &this->_M_header
)
925 if (!_M_key_compare(_KeyOfValue()(__v
), _S_key(_M_rightmost())))
926 return _M_insert(0, _M_rightmost(), __v
);
928 return insert_equal(__v
);
932 iterator __before
= __position
;
934 if (!_M_key_compare(_KeyOfValue()(__v
), _S_key(__before
._M_node
))
935 && !_M_key_compare(_S_key(__position
._M_node
),
938 if (_S_right(__before
._M_node
) == 0)
939 return _M_insert(0, __before
._M_node
, __v
);
941 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
942 // first argument just needs to be non-null
945 return insert_equal(__v
);
949 template<typename _Key
, typename _Val
, typename _KoV
,
950 typename _Cmp
, typename _Alloc
>
953 _Rb_tree
<_Key
,_Val
,_KoV
,_Cmp
,_Alloc
>::
954 insert_equal(_II __first
, _II __last
)
956 for ( ; __first
!= __last
; ++__first
)
957 insert_equal(*__first
);
960 template<typename _Key
, typename _Val
, typename _KoV
,
961 typename _Cmp
, typename _Alloc
>
964 _Rb_tree
<_Key
,_Val
,_KoV
,_Cmp
,_Alloc
>::
965 insert_unique(_II __first
, _II __last
)
967 for ( ; __first
!= __last
; ++__first
)
968 insert_unique(*__first
);
971 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
972 typename _Compare
, typename _Alloc
>
974 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::erase(iterator __position
)
977 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase(__position
._M_node
,
983 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
984 typename _Compare
, typename _Alloc
>
985 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::size_type
986 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::erase(const _Key
& __x
)
988 pair
<iterator
,iterator
> __p
= equal_range(__x
);
989 size_type __n
= std::distance(__p
.first
, __p
.second
);
990 erase(__p
.first
, __p
.second
);
994 template<typename _Key
, typename _Val
, typename _KoV
,
995 typename _Compare
, typename _Alloc
>
996 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
997 _Rb_tree
<_Key
,_Val
,_KoV
,_Compare
,_Alloc
>::
998 _M_copy(_Const_Link_type __x
, _Link_type __p
)
1000 // Structural copy. __x and __p must be non-null.
1001 _Link_type __top
= _M_clone_node(__x
);
1002 __top
->_M_parent
= __p
;
1007 __top
->_M_right
= _M_copy(_S_right(__x
), __top
);
1013 _Link_type __y
= _M_clone_node(__x
);
1015 __y
->_M_parent
= __p
;
1017 __y
->_M_right
= _M_copy(_S_right(__x
), __y
);
1025 __throw_exception_again
;
1030 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1031 typename _Compare
, typename _Alloc
>
1033 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::_M_erase(_Link_type __x
)
1035 // Erase without rebalancing.
1038 _M_erase(_S_right(__x
));
1039 _Link_type __y
= _S_left(__x
);
1045 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1046 typename _Compare
, typename _Alloc
>
1048 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1049 erase(iterator __first
, iterator __last
)
1051 if (__first
== begin() && __last
== end())
1054 while (__first
!= __last
) erase(__first
++);
1057 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1058 typename _Compare
, typename _Alloc
>
1060 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1061 erase(const _Key
* __first
, const _Key
* __last
)
1063 while (__first
!= __last
)
1067 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1068 typename _Compare
, typename _Alloc
>
1069 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1070 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::find(const _Key
& __k
)
1072 _Link_type __x
= _M_begin(); // Current node.
1073 _Link_type __y
= _M_end(); // Last node which is not less than __k.
1076 if (!_M_key_compare(_S_key(__x
), __k
))
1077 __y
= __x
, __x
= _S_left(__x
);
1079 __x
= _S_right(__x
);
1081 iterator __j
= iterator(__y
);
1082 return (__j
== end() || _M_key_compare(__k
, _S_key(__j
._M_node
))) ?
1086 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1087 typename _Compare
, typename _Alloc
>
1088 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1089 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1090 find(const _Key
& __k
) const
1092 _Const_Link_type __x
= _M_begin(); // Current node.
1093 _Const_Link_type __y
= _M_end(); // Last node which is not less than __k.
1097 if (!_M_key_compare(_S_key(__x
), __k
))
1098 __y
= __x
, __x
= _S_left(__x
);
1100 __x
= _S_right(__x
);
1102 const_iterator __j
= const_iterator(__y
);
1103 return (__j
== end() || _M_key_compare(__k
, _S_key(__j
._M_node
))) ?
1107 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1108 typename _Compare
, typename _Alloc
>
1109 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::size_type
1110 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1111 count(const _Key
& __k
) const
1113 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
1114 size_type __n
= std::distance(__p
.first
, __p
.second
);
1118 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1119 typename _Compare
, typename _Alloc
>
1120 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1121 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1122 lower_bound(const _Key
& __k
)
1124 _Link_type __x
= _M_begin(); // Current node.
1125 _Link_type __y
= _M_end(); // Last node which is not less than __k.
1128 if (!_M_key_compare(_S_key(__x
), __k
))
1129 __y
= __x
, __x
= _S_left(__x
);
1131 __x
= _S_right(__x
);
1133 return iterator(__y
);
1136 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1137 typename _Compare
, typename _Alloc
>
1138 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1139 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1140 lower_bound(const _Key
& __k
) const
1142 _Const_Link_type __x
= _M_begin(); // Current node.
1143 _Const_Link_type __y
= _M_end(); // Last node which is not less than __k.
1146 if (!_M_key_compare(_S_key(__x
), __k
))
1147 __y
= __x
, __x
= _S_left(__x
);
1149 __x
= _S_right(__x
);
1151 return const_iterator(__y
);
1154 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1155 typename _Compare
, typename _Alloc
>
1156 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1157 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1158 upper_bound(const _Key
& __k
)
1160 _Link_type __x
= _M_begin(); // Current node.
1161 _Link_type __y
= _M_end(); // Last node which is greater than __k.
1164 if (_M_key_compare(__k
, _S_key(__x
)))
1165 __y
= __x
, __x
= _S_left(__x
);
1167 __x
= _S_right(__x
);
1169 return iterator(__y
);
1172 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1173 typename _Compare
, typename _Alloc
>
1174 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1175 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1176 upper_bound(const _Key
& __k
) const
1178 _Const_Link_type __x
= _M_begin(); // Current node.
1179 _Const_Link_type __y
= _M_end(); // Last node which is greater than __k.
1182 if (_M_key_compare(__k
, _S_key(__x
)))
1183 __y
= __x
, __x
= _S_left(__x
);
1185 __x
= _S_right(__x
);
1187 return const_iterator(__y
);
1190 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1191 typename _Compare
, typename _Alloc
>
1193 pair
<typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
,
1194 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
>
1195 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1196 equal_range(const _Key
& __k
)
1197 { return pair
<iterator
, iterator
>(lower_bound(__k
), upper_bound(__k
)); }
1199 template<typename _Key
, typename _Val
, typename _KoV
,
1200 typename _Compare
, typename _Alloc
>
1202 pair
<typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::const_iterator
,
1203 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::const_iterator
>
1204 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>
1205 ::equal_range(const _Key
& __k
) const
1207 return pair
<const_iterator
,const_iterator
>(lower_bound(__k
),
1212 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
1213 const _Rb_tree_node_base
* __root
);
1215 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1216 typename _Compare
, typename _Alloc
>
1218 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
1220 if (_M_node_count
== 0 || begin() == end())
1221 return _M_node_count
== 0 && begin() == end() &&
1222 this->_M_header
._M_left
== &this->_M_header
&&
1223 this->_M_header
._M_right
== &this->_M_header
;
1225 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
1226 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
1228 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
1229 _Const_Link_type __L
= _S_left(__x
);
1230 _Const_Link_type __R
= _S_right(__x
);
1232 if (__x
->_M_color
== _S_red
)
1233 if ((__L
&& __L
->_M_color
== _S_red
)
1234 || (__R
&& __R
->_M_color
== _S_red
))
1237 if (__L
&& _M_key_compare(_S_key(__x
), _S_key(__L
)))
1239 if (__R
&& _M_key_compare(_S_key(__R
), _S_key(__x
)))
1242 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
1246 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1248 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))