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 { get_allocator().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 get_allocator().destroy(&__p->_M_value_field);
394 template<typename _Key_compare,
395 bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
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); }
467 return static_cast<_Const_Link_type>
468 (this->_M_impl._M_header._M_parent);
473 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
477 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
479 static const_reference
480 _S_value(_Const_Link_type __x)
481 { return __x->_M_value_field; }
484 _S_key(_Const_Link_type __x)
485 { return _KeyOfValue()(_S_value(__x)); }
488 _S_left(_Base_ptr __x)
489 { return static_cast<_Link_type>(__x->_M_left); }
491 static _Const_Link_type
492 _S_left(_Const_Base_ptr __x)
493 { return static_cast<_Const_Link_type>(__x->_M_left); }
496 _S_right(_Base_ptr __x)
497 { return static_cast<_Link_type>(__x->_M_right); }
499 static _Const_Link_type
500 _S_right(_Const_Base_ptr __x)
501 { return static_cast<_Const_Link_type>(__x->_M_right); }
503 static const_reference
504 _S_value(_Const_Base_ptr __x)
505 { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
508 _S_key(_Const_Base_ptr __x)
509 { return _KeyOfValue()(_S_value(__x)); }
512 _S_minimum(_Base_ptr __x)
513 { return _Rb_tree_node_base::_S_minimum(__x); }
515 static _Const_Base_ptr
516 _S_minimum(_Const_Base_ptr __x)
517 { return _Rb_tree_node_base::_S_minimum(__x); }
520 _S_maximum(_Base_ptr __x)
521 { return _Rb_tree_node_base::_S_maximum(__x); }
523 static _Const_Base_ptr
524 _S_maximum(_Const_Base_ptr __x)
525 { return _Rb_tree_node_base::_S_maximum(__x); }
528 typedef _Rb_tree_iterator<value_type> iterator;
529 typedef _Rb_tree_const_iterator<value_type> const_iterator;
531 typedef std::reverse_iterator<iterator> reverse_iterator;
532 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
536 _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
539 _M_copy(_Const_Link_type __x, _Link_type __p);
542 _M_erase(_Link_type __x);
545 // allocation/deallocation
549 _Rb_tree(const _Compare& __comp)
550 : _M_impl(allocator_type(), __comp)
553 _Rb_tree(const _Compare& __comp, const allocator_type& __a)
554 : _M_impl(__a, __comp)
557 _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
558 : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
560 if (__x._M_root() != 0)
562 _M_root() = _M_copy(__x._M_begin(), _M_end());
563 _M_leftmost() = _S_minimum(_M_root());
564 _M_rightmost() = _S_maximum(_M_root());
565 _M_impl._M_node_count = __x._M_impl._M_node_count;
570 { _M_erase(_M_begin()); }
572 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
573 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
578 { return _M_impl._M_key_compare; }
582 { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
587 return static_cast<_Const_Link_type>
588 (this->_M_impl._M_header._M_left);
593 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
597 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
601 { return reverse_iterator(end()); }
603 const_reverse_iterator
605 { return const_reverse_iterator(end()); }
609 { return reverse_iterator(begin()); }
611 const_reverse_iterator
613 { return const_reverse_iterator(begin()); }
617 { return _M_impl._M_node_count == 0; }
621 { return _M_impl._M_node_count; }
625 { return size_type(-1); }
628 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
632 insert_unique(const value_type& __x);
635 insert_equal(const value_type& __x);
638 insert_unique(iterator __position, const value_type& __x);
641 insert_equal(iterator __position, const value_type& __x);
643 template<typename _InputIterator>
645 insert_unique(_InputIterator __first, _InputIterator __last);
647 template<typename _InputIterator>
649 insert_equal(_InputIterator __first, _InputIterator __last);
652 erase(iterator __position);
655 erase(const key_type& __x);
658 erase(iterator __first, iterator __last);
661 erase(const key_type* __first, const key_type* __last);
666 _M_erase(_M_begin());
667 _M_leftmost() = _M_end();
669 _M_rightmost() = _M_end();
670 _M_impl._M_node_count = 0;
675 find(const key_type& __x);
678 find(const key_type& __x) const;
681 count(const key_type& __x) const;
684 lower_bound(const key_type& __x);
687 lower_bound(const key_type& __x) const;
690 upper_bound(const key_type& __x);
693 upper_bound(const key_type& __x) const;
695 pair<iterator,iterator>
696 equal_range(const key_type& __x);
698 pair<const_iterator, const_iterator>
699 equal_range(const key_type& __x) const;
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)
712 return __x.size() == __y.size()
713 && std::equal(__x.begin(), __x.end(), __y.begin());
716 template<typename _Key, typename _Val, typename _KeyOfValue,
717 typename _Compare, typename _Alloc>
719 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
720 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
722 return std::lexicographical_compare(__x.begin(), __x.end(),
723 __y.begin(), __y.end());
726 template<typename _Key, typename _Val, typename _KeyOfValue,
727 typename _Compare, typename _Alloc>
729 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
730 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
731 { return !(__x == __y); }
733 template<typename _Key, typename _Val, typename _KeyOfValue,
734 typename _Compare, typename _Alloc>
736 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
737 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
738 { return __y < __x; }
740 template<typename _Key, typename _Val, typename _KeyOfValue,
741 typename _Compare, typename _Alloc>
743 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
744 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
745 { return !(__y < __x); }
747 template<typename _Key, typename _Val, typename _KeyOfValue,
748 typename _Compare, typename _Alloc>
750 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
751 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
752 { return !(__x < __y); }
754 template<typename _Key, typename _Val, typename _KeyOfValue,
755 typename _Compare, typename _Alloc>
757 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
758 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
761 template<typename _Key, typename _Val, typename _KeyOfValue,
762 typename _Compare, typename _Alloc>
763 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
764 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
765 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
769 // Note that _Key may be a constant type.
771 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
772 if (__x._M_root() != 0)
774 _M_root() = _M_copy(__x._M_begin(), _M_end());
775 _M_leftmost() = _S_minimum(_M_root());
776 _M_rightmost() = _S_maximum(_M_root());
777 _M_impl._M_node_count = __x._M_impl._M_node_count;
783 template<typename _Key, typename _Val, typename _KeyOfValue,
784 typename _Compare, typename _Alloc>
785 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
786 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
787 _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
789 _Link_type __z = _M_create_node(__v);
792 __insert_left = (__x != 0 || __p == _M_end()
793 || _M_impl._M_key_compare(_KeyOfValue()(__v),
796 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
797 this->_M_impl._M_header);
798 ++_M_impl._M_node_count;
799 return iterator(__z);
802 template<typename _Key, typename _Val, typename _KeyOfValue,
803 typename _Compare, typename _Alloc>
804 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
805 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
806 insert_equal(const _Val& __v)
808 _Link_type __x = _M_begin();
809 _Link_type __y = _M_end();
813 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
814 _S_left(__x) : _S_right(__x);
816 return _M_insert(__x, __y, __v);
819 template<typename _Key, typename _Val, typename _KeyOfValue,
820 typename _Compare, typename _Alloc>
822 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
823 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
827 if (__t._M_root() != 0)
829 _M_root() = __t._M_root();
830 _M_leftmost() = __t._M_leftmost();
831 _M_rightmost() = __t._M_rightmost();
832 _M_root()->_M_parent = _M_end();
835 __t._M_leftmost() = __t._M_end();
836 __t._M_rightmost() = __t._M_end();
839 else if (__t._M_root() == 0)
841 __t._M_root() = _M_root();
842 __t._M_leftmost() = _M_leftmost();
843 __t._M_rightmost() = _M_rightmost();
844 __t._M_root()->_M_parent = __t._M_end();
847 _M_leftmost() = _M_end();
848 _M_rightmost() = _M_end();
852 std::swap(_M_root(),__t._M_root());
853 std::swap(_M_leftmost(),__t._M_leftmost());
854 std::swap(_M_rightmost(),__t._M_rightmost());
856 _M_root()->_M_parent = _M_end();
857 __t._M_root()->_M_parent = __t._M_end();
859 // No need to swap header's color as it does not change.
860 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
861 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
864 template<typename _Key, typename _Val, typename _KeyOfValue,
865 typename _Compare, typename _Alloc>
866 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
867 _Compare, _Alloc>::iterator, bool>
868 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
869 insert_unique(const _Val& __v)
871 _Link_type __x = _M_begin();
872 _Link_type __y = _M_end();
877 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
878 __x = __comp ? _S_left(__x) : _S_right(__x);
880 iterator __j = iterator(__y);
883 return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
886 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
887 return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
888 return pair<iterator, bool>(__j, false);
891 template<typename _Key, typename _Val, typename _KeyOfValue,
892 typename _Compare, typename _Alloc>
893 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
894 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
895 insert_unique(iterator __position, const _Val& __v)
897 if (__position._M_node == _M_end()
898 || __position._M_node == _M_rightmost())
901 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
903 return _M_insert(0, _M_rightmost(), __v);
905 return insert_unique(__v).first;
909 iterator __after = __position;
911 if (_M_impl._M_key_compare(_S_key(__position._M_node),
913 && _M_impl._M_key_compare(_KeyOfValue()(__v),
914 _S_key(__after._M_node)))
916 if (_S_right(__position._M_node) == 0)
917 return _M_insert(0, __position._M_node, __v);
919 return _M_insert(__after._M_node, __after._M_node, __v);
920 // First argument just needs to be non-null.
923 return insert_unique(__v).first;
927 template<typename _Key, typename _Val, typename _KeyOfValue,
928 typename _Compare, typename _Alloc>
929 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
930 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
931 insert_equal(iterator __position, const _Val& __v)
933 if (__position._M_node == _M_end()
934 || __position._M_node == _M_rightmost())
937 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
938 _S_key(_M_rightmost())))
939 return _M_insert(0, _M_rightmost(), __v);
941 return insert_equal(__v);
945 iterator __after = __position;
947 if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
948 _S_key(__position._M_node))
949 && !_M_impl._M_key_compare(_S_key(__after._M_node),
952 if (_S_right(__position._M_node) == 0)
953 return _M_insert(0, __position._M_node, __v);
955 return _M_insert(__after._M_node, __after._M_node, __v);
956 // First argument just needs to be non-null.
959 return insert_equal(__v);
963 template<typename _Key, typename _Val, typename _KoV,
964 typename _Cmp, typename _Alloc>
967 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
968 insert_equal(_II __first, _II __last)
970 for (; __first != __last; ++__first)
971 insert_equal(end(), *__first);
974 template<typename _Key, typename _Val, typename _KoV,
975 typename _Cmp, typename _Alloc>
978 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
979 insert_unique(_II __first, _II __last)
981 for (; __first != __last; ++__first)
982 insert_unique(end(), *__first);
985 template<typename _Key, typename _Val, typename _KeyOfValue,
986 typename _Compare, typename _Alloc>
988 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
989 erase(iterator __position)
992 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
994 this->_M_impl._M_header));
996 --_M_impl._M_node_count;
999 template<typename _Key, typename _Val, typename _KeyOfValue,
1000 typename _Compare, typename _Alloc>
1001 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1002 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1003 erase(const _Key& __x)
1005 pair<iterator,iterator> __p = equal_range(__x);
1006 size_type __n = std::distance(__p.first, __p.second);
1007 erase(__p.first, __p.second);
1011 template<typename _Key, typename _Val, typename _KoV,
1012 typename _Compare, typename _Alloc>
1013 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1014 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1015 _M_copy(_Const_Link_type __x, _Link_type __p)
1017 // Structural copy. __x and __p must be non-null.
1018 _Link_type __top = _M_clone_node(__x);
1019 __top->_M_parent = __p;
1024 __top->_M_right = _M_copy(_S_right(__x), __top);
1030 _Link_type __y = _M_clone_node(__x);
1032 __y->_M_parent = __p;
1034 __y->_M_right = _M_copy(_S_right(__x), __y);
1042 __throw_exception_again;
1047 template<typename _Key, typename _Val, typename _KeyOfValue,
1048 typename _Compare, typename _Alloc>
1050 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1051 _M_erase(_Link_type __x)
1053 // Erase without rebalancing.
1056 _M_erase(_S_right(__x));
1057 _Link_type __y = _S_left(__x);
1063 template<typename _Key, typename _Val, typename _KeyOfValue,
1064 typename _Compare, typename _Alloc>
1066 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1067 erase(iterator __first, iterator __last)
1069 if (__first == begin() && __last == end())
1072 while (__first != __last)
1076 template<typename _Key, typename _Val, typename _KeyOfValue,
1077 typename _Compare, typename _Alloc>
1079 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1080 erase(const _Key* __first, const _Key* __last)
1082 while (__first != __last)
1086 template<typename _Key, typename _Val, typename _KeyOfValue,
1087 typename _Compare, typename _Alloc>
1088 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1089 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1090 find(const _Key& __k)
1092 _Link_type __x = _M_begin(); // Current node.
1093 _Link_type __y = _M_end(); // Last node which is not less than __k.
1096 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1097 __y = __x, __x = _S_left(__x);
1099 __x = _S_right(__x);
1101 iterator __j = iterator(__y);
1102 return (__j == end()
1103 || _M_impl._M_key_compare(__k,
1104 _S_key(__j._M_node))) ? end() : __j;
1107 template<typename _Key, typename _Val, typename _KeyOfValue,
1108 typename _Compare, typename _Alloc>
1109 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1110 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1111 find(const _Key& __k) const
1113 _Const_Link_type __x = _M_begin(); // Current node.
1114 _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1118 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1119 __y = __x, __x = _S_left(__x);
1121 __x = _S_right(__x);
1123 const_iterator __j = const_iterator(__y);
1124 return (__j == end()
1125 || _M_impl._M_key_compare(__k,
1126 _S_key(__j._M_node))) ? end() : __j;
1129 template<typename _Key, typename _Val, typename _KeyOfValue,
1130 typename _Compare, typename _Alloc>
1131 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1132 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1133 count(const _Key& __k) const
1135 pair<const_iterator, const_iterator> __p = equal_range(__k);
1136 const size_type __n = std::distance(__p.first, __p.second);
1140 template<typename _Key, typename _Val, typename _KeyOfValue,
1141 typename _Compare, typename _Alloc>
1142 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1143 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1144 lower_bound(const _Key& __k)
1146 _Link_type __x = _M_begin(); // Current node.
1147 _Link_type __y = _M_end(); // Last node which is not less than __k.
1150 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1151 __y = __x, __x = _S_left(__x);
1153 __x = _S_right(__x);
1155 return iterator(__y);
1158 template<typename _Key, typename _Val, typename _KeyOfValue,
1159 typename _Compare, typename _Alloc>
1160 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1161 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1162 lower_bound(const _Key& __k) const
1164 _Const_Link_type __x = _M_begin(); // Current node.
1165 _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1168 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1169 __y = __x, __x = _S_left(__x);
1171 __x = _S_right(__x);
1173 return const_iterator(__y);
1176 template<typename _Key, typename _Val, typename _KeyOfValue,
1177 typename _Compare, typename _Alloc>
1178 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1179 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1180 upper_bound(const _Key& __k)
1182 _Link_type __x = _M_begin(); // Current node.
1183 _Link_type __y = _M_end(); // Last node which is greater than __k.
1186 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1187 __y = __x, __x = _S_left(__x);
1189 __x = _S_right(__x);
1191 return iterator(__y);
1194 template<typename _Key, typename _Val, typename _KeyOfValue,
1195 typename _Compare, typename _Alloc>
1196 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1197 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1198 upper_bound(const _Key& __k) const
1200 _Const_Link_type __x = _M_begin(); // Current node.
1201 _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1204 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1205 __y = __x, __x = _S_left(__x);
1207 __x = _S_right(__x);
1209 return const_iterator(__y);
1212 template<typename _Key, typename _Val, typename _KeyOfValue,
1213 typename _Compare, typename _Alloc>
1215 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1216 _Compare, _Alloc>::iterator,
1217 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
1218 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1219 equal_range(const _Key& __k)
1220 { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1222 template<typename _Key, typename _Val, typename _KoV,
1223 typename _Compare, typename _Alloc>
1225 pair<typename _Rb_tree<_Key, _Val, _KoV,
1226 _Compare, _Alloc>::const_iterator,
1227 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1228 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1229 equal_range(const _Key& __k) const
1230 { return pair<const_iterator, const_iterator>(lower_bound(__k),
1231 upper_bound(__k)); }
1234 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1235 const _Rb_tree_node_base* __root);
1237 template<typename _Key, typename _Val, typename _KeyOfValue,
1238 typename _Compare, typename _Alloc>
1240 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1242 if (_M_impl._M_node_count == 0 || begin() == end())
1243 return _M_impl._M_node_count == 0 && begin() == end()
1244 && this->_M_impl._M_header._M_left == _M_end()
1245 && this->_M_impl._M_header._M_right == _M_end();
1247 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1248 for (const_iterator __it = begin(); __it != end(); ++__it)
1250 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1251 _Const_Link_type __L = _S_left(__x);
1252 _Const_Link_type __R = _S_right(__x);
1254 if (__x->_M_color == _S_red)
1255 if ((__L && __L->_M_color == _S_red)
1256 || (__R && __R->_M_color == _S_red))
1259 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1261 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1264 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1268 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1270 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))