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;
164 _Rb_tree_iterator() { }
166 _Rb_tree_iterator(_Link_type __x)
171 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
175 { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
180 _M_node = _Rb_tree_increment(_M_node);
188 _M_node = _Rb_tree_increment(_M_node);
195 _M_node = _Rb_tree_decrement(_M_node);
203 _M_node = _Rb_tree_decrement(_M_node);
208 operator==(const _Self& __x) const
209 { return _M_node == __x._M_node; }
212 operator!=(const _Self& __x) const
213 { return _M_node != __x._M_node; }
218 template<typename _Tp>
219 struct _Rb_tree_const_iterator
221 typedef _Tp value_type;
222 typedef const _Tp& reference;
223 typedef const _Tp* pointer;
225 typedef _Rb_tree_iterator<_Tp> iterator;
227 typedef bidirectional_iterator_tag iterator_category;
228 typedef ptrdiff_t difference_type;
230 typedef _Rb_tree_const_iterator<_Tp> _Self;
231 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
232 typedef const _Rb_tree_node<_Tp>* _Link_type;
234 _Rb_tree_const_iterator() { }
236 _Rb_tree_const_iterator(_Link_type __x)
239 _Rb_tree_const_iterator(const iterator& __it)
240 : _M_node(__it._M_node) { }
244 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
248 { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
253 _M_node = _Rb_tree_increment(_M_node);
261 _M_node = _Rb_tree_increment(_M_node);
268 _M_node = _Rb_tree_decrement(_M_node);
276 _M_node = _Rb_tree_decrement(_M_node);
281 operator==(const _Self& __x) const
282 { return _M_node == __x._M_node; }
285 operator!=(const _Self& __x) const
286 { return _M_node != __x._M_node; }
291 template<typename _Val>
293 operator==(const _Rb_tree_iterator<_Val>& __x,
294 const _Rb_tree_const_iterator<_Val>& __y)
295 { return __x._M_node == __y._M_node; }
297 template<typename _Val>
299 operator!=(const _Rb_tree_iterator<_Val>& __x,
300 const _Rb_tree_const_iterator<_Val>& __y)
301 { return __x._M_node != __y._M_node; }
304 _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
305 _Rb_tree_node_base*& __root);
308 _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
309 _Rb_tree_node_base*& __root);
312 _Rb_tree_insert_and_rebalance(const bool __insert_left,
313 _Rb_tree_node_base* __x,
314 _Rb_tree_node_base* __p,
315 _Rb_tree_node_base& __header);
318 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
319 _Rb_tree_node_base& __header);
322 template<typename _Key, typename _Val, typename _KeyOfValue,
323 typename _Compare, typename _Alloc = allocator<_Val> >
326 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
330 typedef _Rb_tree_node_base* _Base_ptr;
331 typedef const _Rb_tree_node_base* _Const_Base_ptr;
332 typedef _Rb_tree_node<_Val> _Rb_tree_node;
335 typedef _Key key_type;
336 typedef _Val value_type;
337 typedef value_type* pointer;
338 typedef const value_type* const_pointer;
339 typedef value_type& reference;
340 typedef const value_type& const_reference;
341 typedef _Rb_tree_node* _Link_type;
342 typedef const _Rb_tree_node* _Const_Link_type;
343 typedef size_t size_type;
344 typedef ptrdiff_t difference_type;
345 typedef _Alloc allocator_type;
348 get_allocator() const
349 { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
354 { return _M_impl._Node_allocator::allocate(1); }
357 _M_put_node(_Rb_tree_node* __p)
358 { _M_impl._Node_allocator::deallocate(__p, 1); }
361 _M_create_node(const value_type& __x)
363 _Link_type __tmp = _M_get_node();
365 { get_allocator().construct(&__tmp->_M_value_field, __x); }
369 __throw_exception_again;
375 _M_clone_node(_Const_Link_type __x)
377 _Link_type __tmp = _M_create_node(__x->_M_value_field);
378 __tmp->_M_color = __x->_M_color;
385 destroy_node(_Link_type __p)
387 get_allocator().destroy(&__p->_M_value_field);
392 template<typename _Key_compare,
393 bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type>
394 struct _Rb_tree_impl : public _Node_allocator
396 _Key_compare _M_key_compare;
397 _Rb_tree_node_base _M_header;
398 size_type _M_node_count; // Keeps track of size of tree.
400 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
401 const _Key_compare& __comp = _Key_compare())
402 : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
404 this->_M_header._M_color = _S_red;
405 this->_M_header._M_parent = 0;
406 this->_M_header._M_left = &this->_M_header;
407 this->_M_header._M_right = &this->_M_header;
411 // Specialization for _Comparison types that are not capable of
412 // being base classes / super classes.
413 template<typename _Key_compare>
414 struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
416 _Key_compare _M_key_compare;
417 _Rb_tree_node_base _M_header;
418 size_type _M_node_count; // Keeps track of size of tree.
420 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
421 const _Key_compare& __comp = _Key_compare())
422 : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
424 this->_M_header._M_color = _S_red;
425 this->_M_header._M_parent = 0;
426 this->_M_header._M_left = &this->_M_header;
427 this->_M_header._M_right = &this->_M_header;
431 _Rb_tree_impl<_Compare> _M_impl;
436 { return this->_M_impl._M_header._M_parent; }
440 { return this->_M_impl._M_header._M_parent; }
444 { return this->_M_impl._M_header._M_left; }
448 { return this->_M_impl._M_header._M_left; }
452 { return this->_M_impl._M_header._M_right; }
456 { return this->_M_impl._M_header._M_right; }
460 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
465 return static_cast<_Const_Link_type>
466 (this->_M_impl._M_header._M_parent);
471 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
475 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
477 static const_reference
478 _S_value(_Const_Link_type __x)
479 { return __x->_M_value_field; }
482 _S_key(_Const_Link_type __x)
483 { return _KeyOfValue()(_S_value(__x)); }
486 _S_left(_Base_ptr __x)
487 { return static_cast<_Link_type>(__x->_M_left); }
489 static _Const_Link_type
490 _S_left(_Const_Base_ptr __x)
491 { return static_cast<_Const_Link_type>(__x->_M_left); }
494 _S_right(_Base_ptr __x)
495 { return static_cast<_Link_type>(__x->_M_right); }
497 static _Const_Link_type
498 _S_right(_Const_Base_ptr __x)
499 { return static_cast<_Const_Link_type>(__x->_M_right); }
501 static const_reference
502 _S_value(_Const_Base_ptr __x)
503 { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
506 _S_key(_Const_Base_ptr __x)
507 { return _KeyOfValue()(_S_value(__x)); }
510 _S_minimum(_Base_ptr __x)
511 { return _Rb_tree_node_base::_S_minimum(__x); }
513 static _Const_Base_ptr
514 _S_minimum(_Const_Base_ptr __x)
515 { return _Rb_tree_node_base::_S_minimum(__x); }
518 _S_maximum(_Base_ptr __x)
519 { return _Rb_tree_node_base::_S_maximum(__x); }
521 static _Const_Base_ptr
522 _S_maximum(_Const_Base_ptr __x)
523 { return _Rb_tree_node_base::_S_maximum(__x); }
526 typedef _Rb_tree_iterator<value_type> iterator;
527 typedef _Rb_tree_const_iterator<value_type> const_iterator;
529 typedef std::reverse_iterator<iterator> reverse_iterator;
530 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
534 _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
537 _M_copy(_Const_Link_type __x, _Link_type __p);
540 _M_erase(_Link_type __x);
543 // allocation/deallocation
547 _Rb_tree(const _Compare& __comp)
548 : _M_impl(allocator_type(), __comp)
551 _Rb_tree(const _Compare& __comp, const allocator_type& __a)
552 : _M_impl(__a, __comp)
555 _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
556 : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
558 if (__x._M_root() != 0)
560 _M_root() = _M_copy(__x._M_begin(), _M_end());
561 _M_leftmost() = _S_minimum(_M_root());
562 _M_rightmost() = _S_maximum(_M_root());
563 _M_impl._M_node_count = __x._M_impl._M_node_count;
568 { _M_erase(_M_begin()); }
570 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
571 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
576 { return _M_impl._M_key_compare; }
580 { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
585 return static_cast<_Const_Link_type>
586 (this->_M_impl._M_header._M_left);
591 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
595 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
599 { return reverse_iterator(end()); }
601 const_reverse_iterator
603 { return const_reverse_iterator(end()); }
607 { return reverse_iterator(begin()); }
609 const_reverse_iterator
611 { return const_reverse_iterator(begin()); }
615 { return _M_impl._M_node_count == 0; }
619 { return _M_impl._M_node_count; }
623 { return size_type(-1); }
626 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
630 insert_unique(const value_type& __x);
633 insert_equal(const value_type& __x);
636 insert_unique(iterator __position, const value_type& __x);
639 insert_equal(iterator __position, const value_type& __x);
641 template<typename _InputIterator>
643 insert_unique(_InputIterator __first, _InputIterator __last);
645 template<typename _InputIterator>
647 insert_equal(_InputIterator __first, _InputIterator __last);
650 erase(iterator __position);
653 erase(const key_type& __x);
656 erase(iterator __first, iterator __last);
659 erase(const key_type* __first, const key_type* __last);
664 _M_erase(_M_begin());
665 _M_leftmost() = _M_end();
667 _M_rightmost() = _M_end();
668 _M_impl._M_node_count = 0;
673 find(const key_type& __x);
676 find(const key_type& __x) const;
679 count(const key_type& __x) const;
682 lower_bound(const key_type& __x);
685 lower_bound(const key_type& __x) const;
688 upper_bound(const key_type& __x);
691 upper_bound(const key_type& __x) const;
693 pair<iterator,iterator>
694 equal_range(const key_type& __x);
696 pair<const_iterator, const_iterator>
697 equal_range(const key_type& __x) const;
704 template<typename _Key, typename _Val, typename _KeyOfValue,
705 typename _Compare, typename _Alloc>
707 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
708 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
710 return __x.size() == __y.size()
711 && std::equal(__x.begin(), __x.end(), __y.begin());
714 template<typename _Key, typename _Val, typename _KeyOfValue,
715 typename _Compare, typename _Alloc>
717 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
718 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
720 return std::lexicographical_compare(__x.begin(), __x.end(),
721 __y.begin(), __y.end());
724 template<typename _Key, typename _Val, typename _KeyOfValue,
725 typename _Compare, typename _Alloc>
727 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
728 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
729 { return !(__x == __y); }
731 template<typename _Key, typename _Val, typename _KeyOfValue,
732 typename _Compare, typename _Alloc>
734 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
735 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
736 { return __y < __x; }
738 template<typename _Key, typename _Val, typename _KeyOfValue,
739 typename _Compare, typename _Alloc>
741 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
742 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
743 { return !(__y < __x); }
745 template<typename _Key, typename _Val, typename _KeyOfValue,
746 typename _Compare, typename _Alloc>
748 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
749 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
750 { return !(__x < __y); }
752 template<typename _Key, typename _Val, typename _KeyOfValue,
753 typename _Compare, typename _Alloc>
755 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
756 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
759 template<typename _Key, typename _Val, typename _KeyOfValue,
760 typename _Compare, typename _Alloc>
761 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
762 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
763 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
767 // Note that _Key may be a constant type.
769 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
770 if (__x._M_root() != 0)
772 _M_root() = _M_copy(__x._M_begin(), _M_end());
773 _M_leftmost() = _S_minimum(_M_root());
774 _M_rightmost() = _S_maximum(_M_root());
775 _M_impl._M_node_count = __x._M_impl._M_node_count;
781 template<typename _Key, typename _Val, typename _KeyOfValue,
782 typename _Compare, typename _Alloc>
783 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
784 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
785 _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
787 _Link_type __z = _M_create_node(__v);
790 __insert_left = (__x != 0 || __p == _M_end()
791 || _M_impl._M_key_compare(_KeyOfValue()(__v),
794 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
795 this->_M_impl._M_header);
796 ++_M_impl._M_node_count;
797 return iterator(__z);
800 template<typename _Key, typename _Val, typename _KeyOfValue,
801 typename _Compare, typename _Alloc>
802 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
803 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
804 insert_equal(const _Val& __v)
806 _Link_type __x = _M_begin();
807 _Link_type __y = _M_end();
811 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
812 _S_left(__x) : _S_right(__x);
814 return _M_insert(__x, __y, __v);
817 template<typename _Key, typename _Val, typename _KeyOfValue,
818 typename _Compare, typename _Alloc>
820 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
821 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
825 if (__t._M_root() != 0)
827 _M_root() = __t._M_root();
828 _M_leftmost() = __t._M_leftmost();
829 _M_rightmost() = __t._M_rightmost();
830 _M_root()->_M_parent = _M_end();
833 __t._M_leftmost() = __t._M_end();
834 __t._M_rightmost() = __t._M_end();
837 else if (__t._M_root() == 0)
839 __t._M_root() = _M_root();
840 __t._M_leftmost() = _M_leftmost();
841 __t._M_rightmost() = _M_rightmost();
842 __t._M_root()->_M_parent = __t._M_end();
845 _M_leftmost() = _M_end();
846 _M_rightmost() = _M_end();
850 std::swap(_M_root(),__t._M_root());
851 std::swap(_M_leftmost(),__t._M_leftmost());
852 std::swap(_M_rightmost(),__t._M_rightmost());
854 _M_root()->_M_parent = _M_end();
855 __t._M_root()->_M_parent = __t._M_end();
857 // No need to swap header's color as it does not change.
858 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
859 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
862 template<typename _Key, typename _Val, typename _KeyOfValue,
863 typename _Compare, typename _Alloc>
864 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
865 _Compare, _Alloc>::iterator, bool>
866 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
867 insert_unique(const _Val& __v)
869 _Link_type __x = _M_begin();
870 _Link_type __y = _M_end();
875 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
876 __x = __comp ? _S_left(__x) : _S_right(__x);
878 iterator __j = iterator(__y);
881 return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
884 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
885 return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
886 return pair<iterator, bool>(__j, false);
889 template<typename _Key, typename _Val, typename _KeyOfValue,
890 typename _Compare, typename _Alloc>
891 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
892 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
893 insert_unique(iterator __position, const _Val& __v)
895 if (__position._M_node == _M_end()
896 || __position._M_node == _M_rightmost())
899 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
901 return _M_insert(0, _M_rightmost(), __v);
903 return insert_unique(__v).first;
907 iterator __after = __position;
909 if (_M_impl._M_key_compare(_S_key(__position._M_node),
911 && _M_impl._M_key_compare(_KeyOfValue()(__v),
912 _S_key(__after._M_node)))
914 if (_S_right(__position._M_node) == 0)
915 return _M_insert(0, __position._M_node, __v);
917 return _M_insert(__after._M_node, __after._M_node, __v);
918 // First argument just needs to be non-null.
921 return insert_unique(__v).first;
925 template<typename _Key, typename _Val, typename _KeyOfValue,
926 typename _Compare, typename _Alloc>
927 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
928 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
929 insert_equal(iterator __position, const _Val& __v)
931 if (__position._M_node == _M_end()
932 || __position._M_node == _M_rightmost())
935 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
936 _S_key(_M_rightmost())))
937 return _M_insert(0, _M_rightmost(), __v);
939 return insert_equal(__v);
943 iterator __after = __position;
945 if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
946 _S_key(__position._M_node))
947 && !_M_impl._M_key_compare(_S_key(__after._M_node),
950 if (_S_right(__position._M_node) == 0)
951 return _M_insert(0, __position._M_node, __v);
953 return _M_insert(__after._M_node, __after._M_node, __v);
954 // First argument just needs to be non-null.
957 return insert_equal(__v);
961 template<typename _Key, typename _Val, typename _KoV,
962 typename _Cmp, typename _Alloc>
965 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
966 insert_equal(_II __first, _II __last)
968 for (; __first != __last; ++__first)
969 insert_equal(end(), *__first);
972 template<typename _Key, typename _Val, typename _KoV,
973 typename _Cmp, typename _Alloc>
976 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
977 insert_unique(_II __first, _II __last)
979 for (; __first != __last; ++__first)
980 insert_unique(end(), *__first);
983 template<typename _Key, typename _Val, typename _KeyOfValue,
984 typename _Compare, typename _Alloc>
986 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
987 erase(iterator __position)
990 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
992 this->_M_impl._M_header));
994 --_M_impl._M_node_count;
997 template<typename _Key, typename _Val, typename _KeyOfValue,
998 typename _Compare, typename _Alloc>
999 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1000 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1001 erase(const _Key& __x)
1003 pair<iterator,iterator> __p = equal_range(__x);
1004 size_type __n = std::distance(__p.first, __p.second);
1005 erase(__p.first, __p.second);
1009 template<typename _Key, typename _Val, typename _KoV,
1010 typename _Compare, typename _Alloc>
1011 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1012 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1013 _M_copy(_Const_Link_type __x, _Link_type __p)
1015 // Structural copy. __x and __p must be non-null.
1016 _Link_type __top = _M_clone_node(__x);
1017 __top->_M_parent = __p;
1022 __top->_M_right = _M_copy(_S_right(__x), __top);
1028 _Link_type __y = _M_clone_node(__x);
1030 __y->_M_parent = __p;
1032 __y->_M_right = _M_copy(_S_right(__x), __y);
1040 __throw_exception_again;
1045 template<typename _Key, typename _Val, typename _KeyOfValue,
1046 typename _Compare, typename _Alloc>
1048 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1049 _M_erase(_Link_type __x)
1051 // Erase without rebalancing.
1054 _M_erase(_S_right(__x));
1055 _Link_type __y = _S_left(__x);
1061 template<typename _Key, typename _Val, typename _KeyOfValue,
1062 typename _Compare, typename _Alloc>
1064 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1065 erase(iterator __first, iterator __last)
1067 if (__first == begin() && __last == end())
1070 while (__first != __last)
1074 template<typename _Key, typename _Val, typename _KeyOfValue,
1075 typename _Compare, typename _Alloc>
1077 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1078 erase(const _Key* __first, const _Key* __last)
1080 while (__first != __last)
1084 template<typename _Key, typename _Val, typename _KeyOfValue,
1085 typename _Compare, typename _Alloc>
1086 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1087 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1088 find(const _Key& __k)
1090 _Link_type __x = _M_begin(); // Current node.
1091 _Link_type __y = _M_end(); // Last node which is not less than __k.
1094 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1095 __y = __x, __x = _S_left(__x);
1097 __x = _S_right(__x);
1099 iterator __j = iterator(__y);
1100 return (__j == end()
1101 || _M_impl._M_key_compare(__k,
1102 _S_key(__j._M_node))) ? end() : __j;
1105 template<typename _Key, typename _Val, typename _KeyOfValue,
1106 typename _Compare, typename _Alloc>
1107 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1108 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1109 find(const _Key& __k) const
1111 _Const_Link_type __x = _M_begin(); // Current node.
1112 _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1116 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1117 __y = __x, __x = _S_left(__x);
1119 __x = _S_right(__x);
1121 const_iterator __j = const_iterator(__y);
1122 return (__j == end()
1123 || _M_impl._M_key_compare(__k,
1124 _S_key(__j._M_node))) ? end() : __j;
1127 template<typename _Key, typename _Val, typename _KeyOfValue,
1128 typename _Compare, typename _Alloc>
1129 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1130 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1131 count(const _Key& __k) const
1133 pair<const_iterator, const_iterator> __p = equal_range(__k);
1134 const size_type __n = std::distance(__p.first, __p.second);
1138 template<typename _Key, typename _Val, typename _KeyOfValue,
1139 typename _Compare, typename _Alloc>
1140 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1141 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1142 lower_bound(const _Key& __k)
1144 _Link_type __x = _M_begin(); // Current node.
1145 _Link_type __y = _M_end(); // Last node which is not less than __k.
1148 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1149 __y = __x, __x = _S_left(__x);
1151 __x = _S_right(__x);
1153 return iterator(__y);
1156 template<typename _Key, typename _Val, typename _KeyOfValue,
1157 typename _Compare, typename _Alloc>
1158 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1159 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1160 lower_bound(const _Key& __k) const
1162 _Const_Link_type __x = _M_begin(); // Current node.
1163 _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1166 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1167 __y = __x, __x = _S_left(__x);
1169 __x = _S_right(__x);
1171 return const_iterator(__y);
1174 template<typename _Key, typename _Val, typename _KeyOfValue,
1175 typename _Compare, typename _Alloc>
1176 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1177 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1178 upper_bound(const _Key& __k)
1180 _Link_type __x = _M_begin(); // Current node.
1181 _Link_type __y = _M_end(); // Last node which is greater than __k.
1184 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1185 __y = __x, __x = _S_left(__x);
1187 __x = _S_right(__x);
1189 return iterator(__y);
1192 template<typename _Key, typename _Val, typename _KeyOfValue,
1193 typename _Compare, typename _Alloc>
1194 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1195 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1196 upper_bound(const _Key& __k) const
1198 _Const_Link_type __x = _M_begin(); // Current node.
1199 _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1202 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1203 __y = __x, __x = _S_left(__x);
1205 __x = _S_right(__x);
1207 return const_iterator(__y);
1210 template<typename _Key, typename _Val, typename _KeyOfValue,
1211 typename _Compare, typename _Alloc>
1213 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1214 _Compare, _Alloc>::iterator,
1215 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
1216 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1217 equal_range(const _Key& __k)
1218 { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1220 template<typename _Key, typename _Val, typename _KoV,
1221 typename _Compare, typename _Alloc>
1223 pair<typename _Rb_tree<_Key, _Val, _KoV,
1224 _Compare, _Alloc>::const_iterator,
1225 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1226 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1227 equal_range(const _Key& __k) const
1228 { return pair<const_iterator, const_iterator>(lower_bound(__k),
1229 upper_bound(__k)); }
1232 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1233 const _Rb_tree_node_base* __root);
1235 template<typename _Key, typename _Val, typename _KeyOfValue,
1236 typename _Compare, typename _Alloc>
1238 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1240 if (_M_impl._M_node_count == 0 || begin() == end())
1241 return _M_impl._M_node_count == 0 && begin() == end()
1242 && this->_M_impl._M_header._M_left == _M_end()
1243 && this->_M_impl._M_header._M_right == _M_end();
1245 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1246 for (const_iterator __it = begin(); __it != end(); ++__it)
1248 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1249 _Const_Link_type __L = _S_left(__x);
1250 _Const_Link_type __R = _S_right(__x);
1252 if (__x->_M_color == _S_red)
1253 if ((__L && __L->_M_color == _S_red)
1254 || (__R && __R->_M_color == _S_red))
1257 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1259 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1262 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1266 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1268 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))