1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001-2024 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 #pragma GCC system_header
63 #include <bits/stl_algobase.h>
64 #include <bits/allocator.h>
65 #include <bits/stl_function.h>
66 #include <bits/cpp_type_traits.h>
67 #include <ext/alloc_traits.h>
68 #if __cplusplus >= 201103L
69 # include <ext/aligned_buffer.h>
71 #if __cplusplus > 201402L
72 # include <bits/node_handle.h>
75 namespace std
_GLIBCXX_VISIBILITY(default)
77 _GLIBCXX_BEGIN_NAMESPACE_VERSION
79 // Red-black tree class, designed for use in implementing STL
80 // associative containers (set, multiset, map, and multimap). The
81 // insertion and deletion algorithms are based on those in Cormen,
82 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
85 // (1) the header cell is maintained with links not only to the root
86 // but also to the leftmost node of the tree, to enable constant
87 // time begin(), and to the rightmost node of the tree, to enable
88 // linear time performance when used with the generic set algorithms
91 // (2) when a node being deleted has two children its successor node
92 // is relinked into its place, rather than copied, so that the only
93 // iterators invalidated are those referring to the deleted node.
95 enum _Rb_tree_color
{ _S_red
= false, _S_black
= true };
97 struct _Rb_tree_node_base
99 typedef _Rb_tree_node_base
* _Base_ptr
;
100 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
102 _Rb_tree_color _M_color
;
108 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
110 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
114 static _Const_Base_ptr
115 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
117 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
122 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
124 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
128 static _Const_Base_ptr
129 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
131 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
136 // Helper type offering value initialization guarantee on the compare functor.
137 template<typename _Key_compare
>
138 struct _Rb_tree_key_compare
140 _Key_compare _M_key_compare
;
142 _Rb_tree_key_compare()
143 _GLIBCXX_NOEXCEPT_IF(
144 is_nothrow_default_constructible
<_Key_compare
>::value
)
148 _Rb_tree_key_compare(const _Key_compare
& __comp
)
149 : _M_key_compare(__comp
)
152 #if __cplusplus >= 201103L
153 // Copy constructor added for consistency with C++98 mode.
154 _Rb_tree_key_compare(const _Rb_tree_key_compare
&) = default;
156 _Rb_tree_key_compare(_Rb_tree_key_compare
&& __x
)
157 noexcept(is_nothrow_copy_constructible
<_Key_compare
>::value
)
158 : _M_key_compare(__x
._M_key_compare
)
163 // Helper type to manage default initialization of node count and header.
164 struct _Rb_tree_header
166 _Rb_tree_node_base _M_header
;
167 size_t _M_node_count
; // Keeps track of size of tree.
169 _Rb_tree_header() _GLIBCXX_NOEXCEPT
171 _M_header
._M_color
= _S_red
;
175 #if __cplusplus >= 201103L
176 _Rb_tree_header(_Rb_tree_header
&& __x
) noexcept
178 if (__x
._M_header
._M_parent
!= nullptr)
182 _M_header
._M_color
= _S_red
;
189 _M_move_data(_Rb_tree_header
& __from
)
191 _M_header
._M_color
= __from
._M_header
._M_color
;
192 _M_header
._M_parent
= __from
._M_header
._M_parent
;
193 _M_header
._M_left
= __from
._M_header
._M_left
;
194 _M_header
._M_right
= __from
._M_header
._M_right
;
195 _M_header
._M_parent
->_M_parent
= &_M_header
;
196 _M_node_count
= __from
._M_node_count
;
204 _M_header
._M_parent
= 0;
205 _M_header
._M_left
= &_M_header
;
206 _M_header
._M_right
= &_M_header
;
211 template<typename _Val
>
212 struct _Rb_tree_node
: public _Rb_tree_node_base
214 typedef _Rb_tree_node
<_Val
>* _Link_type
;
216 #if __cplusplus < 201103L
221 { return std::__addressof(_M_value_field
); }
225 { return std::__addressof(_M_value_field
); }
227 __gnu_cxx::__aligned_membuf
<_Val
> _M_storage
;
231 { return _M_storage
._M_ptr(); }
235 { return _M_storage
._M_ptr(); }
239 _GLIBCXX_PURE _Rb_tree_node_base
*
240 _Rb_tree_increment(_Rb_tree_node_base
* __x
) throw ();
242 _GLIBCXX_PURE
const _Rb_tree_node_base
*
243 _Rb_tree_increment(const _Rb_tree_node_base
* __x
) throw ();
245 _GLIBCXX_PURE _Rb_tree_node_base
*
246 _Rb_tree_decrement(_Rb_tree_node_base
* __x
) throw ();
248 _GLIBCXX_PURE
const _Rb_tree_node_base
*
249 _Rb_tree_decrement(const _Rb_tree_node_base
* __x
) throw ();
251 template<typename _Tp
>
252 struct _Rb_tree_iterator
254 typedef _Tp value_type
;
255 typedef _Tp
& reference
;
256 typedef _Tp
* pointer
;
258 typedef bidirectional_iterator_tag iterator_category
;
259 typedef ptrdiff_t difference_type
;
261 typedef _Rb_tree_iterator
<_Tp
> _Self
;
262 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
263 typedef _Rb_tree_node
<_Tp
>* _Link_type
;
265 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
269 _Rb_tree_iterator(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
273 operator*() const _GLIBCXX_NOEXCEPT
274 { return *static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
277 operator->() const _GLIBCXX_NOEXCEPT
278 { return static_cast<_Link_type
> (_M_node
)->_M_valptr(); }
281 operator++() _GLIBCXX_NOEXCEPT
283 _M_node
= _Rb_tree_increment(_M_node
);
288 operator++(int) _GLIBCXX_NOEXCEPT
291 _M_node
= _Rb_tree_increment(_M_node
);
296 operator--() _GLIBCXX_NOEXCEPT
298 _M_node
= _Rb_tree_decrement(_M_node
);
303 operator--(int) _GLIBCXX_NOEXCEPT
306 _M_node
= _Rb_tree_decrement(_M_node
);
311 operator==(const _Self
& __x
, const _Self
& __y
) _GLIBCXX_NOEXCEPT
312 { return __x
._M_node
== __y
._M_node
; }
314 #if ! __cpp_lib_three_way_comparison
316 operator!=(const _Self
& __x
, const _Self
& __y
) _GLIBCXX_NOEXCEPT
317 { return __x
._M_node
!= __y
._M_node
; }
323 template<typename _Tp
>
324 struct _Rb_tree_const_iterator
326 typedef _Tp value_type
;
327 typedef const _Tp
& reference
;
328 typedef const _Tp
* pointer
;
330 typedef _Rb_tree_iterator
<_Tp
> iterator
;
332 typedef bidirectional_iterator_tag iterator_category
;
333 typedef ptrdiff_t difference_type
;
335 typedef _Rb_tree_const_iterator
<_Tp
> _Self
;
336 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr
;
337 typedef const _Rb_tree_node
<_Tp
>* _Link_type
;
339 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
343 _Rb_tree_const_iterator(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
346 _Rb_tree_const_iterator(const iterator
& __it
) _GLIBCXX_NOEXCEPT
347 : _M_node(__it
._M_node
) { }
350 _M_const_cast() const _GLIBCXX_NOEXCEPT
351 { return iterator(const_cast<typename
iterator::_Base_ptr
>(_M_node
)); }
354 operator*() const _GLIBCXX_NOEXCEPT
355 { return *static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
358 operator->() const _GLIBCXX_NOEXCEPT
359 { return static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
362 operator++() _GLIBCXX_NOEXCEPT
364 _M_node
= _Rb_tree_increment(_M_node
);
369 operator++(int) _GLIBCXX_NOEXCEPT
372 _M_node
= _Rb_tree_increment(_M_node
);
377 operator--() _GLIBCXX_NOEXCEPT
379 _M_node
= _Rb_tree_decrement(_M_node
);
384 operator--(int) _GLIBCXX_NOEXCEPT
387 _M_node
= _Rb_tree_decrement(_M_node
);
392 operator==(const _Self
& __x
, const _Self
& __y
) _GLIBCXX_NOEXCEPT
393 { return __x
._M_node
== __y
._M_node
; }
395 #if ! __cpp_lib_three_way_comparison
397 operator!=(const _Self
& __x
, const _Self
& __y
) _GLIBCXX_NOEXCEPT
398 { return __x
._M_node
!= __y
._M_node
; }
404 __attribute__((__nonnull__
))
406 _Rb_tree_insert_and_rebalance(const bool __insert_left
,
407 _Rb_tree_node_base
* __x
,
408 _Rb_tree_node_base
* __p
,
409 _Rb_tree_node_base
& __header
) throw ();
411 __attribute__((__nonnull__
,__returns_nonnull__
))
413 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
414 _Rb_tree_node_base
& __header
) throw ();
416 #if __cplusplus > 201402L
417 template<typename _Tree1
, typename _Cmp2
>
418 struct _Rb_tree_merge_helper
{ };
421 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
422 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
425 typedef typename
__gnu_cxx::__alloc_traits
<_Alloc
>::template
426 rebind
<_Rb_tree_node
<_Val
> >::other _Node_allocator
;
428 typedef __gnu_cxx::__alloc_traits
<_Node_allocator
> _Alloc_traits
;
431 typedef _Rb_tree_node_base
* _Base_ptr
;
432 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
433 typedef _Rb_tree_node
<_Val
>* _Link_type
;
434 typedef const _Rb_tree_node
<_Val
>* _Const_Link_type
;
437 // Functor recycling a pool of nodes and using allocation once the pool
439 struct _Reuse_or_alloc_node
441 _Reuse_or_alloc_node(_Rb_tree
& __t
)
442 : _M_root(__t
._M_root()), _M_nodes(__t
._M_rightmost()), _M_t(__t
)
446 _M_root
->_M_parent
= 0;
448 if (_M_nodes
->_M_left
)
449 _M_nodes
= _M_nodes
->_M_left
;
455 #if __cplusplus >= 201103L
456 _Reuse_or_alloc_node(const _Reuse_or_alloc_node
&) = delete;
459 ~_Reuse_or_alloc_node()
460 { _M_t
._M_erase(static_cast<_Link_type
>(_M_root
)); }
462 template<typename _Arg
>
464 operator()(_GLIBCXX_FWDREF(_Arg
) __arg
)
466 _Link_type __node
= static_cast<_Link_type
>(_M_extract());
469 _M_t
._M_destroy_node(__node
);
470 _M_t
._M_construct_node(__node
, _GLIBCXX_FORWARD(_Arg
, __arg
));
474 return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
));
484 _Base_ptr __node
= _M_nodes
;
485 _M_nodes
= _M_nodes
->_M_parent
;
488 if (_M_nodes
->_M_right
== __node
)
490 _M_nodes
->_M_right
= 0;
492 if (_M_nodes
->_M_left
)
494 _M_nodes
= _M_nodes
->_M_left
;
496 while (_M_nodes
->_M_right
)
497 _M_nodes
= _M_nodes
->_M_right
;
499 if (_M_nodes
->_M_left
)
500 _M_nodes
= _M_nodes
->_M_left
;
503 else // __node is on the left.
504 _M_nodes
->_M_left
= 0;
517 // Functor similar to the previous one but without any pool of nodes to
521 _Alloc_node(_Rb_tree
& __t
)
524 template<typename _Arg
>
526 operator()(_GLIBCXX_FWDREF(_Arg
) __arg
) const
527 { return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
)); }
534 typedef _Key key_type
;
535 typedef _Val value_type
;
536 typedef value_type
* pointer
;
537 typedef const value_type
* const_pointer
;
538 typedef value_type
& reference
;
539 typedef const value_type
& const_reference
;
540 typedef size_t size_type
;
541 typedef ptrdiff_t difference_type
;
542 typedef _Alloc allocator_type
;
545 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
546 { return this->_M_impl
; }
548 const _Node_allocator
&
549 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
550 { return this->_M_impl
; }
553 get_allocator() const _GLIBCXX_NOEXCEPT
554 { return allocator_type(_M_get_Node_allocator()); }
559 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
562 _M_put_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
563 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p
, 1); }
565 #if __cplusplus < 201103L
567 _M_construct_node(_Link_type __node
, const value_type
& __x
)
570 { get_allocator().construct(__node
->_M_valptr(), __x
); }
574 __throw_exception_again
;
579 _M_create_node(const value_type
& __x
)
581 _Link_type __tmp
= _M_get_node();
582 _M_construct_node(__tmp
, __x
);
586 template<typename
... _Args
>
588 _M_construct_node(_Link_type __node
, _Args
&&... __args
)
592 ::new(__node
) _Rb_tree_node
<_Val
>;
593 _Alloc_traits::construct(_M_get_Node_allocator(),
595 std::forward
<_Args
>(__args
)...);
599 __node
->~_Rb_tree_node
<_Val
>();
601 __throw_exception_again
;
605 template<typename
... _Args
>
607 _M_create_node(_Args
&&... __args
)
609 _Link_type __tmp
= _M_get_node();
610 _M_construct_node(__tmp
, std::forward
<_Args
>(__args
)...);
616 _M_destroy_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
618 #if __cplusplus < 201103L
619 get_allocator().destroy(__p
->_M_valptr());
621 _Alloc_traits::destroy(_M_get_Node_allocator(), __p
->_M_valptr());
622 __p
->~_Rb_tree_node
<_Val
>();
627 _M_drop_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
629 _M_destroy_node(__p
);
633 template<bool _MoveValue
, typename _NodeGen
>
635 _M_clone_node(_Link_type __x
, _NodeGen
& __node_gen
)
637 #if __cplusplus >= 201103L
638 using _Vp
= __conditional_t
<_MoveValue
,
643 = __node_gen(_GLIBCXX_FORWARD(_Vp
, *__x
->_M_valptr()));
644 __tmp
->_M_color
= __x
->_M_color
;
651 #if _GLIBCXX_INLINE_VERSION
652 template<typename _Key_compare
>
654 // Unused _Is_pod_comparator is kept as it is part of mangled name.
655 template<typename _Key_compare
,
656 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare
)>
659 : public _Node_allocator
660 , public _Rb_tree_key_compare
<_Key_compare
>
661 , public _Rb_tree_header
663 typedef _Rb_tree_key_compare
<_Key_compare
> _Base_key_compare
;
666 _GLIBCXX_NOEXCEPT_IF(
667 is_nothrow_default_constructible
<_Node_allocator
>::value
668 && is_nothrow_default_constructible
<_Base_key_compare
>::value
)
672 _Rb_tree_impl(const _Rb_tree_impl
& __x
)
673 : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x
))
674 , _Base_key_compare(__x
._M_key_compare
)
678 #if __cplusplus < 201103L
679 _Rb_tree_impl(const _Key_compare
& __comp
, const _Node_allocator
& __a
)
680 : _Node_allocator(__a
), _Base_key_compare(__comp
)
683 _Rb_tree_impl(_Rb_tree_impl
&&)
684 noexcept( is_nothrow_move_constructible
<_Base_key_compare
>::value
)
688 _Rb_tree_impl(_Node_allocator
&& __a
)
689 : _Node_allocator(std::move(__a
))
692 _Rb_tree_impl(_Rb_tree_impl
&& __x
, _Node_allocator
&& __a
)
693 : _Node_allocator(std::move(__a
)),
694 _Base_key_compare(std::move(__x
)),
695 _Rb_tree_header(std::move(__x
))
698 _Rb_tree_impl(const _Key_compare
& __comp
, _Node_allocator
&& __a
)
699 : _Node_allocator(std::move(__a
)), _Base_key_compare(__comp
)
704 _Rb_tree_impl
<_Compare
> _M_impl
;
708 _M_root() _GLIBCXX_NOEXCEPT
709 { return this->_M_impl
._M_header
._M_parent
; }
712 _M_root() const _GLIBCXX_NOEXCEPT
713 { return this->_M_impl
._M_header
._M_parent
; }
716 _M_leftmost() _GLIBCXX_NOEXCEPT
717 { return this->_M_impl
._M_header
._M_left
; }
720 _M_leftmost() const _GLIBCXX_NOEXCEPT
721 { return this->_M_impl
._M_header
._M_left
; }
724 _M_rightmost() _GLIBCXX_NOEXCEPT
725 { return this->_M_impl
._M_header
._M_right
; }
728 _M_rightmost() const _GLIBCXX_NOEXCEPT
729 { return this->_M_impl
._M_header
._M_right
; }
732 _M_mbegin() const _GLIBCXX_NOEXCEPT
733 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
736 _M_begin() _GLIBCXX_NOEXCEPT
737 { return _M_mbegin(); }
740 _M_begin() const _GLIBCXX_NOEXCEPT
742 return static_cast<_Const_Link_type
>
743 (this->_M_impl
._M_header
._M_parent
);
747 _M_end() _GLIBCXX_NOEXCEPT
748 { return &this->_M_impl
._M_header
; }
751 _M_end() const _GLIBCXX_NOEXCEPT
752 { return &this->_M_impl
._M_header
; }
755 _S_key(_Const_Link_type __x
)
757 #if __cplusplus >= 201103L
758 // If we're asking for the key we're presumably using the comparison
759 // object, and so this is a good place to sanity check it.
760 static_assert(__is_invocable
<_Compare
&, const _Key
&, const _Key
&>{},
761 "comparison object must be invocable "
762 "with two arguments of key type");
763 # if __cplusplus >= 201703L
764 // _GLIBCXX_RESOLVE_LIB_DEFECTS
765 // 2542. Missing const requirements for associative containers
766 if constexpr (__is_invocable
<_Compare
&, const _Key
&, const _Key
&>{})
768 is_invocable_v
<const _Compare
&, const _Key
&, const _Key
&>,
769 "comparison object must be invocable as const");
773 return _KeyOfValue()(*__x
->_M_valptr());
777 _S_left(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
778 { return static_cast<_Link_type
>(__x
->_M_left
); }
780 static _Const_Link_type
781 _S_left(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
782 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
785 _S_right(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
786 { return static_cast<_Link_type
>(__x
->_M_right
); }
788 static _Const_Link_type
789 _S_right(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
790 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
793 _S_key(_Const_Base_ptr __x
)
794 { return _S_key(static_cast<_Const_Link_type
>(__x
)); }
797 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
798 { return _Rb_tree_node_base::_S_minimum(__x
); }
800 static _Const_Base_ptr
801 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
802 { return _Rb_tree_node_base::_S_minimum(__x
); }
805 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
806 { return _Rb_tree_node_base::_S_maximum(__x
); }
808 static _Const_Base_ptr
809 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
810 { return _Rb_tree_node_base::_S_maximum(__x
); }
813 typedef _Rb_tree_iterator
<value_type
> iterator
;
814 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
816 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
817 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
819 #if __cplusplus > 201402L
820 using node_type
= _Node_handle
<_Key
, _Val
, _Node_allocator
>;
821 using insert_return_type
= _Node_insert_return
<
822 __conditional_t
<is_same_v
<_Key
, _Val
>, const_iterator
, iterator
>,
826 pair
<_Base_ptr
, _Base_ptr
>
827 _M_get_insert_unique_pos(const key_type
& __k
);
829 pair
<_Base_ptr
, _Base_ptr
>
830 _M_get_insert_equal_pos(const key_type
& __k
);
832 pair
<_Base_ptr
, _Base_ptr
>
833 _M_get_insert_hint_unique_pos(const_iterator __pos
,
834 const key_type
& __k
);
836 pair
<_Base_ptr
, _Base_ptr
>
837 _M_get_insert_hint_equal_pos(const_iterator __pos
,
838 const key_type
& __k
);
841 #if __cplusplus >= 201103L
842 template<typename _Arg
, typename _NodeGen
>
844 _M_insert_(_Base_ptr __x
, _Base_ptr __y
, _Arg
&& __v
, _NodeGen
&);
847 _M_insert_node(_Base_ptr __x
, _Base_ptr __y
, _Link_type __z
);
849 template<typename _Arg
>
851 _M_insert_lower(_Base_ptr __y
, _Arg
&& __v
);
853 template<typename _Arg
>
855 _M_insert_equal_lower(_Arg
&& __x
);
858 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
);
861 _M_insert_equal_lower_node(_Link_type __z
);
863 template<typename _NodeGen
>
865 _M_insert_(_Base_ptr __x
, _Base_ptr __y
,
866 const value_type
& __v
, _NodeGen
&);
868 // _GLIBCXX_RESOLVE_LIB_DEFECTS
869 // 233. Insertion hints in associative containers.
871 _M_insert_lower(_Base_ptr __y
, const value_type
& __v
);
874 _M_insert_equal_lower(const value_type
& __x
);
877 enum { __as_lvalue
, __as_rvalue
};
879 template<bool _MoveValues
, typename _NodeGen
>
881 _M_copy(_Link_type
, _Base_ptr
, _NodeGen
&);
883 template<bool _MoveValues
, typename _NodeGen
>
885 _M_copy(const _Rb_tree
& __x
, _NodeGen
& __gen
)
888 _M_copy
<_MoveValues
>(__x
._M_mbegin(), _M_end(), __gen
);
889 _M_leftmost() = _S_minimum(__root
);
890 _M_rightmost() = _S_maximum(__root
);
891 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
896 _M_copy(const _Rb_tree
& __x
)
898 _Alloc_node
__an(*this);
899 return _M_copy
<__as_lvalue
>(__x
, __an
);
903 _M_erase(_Link_type __x
);
906 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
910 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
911 const _Key
& __k
) const;
914 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
918 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
919 const _Key
& __k
) const;
922 // allocation/deallocation
923 #if __cplusplus < 201103L
926 _Rb_tree() = default;
929 _Rb_tree(const _Compare
& __comp
,
930 const allocator_type
& __a
= allocator_type())
931 : _M_impl(__comp
, _Node_allocator(__a
)) { }
933 _Rb_tree(const _Rb_tree
& __x
)
934 : _M_impl(__x
._M_impl
)
936 if (__x
._M_root() != 0)
937 _M_root() = _M_copy(__x
);
940 #if __cplusplus >= 201103L
941 _Rb_tree(const allocator_type
& __a
)
942 : _M_impl(_Node_allocator(__a
))
945 _Rb_tree(const _Rb_tree
& __x
, const allocator_type
& __a
)
946 : _M_impl(__x
._M_impl
._M_key_compare
, _Node_allocator(__a
))
948 if (__x
._M_root() != nullptr)
949 _M_root() = _M_copy(__x
);
952 _Rb_tree(_Rb_tree
&&) = default;
954 _Rb_tree(_Rb_tree
&& __x
, const allocator_type
& __a
)
955 : _Rb_tree(std::move(__x
), _Node_allocator(__a
))
959 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
, true_type
)
960 noexcept(is_nothrow_default_constructible
<_Compare
>::value
)
961 : _M_impl(std::move(__x
._M_impl
), std::move(__a
))
964 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
, false_type
)
965 : _M_impl(__x
._M_impl
._M_key_compare
, std::move(__a
))
967 if (__x
._M_root() != nullptr)
968 _M_move_data(__x
, false_type
{});
972 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
)
974 _Rb_tree(std::declval
<_Rb_tree
&&>(), std::declval
<_Node_allocator
&&>(),
975 std::declval
<typename
_Alloc_traits::is_always_equal
>())) )
976 : _Rb_tree(std::move(__x
), std::move(__a
),
977 typename
_Alloc_traits::is_always_equal
{})
981 ~_Rb_tree() _GLIBCXX_NOEXCEPT
982 { _M_erase(_M_begin()); }
985 operator=(const _Rb_tree
& __x
);
990 { return _M_impl
._M_key_compare
; }
993 begin() _GLIBCXX_NOEXCEPT
994 { return iterator(this->_M_impl
._M_header
._M_left
); }
997 begin() const _GLIBCXX_NOEXCEPT
998 { return const_iterator(this->_M_impl
._M_header
._M_left
); }
1001 end() _GLIBCXX_NOEXCEPT
1002 { return iterator(&this->_M_impl
._M_header
); }
1005 end() const _GLIBCXX_NOEXCEPT
1006 { return const_iterator(&this->_M_impl
._M_header
); }
1009 rbegin() _GLIBCXX_NOEXCEPT
1010 { return reverse_iterator(end()); }
1012 const_reverse_iterator
1013 rbegin() const _GLIBCXX_NOEXCEPT
1014 { return const_reverse_iterator(end()); }
1017 rend() _GLIBCXX_NOEXCEPT
1018 { return reverse_iterator(begin()); }
1020 const_reverse_iterator
1021 rend() const _GLIBCXX_NOEXCEPT
1022 { return const_reverse_iterator(begin()); }
1024 _GLIBCXX_NODISCARD
bool
1025 empty() const _GLIBCXX_NOEXCEPT
1026 { return _M_impl
._M_node_count
== 0; }
1029 size() const _GLIBCXX_NOEXCEPT
1030 { return _M_impl
._M_node_count
; }
1033 max_size() const _GLIBCXX_NOEXCEPT
1034 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
1038 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
);
1041 #if __cplusplus >= 201103L
1042 template<typename _Arg
>
1043 pair
<iterator
, bool>
1044 _M_insert_unique(_Arg
&& __x
);
1046 template<typename _Arg
>
1048 _M_insert_equal(_Arg
&& __x
);
1050 template<typename _Arg
, typename _NodeGen
>
1052 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
1054 template<typename _Arg
>
1056 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
)
1058 _Alloc_node
__an(*this);
1059 return _M_insert_unique_(__pos
, std::forward
<_Arg
>(__x
), __an
);
1062 template<typename _Arg
, typename _NodeGen
>
1064 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
1066 template<typename _Arg
>
1068 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
)
1070 _Alloc_node
__an(*this);
1071 return _M_insert_equal_(__pos
, std::forward
<_Arg
>(__x
), __an
);
1074 template<typename
... _Args
>
1075 pair
<iterator
, bool>
1076 _M_emplace_unique(_Args
&&... __args
);
1078 template<typename
... _Args
>
1080 _M_emplace_equal(_Args
&&... __args
);
1082 template<typename
... _Args
>
1084 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
);
1086 template<typename
... _Args
>
1088 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
);
1090 template<typename _Iter
>
1091 using __same_value_type
1092 = is_same
<value_type
, typename iterator_traits
<_Iter
>::value_type
>;
1094 template<typename _InputIterator
>
1095 __enable_if_t
<__same_value_type
<_InputIterator
>::value
>
1096 _M_insert_range_unique(_InputIterator __first
, _InputIterator __last
)
1098 _Alloc_node
__an(*this);
1099 for (; __first
!= __last
; ++__first
)
1100 _M_insert_unique_(end(), *__first
, __an
);
1103 template<typename _InputIterator
>
1104 __enable_if_t
<!__same_value_type
<_InputIterator
>::value
>
1105 _M_insert_range_unique(_InputIterator __first
, _InputIterator __last
)
1107 for (; __first
!= __last
; ++__first
)
1108 _M_emplace_unique(*__first
);
1111 template<typename _InputIterator
>
1112 __enable_if_t
<__same_value_type
<_InputIterator
>::value
>
1113 _M_insert_range_equal(_InputIterator __first
, _InputIterator __last
)
1115 _Alloc_node
__an(*this);
1116 for (; __first
!= __last
; ++__first
)
1117 _M_insert_equal_(end(), *__first
, __an
);
1120 template<typename _InputIterator
>
1121 __enable_if_t
<!__same_value_type
<_InputIterator
>::value
>
1122 _M_insert_range_equal(_InputIterator __first
, _InputIterator __last
)
1124 for (; __first
!= __last
; ++__first
)
1125 _M_emplace_equal(*__first
);
1128 pair
<iterator
, bool>
1129 _M_insert_unique(const value_type
& __x
);
1132 _M_insert_equal(const value_type
& __x
);
1134 template<typename _NodeGen
>
1136 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
,
1140 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
)
1142 _Alloc_node
__an(*this);
1143 return _M_insert_unique_(__pos
, __x
, __an
);
1146 template<typename _NodeGen
>
1148 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
,
1151 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
)
1153 _Alloc_node
__an(*this);
1154 return _M_insert_equal_(__pos
, __x
, __an
);
1157 template<typename _InputIterator
>
1159 _M_insert_range_unique(_InputIterator __first
, _InputIterator __last
)
1161 _Alloc_node
__an(*this);
1162 for (; __first
!= __last
; ++__first
)
1163 _M_insert_unique_(end(), *__first
, __an
);
1166 template<typename _InputIterator
>
1168 _M_insert_range_equal(_InputIterator __first
, _InputIterator __last
)
1170 _Alloc_node
__an(*this);
1171 for (; __first
!= __last
; ++__first
)
1172 _M_insert_equal_(end(), *__first
, __an
);
1178 _M_erase_aux(const_iterator __position
);
1181 _M_erase_aux(const_iterator __first
, const_iterator __last
);
1184 #if __cplusplus >= 201103L
1185 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1186 // DR 130. Associative erase should return an iterator.
1187 _GLIBCXX_ABI_TAG_CXX11
1189 erase(const_iterator __position
)
1191 __glibcxx_assert(__position
!= end());
1192 const_iterator __result
= __position
;
1194 _M_erase_aux(__position
);
1195 return __result
._M_const_cast();
1199 _GLIBCXX_ABI_TAG_CXX11
1201 erase(iterator __position
)
1203 __glibcxx_assert(__position
!= end());
1204 iterator __result
= __position
;
1206 _M_erase_aux(__position
);
1211 erase(iterator __position
)
1213 __glibcxx_assert(__position
!= end());
1214 _M_erase_aux(__position
);
1218 erase(const_iterator __position
)
1220 __glibcxx_assert(__position
!= end());
1221 _M_erase_aux(__position
);
1226 erase(const key_type
& __x
);
1228 #if __cplusplus >= 201103L
1229 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1230 // DR 130. Associative erase should return an iterator.
1231 _GLIBCXX_ABI_TAG_CXX11
1233 erase(const_iterator __first
, const_iterator __last
)
1235 _M_erase_aux(__first
, __last
);
1236 return __last
._M_const_cast();
1240 erase(iterator __first
, iterator __last
)
1241 { _M_erase_aux(__first
, __last
); }
1244 erase(const_iterator __first
, const_iterator __last
)
1245 { _M_erase_aux(__first
, __last
); }
1249 clear() _GLIBCXX_NOEXCEPT
1251 _M_erase(_M_begin());
1257 find(const key_type
& __k
);
1260 find(const key_type
& __k
) const;
1263 count(const key_type
& __k
) const;
1266 lower_bound(const key_type
& __k
)
1267 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1270 lower_bound(const key_type
& __k
) const
1271 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1274 upper_bound(const key_type
& __k
)
1275 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1278 upper_bound(const key_type
& __k
) const
1279 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1281 pair
<iterator
, iterator
>
1282 equal_range(const key_type
& __k
);
1284 pair
<const_iterator
, const_iterator
>
1285 equal_range(const key_type
& __k
) const;
1287 #if __cplusplus >= 201402L
1288 template<typename _Kt
,
1289 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1291 _M_find_tr(const _Kt
& __k
)
1293 const _Rb_tree
* __const_this
= this;
1294 return __const_this
->_M_find_tr(__k
)._M_const_cast();
1297 template<typename _Kt
,
1298 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1300 _M_find_tr(const _Kt
& __k
) const
1302 auto __j
= _M_lower_bound_tr(__k
);
1303 if (__j
!= end() && _M_impl
._M_key_compare(__k
, _S_key(__j
._M_node
)))
1308 template<typename _Kt
,
1309 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1311 _M_count_tr(const _Kt
& __k
) const
1313 auto __p
= _M_equal_range_tr(__k
);
1314 return std::distance(__p
.first
, __p
.second
);
1317 template<typename _Kt
,
1318 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1320 _M_lower_bound_tr(const _Kt
& __k
)
1322 const _Rb_tree
* __const_this
= this;
1323 return __const_this
->_M_lower_bound_tr(__k
)._M_const_cast();
1326 template<typename _Kt
,
1327 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1329 _M_lower_bound_tr(const _Kt
& __k
) const
1331 auto __x
= _M_begin();
1332 auto __y
= _M_end();
1334 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1340 __x
= _S_right(__x
);
1341 return const_iterator(__y
);
1344 template<typename _Kt
,
1345 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1347 _M_upper_bound_tr(const _Kt
& __k
)
1349 const _Rb_tree
* __const_this
= this;
1350 return __const_this
->_M_upper_bound_tr(__k
)._M_const_cast();
1353 template<typename _Kt
,
1354 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1356 _M_upper_bound_tr(const _Kt
& __k
) const
1358 auto __x
= _M_begin();
1359 auto __y
= _M_end();
1361 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1367 __x
= _S_right(__x
);
1368 return const_iterator(__y
);
1371 template<typename _Kt
,
1372 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1373 pair
<iterator
, iterator
>
1374 _M_equal_range_tr(const _Kt
& __k
)
1376 const _Rb_tree
* __const_this
= this;
1377 auto __ret
= __const_this
->_M_equal_range_tr(__k
);
1378 return { __ret
.first
._M_const_cast(), __ret
.second
._M_const_cast() };
1381 template<typename _Kt
,
1382 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1383 pair
<const_iterator
, const_iterator
>
1384 _M_equal_range_tr(const _Kt
& __k
) const
1386 auto __low
= _M_lower_bound_tr(__k
);
1387 auto __high
= __low
;
1388 auto& __cmp
= _M_impl
._M_key_compare
;
1389 while (__high
!= end() && !__cmp(__k
, _S_key(__high
._M_node
)))
1391 return { __low
, __high
};
1397 __rb_verify() const;
1399 #if __cplusplus >= 201103L
1401 operator=(_Rb_tree
&&)
1402 noexcept(_Alloc_traits::_S_nothrow_move()
1403 && is_nothrow_move_assignable
<_Compare
>::value
);
1405 template<typename _Iterator
>
1407 _M_assign_unique(_Iterator
, _Iterator
);
1409 template<typename _Iterator
>
1411 _M_assign_equal(_Iterator
, _Iterator
);
1414 // Move elements from container with equal allocator.
1416 _M_move_data(_Rb_tree
& __x
, true_type
)
1417 { _M_impl
._M_move_data(__x
._M_impl
); }
1419 // Move elements from container with possibly non-equal allocator,
1420 // which might result in a copy not a move.
1422 _M_move_data(_Rb_tree
&, false_type
);
1424 // Move assignment from container with equal allocator.
1426 _M_move_assign(_Rb_tree
&, true_type
);
1428 // Move assignment from container with possibly non-equal allocator,
1429 // which might result in a copy not a move.
1431 _M_move_assign(_Rb_tree
&, false_type
);
1434 #if __glibcxx_node_extract // >= C++17
1436 /// Re-insert an extracted node.
1438 _M_reinsert_node_unique(node_type
&& __nh
)
1440 insert_return_type __ret
;
1442 __ret
.position
= end();
1445 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1447 auto __res
= _M_get_insert_unique_pos(__nh
._M_key());
1451 = _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1453 __ret
.inserted
= true;
1457 __ret
.node
= std::move(__nh
);
1458 __ret
.position
= iterator(__res
.first
);
1459 __ret
.inserted
= false;
1465 /// Re-insert an extracted node.
1467 _M_reinsert_node_equal(node_type
&& __nh
)
1474 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1475 auto __res
= _M_get_insert_equal_pos(__nh
._M_key());
1477 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1479 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1485 /// Re-insert an extracted node.
1487 _M_reinsert_node_hint_unique(const_iterator __hint
, node_type
&& __nh
)
1494 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1495 auto __res
= _M_get_insert_hint_unique_pos(__hint
, __nh
._M_key());
1498 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1502 __ret
= iterator(__res
.first
);
1507 /// Re-insert an extracted node.
1509 _M_reinsert_node_hint_equal(const_iterator __hint
, node_type
&& __nh
)
1516 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1517 auto __res
= _M_get_insert_hint_equal_pos(__hint
, __nh
._M_key());
1519 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1521 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1529 extract(const_iterator __pos
)
1531 auto __ptr
= _Rb_tree_rebalance_for_erase(
1532 __pos
._M_const_cast()._M_node
, _M_impl
._M_header
);
1533 --_M_impl
._M_node_count
;
1534 return { static_cast<_Link_type
>(__ptr
), _M_get_Node_allocator() };
1539 extract(const key_type
& __k
)
1542 auto __pos
= find(__k
);
1544 __nh
= extract(const_iterator(__pos
));
1548 template<typename _Compare2
>
1549 using _Compatible_tree
1550 = _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare2
, _Alloc
>;
1552 template<typename
, typename
>
1553 friend struct _Rb_tree_merge_helper
;
1555 /// Merge from a compatible container into one with unique keys.
1556 template<typename _Compare2
>
1558 _M_merge_unique(_Compatible_tree
<_Compare2
>& __src
) noexcept
1560 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1561 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1564 auto __res
= _M_get_insert_unique_pos(_KeyOfValue()(*__pos
));
1567 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1568 auto __ptr
= _Rb_tree_rebalance_for_erase(
1569 __pos
._M_node
, __src_impl
._M_header
);
1570 --__src_impl
._M_node_count
;
1571 _M_insert_node(__res
.first
, __res
.second
,
1572 static_cast<_Link_type
>(__ptr
));
1577 /// Merge from a compatible container into one with equivalent keys.
1578 template<typename _Compare2
>
1580 _M_merge_equal(_Compatible_tree
<_Compare2
>& __src
) noexcept
1582 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1583 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1586 auto __res
= _M_get_insert_equal_pos(_KeyOfValue()(*__pos
));
1589 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1590 auto __ptr
= _Rb_tree_rebalance_for_erase(
1591 __pos
._M_node
, __src_impl
._M_header
);
1592 --__src_impl
._M_node_count
;
1593 _M_insert_node(__res
.first
, __res
.second
,
1594 static_cast<_Link_type
>(__ptr
));
1598 #endif // C++17 node_extract
1601 operator==(const _Rb_tree
& __x
, const _Rb_tree
& __y
)
1603 return __x
.size() == __y
.size()
1604 && std::equal(__x
.begin(), __x
.end(), __y
.begin());
1607 #if __cpp_lib_three_way_comparison
1609 operator<=>(const _Rb_tree
& __x
, const _Rb_tree
& __y
)
1611 if constexpr (requires
{ typename
__detail::__synth3way_t
<_Val
>; })
1612 return std::lexicographical_compare_three_way(__x
.begin(), __x
.end(),
1613 __y
.begin(), __y
.end(),
1614 __detail::__synth3way
);
1618 operator<(const _Rb_tree
& __x
, const _Rb_tree
& __y
)
1620 return std::lexicographical_compare(__x
.begin(), __x
.end(),
1621 __y
.begin(), __y
.end());
1626 #if __cplusplus >= 201103L
1627 // An RAII _Node handle
1630 template<typename
... _Args
>
1631 _Auto_node(_Rb_tree
& __t
, _Args
&&... __args
)
1633 _M_node(__t
._M_create_node(std::forward
<_Args
>(__args
)...))
1639 _M_t
._M_drop_node(_M_node
);
1642 _Auto_node(_Auto_node
&& __n
)
1643 : _M_t(__n
._M_t
), _M_node(__n
._M_node
)
1644 { __n
._M_node
= nullptr; }
1648 { return _S_key(_M_node
); }
1651 _M_insert(pair
<_Base_ptr
, _Base_ptr
> __p
)
1653 auto __it
= _M_t
._M_insert_node(__p
.first
, __p
.second
, _M_node
);
1659 _M_insert_equal_lower()
1661 auto __it
= _M_t
._M_insert_equal_lower_node(_M_node
);
1672 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1673 typename _Compare
, typename _Alloc
>
1675 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1676 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1679 #if __cplusplus >= 201103L
1680 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1681 typename _Compare
, typename _Alloc
>
1683 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1684 _M_move_data(_Rb_tree
& __x
, false_type
)
1686 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1687 _M_move_data(__x
, true_type());
1690 constexpr bool __move
= !__move_if_noexcept_cond
<value_type
>::value
;
1691 _Alloc_node
__an(*this);
1692 _M_root() = _M_copy
<__move
>(__x
, __an
);
1693 if _GLIBCXX17_CONSTEXPR (__move
)
1698 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1699 typename _Compare
, typename _Alloc
>
1701 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1702 _M_move_assign(_Rb_tree
& __x
, true_type
)
1705 if (__x
._M_root() != nullptr)
1706 _M_move_data(__x
, true_type());
1707 std::__alloc_on_move(_M_get_Node_allocator(),
1708 __x
._M_get_Node_allocator());
1711 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1712 typename _Compare
, typename _Alloc
>
1714 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1715 _M_move_assign(_Rb_tree
& __x
, false_type
)
1717 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1718 return _M_move_assign(__x
, true_type
{});
1720 // Try to move each node reusing existing nodes and copying __x nodes
1722 _Reuse_or_alloc_node
__roan(*this);
1724 if (__x
._M_root() != nullptr)
1726 _M_root() = _M_copy
<__as_rvalue
>(__x
, __roan
);
1731 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1732 typename _Compare
, typename _Alloc
>
1733 inline _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1734 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1735 operator=(_Rb_tree
&& __x
)
1736 noexcept(_Alloc_traits::_S_nothrow_move()
1737 && is_nothrow_move_assignable
<_Compare
>::value
)
1739 _M_impl
._M_key_compare
= std::move(__x
._M_impl
._M_key_compare
);
1740 _M_move_assign(__x
, __bool_constant
<_Alloc_traits::_S_nothrow_move()>());
1744 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1745 typename _Compare
, typename _Alloc
>
1746 template<typename _Iterator
>
1748 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1749 _M_assign_unique(_Iterator __first
, _Iterator __last
)
1751 _Reuse_or_alloc_node
__roan(*this);
1753 for (; __first
!= __last
; ++__first
)
1754 _M_insert_unique_(end(), *__first
, __roan
);
1757 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1758 typename _Compare
, typename _Alloc
>
1759 template<typename _Iterator
>
1761 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1762 _M_assign_equal(_Iterator __first
, _Iterator __last
)
1764 _Reuse_or_alloc_node
__roan(*this);
1766 for (; __first
!= __last
; ++__first
)
1767 _M_insert_equal_(end(), *__first
, __roan
);
1771 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1772 typename _Compare
, typename _Alloc
>
1773 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1774 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1775 operator=(const _Rb_tree
& __x
)
1777 if (this != std::__addressof(__x
))
1779 // Note that _Key may be a constant type.
1780 #if __cplusplus >= 201103L
1781 if (_Alloc_traits::_S_propagate_on_copy_assign())
1783 auto& __this_alloc
= this->_M_get_Node_allocator();
1784 auto& __that_alloc
= __x
._M_get_Node_allocator();
1785 if (!_Alloc_traits::_S_always_equal()
1786 && __this_alloc
!= __that_alloc
)
1788 // Replacement allocator cannot free existing storage, we need
1789 // to erase nodes first.
1791 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1796 _Reuse_or_alloc_node
__roan(*this);
1798 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
1799 if (__x
._M_root() != 0)
1800 _M_root() = _M_copy
<__as_lvalue
>(__x
, __roan
);
1806 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1807 typename _Compare
, typename _Alloc
>
1808 #if __cplusplus >= 201103L
1809 template<typename _Arg
, typename _NodeGen
>
1811 template<typename _NodeGen
>
1813 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1814 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1815 _M_insert_(_Base_ptr __x
, _Base_ptr __p
,
1816 #if __cplusplus >= 201103L
1821 _NodeGen
& __node_gen
)
1823 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
1824 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
1827 _Link_type __z
= __node_gen(_GLIBCXX_FORWARD(_Arg
, __v
));
1829 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1830 this->_M_impl
._M_header
);
1831 ++_M_impl
._M_node_count
;
1832 return iterator(__z
);
1835 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1836 typename _Compare
, typename _Alloc
>
1837 #if __cplusplus >= 201103L
1838 template<typename _Arg
>
1840 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1841 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1842 #if __cplusplus >= 201103L
1843 _M_insert_lower(_Base_ptr __p
, _Arg
&& __v
)
1845 _M_insert_lower(_Base_ptr __p
, const _Val
& __v
)
1848 bool __insert_left
= (__p
== _M_end()
1849 || !_M_impl
._M_key_compare(_S_key(__p
),
1850 _KeyOfValue()(__v
)));
1852 _Link_type __z
= _M_create_node(_GLIBCXX_FORWARD(_Arg
, __v
));
1854 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1855 this->_M_impl
._M_header
);
1856 ++_M_impl
._M_node_count
;
1857 return iterator(__z
);
1860 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1861 typename _Compare
, typename _Alloc
>
1862 #if __cplusplus >= 201103L
1863 template<typename _Arg
>
1865 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1866 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1867 #if __cplusplus >= 201103L
1868 _M_insert_equal_lower(_Arg
&& __v
)
1870 _M_insert_equal_lower(const _Val
& __v
)
1873 _Link_type __x
= _M_begin();
1874 _Base_ptr __y
= _M_end();
1878 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _KeyOfValue()(__v
)) ?
1879 _S_left(__x
) : _S_right(__x
);
1881 return _M_insert_lower(__y
, _GLIBCXX_FORWARD(_Arg
, __v
));
1884 template<typename _Key
, typename _Val
, typename _KoV
,
1885 typename _Compare
, typename _Alloc
>
1886 template<bool _MoveValues
, typename _NodeGen
>
1887 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1888 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
1889 _M_copy(_Link_type __x
, _Base_ptr __p
, _NodeGen
& __node_gen
)
1891 // Structural copy. __x and __p must be non-null.
1892 _Link_type __top
= _M_clone_node
<_MoveValues
>(__x
, __node_gen
);
1893 __top
->_M_parent
= __p
;
1899 _M_copy
<_MoveValues
>(_S_right(__x
), __top
, __node_gen
);
1905 _Link_type __y
= _M_clone_node
<_MoveValues
>(__x
, __node_gen
);
1907 __y
->_M_parent
= __p
;
1909 __y
->_M_right
= _M_copy
<_MoveValues
>(_S_right(__x
),
1918 __throw_exception_again
;
1923 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1924 typename _Compare
, typename _Alloc
>
1926 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1927 _M_erase(_Link_type __x
)
1929 // Erase without rebalancing.
1932 _M_erase(_S_right(__x
));
1933 _Link_type __y
= _S_left(__x
);
1939 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1940 typename _Compare
, typename _Alloc
>
1941 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1942 _Compare
, _Alloc
>::iterator
1943 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1944 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
1948 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1949 __y
= __x
, __x
= _S_left(__x
);
1951 __x
= _S_right(__x
);
1952 return iterator(__y
);
1955 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1956 typename _Compare
, typename _Alloc
>
1957 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1958 _Compare
, _Alloc
>::const_iterator
1959 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1960 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1961 const _Key
& __k
) const
1964 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1965 __y
= __x
, __x
= _S_left(__x
);
1967 __x
= _S_right(__x
);
1968 return const_iterator(__y
);
1971 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1972 typename _Compare
, typename _Alloc
>
1973 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1974 _Compare
, _Alloc
>::iterator
1975 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1976 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
1980 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1981 __y
= __x
, __x
= _S_left(__x
);
1983 __x
= _S_right(__x
);
1984 return iterator(__y
);
1987 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1988 typename _Compare
, typename _Alloc
>
1989 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1990 _Compare
, _Alloc
>::const_iterator
1991 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1992 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1993 const _Key
& __k
) const
1996 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1997 __y
= __x
, __x
= _S_left(__x
);
1999 __x
= _S_right(__x
);
2000 return const_iterator(__y
);
2003 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2004 typename _Compare
, typename _Alloc
>
2005 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2006 _Compare
, _Alloc
>::iterator
,
2007 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2008 _Compare
, _Alloc
>::iterator
>
2009 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2010 equal_range(const _Key
& __k
)
2012 _Link_type __x
= _M_begin();
2013 _Base_ptr __y
= _M_end();
2016 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
2017 __x
= _S_right(__x
);
2018 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
2019 __y
= __x
, __x
= _S_left(__x
);
2022 _Link_type
__xu(__x
);
2023 _Base_ptr
__yu(__y
);
2024 __y
= __x
, __x
= _S_left(__x
);
2025 __xu
= _S_right(__xu
);
2026 return pair
<iterator
,
2027 iterator
>(_M_lower_bound(__x
, __y
, __k
),
2028 _M_upper_bound(__xu
, __yu
, __k
));
2031 return pair
<iterator
, iterator
>(iterator(__y
),
2035 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2036 typename _Compare
, typename _Alloc
>
2037 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2038 _Compare
, _Alloc
>::const_iterator
,
2039 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2040 _Compare
, _Alloc
>::const_iterator
>
2041 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2042 equal_range(const _Key
& __k
) const
2044 _Const_Link_type __x
= _M_begin();
2045 _Const_Base_ptr __y
= _M_end();
2048 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
2049 __x
= _S_right(__x
);
2050 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
2051 __y
= __x
, __x
= _S_left(__x
);
2054 _Const_Link_type
__xu(__x
);
2055 _Const_Base_ptr
__yu(__y
);
2056 __y
= __x
, __x
= _S_left(__x
);
2057 __xu
= _S_right(__xu
);
2058 return pair
<const_iterator
,
2059 const_iterator
>(_M_lower_bound(__x
, __y
, __k
),
2060 _M_upper_bound(__xu
, __yu
, __k
));
2063 return pair
<const_iterator
, const_iterator
>(const_iterator(__y
),
2064 const_iterator(__y
));
2067 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2068 typename _Compare
, typename _Alloc
>
2070 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2072 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
)
2076 if (__t
._M_root() != 0)
2077 _M_impl
._M_move_data(__t
._M_impl
);
2079 else if (__t
._M_root() == 0)
2080 __t
._M_impl
._M_move_data(_M_impl
);
2083 std::swap(_M_root(),__t
._M_root());
2084 std::swap(_M_leftmost(),__t
._M_leftmost());
2085 std::swap(_M_rightmost(),__t
._M_rightmost());
2087 _M_root()->_M_parent
= _M_end();
2088 __t
._M_root()->_M_parent
= __t
._M_end();
2089 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
2091 // No need to swap header's color as it does not change.
2092 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
2094 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2095 __t
._M_get_Node_allocator());
2098 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2099 typename _Compare
, typename _Alloc
>
2100 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2101 _Compare
, _Alloc
>::_Base_ptr
,
2102 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2103 _Compare
, _Alloc
>::_Base_ptr
>
2104 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2105 _M_get_insert_unique_pos(const key_type
& __k
)
2107 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2108 _Link_type __x
= _M_begin();
2109 _Base_ptr __y
= _M_end();
2114 __comp
= _M_impl
._M_key_compare(__k
, _S_key(__x
));
2115 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
2117 iterator __j
= iterator(__y
);
2121 return _Res(__x
, __y
);
2125 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), __k
))
2126 return _Res(__x
, __y
);
2127 return _Res(__j
._M_node
, 0);
2130 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2131 typename _Compare
, typename _Alloc
>
2132 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2133 _Compare
, _Alloc
>::_Base_ptr
,
2134 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2135 _Compare
, _Alloc
>::_Base_ptr
>
2136 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2137 _M_get_insert_equal_pos(const key_type
& __k
)
2139 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2140 _Link_type __x
= _M_begin();
2141 _Base_ptr __y
= _M_end();
2145 __x
= _M_impl
._M_key_compare(__k
, _S_key(__x
)) ?
2146 _S_left(__x
) : _S_right(__x
);
2148 return _Res(__x
, __y
);
2151 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2152 typename _Compare
, typename _Alloc
>
2153 #if __cplusplus >= 201103L
2154 template<typename _Arg
>
2156 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2157 _Compare
, _Alloc
>::iterator
, bool>
2158 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2159 #if __cplusplus >= 201103L
2160 _M_insert_unique(_Arg
&& __v
)
2162 _M_insert_unique(const _Val
& __v
)
2165 typedef pair
<iterator
, bool> _Res
;
2166 pair
<_Base_ptr
, _Base_ptr
> __res
2167 = _M_get_insert_unique_pos(_KeyOfValue()(__v
));
2171 _Alloc_node
__an(*this);
2172 return _Res(_M_insert_(__res
.first
, __res
.second
,
2173 _GLIBCXX_FORWARD(_Arg
, __v
), __an
),
2177 return _Res(iterator(__res
.first
), false);
2180 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2181 typename _Compare
, typename _Alloc
>
2182 #if __cplusplus >= 201103L
2183 template<typename _Arg
>
2185 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2186 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2187 #if __cplusplus >= 201103L
2188 _M_insert_equal(_Arg
&& __v
)
2190 _M_insert_equal(const _Val
& __v
)
2193 pair
<_Base_ptr
, _Base_ptr
> __res
2194 = _M_get_insert_equal_pos(_KeyOfValue()(__v
));
2195 _Alloc_node
__an(*this);
2196 return _M_insert_(__res
.first
, __res
.second
,
2197 _GLIBCXX_FORWARD(_Arg
, __v
), __an
);
2200 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2201 typename _Compare
, typename _Alloc
>
2202 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2203 _Compare
, _Alloc
>::_Base_ptr
,
2204 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2205 _Compare
, _Alloc
>::_Base_ptr
>
2206 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2207 _M_get_insert_hint_unique_pos(const_iterator __position
,
2208 const key_type
& __k
)
2210 iterator __pos
= __position
._M_const_cast();
2211 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2214 if (__pos
._M_node
== _M_end())
2217 && _M_impl
._M_key_compare(_S_key(_M_rightmost()), __k
))
2218 return _Res(0, _M_rightmost());
2220 return _M_get_insert_unique_pos(__k
);
2222 else if (_M_impl
._M_key_compare(__k
, _S_key(__pos
._M_node
)))
2224 // First, try before...
2225 iterator __before
= __pos
;
2226 if (__pos
._M_node
== _M_leftmost()) // begin()
2227 return _Res(_M_leftmost(), _M_leftmost());
2228 else if (_M_impl
._M_key_compare(_S_key((--__before
)._M_node
), __k
))
2230 if (_S_right(__before
._M_node
) == 0)
2231 return _Res(0, __before
._M_node
);
2233 return _Res(__pos
._M_node
, __pos
._M_node
);
2236 return _M_get_insert_unique_pos(__k
);
2238 else if (_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2240 // ... then try after.
2241 iterator __after
= __pos
;
2242 if (__pos
._M_node
== _M_rightmost())
2243 return _Res(0, _M_rightmost());
2244 else if (_M_impl
._M_key_compare(__k
, _S_key((++__after
)._M_node
)))
2246 if (_S_right(__pos
._M_node
) == 0)
2247 return _Res(0, __pos
._M_node
);
2249 return _Res(__after
._M_node
, __after
._M_node
);
2252 return _M_get_insert_unique_pos(__k
);
2256 return _Res(__pos
._M_node
, 0);
2259 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2260 typename _Compare
, typename _Alloc
>
2261 #if __cplusplus >= 201103L
2262 template<typename _Arg
, typename _NodeGen
>
2264 template<typename _NodeGen
>
2266 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2267 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2268 _M_insert_unique_(const_iterator __position
,
2269 #if __cplusplus >= 201103L
2274 _NodeGen
& __node_gen
)
2276 pair
<_Base_ptr
, _Base_ptr
> __res
2277 = _M_get_insert_hint_unique_pos(__position
, _KeyOfValue()(__v
));
2280 return _M_insert_(__res
.first
, __res
.second
,
2281 _GLIBCXX_FORWARD(_Arg
, __v
),
2283 return iterator(__res
.first
);
2286 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2287 typename _Compare
, typename _Alloc
>
2288 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2289 _Compare
, _Alloc
>::_Base_ptr
,
2290 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2291 _Compare
, _Alloc
>::_Base_ptr
>
2292 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2293 _M_get_insert_hint_equal_pos(const_iterator __position
, const key_type
& __k
)
2295 iterator __pos
= __position
._M_const_cast();
2296 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2299 if (__pos
._M_node
== _M_end())
2302 && !_M_impl
._M_key_compare(__k
, _S_key(_M_rightmost())))
2303 return _Res(0, _M_rightmost());
2305 return _M_get_insert_equal_pos(__k
);
2307 else if (!_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2309 // First, try before...
2310 iterator __before
= __pos
;
2311 if (__pos
._M_node
== _M_leftmost()) // begin()
2312 return _Res(_M_leftmost(), _M_leftmost());
2313 else if (!_M_impl
._M_key_compare(__k
, _S_key((--__before
)._M_node
)))
2315 if (_S_right(__before
._M_node
) == 0)
2316 return _Res(0, __before
._M_node
);
2318 return _Res(__pos
._M_node
, __pos
._M_node
);
2321 return _M_get_insert_equal_pos(__k
);
2325 // ... then try after.
2326 iterator __after
= __pos
;
2327 if (__pos
._M_node
== _M_rightmost())
2328 return _Res(0, _M_rightmost());
2329 else if (!_M_impl
._M_key_compare(_S_key((++__after
)._M_node
), __k
))
2331 if (_S_right(__pos
._M_node
) == 0)
2332 return _Res(0, __pos
._M_node
);
2334 return _Res(__after
._M_node
, __after
._M_node
);
2341 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2342 typename _Compare
, typename _Alloc
>
2343 #if __cplusplus >= 201103L
2344 template<typename _Arg
, typename _NodeGen
>
2346 template<typename _NodeGen
>
2348 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2349 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2350 _M_insert_equal_(const_iterator __position
,
2351 #if __cplusplus >= 201103L
2356 _NodeGen
& __node_gen
)
2358 pair
<_Base_ptr
, _Base_ptr
> __res
2359 = _M_get_insert_hint_equal_pos(__position
, _KeyOfValue()(__v
));
2362 return _M_insert_(__res
.first
, __res
.second
,
2363 _GLIBCXX_FORWARD(_Arg
, __v
),
2366 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg
, __v
));
2369 #if __cplusplus >= 201103L
2370 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2371 typename _Compare
, typename _Alloc
>
2373 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2374 _M_insert_node(_Base_ptr __x
, _Base_ptr __p
, _Link_type __z
)
2377 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
2378 || _M_impl
._M_key_compare(_S_key(__z
),
2381 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2382 this->_M_impl
._M_header
);
2383 ++_M_impl
._M_node_count
;
2384 return iterator(__z
);
2387 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2388 typename _Compare
, typename _Alloc
>
2390 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2391 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
)
2394 bool __insert_left
= (__p
== _M_end()
2395 || !_M_impl
._M_key_compare(_S_key(__p
),
2398 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2399 this->_M_impl
._M_header
);
2400 ++_M_impl
._M_node_count
;
2401 return iterator(__z
);
2404 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2405 typename _Compare
, typename _Alloc
>
2407 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2408 _M_insert_equal_lower_node(_Link_type __z
)
2411 _Link_type __x
= _M_begin();
2412 _Base_ptr __y
= _M_end();
2416 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _S_key(__z
)) ?
2417 _S_left(__x
) : _S_right(__x
);
2419 return _M_insert_lower_node(__y
, __z
);
2422 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2423 typename _Compare
, typename _Alloc
>
2424 template<typename
... _Args
>
2426 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2427 _M_emplace_unique(_Args
&&... __args
)
2428 -> pair
<iterator
, bool>
2430 _Auto_node
__z(*this, std::forward
<_Args
>(__args
)...);
2431 auto __res
= _M_get_insert_unique_pos(__z
._M_key());
2433 return {__z
._M_insert(__res
), true};
2434 return {iterator(__res
.first
), false};
2437 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2438 typename _Compare
, typename _Alloc
>
2439 template<typename
... _Args
>
2441 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2442 _M_emplace_equal(_Args
&&... __args
)
2445 _Auto_node
__z(*this, std::forward
<_Args
>(__args
)...);
2446 auto __res
= _M_get_insert_equal_pos(__z
._M_key());
2447 return __z
._M_insert(__res
);
2450 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2451 typename _Compare
, typename _Alloc
>
2452 template<typename
... _Args
>
2454 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2455 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
)
2458 _Auto_node
__z(*this, std::forward
<_Args
>(__args
)...);
2459 auto __res
= _M_get_insert_hint_unique_pos(__pos
, __z
._M_key());
2461 return __z
._M_insert(__res
);
2462 return iterator(__res
.first
);
2465 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2466 typename _Compare
, typename _Alloc
>
2467 template<typename
... _Args
>
2469 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2470 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
)
2473 _Auto_node
__z(*this, std::forward
<_Args
>(__args
)...);
2474 auto __res
= _M_get_insert_hint_equal_pos(__pos
, __z
._M_key());
2476 return __z
._M_insert(__res
);
2477 return __z
._M_insert_equal_lower();
2482 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2483 typename _Compare
, typename _Alloc
>
2485 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2486 _M_erase_aux(const_iterator __position
)
2489 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
2490 (const_cast<_Base_ptr
>(__position
._M_node
),
2491 this->_M_impl
._M_header
));
2493 --_M_impl
._M_node_count
;
2496 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2497 typename _Compare
, typename _Alloc
>
2499 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2500 _M_erase_aux(const_iterator __first
, const_iterator __last
)
2502 if (__first
== begin() && __last
== end())
2505 while (__first
!= __last
)
2506 _M_erase_aux(__first
++);
2509 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2510 typename _Compare
, typename _Alloc
>
2511 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2512 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2513 erase(const _Key
& __x
)
2515 pair
<iterator
, iterator
> __p
= equal_range(__x
);
2516 const size_type __old_size
= size();
2517 _M_erase_aux(__p
.first
, __p
.second
);
2518 return __old_size
- size();
2521 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2522 typename _Compare
, typename _Alloc
>
2523 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2524 _Compare
, _Alloc
>::iterator
2525 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2526 find(const _Key
& __k
)
2528 iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2529 return (__j
== end()
2530 || _M_impl
._M_key_compare(__k
,
2531 _S_key(__j
._M_node
))) ? end() : __j
;
2534 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2535 typename _Compare
, typename _Alloc
>
2536 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2537 _Compare
, _Alloc
>::const_iterator
2538 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2539 find(const _Key
& __k
) const
2541 const_iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2542 return (__j
== end()
2543 || _M_impl
._M_key_compare(__k
,
2544 _S_key(__j
._M_node
))) ? end() : __j
;
2547 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2548 typename _Compare
, typename _Alloc
>
2549 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2550 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2551 count(const _Key
& __k
) const
2553 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
2554 const size_type __n
= std::distance(__p
.first
, __p
.second
);
2558 _GLIBCXX_PURE
unsigned int
2559 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
2560 const _Rb_tree_node_base
* __root
) throw ();
2562 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2563 typename _Compare
, typename _Alloc
>
2565 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
2567 if (_M_impl
._M_node_count
== 0 || begin() == end())
2568 return _M_impl
._M_node_count
== 0 && begin() == end()
2569 && this->_M_impl
._M_header
._M_left
== _M_end()
2570 && this->_M_impl
._M_header
._M_right
== _M_end();
2572 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
2573 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
2575 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
2576 _Const_Link_type __L
= _S_left(__x
);
2577 _Const_Link_type __R
= _S_right(__x
);
2579 if (__x
->_M_color
== _S_red
)
2580 if ((__L
&& __L
->_M_color
== _S_red
)
2581 || (__R
&& __R
->_M_color
== _S_red
))
2584 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
2586 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
2589 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
2593 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2595 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2600 #if __cplusplus > 201402L
2601 // Allow access to internals of compatible _Rb_tree specializations.
2602 template<typename _Key
, typename _Val
, typename _Sel
, typename _Cmp1
,
2603 typename _Alloc
, typename _Cmp2
>
2604 struct _Rb_tree_merge_helper
<_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>,
2608 friend class _Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>;
2611 _S_get_impl(_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp2
, _Alloc
>& __tree
)
2612 { return __tree
._M_impl
; }
2616 _GLIBCXX_END_NAMESPACE_VERSION