1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 2, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
33 * Copyright (c) 1996,1997
34 * Silicon Graphics Computer Systems, Inc.
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation. Silicon Graphics makes no
41 * representations about the suitability of this software for any
42 * purpose. It is provided "as is" without express or implied warranty.
46 * Hewlett-Packard Company
48 * Permission to use, copy, modify, distribute and sell this software
49 * and its documentation for any purpose is hereby granted without fee,
50 * provided that the above copyright notice appear in all copies and
51 * that both that copyright notice and this permission notice appear
52 * in supporting documentation. Hewlett-Packard Company makes no
53 * representations about the suitability of this software for any
54 * purpose. It is provided "as is" without express or implied warranty.
60 * This is an internal header file, included by other library headers.
61 * You should not attempt to use it directly.
67 #include <bits/stl_algobase.h>
68 #include <bits/allocator.h>
69 #include <bits/stl_construct.h>
70 #include <bits/stl_function.h>
71 #include <bits/cpp_type_traits.h>
73 _GLIBCXX_BEGIN_NAMESPACE(std)
75 // Red-black tree class, designed for use in implementing STL
76 // associative containers (set, multiset, map, and multimap). The
77 // insertion and deletion algorithms are based on those in Cormen,
78 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
81 // (1) the header cell is maintained with links not only to the root
82 // but also to the leftmost node of the tree, to enable constant
83 // time begin(), and to the rightmost node of the tree, to enable
84 // linear time performance when used with the generic set algorithms
87 // (2) when a node being deleted has two children its successor node
88 // is relinked into its place, rather than copied, so that the only
89 // iterators invalidated are those referring to the deleted node.
91 enum _Rb_tree_color { _S_red = false, _S_black = true };
93 struct _Rb_tree_node_base
95 typedef _Rb_tree_node_base* _Base_ptr;
96 typedef const _Rb_tree_node_base* _Const_Base_ptr;
98 _Rb_tree_color _M_color;
104 _S_minimum(_Base_ptr __x)
106 while (__x->_M_left != 0) __x = __x->_M_left;
110 static _Const_Base_ptr
111 _S_minimum(_Const_Base_ptr __x)
113 while (__x->_M_left != 0) __x = __x->_M_left;
118 _S_maximum(_Base_ptr __x)
120 while (__x->_M_right != 0) __x = __x->_M_right;
124 static _Const_Base_ptr
125 _S_maximum(_Const_Base_ptr __x)
127 while (__x->_M_right != 0) __x = __x->_M_right;
132 template<typename _Val>
133 struct _Rb_tree_node : public _Rb_tree_node_base
135 typedef _Rb_tree_node<_Val>* _Link_type;
140 _Rb_tree_increment(_Rb_tree_node_base* __x);
142 const _Rb_tree_node_base*
143 _Rb_tree_increment(const _Rb_tree_node_base* __x);
146 _Rb_tree_decrement(_Rb_tree_node_base* __x);
148 const _Rb_tree_node_base*
149 _Rb_tree_decrement(const _Rb_tree_node_base* __x);
151 template<typename _Tp>
152 struct _Rb_tree_iterator
154 typedef _Tp value_type;
155 typedef _Tp& reference;
156 typedef _Tp* pointer;
158 typedef bidirectional_iterator_tag iterator_category;
159 typedef ptrdiff_t difference_type;
161 typedef _Rb_tree_iterator<_Tp> _Self;
162 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
163 typedef _Rb_tree_node<_Tp>* _Link_type;
169 _Rb_tree_iterator(_Link_type __x)
174 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
178 { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
183 _M_node = _Rb_tree_increment(_M_node);
191 _M_node = _Rb_tree_increment(_M_node);
198 _M_node = _Rb_tree_decrement(_M_node);
206 _M_node = _Rb_tree_decrement(_M_node);
211 operator==(const _Self& __x) const
212 { return _M_node == __x._M_node; }
215 operator!=(const _Self& __x) const
216 { return _M_node != __x._M_node; }
221 template<typename _Tp>
222 struct _Rb_tree_const_iterator
224 typedef _Tp value_type;
225 typedef const _Tp& reference;
226 typedef const _Tp* pointer;
228 typedef _Rb_tree_iterator<_Tp> iterator;
230 typedef bidirectional_iterator_tag iterator_category;
231 typedef ptrdiff_t difference_type;
233 typedef _Rb_tree_const_iterator<_Tp> _Self;
234 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
235 typedef const _Rb_tree_node<_Tp>* _Link_type;
237 _Rb_tree_const_iterator()
241 _Rb_tree_const_iterator(_Link_type __x)
244 _Rb_tree_const_iterator(const iterator& __it)
245 : _M_node(__it._M_node) { }
249 { return static_cast<_Link_type>(_M_node)->_M_value_field; }
253 { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
258 _M_node = _Rb_tree_increment(_M_node);
266 _M_node = _Rb_tree_increment(_M_node);
273 _M_node = _Rb_tree_decrement(_M_node);
281 _M_node = _Rb_tree_decrement(_M_node);
286 operator==(const _Self& __x) const
287 { return _M_node == __x._M_node; }
290 operator!=(const _Self& __x) const
291 { return _M_node != __x._M_node; }
296 template<typename _Val>
298 operator==(const _Rb_tree_iterator<_Val>& __x,
299 const _Rb_tree_const_iterator<_Val>& __y)
300 { return __x._M_node == __y._M_node; }
302 template<typename _Val>
304 operator!=(const _Rb_tree_iterator<_Val>& __x,
305 const _Rb_tree_const_iterator<_Val>& __y)
306 { return __x._M_node != __y._M_node; }
309 _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
310 _Rb_tree_node_base*& __root);
313 _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
314 _Rb_tree_node_base*& __root);
317 _Rb_tree_insert_and_rebalance(const bool __insert_left,
318 _Rb_tree_node_base* __x,
319 _Rb_tree_node_base* __p,
320 _Rb_tree_node_base& __header);
323 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
324 _Rb_tree_node_base& __header);
327 template<typename _Key, typename _Val, typename _KeyOfValue,
328 typename _Compare, typename _Alloc = allocator<_Val> >
331 typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
335 typedef _Rb_tree_node_base* _Base_ptr;
336 typedef const _Rb_tree_node_base* _Const_Base_ptr;
337 typedef _Rb_tree_node<_Val> _Rb_tree_node;
340 typedef _Key key_type;
341 typedef _Val value_type;
342 typedef value_type* pointer;
343 typedef const value_type* const_pointer;
344 typedef value_type& reference;
345 typedef const value_type& const_reference;
346 typedef _Rb_tree_node* _Link_type;
347 typedef const _Rb_tree_node* _Const_Link_type;
348 typedef size_t size_type;
349 typedef ptrdiff_t difference_type;
350 typedef _Alloc allocator_type;
353 _M_get_Node_allocator()
354 { return *static_cast<_Node_allocator*>(&this->_M_impl); }
356 const _Node_allocator&
357 _M_get_Node_allocator() const
358 { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
361 get_allocator() const
362 { return allocator_type(_M_get_Node_allocator()); }
367 { return _M_impl._Node_allocator::allocate(1); }
370 _M_put_node(_Rb_tree_node* __p)
371 { _M_impl._Node_allocator::deallocate(__p, 1); }
374 _M_create_node(const value_type& __x)
376 _Link_type __tmp = _M_get_node();
378 { get_allocator().construct(&__tmp->_M_value_field, __x); }
382 __throw_exception_again;
388 _M_clone_node(_Const_Link_type __x)
390 _Link_type __tmp = _M_create_node(__x->_M_value_field);
391 __tmp->_M_color = __x->_M_color;
398 _M_destroy_node(_Link_type __p)
400 get_allocator().destroy(&__p->_M_value_field);
405 template<typename _Key_compare,
406 bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
407 struct _Rb_tree_impl : public _Node_allocator
409 _Key_compare _M_key_compare;
410 _Rb_tree_node_base _M_header;
411 size_type _M_node_count; // Keeps track of size of tree.
413 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
414 const _Key_compare& __comp = _Key_compare())
415 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
418 this->_M_header._M_color = _S_red;
419 this->_M_header._M_parent = 0;
420 this->_M_header._M_left = &this->_M_header;
421 this->_M_header._M_right = &this->_M_header;
425 // Specialization for _Comparison types that are not capable of
426 // being base classes / super classes.
427 template<typename _Key_compare>
428 struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
430 _Key_compare _M_key_compare;
431 _Rb_tree_node_base _M_header;
432 size_type _M_node_count; // Keeps track of size of tree.
434 _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
435 const _Key_compare& __comp = _Key_compare())
436 : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
439 this->_M_header._M_color = _S_red;
440 this->_M_header._M_parent = 0;
441 this->_M_header._M_left = &this->_M_header;
442 this->_M_header._M_right = &this->_M_header;
446 _Rb_tree_impl<_Compare> _M_impl;
451 { return this->_M_impl._M_header._M_parent; }
455 { return this->_M_impl._M_header._M_parent; }
459 { return this->_M_impl._M_header._M_left; }
463 { return this->_M_impl._M_header._M_left; }
467 { return this->_M_impl._M_header._M_right; }
471 { return this->_M_impl._M_header._M_right; }
475 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
480 return static_cast<_Const_Link_type>
481 (this->_M_impl._M_header._M_parent);
486 { return static_cast<_Link_type>(&this->_M_impl._M_header); }
490 { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
492 static const_reference
493 _S_value(_Const_Link_type __x)
494 { return __x->_M_value_field; }
497 _S_key(_Const_Link_type __x)
498 { return _KeyOfValue()(_S_value(__x)); }
501 _S_left(_Base_ptr __x)
502 { return static_cast<_Link_type>(__x->_M_left); }
504 static _Const_Link_type
505 _S_left(_Const_Base_ptr __x)
506 { return static_cast<_Const_Link_type>(__x->_M_left); }
509 _S_right(_Base_ptr __x)
510 { return static_cast<_Link_type>(__x->_M_right); }
512 static _Const_Link_type
513 _S_right(_Const_Base_ptr __x)
514 { return static_cast<_Const_Link_type>(__x->_M_right); }
516 static const_reference
517 _S_value(_Const_Base_ptr __x)
518 { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
521 _S_key(_Const_Base_ptr __x)
522 { return _KeyOfValue()(_S_value(__x)); }
525 _S_minimum(_Base_ptr __x)
526 { return _Rb_tree_node_base::_S_minimum(__x); }
528 static _Const_Base_ptr
529 _S_minimum(_Const_Base_ptr __x)
530 { return _Rb_tree_node_base::_S_minimum(__x); }
533 _S_maximum(_Base_ptr __x)
534 { return _Rb_tree_node_base::_S_maximum(__x); }
536 static _Const_Base_ptr
537 _S_maximum(_Const_Base_ptr __x)
538 { return _Rb_tree_node_base::_S_maximum(__x); }
541 typedef _Rb_tree_iterator<value_type> iterator;
542 typedef _Rb_tree_const_iterator<value_type> const_iterator;
544 typedef std::reverse_iterator<iterator> reverse_iterator;
545 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
549 _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
551 // _GLIBCXX_RESOLVE_LIB_DEFECTS
552 // 233. Insertion hints in associative containers.
554 _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
557 _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,
558 const value_type& __v);
561 _M_copy(_Const_Link_type __x, _Link_type __p);
564 _M_erase(_Link_type __x);
567 // allocation/deallocation
571 _Rb_tree(const _Compare& __comp)
572 : _M_impl(allocator_type(), __comp)
575 _Rb_tree(const _Compare& __comp, const allocator_type& __a)
576 : _M_impl(__a, __comp)
579 _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
580 : _M_impl(__x._M_get_Node_allocator(), __x._M_impl._M_key_compare)
582 if (__x._M_root() != 0)
584 _M_root() = _M_copy(__x._M_begin(), _M_end());
585 _M_leftmost() = _S_minimum(_M_root());
586 _M_rightmost() = _S_maximum(_M_root());
587 _M_impl._M_node_count = __x._M_impl._M_node_count;
592 { _M_erase(_M_begin()); }
594 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
595 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
600 { return _M_impl._M_key_compare; }
605 return iterator(static_cast<_Link_type>
606 (this->_M_impl._M_header._M_left));
612 return const_iterator(static_cast<_Const_Link_type>
613 (this->_M_impl._M_header._M_left));
618 { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
623 return const_iterator(static_cast<_Const_Link_type>
624 (&this->_M_impl._M_header));
629 { return reverse_iterator(end()); }
631 const_reverse_iterator
633 { return const_reverse_iterator(end()); }
637 { return reverse_iterator(begin()); }
639 const_reverse_iterator
641 { return const_reverse_iterator(begin()); }
645 { return _M_impl._M_node_count == 0; }
649 { return _M_impl._M_node_count; }
653 { return get_allocator().max_size(); }
656 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
660 _M_insert_unique(const value_type& __x);
663 _M_insert_equal(const value_type& __x);
665 // _GLIBCXX_RESOLVE_LIB_DEFECTS
666 // 233. Insertion hints in associative containers.
668 _M_insert_equal_lower(const value_type& __x);
671 _M_insert_unique(iterator __position, const value_type& __x);
674 _M_insert_unique(const_iterator __position, const value_type& __x);
677 _M_insert_equal(iterator __position, const value_type& __x);
680 _M_insert_equal(const_iterator __position, const value_type& __x);
682 template<typename _InputIterator>
684 _M_insert_unique(_InputIterator __first, _InputIterator __last);
686 template<typename _InputIterator>
688 _M_insert_equal(_InputIterator __first, _InputIterator __last);
691 erase(iterator __position);
694 erase(const_iterator __position);
697 erase(const key_type& __x);
700 erase(iterator __first, iterator __last);
703 erase(const_iterator __first, const_iterator __last);
706 erase(const key_type* __first, const key_type* __last);
711 _M_erase(_M_begin());
712 _M_leftmost() = _M_end();
714 _M_rightmost() = _M_end();
715 _M_impl._M_node_count = 0;
720 find(const key_type& __x);
723 find(const key_type& __x) const;
726 count(const key_type& __x) const;
729 lower_bound(const key_type& __x);
732 lower_bound(const key_type& __x) const;
735 upper_bound(const key_type& __x);
738 upper_bound(const key_type& __x) const;
740 pair<iterator,iterator>
741 equal_range(const key_type& __x);
743 pair<const_iterator, const_iterator>
744 equal_range(const key_type& __x) const;
751 template<typename _Key, typename _Val, typename _KeyOfValue,
752 typename _Compare, typename _Alloc>
754 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
755 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
757 return __x.size() == __y.size()
758 && std::equal(__x.begin(), __x.end(), __y.begin());
761 template<typename _Key, typename _Val, typename _KeyOfValue,
762 typename _Compare, typename _Alloc>
764 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
765 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
767 return std::lexicographical_compare(__x.begin(), __x.end(),
768 __y.begin(), __y.end());
771 template<typename _Key, typename _Val, typename _KeyOfValue,
772 typename _Compare, typename _Alloc>
774 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
775 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
776 { return !(__x == __y); }
778 template<typename _Key, typename _Val, typename _KeyOfValue,
779 typename _Compare, typename _Alloc>
781 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
782 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
783 { return __y < __x; }
785 template<typename _Key, typename _Val, typename _KeyOfValue,
786 typename _Compare, typename _Alloc>
788 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
789 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
790 { return !(__y < __x); }
792 template<typename _Key, typename _Val, typename _KeyOfValue,
793 typename _Compare, typename _Alloc>
795 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
796 const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
797 { return !(__x < __y); }
799 template<typename _Key, typename _Val, typename _KeyOfValue,
800 typename _Compare, typename _Alloc>
802 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
803 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
806 template<typename _Key, typename _Val, typename _KeyOfValue,
807 typename _Compare, typename _Alloc>
808 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
809 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
810 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
814 // Note that _Key may be a constant type.
816 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
817 if (__x._M_root() != 0)
819 _M_root() = _M_copy(__x._M_begin(), _M_end());
820 _M_leftmost() = _S_minimum(_M_root());
821 _M_rightmost() = _S_maximum(_M_root());
822 _M_impl._M_node_count = __x._M_impl._M_node_count;
828 template<typename _Key, typename _Val, typename _KeyOfValue,
829 typename _Compare, typename _Alloc>
830 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
831 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
832 _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
834 bool __insert_left = (__x != 0 || __p == _M_end()
835 || _M_impl._M_key_compare(_KeyOfValue()(__v),
838 _Link_type __z = _M_create_node(__v);
840 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
841 this->_M_impl._M_header);
842 ++_M_impl._M_node_count;
843 return iterator(__z);
846 template<typename _Key, typename _Val, typename _KeyOfValue,
847 typename _Compare, typename _Alloc>
848 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
849 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
850 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
852 bool __insert_left = (__x != 0 || __p == _M_end()
853 || !_M_impl._M_key_compare(_S_key(__p),
854 _KeyOfValue()(__v)));
856 _Link_type __z = _M_create_node(__v);
858 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
859 this->_M_impl._M_header);
860 ++_M_impl._M_node_count;
861 return iterator(__z);
864 template<typename _Key, typename _Val, typename _KeyOfValue,
865 typename _Compare, typename _Alloc>
866 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
867 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
868 _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
870 bool __insert_left = (__x != 0 || __p == _M_end()
871 || _M_impl._M_key_compare(_KeyOfValue()(__v),
874 _Link_type __z = _M_create_node(__v);
876 _Rb_tree_insert_and_rebalance(__insert_left, __z,
877 const_cast<_Base_ptr>(__p),
878 this->_M_impl._M_header);
879 ++_M_impl._M_node_count;
880 return const_iterator(__z);
883 template<typename _Key, typename _Val, typename _KeyOfValue,
884 typename _Compare, typename _Alloc>
885 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
886 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
887 _M_insert_equal(const _Val& __v)
889 _Link_type __x = _M_begin();
890 _Link_type __y = _M_end();
894 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
895 _S_left(__x) : _S_right(__x);
897 return _M_insert(__x, __y, __v);
900 template<typename _Key, typename _Val, typename _KeyOfValue,
901 typename _Compare, typename _Alloc>
902 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
903 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
904 _M_insert_equal_lower(const _Val& __v)
906 _Link_type __x = _M_begin();
907 _Link_type __y = _M_end();
911 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
912 _S_left(__x) : _S_right(__x);
914 return _M_insert_lower(__x, __y, __v);
917 template<typename _Key, typename _Val, typename _KeyOfValue,
918 typename _Compare, typename _Alloc>
920 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
921 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
925 if (__t._M_root() != 0)
927 _M_root() = __t._M_root();
928 _M_leftmost() = __t._M_leftmost();
929 _M_rightmost() = __t._M_rightmost();
930 _M_root()->_M_parent = _M_end();
933 __t._M_leftmost() = __t._M_end();
934 __t._M_rightmost() = __t._M_end();
937 else if (__t._M_root() == 0)
939 __t._M_root() = _M_root();
940 __t._M_leftmost() = _M_leftmost();
941 __t._M_rightmost() = _M_rightmost();
942 __t._M_root()->_M_parent = __t._M_end();
945 _M_leftmost() = _M_end();
946 _M_rightmost() = _M_end();
950 std::swap(_M_root(),__t._M_root());
951 std::swap(_M_leftmost(),__t._M_leftmost());
952 std::swap(_M_rightmost(),__t._M_rightmost());
954 _M_root()->_M_parent = _M_end();
955 __t._M_root()->_M_parent = __t._M_end();
957 // No need to swap header's color as it does not change.
958 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
959 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
961 // _GLIBCXX_RESOLVE_LIB_DEFECTS
962 // 431. Swapping containers with unequal allocators.
963 std::__alloc_swap<_Node_allocator>::
964 _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
967 template<typename _Key, typename _Val, typename _KeyOfValue,
968 typename _Compare, typename _Alloc>
969 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
970 _Compare, _Alloc>::iterator, bool>
971 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
972 _M_insert_unique(const _Val& __v)
974 _Link_type __x = _M_begin();
975 _Link_type __y = _M_end();
980 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
981 __x = __comp ? _S_left(__x) : _S_right(__x);
983 iterator __j = iterator(__y);
986 return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
989 if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
990 return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
991 return pair<iterator, bool>(__j, false);
994 template<typename _Key, typename _Val, typename _KeyOfValue,
995 typename _Compare, typename _Alloc>
996 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
997 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
998 _M_insert_unique(iterator __position, const _Val& __v)
1001 if (__position._M_node == _M_end())
1004 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1005 _KeyOfValue()(__v)))
1006 return _M_insert(0, _M_rightmost(), __v);
1008 return _M_insert_unique(__v).first;
1010 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1011 _S_key(__position._M_node)))
1013 // First, try before...
1014 iterator __before = __position;
1015 if (__position._M_node == _M_leftmost()) // begin()
1016 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1017 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1018 _KeyOfValue()(__v)))
1020 if (_S_right(__before._M_node) == 0)
1021 return _M_insert(0, __before._M_node, __v);
1023 return _M_insert(__position._M_node,
1024 __position._M_node, __v);
1027 return _M_insert_unique(__v).first;
1029 else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1030 _KeyOfValue()(__v)))
1032 // ... then try after.
1033 iterator __after = __position;
1034 if (__position._M_node == _M_rightmost())
1035 return _M_insert(0, _M_rightmost(), __v);
1036 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1037 _S_key((++__after)._M_node)))
1039 if (_S_right(__position._M_node) == 0)
1040 return _M_insert(0, __position._M_node, __v);
1042 return _M_insert(__after._M_node, __after._M_node, __v);
1045 return _M_insert_unique(__v).first;
1048 return __position; // Equivalent keys.
1051 template<typename _Key, typename _Val, typename _KeyOfValue,
1052 typename _Compare, typename _Alloc>
1053 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1054 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1055 _M_insert_unique(const_iterator __position, const _Val& __v)
1058 if (__position._M_node == _M_end())
1061 && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1062 _KeyOfValue()(__v)))
1063 return _M_insert(0, _M_rightmost(), __v);
1065 return const_iterator(_M_insert_unique(__v).first);
1067 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1068 _S_key(__position._M_node)))
1070 // First, try before...
1071 const_iterator __before = __position;
1072 if (__position._M_node == _M_leftmost()) // begin()
1073 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1074 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1075 _KeyOfValue()(__v)))
1077 if (_S_right(__before._M_node) == 0)
1078 return _M_insert(0, __before._M_node, __v);
1080 return _M_insert(__position._M_node,
1081 __position._M_node, __v);
1084 return const_iterator(_M_insert_unique(__v).first);
1086 else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1087 _KeyOfValue()(__v)))
1089 // ... then try after.
1090 const_iterator __after = __position;
1091 if (__position._M_node == _M_rightmost())
1092 return _M_insert(0, _M_rightmost(), __v);
1093 else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1094 _S_key((++__after)._M_node)))
1096 if (_S_right(__position._M_node) == 0)
1097 return _M_insert(0, __position._M_node, __v);
1099 return _M_insert(__after._M_node, __after._M_node, __v);
1102 return const_iterator(_M_insert_unique(__v).first);
1105 return __position; // Equivalent keys.
1108 template<typename _Key, typename _Val, typename _KeyOfValue,
1109 typename _Compare, typename _Alloc>
1110 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1111 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1112 _M_insert_equal(iterator __position, const _Val& __v)
1115 if (__position._M_node == _M_end())
1118 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1119 _S_key(_M_rightmost())))
1120 return _M_insert(0, _M_rightmost(), __v);
1122 return _M_insert_equal(__v);
1124 else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1125 _KeyOfValue()(__v)))
1127 // First, try before...
1128 iterator __before = __position;
1129 if (__position._M_node == _M_leftmost()) // begin()
1130 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1131 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1132 _S_key((--__before)._M_node)))
1134 if (_S_right(__before._M_node) == 0)
1135 return _M_insert(0, __before._M_node, __v);
1137 return _M_insert(__position._M_node,
1138 __position._M_node, __v);
1141 return _M_insert_equal(__v);
1145 // ... then try after.
1146 iterator __after = __position;
1147 if (__position._M_node == _M_rightmost())
1148 return _M_insert(0, _M_rightmost(), __v);
1149 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1150 _KeyOfValue()(__v)))
1152 if (_S_right(__position._M_node) == 0)
1153 return _M_insert(0, __position._M_node, __v);
1155 return _M_insert(__after._M_node, __after._M_node, __v);
1158 return _M_insert_equal_lower(__v);
1162 template<typename _Key, typename _Val, typename _KeyOfValue,
1163 typename _Compare, typename _Alloc>
1164 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1165 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1166 _M_insert_equal(const_iterator __position, const _Val& __v)
1169 if (__position._M_node == _M_end())
1172 && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1173 _S_key(_M_rightmost())))
1174 return _M_insert(0, _M_rightmost(), __v);
1176 return const_iterator(_M_insert_equal(__v));
1178 else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1179 _KeyOfValue()(__v)))
1181 // First, try before...
1182 const_iterator __before = __position;
1183 if (__position._M_node == _M_leftmost()) // begin()
1184 return _M_insert(_M_leftmost(), _M_leftmost(), __v);
1185 else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1186 _S_key((--__before)._M_node)))
1188 if (_S_right(__before._M_node) == 0)
1189 return _M_insert(0, __before._M_node, __v);
1191 return _M_insert(__position._M_node,
1192 __position._M_node, __v);
1195 return const_iterator(_M_insert_equal(__v));
1199 // ... then try after.
1200 const_iterator __after = __position;
1201 if (__position._M_node == _M_rightmost())
1202 return _M_insert(0, _M_rightmost(), __v);
1203 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1204 _KeyOfValue()(__v)))
1206 if (_S_right(__position._M_node) == 0)
1207 return _M_insert(0, __position._M_node, __v);
1209 return _M_insert(__after._M_node, __after._M_node, __v);
1212 return const_iterator(_M_insert_equal_lower(__v));
1216 template<typename _Key, typename _Val, typename _KoV,
1217 typename _Cmp, typename _Alloc>
1220 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1221 _M_insert_equal(_II __first, _II __last)
1223 for (; __first != __last; ++__first)
1224 _M_insert_equal(end(), *__first);
1227 template<typename _Key, typename _Val, typename _KoV,
1228 typename _Cmp, typename _Alloc>
1231 _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1232 _M_insert_unique(_II __first, _II __last)
1234 for (; __first != __last; ++__first)
1235 _M_insert_unique(end(), *__first);
1238 template<typename _Key, typename _Val, typename _KeyOfValue,
1239 typename _Compare, typename _Alloc>
1241 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1242 erase(iterator __position)
1245 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1246 (__position._M_node,
1247 this->_M_impl._M_header));
1248 _M_destroy_node(__y);
1249 --_M_impl._M_node_count;
1252 template<typename _Key, typename _Val, typename _KeyOfValue,
1253 typename _Compare, typename _Alloc>
1255 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1256 erase(const_iterator __position)
1259 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1260 (const_cast<_Base_ptr>(__position._M_node),
1261 this->_M_impl._M_header));
1262 _M_destroy_node(__y);
1263 --_M_impl._M_node_count;
1266 template<typename _Key, typename _Val, typename _KeyOfValue,
1267 typename _Compare, typename _Alloc>
1268 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1269 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1270 erase(const _Key& __x)
1272 pair<iterator, iterator> __p = equal_range(__x);
1273 const size_type __old_size = size();
1274 erase(__p.first, __p.second);
1275 return __old_size - size();
1278 template<typename _Key, typename _Val, typename _KoV,
1279 typename _Compare, typename _Alloc>
1280 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1281 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1282 _M_copy(_Const_Link_type __x, _Link_type __p)
1284 // Structural copy. __x and __p must be non-null.
1285 _Link_type __top = _M_clone_node(__x);
1286 __top->_M_parent = __p;
1291 __top->_M_right = _M_copy(_S_right(__x), __top);
1297 _Link_type __y = _M_clone_node(__x);
1299 __y->_M_parent = __p;
1301 __y->_M_right = _M_copy(_S_right(__x), __y);
1309 __throw_exception_again;
1314 template<typename _Key, typename _Val, typename _KeyOfValue,
1315 typename _Compare, typename _Alloc>
1317 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1318 _M_erase(_Link_type __x)
1320 // Erase without rebalancing.
1323 _M_erase(_S_right(__x));
1324 _Link_type __y = _S_left(__x);
1325 _M_destroy_node(__x);
1330 template<typename _Key, typename _Val, typename _KeyOfValue,
1331 typename _Compare, typename _Alloc>
1333 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1334 erase(iterator __first, iterator __last)
1336 if (__first == begin() && __last == end())
1339 while (__first != __last)
1343 template<typename _Key, typename _Val, typename _KeyOfValue,
1344 typename _Compare, typename _Alloc>
1346 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1347 erase(const_iterator __first, const_iterator __last)
1349 if (__first == begin() && __last == end())
1352 while (__first != __last)
1356 template<typename _Key, typename _Val, typename _KeyOfValue,
1357 typename _Compare, typename _Alloc>
1359 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1360 erase(const _Key* __first, const _Key* __last)
1362 while (__first != __last)
1366 template<typename _Key, typename _Val, typename _KeyOfValue,
1367 typename _Compare, typename _Alloc>
1368 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1369 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1370 find(const _Key& __k)
1372 _Link_type __x = _M_begin(); // Current node.
1373 _Link_type __y = _M_end(); // Last node which is not less than __k.
1376 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1377 __y = __x, __x = _S_left(__x);
1379 __x = _S_right(__x);
1381 iterator __j = iterator(__y);
1382 return (__j == end()
1383 || _M_impl._M_key_compare(__k,
1384 _S_key(__j._M_node))) ? end() : __j;
1387 template<typename _Key, typename _Val, typename _KeyOfValue,
1388 typename _Compare, typename _Alloc>
1389 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1390 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1391 find(const _Key& __k) const
1393 _Const_Link_type __x = _M_begin(); // Current node.
1394 _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1398 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1399 __y = __x, __x = _S_left(__x);
1401 __x = _S_right(__x);
1403 const_iterator __j = const_iterator(__y);
1404 return (__j == end()
1405 || _M_impl._M_key_compare(__k,
1406 _S_key(__j._M_node))) ? end() : __j;
1409 template<typename _Key, typename _Val, typename _KeyOfValue,
1410 typename _Compare, typename _Alloc>
1411 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1412 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1413 count(const _Key& __k) const
1415 pair<const_iterator, const_iterator> __p = equal_range(__k);
1416 const size_type __n = std::distance(__p.first, __p.second);
1420 template<typename _Key, typename _Val, typename _KeyOfValue,
1421 typename _Compare, typename _Alloc>
1422 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1423 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1424 lower_bound(const _Key& __k)
1426 _Link_type __x = _M_begin(); // Current node.
1427 _Link_type __y = _M_end(); // Last node which is not less than __k.
1430 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1431 __y = __x, __x = _S_left(__x);
1433 __x = _S_right(__x);
1435 return iterator(__y);
1438 template<typename _Key, typename _Val, typename _KeyOfValue,
1439 typename _Compare, typename _Alloc>
1440 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1441 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1442 lower_bound(const _Key& __k) const
1444 _Const_Link_type __x = _M_begin(); // Current node.
1445 _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
1448 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1449 __y = __x, __x = _S_left(__x);
1451 __x = _S_right(__x);
1453 return const_iterator(__y);
1456 template<typename _Key, typename _Val, typename _KeyOfValue,
1457 typename _Compare, typename _Alloc>
1458 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1459 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1460 upper_bound(const _Key& __k)
1462 _Link_type __x = _M_begin(); // Current node.
1463 _Link_type __y = _M_end(); // Last node which is greater than __k.
1466 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1467 __y = __x, __x = _S_left(__x);
1469 __x = _S_right(__x);
1471 return iterator(__y);
1474 template<typename _Key, typename _Val, typename _KeyOfValue,
1475 typename _Compare, typename _Alloc>
1476 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1477 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1478 upper_bound(const _Key& __k) const
1480 _Const_Link_type __x = _M_begin(); // Current node.
1481 _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
1484 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1485 __y = __x, __x = _S_left(__x);
1487 __x = _S_right(__x);
1489 return const_iterator(__y);
1492 template<typename _Key, typename _Val, typename _KeyOfValue,
1493 typename _Compare, typename _Alloc>
1495 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1496 _Compare, _Alloc>::iterator,
1497 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
1498 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1499 equal_range(const _Key& __k)
1500 { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
1502 template<typename _Key, typename _Val, typename _KoV,
1503 typename _Compare, typename _Alloc>
1505 pair<typename _Rb_tree<_Key, _Val, _KoV,
1506 _Compare, _Alloc>::const_iterator,
1507 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
1508 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1509 equal_range(const _Key& __k) const
1510 { return pair<const_iterator, const_iterator>(lower_bound(__k),
1511 upper_bound(__k)); }
1514 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1515 const _Rb_tree_node_base* __root);
1517 template<typename _Key, typename _Val, typename _KeyOfValue,
1518 typename _Compare, typename _Alloc>
1520 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1522 if (_M_impl._M_node_count == 0 || begin() == end())
1523 return _M_impl._M_node_count == 0 && begin() == end()
1524 && this->_M_impl._M_header._M_left == _M_end()
1525 && this->_M_impl._M_header._M_right == _M_end();
1527 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1528 for (const_iterator __it = begin(); __it != end(); ++__it)
1530 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1531 _Const_Link_type __L = _S_left(__x);
1532 _Const_Link_type __R = _S_right(__x);
1534 if (__x->_M_color == _S_red)
1535 if ((__L && __L->_M_color == _S_red)
1536 || (__R && __R->_M_color == _S_red))
1539 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1541 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1544 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1548 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1550 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1555 _GLIBCXX_END_NAMESPACE