1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001-2013 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
27 * Copyright (c) 1996,1997
28 * Silicon Graphics Computer Systems, Inc.
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Silicon Graphics makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
40 * Hewlett-Packard Company
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Hewlett-Packard Company makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
53 /** @file bits/stl_tree.h
54 * This is an internal header file, included by other library headers.
55 * Do not attempt to use it directly. @headername{map,set}
61 #include <bits/stl_algobase.h>
62 #include <bits/allocator.h>
63 #include <bits/stl_function.h>
64 #include <bits/cpp_type_traits.h>
65 #if __cplusplus >= 201103L
66 #include <bits/alloc_traits.h>
69 namespace std
_GLIBCXX_VISIBILITY(default)
71 _GLIBCXX_BEGIN_NAMESPACE_VERSION
73 // Red-black tree class, designed for use in implementing STL
74 // associative containers (set, multiset, map, and multimap). The
75 // insertion and deletion algorithms are based on those in Cormen,
76 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
79 // (1) the header cell is maintained with links not only to the root
80 // but also to the leftmost node of the tree, to enable constant
81 // time begin(), and to the rightmost node of the tree, to enable
82 // linear time performance when used with the generic set algorithms
85 // (2) when a node being deleted has two children its successor node
86 // is relinked into its place, rather than copied, so that the only
87 // iterators invalidated are those referring to the deleted node.
89 enum _Rb_tree_color
{ _S_red
= false, _S_black
= true };
91 struct _Rb_tree_node_base
93 typedef _Rb_tree_node_base
* _Base_ptr
;
94 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
96 _Rb_tree_color _M_color
;
102 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
104 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
108 static _Const_Base_ptr
109 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
111 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
116 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
118 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
122 static _Const_Base_ptr
123 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
125 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
130 template<typename _Val
>
131 struct _Rb_tree_node
: public _Rb_tree_node_base
133 typedef _Rb_tree_node
<_Val
>* _Link_type
;
136 #if __cplusplus >= 201103L
137 template<typename
... _Args
>
138 _Rb_tree_node(_Args
&&... __args
)
139 : _Rb_tree_node_base(),
140 _M_value_field(std::forward
<_Args
>(__args
)...) { }
144 _GLIBCXX_PURE _Rb_tree_node_base
*
145 _Rb_tree_increment(_Rb_tree_node_base
* __x
) throw ();
147 _GLIBCXX_PURE
const _Rb_tree_node_base
*
148 _Rb_tree_increment(const _Rb_tree_node_base
* __x
) throw ();
150 _GLIBCXX_PURE _Rb_tree_node_base
*
151 _Rb_tree_decrement(_Rb_tree_node_base
* __x
) throw ();
153 _GLIBCXX_PURE
const _Rb_tree_node_base
*
154 _Rb_tree_decrement(const _Rb_tree_node_base
* __x
) throw ();
156 template<typename _Tp
>
157 struct _Rb_tree_iterator
159 typedef _Tp value_type
;
160 typedef _Tp
& reference
;
161 typedef _Tp
* pointer
;
163 typedef bidirectional_iterator_tag iterator_category
;
164 typedef ptrdiff_t difference_type
;
166 typedef _Rb_tree_iterator
<_Tp
> _Self
;
167 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
168 typedef _Rb_tree_node
<_Tp
>* _Link_type
;
170 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
174 _Rb_tree_iterator(_Link_type __x
) _GLIBCXX_NOEXCEPT
178 operator*() const _GLIBCXX_NOEXCEPT
179 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
182 operator->() const _GLIBCXX_NOEXCEPT
183 { return std::__addressof(static_cast<_Link_type
>
184 (_M_node
)->_M_value_field
); }
187 operator++() _GLIBCXX_NOEXCEPT
189 _M_node
= _Rb_tree_increment(_M_node
);
194 operator++(int) _GLIBCXX_NOEXCEPT
197 _M_node
= _Rb_tree_increment(_M_node
);
202 operator--() _GLIBCXX_NOEXCEPT
204 _M_node
= _Rb_tree_decrement(_M_node
);
209 operator--(int) _GLIBCXX_NOEXCEPT
212 _M_node
= _Rb_tree_decrement(_M_node
);
217 operator==(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
218 { return _M_node
== __x
._M_node
; }
221 operator!=(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
222 { return _M_node
!= __x
._M_node
; }
227 template<typename _Tp
>
228 struct _Rb_tree_const_iterator
230 typedef _Tp value_type
;
231 typedef const _Tp
& reference
;
232 typedef const _Tp
* pointer
;
234 typedef _Rb_tree_iterator
<_Tp
> iterator
;
236 typedef bidirectional_iterator_tag iterator_category
;
237 typedef ptrdiff_t difference_type
;
239 typedef _Rb_tree_const_iterator
<_Tp
> _Self
;
240 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr
;
241 typedef const _Rb_tree_node
<_Tp
>* _Link_type
;
243 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
247 _Rb_tree_const_iterator(_Link_type __x
) _GLIBCXX_NOEXCEPT
250 _Rb_tree_const_iterator(const iterator
& __it
) _GLIBCXX_NOEXCEPT
251 : _M_node(__it
._M_node
) { }
254 _M_const_cast() const _GLIBCXX_NOEXCEPT
255 { return iterator(static_cast<typename
iterator::_Link_type
>
256 (const_cast<typename
iterator::_Base_ptr
>(_M_node
))); }
259 operator*() const _GLIBCXX_NOEXCEPT
260 { return static_cast<_Link_type
>(_M_node
)->_M_value_field
; }
263 operator->() const _GLIBCXX_NOEXCEPT
264 { return std::__addressof(static_cast<_Link_type
>
265 (_M_node
)->_M_value_field
); }
268 operator++() _GLIBCXX_NOEXCEPT
270 _M_node
= _Rb_tree_increment(_M_node
);
275 operator++(int) _GLIBCXX_NOEXCEPT
278 _M_node
= _Rb_tree_increment(_M_node
);
283 operator--() _GLIBCXX_NOEXCEPT
285 _M_node
= _Rb_tree_decrement(_M_node
);
290 operator--(int) _GLIBCXX_NOEXCEPT
293 _M_node
= _Rb_tree_decrement(_M_node
);
298 operator==(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
299 { return _M_node
== __x
._M_node
; }
302 operator!=(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
303 { return _M_node
!= __x
._M_node
; }
308 template<typename _Val
>
310 operator==(const _Rb_tree_iterator
<_Val
>& __x
,
311 const _Rb_tree_const_iterator
<_Val
>& __y
) _GLIBCXX_NOEXCEPT
312 { return __x
._M_node
== __y
._M_node
; }
314 template<typename _Val
>
316 operator!=(const _Rb_tree_iterator
<_Val
>& __x
,
317 const _Rb_tree_const_iterator
<_Val
>& __y
) _GLIBCXX_NOEXCEPT
318 { return __x
._M_node
!= __y
._M_node
; }
321 _Rb_tree_insert_and_rebalance(const bool __insert_left
,
322 _Rb_tree_node_base
* __x
,
323 _Rb_tree_node_base
* __p
,
324 _Rb_tree_node_base
& __header
) throw ();
327 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
328 _Rb_tree_node_base
& __header
) throw ();
331 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
332 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
335 typedef typename
_Alloc::template rebind
<_Rb_tree_node
<_Val
> >::other
339 typedef _Rb_tree_node_base
* _Base_ptr
;
340 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
343 typedef _Key key_type
;
344 typedef _Val value_type
;
345 typedef value_type
* pointer
;
346 typedef const value_type
* const_pointer
;
347 typedef value_type
& reference
;
348 typedef const value_type
& const_reference
;
349 typedef _Rb_tree_node
<_Val
>* _Link_type
;
350 typedef const _Rb_tree_node
<_Val
>* _Const_Link_type
;
351 typedef size_t size_type
;
352 typedef ptrdiff_t difference_type
;
353 typedef _Alloc allocator_type
;
356 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
357 { return *static_cast<_Node_allocator
*>(&this->_M_impl
); }
359 const _Node_allocator
&
360 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
361 { return *static_cast<const _Node_allocator
*>(&this->_M_impl
); }
364 get_allocator() const _GLIBCXX_NOEXCEPT
365 { return allocator_type(_M_get_Node_allocator()); }
370 { return _M_impl
._Node_allocator::allocate(1); }
373 _M_put_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
374 { _M_impl
._Node_allocator::deallocate(__p
, 1); }
376 #if __cplusplus < 201103L
378 _M_create_node(const value_type
& __x
)
380 _Link_type __tmp
= _M_get_node();
382 { get_allocator().construct
383 (std::__addressof(__tmp
->_M_value_field
), __x
); }
387 __throw_exception_again
;
393 _M_destroy_node(_Link_type __p
)
395 get_allocator().destroy(std::__addressof(__p
->_M_value_field
));
399 template<typename
... _Args
>
401 _M_create_node(_Args
&&... __args
)
403 _Link_type __tmp
= _M_get_node();
406 allocator_traits
<_Node_allocator
>::
407 construct(_M_get_Node_allocator(), __tmp
,
408 std::forward
<_Args
>(__args
)...);
413 __throw_exception_again
;
419 _M_destroy_node(_Link_type __p
) noexcept
421 _M_get_Node_allocator().destroy(__p
);
427 _M_clone_node(_Const_Link_type __x
)
429 _Link_type __tmp
= _M_create_node(__x
->_M_value_field
);
430 __tmp
->_M_color
= __x
->_M_color
;
437 template<typename _Key_compare
,
438 bool _Is_pod_comparator
= __is_pod(_Key_compare
)>
439 struct _Rb_tree_impl
: public _Node_allocator
441 _Key_compare _M_key_compare
;
442 _Rb_tree_node_base _M_header
;
443 size_type _M_node_count
; // Keeps track of size of tree.
446 : _Node_allocator(), _M_key_compare(), _M_header(),
450 _Rb_tree_impl(const _Key_compare
& __comp
, const _Node_allocator
& __a
)
451 : _Node_allocator(__a
), _M_key_compare(__comp
), _M_header(),
455 #if __cplusplus >= 201103L
456 _Rb_tree_impl(const _Key_compare
& __comp
, _Node_allocator
&& __a
)
457 : _Node_allocator(std::move(__a
)), _M_key_compare(__comp
),
458 _M_header(), _M_node_count(0)
466 this->_M_header
._M_color
= _S_red
;
467 this->_M_header
._M_parent
= 0;
468 this->_M_header
._M_left
= &this->_M_header
;
469 this->_M_header
._M_right
= &this->_M_header
;
473 _Rb_tree_impl
<_Compare
> _M_impl
;
477 _M_root() _GLIBCXX_NOEXCEPT
478 { return this->_M_impl
._M_header
._M_parent
; }
481 _M_root() const _GLIBCXX_NOEXCEPT
482 { return this->_M_impl
._M_header
._M_parent
; }
485 _M_leftmost() _GLIBCXX_NOEXCEPT
486 { return this->_M_impl
._M_header
._M_left
; }
489 _M_leftmost() const _GLIBCXX_NOEXCEPT
490 { return this->_M_impl
._M_header
._M_left
; }
493 _M_rightmost() _GLIBCXX_NOEXCEPT
494 { return this->_M_impl
._M_header
._M_right
; }
497 _M_rightmost() const _GLIBCXX_NOEXCEPT
498 { return this->_M_impl
._M_header
._M_right
; }
501 _M_begin() _GLIBCXX_NOEXCEPT
502 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
505 _M_begin() const _GLIBCXX_NOEXCEPT
507 return static_cast<_Const_Link_type
>
508 (this->_M_impl
._M_header
._M_parent
);
512 _M_end() _GLIBCXX_NOEXCEPT
513 { return static_cast<_Link_type
>(&this->_M_impl
._M_header
); }
516 _M_end() const _GLIBCXX_NOEXCEPT
517 { return static_cast<_Const_Link_type
>(&this->_M_impl
._M_header
); }
519 static const_reference
520 _S_value(_Const_Link_type __x
)
521 { return __x
->_M_value_field
; }
524 _S_key(_Const_Link_type __x
)
525 { return _KeyOfValue()(_S_value(__x
)); }
528 _S_left(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
529 { return static_cast<_Link_type
>(__x
->_M_left
); }
531 static _Const_Link_type
532 _S_left(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
533 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
536 _S_right(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
537 { return static_cast<_Link_type
>(__x
->_M_right
); }
539 static _Const_Link_type
540 _S_right(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
541 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
543 static const_reference
544 _S_value(_Const_Base_ptr __x
)
545 { return static_cast<_Const_Link_type
>(__x
)->_M_value_field
; }
548 _S_key(_Const_Base_ptr __x
)
549 { return _KeyOfValue()(_S_value(__x
)); }
552 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
553 { return _Rb_tree_node_base::_S_minimum(__x
); }
555 static _Const_Base_ptr
556 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
557 { return _Rb_tree_node_base::_S_minimum(__x
); }
560 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
561 { return _Rb_tree_node_base::_S_maximum(__x
); }
563 static _Const_Base_ptr
564 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
565 { return _Rb_tree_node_base::_S_maximum(__x
); }
568 typedef _Rb_tree_iterator
<value_type
> iterator
;
569 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
571 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
572 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
575 pair
<_Base_ptr
, _Base_ptr
>
576 _M_get_insert_unique_pos(const key_type
& __k
);
578 pair
<_Base_ptr
, _Base_ptr
>
579 _M_get_insert_equal_pos(const key_type
& __k
);
581 pair
<_Base_ptr
, _Base_ptr
>
582 _M_get_insert_hint_unique_pos(const_iterator __pos
,
583 const key_type
& __k
);
585 pair
<_Base_ptr
, _Base_ptr
>
586 _M_get_insert_hint_equal_pos(const_iterator __pos
,
587 const key_type
& __k
);
589 #if __cplusplus >= 201103L
590 template<typename _Arg
>
592 _M_insert_(_Base_ptr __x
, _Base_ptr __y
, _Arg
&& __v
);
595 _M_insert_node(_Base_ptr __x
, _Base_ptr __y
, _Link_type __z
);
597 template<typename _Arg
>
599 _M_insert_lower(_Base_ptr __y
, _Arg
&& __v
);
601 template<typename _Arg
>
603 _M_insert_equal_lower(_Arg
&& __x
);
606 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
);
609 _M_insert_equal_lower_node(_Link_type __z
);
612 _M_insert_(_Base_ptr __x
, _Base_ptr __y
,
613 const value_type
& __v
);
615 // _GLIBCXX_RESOLVE_LIB_DEFECTS
616 // 233. Insertion hints in associative containers.
618 _M_insert_lower(_Base_ptr __y
, const value_type
& __v
);
621 _M_insert_equal_lower(const value_type
& __x
);
625 _M_copy(_Const_Link_type __x
, _Link_type __p
);
628 _M_erase(_Link_type __x
);
631 _M_lower_bound(_Link_type __x
, _Link_type __y
,
635 _M_lower_bound(_Const_Link_type __x
, _Const_Link_type __y
,
636 const _Key
& __k
) const;
639 _M_upper_bound(_Link_type __x
, _Link_type __y
,
643 _M_upper_bound(_Const_Link_type __x
, _Const_Link_type __y
,
644 const _Key
& __k
) const;
647 // allocation/deallocation
650 _Rb_tree(const _Compare
& __comp
,
651 const allocator_type
& __a
= allocator_type())
652 : _M_impl(__comp
, _Node_allocator(__a
)) { }
654 _Rb_tree(const _Rb_tree
& __x
)
655 : _M_impl(__x
._M_impl
._M_key_compare
, __x
._M_get_Node_allocator())
657 if (__x
._M_root() != 0)
659 _M_root() = _M_copy(__x
._M_begin(), _M_end());
660 _M_leftmost() = _S_minimum(_M_root());
661 _M_rightmost() = _S_maximum(_M_root());
662 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
666 #if __cplusplus >= 201103L
667 _Rb_tree(_Rb_tree
&& __x
);
670 ~_Rb_tree() _GLIBCXX_NOEXCEPT
671 { _M_erase(_M_begin()); }
674 operator=(const _Rb_tree
& __x
);
679 { return _M_impl
._M_key_compare
; }
682 begin() _GLIBCXX_NOEXCEPT
684 return iterator(static_cast<_Link_type
>
685 (this->_M_impl
._M_header
._M_left
));
689 begin() const _GLIBCXX_NOEXCEPT
691 return const_iterator(static_cast<_Const_Link_type
>
692 (this->_M_impl
._M_header
._M_left
));
696 end() _GLIBCXX_NOEXCEPT
697 { return iterator(static_cast<_Link_type
>(&this->_M_impl
._M_header
)); }
700 end() const _GLIBCXX_NOEXCEPT
702 return const_iterator(static_cast<_Const_Link_type
>
703 (&this->_M_impl
._M_header
));
707 rbegin() _GLIBCXX_NOEXCEPT
708 { return reverse_iterator(end()); }
710 const_reverse_iterator
711 rbegin() const _GLIBCXX_NOEXCEPT
712 { return const_reverse_iterator(end()); }
715 rend() _GLIBCXX_NOEXCEPT
716 { return reverse_iterator(begin()); }
718 const_reverse_iterator
719 rend() const _GLIBCXX_NOEXCEPT
720 { return const_reverse_iterator(begin()); }
723 empty() const _GLIBCXX_NOEXCEPT
724 { return _M_impl
._M_node_count
== 0; }
727 size() const _GLIBCXX_NOEXCEPT
728 { return _M_impl
._M_node_count
; }
731 max_size() const _GLIBCXX_NOEXCEPT
732 { return _M_get_Node_allocator().max_size(); }
738 #if __cplusplus >= 201103L
739 template<typename _Arg
>
741 _M_insert_unique(_Arg
&& __x
);
743 template<typename _Arg
>
745 _M_insert_equal(_Arg
&& __x
);
747 template<typename _Arg
>
749 _M_insert_unique_(const_iterator __position
, _Arg
&& __x
);
751 template<typename _Arg
>
753 _M_insert_equal_(const_iterator __position
, _Arg
&& __x
);
755 template<typename
... _Args
>
757 _M_emplace_unique(_Args
&&... __args
);
759 template<typename
... _Args
>
761 _M_emplace_equal(_Args
&&... __args
);
763 template<typename
... _Args
>
765 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
);
767 template<typename
... _Args
>
769 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
);
772 _M_insert_unique(const value_type
& __x
);
775 _M_insert_equal(const value_type
& __x
);
778 _M_insert_unique_(const_iterator __position
, const value_type
& __x
);
781 _M_insert_equal_(const_iterator __position
, const value_type
& __x
);
784 template<typename _InputIterator
>
786 _M_insert_unique(_InputIterator __first
, _InputIterator __last
);
788 template<typename _InputIterator
>
790 _M_insert_equal(_InputIterator __first
, _InputIterator __last
);
794 _M_erase_aux(const_iterator __position
);
797 _M_erase_aux(const_iterator __first
, const_iterator __last
);
800 #if __cplusplus >= 201103L
801 // _GLIBCXX_RESOLVE_LIB_DEFECTS
802 // DR 130. Associative erase should return an iterator.
803 _GLIBCXX_ABI_TAG_CXX11
805 erase(const_iterator __position
)
807 const_iterator __result
= __position
;
809 _M_erase_aux(__position
);
810 return __result
._M_const_cast();
814 _GLIBCXX_ABI_TAG_CXX11
816 erase(iterator __position
)
818 iterator __result
= __position
;
820 _M_erase_aux(__position
);
825 erase(iterator __position
)
826 { _M_erase_aux(__position
); }
829 erase(const_iterator __position
)
830 { _M_erase_aux(__position
); }
833 erase(const key_type
& __x
);
835 #if __cplusplus >= 201103L
836 // _GLIBCXX_RESOLVE_LIB_DEFECTS
837 // DR 130. Associative erase should return an iterator.
838 _GLIBCXX_ABI_TAG_CXX11
840 erase(const_iterator __first
, const_iterator __last
)
842 _M_erase_aux(__first
, __last
);
843 return __last
._M_const_cast();
847 erase(iterator __first
, iterator __last
)
848 { _M_erase_aux(__first
, __last
); }
851 erase(const_iterator __first
, const_iterator __last
)
852 { _M_erase_aux(__first
, __last
); }
855 erase(const key_type
* __first
, const key_type
* __last
);
858 clear() _GLIBCXX_NOEXCEPT
860 _M_erase(_M_begin());
861 _M_leftmost() = _M_end();
863 _M_rightmost() = _M_end();
864 _M_impl
._M_node_count
= 0;
869 find(const key_type
& __k
);
872 find(const key_type
& __k
) const;
875 count(const key_type
& __k
) const;
878 lower_bound(const key_type
& __k
)
879 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
882 lower_bound(const key_type
& __k
) const
883 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
886 upper_bound(const key_type
& __k
)
887 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
890 upper_bound(const key_type
& __k
) const
891 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
893 pair
<iterator
, iterator
>
894 equal_range(const key_type
& __k
);
896 pair
<const_iterator
, const_iterator
>
897 equal_range(const key_type
& __k
) const;
904 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
905 typename _Compare
, typename _Alloc
>
907 operator==(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
908 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
910 return __x
.size() == __y
.size()
911 && std::equal(__x
.begin(), __x
.end(), __y
.begin());
914 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
915 typename _Compare
, typename _Alloc
>
917 operator<(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
918 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
920 return std::lexicographical_compare(__x
.begin(), __x
.end(),
921 __y
.begin(), __y
.end());
924 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
925 typename _Compare
, typename _Alloc
>
927 operator!=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
928 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
929 { return !(__x
== __y
); }
931 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
932 typename _Compare
, typename _Alloc
>
934 operator>(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
935 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
936 { return __y
< __x
; }
938 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
939 typename _Compare
, typename _Alloc
>
941 operator<=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
942 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
943 { return !(__y
< __x
); }
945 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
946 typename _Compare
, typename _Alloc
>
948 operator>=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
949 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
950 { return !(__x
< __y
); }
952 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
953 typename _Compare
, typename _Alloc
>
955 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
956 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
959 #if __cplusplus >= 201103L
960 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
961 typename _Compare
, typename _Alloc
>
962 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
963 _Rb_tree(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&& __x
)
964 : _M_impl(__x
._M_impl
._M_key_compare
,
965 std::move(__x
._M_get_Node_allocator()))
967 if (__x
._M_root() != 0)
969 _M_root() = __x
._M_root();
970 _M_leftmost() = __x
._M_leftmost();
971 _M_rightmost() = __x
._M_rightmost();
972 _M_root()->_M_parent
= _M_end();
975 __x
._M_leftmost() = __x
._M_end();
976 __x
._M_rightmost() = __x
._M_end();
978 this->_M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
979 __x
._M_impl
._M_node_count
= 0;
984 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
985 typename _Compare
, typename _Alloc
>
986 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
987 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
988 operator=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
)
992 // Note that _Key may be a constant type.
994 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
995 if (__x
._M_root() != 0)
997 _M_root() = _M_copy(__x
._M_begin(), _M_end());
998 _M_leftmost() = _S_minimum(_M_root());
999 _M_rightmost() = _S_maximum(_M_root());
1000 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1006 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1007 typename _Compare
, typename _Alloc
>
1008 #if __cplusplus >= 201103L
1009 template<typename _Arg
>
1011 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1012 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1013 #if __cplusplus >= 201103L
1014 _M_insert_(_Base_ptr __x
, _Base_ptr __p
, _Arg
&& __v
)
1016 _M_insert_(_Base_ptr __x
, _Base_ptr __p
, const _Val
& __v
)
1019 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
1020 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
1023 _Link_type __z
= _M_create_node(_GLIBCXX_FORWARD(_Arg
, __v
));
1025 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1026 this->_M_impl
._M_header
);
1027 ++_M_impl
._M_node_count
;
1028 return iterator(__z
);
1031 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1032 typename _Compare
, typename _Alloc
>
1033 #if __cplusplus >= 201103L
1034 template<typename _Arg
>
1036 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1037 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1038 #if __cplusplus >= 201103L
1039 _M_insert_lower(_Base_ptr __p
, _Arg
&& __v
)
1041 _M_insert_lower(_Base_ptr __p
, const _Val
& __v
)
1044 bool __insert_left
= (__p
== _M_end()
1045 || !_M_impl
._M_key_compare(_S_key(__p
),
1046 _KeyOfValue()(__v
)));
1048 _Link_type __z
= _M_create_node(_GLIBCXX_FORWARD(_Arg
, __v
));
1050 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1051 this->_M_impl
._M_header
);
1052 ++_M_impl
._M_node_count
;
1053 return iterator(__z
);
1056 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1057 typename _Compare
, typename _Alloc
>
1058 #if __cplusplus >= 201103L
1059 template<typename _Arg
>
1061 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1062 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1063 #if __cplusplus >= 201103L
1064 _M_insert_equal_lower(_Arg
&& __v
)
1066 _M_insert_equal_lower(const _Val
& __v
)
1069 _Link_type __x
= _M_begin();
1070 _Link_type __y
= _M_end();
1074 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _KeyOfValue()(__v
)) ?
1075 _S_left(__x
) : _S_right(__x
);
1077 return _M_insert_lower(__y
, _GLIBCXX_FORWARD(_Arg
, __v
));
1080 template<typename _Key
, typename _Val
, typename _KoV
,
1081 typename _Compare
, typename _Alloc
>
1082 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1083 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
1084 _M_copy(_Const_Link_type __x
, _Link_type __p
)
1086 // Structural copy. __x and __p must be non-null.
1087 _Link_type __top
= _M_clone_node(__x
);
1088 __top
->_M_parent
= __p
;
1093 __top
->_M_right
= _M_copy(_S_right(__x
), __top
);
1099 _Link_type __y
= _M_clone_node(__x
);
1101 __y
->_M_parent
= __p
;
1103 __y
->_M_right
= _M_copy(_S_right(__x
), __y
);
1111 __throw_exception_again
;
1116 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1117 typename _Compare
, typename _Alloc
>
1119 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1120 _M_erase(_Link_type __x
)
1122 // Erase without rebalancing.
1125 _M_erase(_S_right(__x
));
1126 _Link_type __y
= _S_left(__x
);
1127 _M_destroy_node(__x
);
1132 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1133 typename _Compare
, typename _Alloc
>
1134 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1135 _Compare
, _Alloc
>::iterator
1136 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1137 _M_lower_bound(_Link_type __x
, _Link_type __y
,
1141 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1142 __y
= __x
, __x
= _S_left(__x
);
1144 __x
= _S_right(__x
);
1145 return iterator(__y
);
1148 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1149 typename _Compare
, typename _Alloc
>
1150 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1151 _Compare
, _Alloc
>::const_iterator
1152 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1153 _M_lower_bound(_Const_Link_type __x
, _Const_Link_type __y
,
1154 const _Key
& __k
) const
1157 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1158 __y
= __x
, __x
= _S_left(__x
);
1160 __x
= _S_right(__x
);
1161 return const_iterator(__y
);
1164 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1165 typename _Compare
, typename _Alloc
>
1166 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1167 _Compare
, _Alloc
>::iterator
1168 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1169 _M_upper_bound(_Link_type __x
, _Link_type __y
,
1173 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1174 __y
= __x
, __x
= _S_left(__x
);
1176 __x
= _S_right(__x
);
1177 return iterator(__y
);
1180 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1181 typename _Compare
, typename _Alloc
>
1182 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1183 _Compare
, _Alloc
>::const_iterator
1184 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1185 _M_upper_bound(_Const_Link_type __x
, _Const_Link_type __y
,
1186 const _Key
& __k
) const
1189 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1190 __y
= __x
, __x
= _S_left(__x
);
1192 __x
= _S_right(__x
);
1193 return const_iterator(__y
);
1196 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1197 typename _Compare
, typename _Alloc
>
1198 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1199 _Compare
, _Alloc
>::iterator
,
1200 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1201 _Compare
, _Alloc
>::iterator
>
1202 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1203 equal_range(const _Key
& __k
)
1205 _Link_type __x
= _M_begin();
1206 _Link_type __y
= _M_end();
1209 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1210 __x
= _S_right(__x
);
1211 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1212 __y
= __x
, __x
= _S_left(__x
);
1215 _Link_type
__xu(__x
), __yu(__y
);
1216 __y
= __x
, __x
= _S_left(__x
);
1217 __xu
= _S_right(__xu
);
1218 return pair
<iterator
,
1219 iterator
>(_M_lower_bound(__x
, __y
, __k
),
1220 _M_upper_bound(__xu
, __yu
, __k
));
1223 return pair
<iterator
, iterator
>(iterator(__y
),
1227 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1228 typename _Compare
, typename _Alloc
>
1229 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1230 _Compare
, _Alloc
>::const_iterator
,
1231 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1232 _Compare
, _Alloc
>::const_iterator
>
1233 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1234 equal_range(const _Key
& __k
) const
1236 _Const_Link_type __x
= _M_begin();
1237 _Const_Link_type __y
= _M_end();
1240 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1241 __x
= _S_right(__x
);
1242 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1243 __y
= __x
, __x
= _S_left(__x
);
1246 _Const_Link_type
__xu(__x
), __yu(__y
);
1247 __y
= __x
, __x
= _S_left(__x
);
1248 __xu
= _S_right(__xu
);
1249 return pair
<const_iterator
,
1250 const_iterator
>(_M_lower_bound(__x
, __y
, __k
),
1251 _M_upper_bound(__xu
, __yu
, __k
));
1254 return pair
<const_iterator
, const_iterator
>(const_iterator(__y
),
1255 const_iterator(__y
));
1258 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1259 typename _Compare
, typename _Alloc
>
1261 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1262 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __t
)
1266 if (__t
._M_root() != 0)
1268 _M_root() = __t
._M_root();
1269 _M_leftmost() = __t
._M_leftmost();
1270 _M_rightmost() = __t
._M_rightmost();
1271 _M_root()->_M_parent
= _M_end();
1274 __t
._M_leftmost() = __t
._M_end();
1275 __t
._M_rightmost() = __t
._M_end();
1278 else if (__t
._M_root() == 0)
1280 __t
._M_root() = _M_root();
1281 __t
._M_leftmost() = _M_leftmost();
1282 __t
._M_rightmost() = _M_rightmost();
1283 __t
._M_root()->_M_parent
= __t
._M_end();
1286 _M_leftmost() = _M_end();
1287 _M_rightmost() = _M_end();
1291 std::swap(_M_root(),__t
._M_root());
1292 std::swap(_M_leftmost(),__t
._M_leftmost());
1293 std::swap(_M_rightmost(),__t
._M_rightmost());
1295 _M_root()->_M_parent
= _M_end();
1296 __t
._M_root()->_M_parent
= __t
._M_end();
1298 // No need to swap header's color as it does not change.
1299 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
1300 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
1302 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1303 // 431. Swapping containers with unequal allocators.
1304 std::__alloc_swap
<_Node_allocator
>::
1305 _S_do_it(_M_get_Node_allocator(), __t
._M_get_Node_allocator());
1308 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1309 typename _Compare
, typename _Alloc
>
1310 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1311 _Compare
, _Alloc
>::_Base_ptr
,
1312 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1313 _Compare
, _Alloc
>::_Base_ptr
>
1314 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1315 _M_get_insert_unique_pos(const key_type
& __k
)
1317 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
1318 _Link_type __x
= _M_begin();
1319 _Link_type __y
= _M_end();
1324 __comp
= _M_impl
._M_key_compare(__k
, _S_key(__x
));
1325 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
1327 iterator __j
= iterator(__y
);
1331 return _Res(__x
, __y
);
1335 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), __k
))
1336 return _Res(__x
, __y
);
1337 return _Res(__j
._M_node
, 0);
1340 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1341 typename _Compare
, typename _Alloc
>
1342 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1343 _Compare
, _Alloc
>::_Base_ptr
,
1344 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1345 _Compare
, _Alloc
>::_Base_ptr
>
1346 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1347 _M_get_insert_equal_pos(const key_type
& __k
)
1349 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
1350 _Link_type __x
= _M_begin();
1351 _Link_type __y
= _M_end();
1355 __x
= _M_impl
._M_key_compare(__k
, _S_key(__x
)) ?
1356 _S_left(__x
) : _S_right(__x
);
1358 return _Res(__x
, __y
);
1361 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1362 typename _Compare
, typename _Alloc
>
1363 #if __cplusplus >= 201103L
1364 template<typename _Arg
>
1366 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1367 _Compare
, _Alloc
>::iterator
, bool>
1368 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1369 #if __cplusplus >= 201103L
1370 _M_insert_unique(_Arg
&& __v
)
1372 _M_insert_unique(const _Val
& __v
)
1375 typedef pair
<iterator
, bool> _Res
;
1376 pair
<_Base_ptr
, _Base_ptr
> __res
1377 = _M_get_insert_unique_pos(_KeyOfValue()(__v
));
1380 return _Res(_M_insert_(__res
.first
, __res
.second
,
1381 _GLIBCXX_FORWARD(_Arg
, __v
)),
1384 return _Res(iterator(static_cast<_Link_type
>(__res
.first
)), false);
1387 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1388 typename _Compare
, typename _Alloc
>
1389 #if __cplusplus >= 201103L
1390 template<typename _Arg
>
1392 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1393 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1394 #if __cplusplus >= 201103L
1395 _M_insert_equal(_Arg
&& __v
)
1397 _M_insert_equal(const _Val
& __v
)
1400 pair
<_Base_ptr
, _Base_ptr
> __res
1401 = _M_get_insert_equal_pos(_KeyOfValue()(__v
));
1402 return _M_insert_(__res
.first
, __res
.second
, _GLIBCXX_FORWARD(_Arg
, __v
));
1405 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1406 typename _Compare
, typename _Alloc
>
1407 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1408 _Compare
, _Alloc
>::_Base_ptr
,
1409 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1410 _Compare
, _Alloc
>::_Base_ptr
>
1411 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1412 _M_get_insert_hint_unique_pos(const_iterator __position
,
1413 const key_type
& __k
)
1415 iterator __pos
= __position
._M_const_cast();
1416 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
1419 if (__pos
._M_node
== _M_end())
1422 && _M_impl
._M_key_compare(_S_key(_M_rightmost()), __k
))
1423 return _Res(0, _M_rightmost());
1425 return _M_get_insert_unique_pos(__k
);
1427 else if (_M_impl
._M_key_compare(__k
, _S_key(__pos
._M_node
)))
1429 // First, try before...
1430 iterator __before
= __pos
;
1431 if (__pos
._M_node
== _M_leftmost()) // begin()
1432 return _Res(_M_leftmost(), _M_leftmost());
1433 else if (_M_impl
._M_key_compare(_S_key((--__before
)._M_node
), __k
))
1435 if (_S_right(__before
._M_node
) == 0)
1436 return _Res(0, __before
._M_node
);
1438 return _Res(__pos
._M_node
, __pos
._M_node
);
1441 return _M_get_insert_unique_pos(__k
);
1443 else if (_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
1445 // ... then try after.
1446 iterator __after
= __pos
;
1447 if (__pos
._M_node
== _M_rightmost())
1448 return _Res(0, _M_rightmost());
1449 else if (_M_impl
._M_key_compare(__k
, _S_key((++__after
)._M_node
)))
1451 if (_S_right(__pos
._M_node
) == 0)
1452 return _Res(0, __pos
._M_node
);
1454 return _Res(__after
._M_node
, __after
._M_node
);
1457 return _M_get_insert_unique_pos(__k
);
1461 return _Res(__pos
._M_node
, 0);
1464 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1465 typename _Compare
, typename _Alloc
>
1466 #if __cplusplus >= 201103L
1467 template<typename _Arg
>
1469 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1470 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1471 #if __cplusplus >= 201103L
1472 _M_insert_unique_(const_iterator __position
, _Arg
&& __v
)
1474 _M_insert_unique_(const_iterator __position
, const _Val
& __v
)
1477 pair
<_Base_ptr
, _Base_ptr
> __res
1478 = _M_get_insert_hint_unique_pos(__position
, _KeyOfValue()(__v
));
1481 return _M_insert_(__res
.first
, __res
.second
,
1482 _GLIBCXX_FORWARD(_Arg
, __v
));
1483 return iterator(static_cast<_Link_type
>(__res
.first
));
1486 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1487 typename _Compare
, typename _Alloc
>
1488 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1489 _Compare
, _Alloc
>::_Base_ptr
,
1490 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1491 _Compare
, _Alloc
>::_Base_ptr
>
1492 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1493 _M_get_insert_hint_equal_pos(const_iterator __position
, const key_type
& __k
)
1495 iterator __pos
= __position
._M_const_cast();
1496 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
1499 if (__pos
._M_node
== _M_end())
1502 && !_M_impl
._M_key_compare(__k
, _S_key(_M_rightmost())))
1503 return _Res(0, _M_rightmost());
1505 return _M_get_insert_equal_pos(__k
);
1507 else if (!_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
1509 // First, try before...
1510 iterator __before
= __pos
;
1511 if (__pos
._M_node
== _M_leftmost()) // begin()
1512 return _Res(_M_leftmost(), _M_leftmost());
1513 else if (!_M_impl
._M_key_compare(__k
, _S_key((--__before
)._M_node
)))
1515 if (_S_right(__before
._M_node
) == 0)
1516 return _Res(0, __before
._M_node
);
1518 return _Res(__pos
._M_node
, __pos
._M_node
);
1521 return _M_get_insert_equal_pos(__k
);
1525 // ... then try after.
1526 iterator __after
= __pos
;
1527 if (__pos
._M_node
== _M_rightmost())
1528 return _Res(0, _M_rightmost());
1529 else if (!_M_impl
._M_key_compare(_S_key((++__after
)._M_node
), __k
))
1531 if (_S_right(__pos
._M_node
) == 0)
1532 return _Res(0, __pos
._M_node
);
1534 return _Res(__after
._M_node
, __after
._M_node
);
1541 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1542 typename _Compare
, typename _Alloc
>
1543 #if __cplusplus >= 201103L
1544 template<typename _Arg
>
1546 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1547 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1548 #if __cplusplus >= 201103L
1549 _M_insert_equal_(const_iterator __position
, _Arg
&& __v
)
1551 _M_insert_equal_(const_iterator __position
, const _Val
& __v
)
1554 pair
<_Base_ptr
, _Base_ptr
> __res
1555 = _M_get_insert_hint_equal_pos(__position
, _KeyOfValue()(__v
));
1558 return _M_insert_(__res
.first
, __res
.second
,
1559 _GLIBCXX_FORWARD(_Arg
, __v
));
1561 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg
, __v
));
1564 #if __cplusplus >= 201103L
1565 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1566 typename _Compare
, typename _Alloc
>
1567 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1568 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1569 _M_insert_node(_Base_ptr __x
, _Base_ptr __p
, _Link_type __z
)
1571 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
1572 || _M_impl
._M_key_compare(_S_key(__z
),
1575 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1576 this->_M_impl
._M_header
);
1577 ++_M_impl
._M_node_count
;
1578 return iterator(__z
);
1581 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1582 typename _Compare
, typename _Alloc
>
1583 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1584 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1585 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
)
1587 bool __insert_left
= (__p
== _M_end()
1588 || !_M_impl
._M_key_compare(_S_key(__p
),
1591 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1592 this->_M_impl
._M_header
);
1593 ++_M_impl
._M_node_count
;
1594 return iterator(__z
);
1597 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1598 typename _Compare
, typename _Alloc
>
1599 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1600 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1601 _M_insert_equal_lower_node(_Link_type __z
)
1603 _Link_type __x
= _M_begin();
1604 _Link_type __y
= _M_end();
1608 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _S_key(__z
)) ?
1609 _S_left(__x
) : _S_right(__x
);
1611 return _M_insert_lower_node(__y
, __z
);
1614 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1615 typename _Compare
, typename _Alloc
>
1616 template<typename
... _Args
>
1617 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1618 _Compare
, _Alloc
>::iterator
, bool>
1619 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1620 _M_emplace_unique(_Args
&&... __args
)
1622 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
1626 typedef pair
<iterator
, bool> _Res
;
1627 auto __res
= _M_get_insert_unique_pos(_S_key(__z
));
1629 return _Res(_M_insert_node(__res
.first
, __res
.second
, __z
), true);
1631 _M_destroy_node(__z
);
1632 return _Res(iterator(static_cast<_Link_type
>(__res
.first
)), false);
1636 _M_destroy_node(__z
);
1637 __throw_exception_again
;
1641 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1642 typename _Compare
, typename _Alloc
>
1643 template<typename
... _Args
>
1644 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1645 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1646 _M_emplace_equal(_Args
&&... __args
)
1648 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
1652 auto __res
= _M_get_insert_equal_pos(_S_key(__z
));
1653 return _M_insert_node(__res
.first
, __res
.second
, __z
);
1657 _M_destroy_node(__z
);
1658 __throw_exception_again
;
1662 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1663 typename _Compare
, typename _Alloc
>
1664 template<typename
... _Args
>
1665 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1666 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1667 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
)
1669 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
1673 auto __res
= _M_get_insert_hint_unique_pos(__pos
, _S_key(__z
));
1676 return _M_insert_node(__res
.first
, __res
.second
, __z
);
1678 _M_destroy_node(__z
);
1679 return iterator(static_cast<_Link_type
>(__res
.first
));
1683 _M_destroy_node(__z
);
1684 __throw_exception_again
;
1688 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1689 typename _Compare
, typename _Alloc
>
1690 template<typename
... _Args
>
1691 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1692 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1693 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
)
1695 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
1699 auto __res
= _M_get_insert_hint_equal_pos(__pos
, _S_key(__z
));
1702 return _M_insert_node(__res
.first
, __res
.second
, __z
);
1704 return _M_insert_equal_lower_node(__z
);
1708 _M_destroy_node(__z
);
1709 __throw_exception_again
;
1714 template<typename _Key
, typename _Val
, typename _KoV
,
1715 typename _Cmp
, typename _Alloc
>
1718 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
1719 _M_insert_unique(_II __first
, _II __last
)
1721 for (; __first
!= __last
; ++__first
)
1722 _M_insert_unique_(end(), *__first
);
1725 template<typename _Key
, typename _Val
, typename _KoV
,
1726 typename _Cmp
, typename _Alloc
>
1729 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
1730 _M_insert_equal(_II __first
, _II __last
)
1732 for (; __first
!= __last
; ++__first
)
1733 _M_insert_equal_(end(), *__first
);
1736 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1737 typename _Compare
, typename _Alloc
>
1739 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1740 _M_erase_aux(const_iterator __position
)
1743 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
1744 (const_cast<_Base_ptr
>(__position
._M_node
),
1745 this->_M_impl
._M_header
));
1746 _M_destroy_node(__y
);
1747 --_M_impl
._M_node_count
;
1750 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1751 typename _Compare
, typename _Alloc
>
1753 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1754 _M_erase_aux(const_iterator __first
, const_iterator __last
)
1756 if (__first
== begin() && __last
== end())
1759 while (__first
!= __last
)
1763 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1764 typename _Compare
, typename _Alloc
>
1765 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
1766 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1767 erase(const _Key
& __x
)
1769 pair
<iterator
, iterator
> __p
= equal_range(__x
);
1770 const size_type __old_size
= size();
1771 erase(__p
.first
, __p
.second
);
1772 return __old_size
- size();
1775 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1776 typename _Compare
, typename _Alloc
>
1778 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1779 erase(const _Key
* __first
, const _Key
* __last
)
1781 while (__first
!= __last
)
1785 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1786 typename _Compare
, typename _Alloc
>
1787 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1788 _Compare
, _Alloc
>::iterator
1789 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1790 find(const _Key
& __k
)
1792 iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
1793 return (__j
== end()
1794 || _M_impl
._M_key_compare(__k
,
1795 _S_key(__j
._M_node
))) ? end() : __j
;
1798 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1799 typename _Compare
, typename _Alloc
>
1800 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1801 _Compare
, _Alloc
>::const_iterator
1802 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1803 find(const _Key
& __k
) const
1805 const_iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
1806 return (__j
== end()
1807 || _M_impl
._M_key_compare(__k
,
1808 _S_key(__j
._M_node
))) ? end() : __j
;
1811 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1812 typename _Compare
, typename _Alloc
>
1813 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
1814 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1815 count(const _Key
& __k
) const
1817 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
1818 const size_type __n
= std::distance(__p
.first
, __p
.second
);
1822 _GLIBCXX_PURE
unsigned int
1823 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
1824 const _Rb_tree_node_base
* __root
) throw ();
1826 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1827 typename _Compare
, typename _Alloc
>
1829 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
1831 if (_M_impl
._M_node_count
== 0 || begin() == end())
1832 return _M_impl
._M_node_count
== 0 && begin() == end()
1833 && this->_M_impl
._M_header
._M_left
== _M_end()
1834 && this->_M_impl
._M_header
._M_right
== _M_end();
1836 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
1837 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
1839 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
1840 _Const_Link_type __L
= _S_left(__x
);
1841 _Const_Link_type __R
= _S_right(__x
);
1843 if (__x
->_M_color
== _S_red
)
1844 if ((__L
&& __L
->_M_color
== _S_red
)
1845 || (__R
&& __R
->_M_color
== _S_red
))
1848 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
1850 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
1853 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
1857 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1859 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1864 _GLIBCXX_END_NAMESPACE_VERSION