1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005 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;
167 _Rb_tree_iterator(_Link_type __x)
172 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
176 { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
181 _M_node = _Rb_tree_increment(_M_node);
189 _M_node = _Rb_tree_increment(_M_node);
196 _M_node = _Rb_tree_decrement(_M_node);
204 _M_node = _Rb_tree_decrement(_M_node);
209 operator==(const _Self& __x) const
210 { return _M_node == __x._M_node; }
213 operator!=(const _Self& __x) const
214 { return _M_node != __x._M_node; }
219 template<typename _Tp>
220 struct _Rb_tree_const_iterator
222 typedef _Tp value_type;
223 typedef const _Tp& reference;
224 typedef const _Tp* pointer;
226 typedef _Rb_tree_iterator<_Tp> iterator;
228 typedef bidirectional_iterator_tag iterator_category;
229 typedef ptrdiff_t difference_type;
231 typedef _Rb_tree_const_iterator<_Tp> _Self;
232 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
233 typedef const _Rb_tree_node<_Tp>* _Link_type;
235 _Rb_tree_const_iterator()
238 _Rb_tree_const_iterator(_Link_type __x)
241 _Rb_tree_const_iterator(const iterator& __it)
242 : _M_node(__it._M_node) { }
246 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
250 { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
255 _M_node = _Rb_tree_increment(_M_node);
263 _M_node = _Rb_tree_increment(_M_node);
270 _M_node = _Rb_tree_decrement(_M_node);
278 _M_node = _Rb_tree_decrement(_M_node);
283 operator==(const _Self& __x) const
284 { return _M_node == __x._M_node; }
287 operator!=(const _Self& __x) const
288 { return _M_node != __x._M_node; }
293 template<typename _Val>
295 operator==(const _Rb_tree_iterator<_Val>& __x,
296 const _Rb_tree_const_iterator<_Val>& __y)
297 { return __x._M_node == __y._M_node; }
299 template<typename _Val>
301 operator!=(const _Rb_tree_iterator<_Val>& __x,
302 const _Rb_tree_const_iterator<_Val>& __y)
303 { return __x._M_node != __y._M_node; }
306 _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
307 _Rb_tree_node_base*& __root);
310 _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
311 _Rb_tree_node_base*& __root);
314 _Rb_tree_insert_and_rebalance(const bool __insert_left,
315 _Rb_tree_node_base* __x,
316 _Rb_tree_node_base* __p,
317 _Rb_tree_node_base& __header);
320 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
321 _Rb_tree_node_base& __header);
324 template<typename _Key, typename _Val, typename _KeyOfValue,
325 typename _Compare, typename _Alloc = allocator<_Val> >
328 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
332 typedef _Rb_tree_node_base* _Base_ptr;
333 typedef const _Rb_tree_node_base* _Const_Base_ptr;
334 typedef _Rb_tree_node<_Val> _Rb_tree_node;
337 typedef _Key key_type;
338 typedef _Val value_type;
339 typedef value_type* pointer;
340 typedef const value_type* const_pointer;
341 typedef value_type& reference;
342 typedef const value_type& const_reference;
343 typedef _Rb_tree_node* _Link_type;
344 typedef const _Rb_tree_node* _Const_Link_type;
345 typedef size_t size_type;
346 typedef ptrdiff_t difference_type;
347 typedef _Alloc allocator_type;
350 get_allocator() const
351 { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
356 { return _M_impl._Node_allocator::allocate(1); }
359 _M_put_node(_Rb_tree_node* __p)
360 { _M_impl._Node_allocator::deallocate(__p, 1); }
363 _M_create_node(const value_type& __x)
365 _Link_type __tmp = _M_get_node();
367 { std::_Construct(&__tmp->_M_value_field, __x); }
371 __throw_exception_again;
377 _M_clone_node(_Const_Link_type __x)
379 _Link_type __tmp = _M_create_node(__x->_M_value_field);
380 __tmp->_M_color = __x->_M_color;
387 destroy_node(_Link_type __p)
389 std::_Destroy(&__p->_M_value_field);
394 template<typename _Key_compare,
395 bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type>
396 struct _Rb_tree_impl : public _Node_allocator
398 _Key_compare _M_key_compare;
399 _Rb_tree_node_base _M_header;
400 size_type _M_node_count; // Keeps track of size of tree.
402 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
403 const _Key_compare& __comp = _Key_compare())
404 : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
406 this->_M_header._M_color = _S_red;
407 this->_M_header._M_parent = 0;
408 this->_M_header._M_left = &this->_M_header;
409 this->_M_header._M_right = &this->_M_header;
413 // Specialization for _Comparison types that are not capable of
414 // being base classes / super classes.
415 template<typename _Key_compare>
416 struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
418 _Key_compare _M_key_compare;
419 _Rb_tree_node_base _M_header;
420 size_type _M_node_count; // Keeps track of size of tree.
422 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
423 const _Key_compare& __comp = _Key_compare())
424 : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
426 this->_M_header._M_color = _S_red;
427 this->_M_header._M_parent = 0;
428 this->_M_header._M_left = &this->_M_header;
429 this->_M_header._M_right = &this->_M_header;
433 _Rb_tree_impl<_Compare> _M_impl;
438 { return this->_M_impl._M_header._M_parent; }
442 { return this->_M_impl._M_header._M_parent; }
446 { return this->_M_impl._M_header._M_left; }
450 { return this->_M_impl._M_header._M_left; }
454 { return this->_M_impl._M_header._M_right; }
458 { return this->_M_impl._M_header._M_right; }
462 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
466 { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_parent); }
470 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
474 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
476 static const_reference
477 _S_value(_Const_Link_type __x)
478 { return __x->_M_value_field; }
481 _S_key(_Const_Link_type __x)
482 { return _KeyOfValue()(_S_value(__x)); }
485 _S_left(_Base_ptr __x)
486 { return static_cast<_Link_type>(__x->_M_left); }
488 static _Const_Link_type
489 _S_left(_Const_Base_ptr __x)
490 { return static_cast<_Const_Link_type>(__x->_M_left); }
493 _S_right(_Base_ptr __x)
494 { return static_cast<_Link_type>(__x->_M_right); }
496 static _Const_Link_type
497 _S_right(_Const_Base_ptr __x)
498 { return static_cast<_Const_Link_type>(__x->_M_right); }
500 static const_reference
501 _S_value(_Const_Base_ptr __x)
502 { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
505 _S_key(_Const_Base_ptr __x)
506 { return _KeyOfValue()(_S_value(__x)); }
509 _S_minimum(_Base_ptr __x)
510 { return _Rb_tree_node_base::_S_minimum(__x); }
512 static _Const_Base_ptr
513 _S_minimum(_Const_Base_ptr __x)
514 { return _Rb_tree_node_base::_S_minimum(__x); }
517 _S_maximum(_Base_ptr __x)
518 { return _Rb_tree_node_base::_S_maximum(__x); }
520 static _Const_Base_ptr
521 _S_maximum(_Const_Base_ptr __x)
522 { return _Rb_tree_node_base::_S_maximum(__x); }
525 typedef _Rb_tree_iterator<value_type> iterator;
526 typedef _Rb_tree_const_iterator<value_type> const_iterator;
528 typedef std::reverse_iterator<iterator> reverse_iterator;
529 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
533 _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
536 _M_copy(_Const_Link_type __x, _Link_type __p);
539 _M_erase(_Link_type __x);
542 // allocation/deallocation
546 _Rb_tree(const _Compare& __comp)
547 : _M_impl(allocator_type(), __comp)
550 _Rb_tree(const _Compare& __comp, const allocator_type& __a)
551 : _M_impl(__a, __comp)
554 _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
555 : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
557 if (__x._M_root() != 0)
559 _M_root() = _M_copy(__x._M_begin(), _M_end());
560 _M_leftmost() = _S_minimum(_M_root());
561 _M_rightmost() = _S_maximum(_M_root());
562 _M_impl._M_node_count = __x._M_impl._M_node_count;
567 { _M_erase(_M_begin()); }
569 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
570 operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
575 { return _M_impl._M_key_compare; }
579 { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
583 { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); }
587 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
591 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
595 { return reverse_iterator(end()); }
597 const_reverse_iterator
599 { return const_reverse_iterator(end()); }
603 { return reverse_iterator(begin()); }
605 const_reverse_iterator
607 { return const_reverse_iterator(begin()); }
611 { return _M_impl._M_node_count == 0; }
615 { return _M_impl._M_node_count; }
619 { return size_type(-1); }
622 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t);
626 insert_unique(const value_type& __x);
629 insert_equal(const value_type& __x);
632 insert_unique(iterator __position, const value_type& __x);
635 insert_equal(iterator __position, const value_type& __x);
637 template<typename _InputIterator>
639 insert_unique(_InputIterator __first, _InputIterator __last);
641 template<typename _InputIterator>
643 insert_equal(_InputIterator __first, _InputIterator __last);
646 erase(iterator __position);
649 erase(const key_type& __x);
652 erase(iterator __first, iterator __last);
655 erase(const key_type* __first, const key_type* __last);
660 _M_erase(_M_begin());
661 _M_leftmost() = _M_end();
663 _M_rightmost() = _M_end();
664 _M_impl._M_node_count = 0;
669 find(const key_type& __x);
672 find(const key_type& __x) const;
675 count(const key_type& __x) const;
678 lower_bound(const key_type& __x);
681 lower_bound(const key_type& __x) const;
684 upper_bound(const key_type& __x);
687 upper_bound(const key_type& __x) const;
689 pair<iterator,iterator>
690 equal_range(const key_type& __x);
692 pair<const_iterator, const_iterator>
693 equal_range(const key_type& __x) const;
700 template<typename _Key, typename _Val, typename _KeyOfValue,
701 typename _Compare, typename _Alloc>
703 operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
704 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
706 return __x.size() == __y.size()
707 && std::equal(__x.begin(), __x.end(), __y.begin());
710 template<typename _Key, typename _Val, typename _KeyOfValue,
711 typename _Compare, typename _Alloc>
713 operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
714 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
716 return std::lexicographical_compare(__x.begin(), __x.end(),
717 __y.begin(), __y.end());
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 !(__x == __y); }
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 __y < __x; }
734 template<typename _Key, typename _Val, typename _KeyOfValue,
735 typename _Compare, typename _Alloc>
737 operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
738 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
739 { return !(__y < __x); }
741 template<typename _Key, typename _Val, typename _KeyOfValue,
742 typename _Compare, typename _Alloc>
744 operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
745 const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
746 { return !(__x < __y); }
748 template<typename _Key, typename _Val, typename _KeyOfValue,
749 typename _Compare, typename _Alloc>
751 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
752 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
755 template<typename _Key, typename _Val, typename _KeyOfValue,
756 typename _Compare, typename _Alloc>
757 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
758 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
759 operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
763 // Note that _Key may be a constant type.
765 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
766 if (__x._M_root() != 0)
768 _M_root() = _M_copy(__x._M_begin(), _M_end());
769 _M_leftmost() = _S_minimum(_M_root());
770 _M_rightmost() = _S_maximum(_M_root());
771 _M_impl._M_node_count = __x._M_impl._M_node_count;
777 template<typename _Key, typename _Val, typename _KeyOfValue,
778 typename _Compare, typename _Alloc>
779 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
780 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
781 _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
783 _Link_type __z = _M_create_node(__v);
786 __insert_left = __x != 0 || __p == _M_end()
787 || _M_impl._M_key_compare(_KeyOfValue()(__v),
790 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
791 this->_M_impl._M_header);
792 ++_M_impl._M_node_count;
793 return iterator(__z);
796 template<typename _Key, typename _Val, typename _KeyOfValue,
797 typename _Compare, typename _Alloc>
798 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
799 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
800 insert_equal(const _Val& __v)
802 _Link_type __x = _M_begin();
803 _Link_type __y = _M_end();
807 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
808 _S_left(__x) : _S_right(__x);
810 return _M_insert(__x, __y, __v);
813 template<typename _Key, typename _Val, typename _KeyOfValue,
814 typename _Compare, typename _Alloc>
816 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
817 swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t)
821 if (__t._M_root() != 0)
823 _M_root() = __t._M_root();
824 _M_leftmost() = __t._M_leftmost();
825 _M_rightmost() = __t._M_rightmost();
826 _M_root()->_M_parent = _M_end();
829 __t._M_leftmost() = __t._M_end();
830 __t._M_rightmost() = __t._M_end();
833 else if (__t._M_root() == 0)
835 __t._M_root() = _M_root();
836 __t._M_leftmost() = _M_leftmost();
837 __t._M_rightmost() = _M_rightmost();
838 __t._M_root()->_M_parent = __t._M_end();
841 _M_leftmost() = _M_end();
842 _M_rightmost() = _M_end();
846 std::swap(_M_root(),__t._M_root());
847 std::swap(_M_leftmost(),__t._M_leftmost());
848 std::swap(_M_rightmost(),__t._M_rightmost());
850 _M_root()->_M_parent = _M_end();
851 __t._M_root()->_M_parent = __t._M_end();
853 // No need to swap header's color as it does not change.
854 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
855 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
858 template<typename _Key, typename _Val, typename _KeyOfValue,
859 typename _Compare, typename _Alloc>
860 pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator,
862 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
863 insert_unique(const _Val& __v)
865 _Link_type __x = _M_begin();
866 _Link_type __y = _M_end();
871 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
872 __x = __comp ? _S_left(__x) : _S_right(__x);
874 iterator __j = iterator(__y);
877 return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
880 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
881 return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
882 return pair<iterator,bool>(__j, false);
885 template<typename _Key, typename _Val, typename _KeyOfValue,
886 typename _Compare, typename _Alloc>
887 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
888 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
889 insert_unique(iterator __position, const _Val& __v)
891 if (__position._M_node == _M_leftmost())
895 && _M_impl._M_key_compare(_KeyOfValue()(__v),
896 _S_key(__position._M_node)))
897 return _M_insert(__position._M_node, __position._M_node, __v);
898 // First argument just needs to be non-null.
900 return insert_unique(__v).first;
902 else if (__position._M_node == _M_end())
905 if (_M_impl._M_key_compare(_S_key(_M_rightmost()),
907 return _M_insert(0, _M_rightmost(), __v);
909 return insert_unique(__v).first;
913 iterator __before = __position;
915 if (_M_impl._M_key_compare(_S_key(__before._M_node),
917 && _M_impl._M_key_compare(_KeyOfValue()(__v),
918 _S_key(__position._M_node)))
920 if (_S_right(__before._M_node) == 0)
921 return _M_insert(0, __before._M_node, __v);
923 return _M_insert(__position._M_node, __position._M_node, __v);
924 // First argument just needs to be non-null.
927 return insert_unique(__v).first;
931 template<typename _Key, typename _Val, typename _KeyOfValue,
932 typename _Compare, typename _Alloc>
933 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
934 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
935 insert_equal(iterator __position, const _Val& __v)
937 if (__position._M_node == _M_leftmost())
941 && !_M_impl._M_key_compare(_S_key(__position._M_node),
943 return _M_insert(__position._M_node, __position._M_node, __v);
944 // first argument just needs to be non-null
946 return insert_equal(__v);
948 else if (__position._M_node == _M_end())
951 if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
952 _S_key(_M_rightmost())))
953 return _M_insert(0, _M_rightmost(), __v);
955 return insert_equal(__v);
959 iterator __before = __position;
961 if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
962 _S_key(__before._M_node))
963 && !_M_impl._M_key_compare(_S_key(__position._M_node),
966 if (_S_right(__before._M_node) == 0)
967 return _M_insert(0, __before._M_node, __v);
969 return _M_insert(__position._M_node, __position._M_node, __v);
970 // First argument just needs to be non-null.
973 return insert_equal(__v);
977 template<typename _Key, typename _Val, typename _KoV,
978 typename _Cmp, typename _Alloc>
981 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
982 insert_equal(_II __first, _II __last)
984 for ( ; __first != __last; ++__first)
985 insert_equal(*__first);
988 template<typename _Key, typename _Val, typename _KoV,
989 typename _Cmp, typename _Alloc>
992 _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
993 insert_unique(_II __first, _II __last)
995 for ( ; __first != __last; ++__first)
996 insert_unique(*__first);
999 template<typename _Key, typename _Val, typename _KeyOfValue,
1000 typename _Compare, typename _Alloc>
1002 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
1005 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
1006 this->_M_impl._M_header));
1008 --_M_impl._M_node_count;
1011 template<typename _Key, typename _Val, typename _KeyOfValue,
1012 typename _Compare, typename _Alloc>
1013 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
1014 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
1016 pair<iterator,iterator> __p = equal_range(__x);
1017 size_type __n = std::distance(__p.first, __p.second);
1018 erase(__p.first, __p.second);
1022 template<typename _Key, typename _Val, typename _KoV,
1023 typename _Compare, typename _Alloc>
1024 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1025 _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>::
1026 _M_copy(_Const_Link_type __x, _Link_type __p)
1028 // Structural copy. __x and __p must be non-null.
1029 _Link_type __top = _M_clone_node(__x);
1030 __top->_M_parent = __p;
1035 __top->_M_right = _M_copy(_S_right(__x), __top);
1041 _Link_type __y = _M_clone_node(__x);
1043 __y->_M_parent = __p;
1045 __y->_M_right = _M_copy(_S_right(__x), __y);
1053 __throw_exception_again;
1058 template<typename _Key, typename _Val, typename _KeyOfValue,
1059 typename _Compare, typename _Alloc>
1061 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x)
1063 // Erase without rebalancing.
1066 _M_erase(_S_right(__x));
1067 _Link_type __y = _S_left(__x);
1073 template<typename _Key, typename _Val, typename _KeyOfValue,
1074 typename _Compare, typename _Alloc>
1076 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1077 erase(iterator __first, iterator __last)
1079 if (__first == begin() && __last == end())
1082 while (__first != __last) erase(__first++);
1085 template<typename _Key, typename _Val, typename _KeyOfValue,
1086 typename _Compare, typename _Alloc>
1088 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1089 erase(const _Key* __first, const _Key* __last)
1091 while (__first != __last)
1095 template<typename _Key, typename _Val, typename _KeyOfValue,
1096 typename _Compare, typename _Alloc>
1097 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1098 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
1100 _Link_type __x = _M_begin(); // Current node.
1101 _Link_type __y = _M_end(); // Last node which is not less than __k.
1104 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1105 __y = __x, __x = _S_left(__x);
1107 __x = _S_right(__x);
1109 iterator __j = iterator(__y);
1110 return (__j == end()
1111 || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
1114 template<typename _Key, typename _Val, typename _KeyOfValue,
1115 typename _Compare, typename _Alloc>
1116 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1117 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1118 find(const _Key& __k) const
1120 _Const_Link_type __x = _M_begin(); // Current node.
1121 _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1125 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1126 __y = __x, __x = _S_left(__x);
1128 __x = _S_right(__x);
1130 const_iterator __j = const_iterator(__y);
1131 return (__j == end()
1132 || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
1135 template<typename _Key, typename _Val, typename _KeyOfValue,
1136 typename _Compare, typename _Alloc>
1137 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
1138 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1139 count(const _Key& __k) const
1141 pair<const_iterator, const_iterator> __p = equal_range(__k);
1142 const size_type __n = std::distance(__p.first, __p.second);
1146 template<typename _Key, typename _Val, typename _KeyOfValue,
1147 typename _Compare, typename _Alloc>
1148 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1149 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1150 lower_bound(const _Key& __k)
1152 _Link_type __x = _M_begin(); // Current node.
1153 _Link_type __y = _M_end(); // Last node which is not less than __k.
1156 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1157 __y = __x, __x = _S_left(__x);
1159 __x = _S_right(__x);
1161 return iterator(__y);
1164 template<typename _Key, typename _Val, typename _KeyOfValue,
1165 typename _Compare, typename _Alloc>
1166 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1167 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1168 lower_bound(const _Key& __k) const
1170 _Const_Link_type __x = _M_begin(); // Current node.
1171 _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1174 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1175 __y = __x, __x = _S_left(__x);
1177 __x = _S_right(__x);
1179 return const_iterator(__y);
1182 template<typename _Key, typename _Val, typename _KeyOfValue,
1183 typename _Compare, typename _Alloc>
1184 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
1185 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1186 upper_bound(const _Key& __k)
1188 _Link_type __x = _M_begin(); // Current node.
1189 _Link_type __y = _M_end(); // Last node which is greater than __k.
1192 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1193 __y = __x, __x = _S_left(__x);
1195 __x = _S_right(__x);
1197 return iterator(__y);
1200 template<typename _Key, typename _Val, typename _KeyOfValue,
1201 typename _Compare, typename _Alloc>
1202 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
1203 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1204 upper_bound(const _Key& __k) const
1206 _Const_Link_type __x = _M_begin(); // Current node.
1207 _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1210 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1211 __y = __x, __x = _S_left(__x);
1213 __x = _S_right(__x);
1215 return const_iterator(__y);
1218 template<typename _Key, typename _Val, typename _KeyOfValue,
1219 typename _Compare, typename _Alloc>
1221 pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,
1222 _Compare,_Alloc>::iterator,
1223 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator>
1224 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
1225 equal_range(const _Key& __k)
1226 { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1228 template<typename _Key, typename _Val, typename _KoV,
1229 typename _Compare, typename _Alloc>
1231 pair<typename _Rb_tree<_Key, _Val, _KoV,
1232 _Compare, _Alloc>::const_iterator,
1233 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1234 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1235 equal_range(const _Key& __k) const
1236 { return pair<const_iterator, const_iterator>(lower_bound(__k),
1237 upper_bound(__k)); }
1240 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1241 const _Rb_tree_node_base* __root);
1243 template<typename _Key, typename _Val, typename _KeyOfValue,
1244 typename _Compare, typename _Alloc>
1246 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1248 if (_M_impl._M_node_count == 0 || begin() == end())
1249 return _M_impl._M_node_count == 0 && begin() == end()
1250 && this->_M_impl._M_header._M_left == _M_end()
1251 && this->_M_impl._M_header._M_right == _M_end();
1253 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1254 for (const_iterator __it = begin(); __it != end(); ++__it)
1256 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1257 _Const_Link_type __L = _S_left(__x);
1258 _Const_Link_type __R = _S_right(__x);
1260 if (__x->_M_color == _S_red)
1261 if ((__L && __L->_M_color == _S_red)
1262 || (__R && __R->_M_color == _S_red))
1265 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1267 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1270 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1274 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1276 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))