1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001-2018 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 #if __cplusplus > 201103L
80 # define __cpp_lib_generic_associative_lookup 201304
83 // Red-black tree class, designed for use in implementing STL
84 // associative containers (set, multiset, map, and multimap). The
85 // insertion and deletion algorithms are based on those in Cormen,
86 // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
89 // (1) the header cell is maintained with links not only to the root
90 // but also to the leftmost node of the tree, to enable constant
91 // time begin(), and to the rightmost node of the tree, to enable
92 // linear time performance when used with the generic set algorithms
95 // (2) when a node being deleted has two children its successor node
96 // is relinked into its place, rather than copied, so that the only
97 // iterators invalidated are those referring to the deleted node.
99 enum _Rb_tree_color
{ _S_red
= false, _S_black
= true };
101 struct _Rb_tree_node_base
103 typedef _Rb_tree_node_base
* _Base_ptr
;
104 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
106 _Rb_tree_color _M_color
;
112 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
114 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
118 static _Const_Base_ptr
119 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
121 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
126 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
128 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
132 static _Const_Base_ptr
133 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
135 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
140 // Helper type offering value initialization guarantee on the compare functor.
141 template<typename _Key_compare
>
142 struct _Rb_tree_key_compare
144 _Key_compare _M_key_compare
;
146 _Rb_tree_key_compare()
147 _GLIBCXX_NOEXCEPT_IF(
148 is_nothrow_default_constructible
<_Key_compare
>::value
)
152 _Rb_tree_key_compare(const _Key_compare
& __comp
)
153 : _M_key_compare(__comp
)
156 #if __cplusplus >= 201103L
157 // Copy constructor added for consistency with C++98 mode.
158 _Rb_tree_key_compare(const _Rb_tree_key_compare
&) = default;
160 _Rb_tree_key_compare(_Rb_tree_key_compare
&& __x
)
161 noexcept(is_nothrow_copy_constructible
<_Key_compare
>::value
)
162 : _M_key_compare(__x
._M_key_compare
)
167 // Helper type to manage default initialization of node count and header.
168 struct _Rb_tree_header
170 _Rb_tree_node_base _M_header
;
171 size_t _M_node_count
; // Keeps track of size of tree.
173 _Rb_tree_header() _GLIBCXX_NOEXCEPT
175 _M_header
._M_color
= _S_red
;
179 #if __cplusplus >= 201103L
180 _Rb_tree_header(_Rb_tree_header
&& __x
) noexcept
182 if (__x
._M_header
._M_parent
!= nullptr)
186 _M_header
._M_color
= _S_red
;
193 _M_move_data(_Rb_tree_header
& __from
)
195 _M_header
._M_color
= __from
._M_header
._M_color
;
196 _M_header
._M_parent
= __from
._M_header
._M_parent
;
197 _M_header
._M_left
= __from
._M_header
._M_left
;
198 _M_header
._M_right
= __from
._M_header
._M_right
;
199 _M_header
._M_parent
->_M_parent
= &_M_header
;
200 _M_node_count
= __from
._M_node_count
;
208 _M_header
._M_parent
= 0;
209 _M_header
._M_left
= &_M_header
;
210 _M_header
._M_right
= &_M_header
;
215 template<typename _Val
>
216 struct _Rb_tree_node
: public _Rb_tree_node_base
218 typedef _Rb_tree_node
<_Val
>* _Link_type
;
220 #if __cplusplus < 201103L
225 { return std::__addressof(_M_value_field
); }
229 { return std::__addressof(_M_value_field
); }
231 __gnu_cxx::__aligned_membuf
<_Val
> _M_storage
;
235 { return _M_storage
._M_ptr(); }
239 { return _M_storage
._M_ptr(); }
243 _GLIBCXX_PURE _Rb_tree_node_base
*
244 _Rb_tree_increment(_Rb_tree_node_base
* __x
) throw ();
246 _GLIBCXX_PURE
const _Rb_tree_node_base
*
247 _Rb_tree_increment(const _Rb_tree_node_base
* __x
) throw ();
249 _GLIBCXX_PURE _Rb_tree_node_base
*
250 _Rb_tree_decrement(_Rb_tree_node_base
* __x
) throw ();
252 _GLIBCXX_PURE
const _Rb_tree_node_base
*
253 _Rb_tree_decrement(const _Rb_tree_node_base
* __x
) throw ();
255 template<typename _Tp
>
256 struct _Rb_tree_iterator
258 typedef _Tp value_type
;
259 typedef _Tp
& reference
;
260 typedef _Tp
* pointer
;
262 typedef bidirectional_iterator_tag iterator_category
;
263 typedef ptrdiff_t difference_type
;
265 typedef _Rb_tree_iterator
<_Tp
> _Self
;
266 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
267 typedef _Rb_tree_node
<_Tp
>* _Link_type
;
269 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
273 _Rb_tree_iterator(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
277 operator*() const _GLIBCXX_NOEXCEPT
278 { return *static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
281 operator->() const _GLIBCXX_NOEXCEPT
282 { return static_cast<_Link_type
> (_M_node
)->_M_valptr(); }
285 operator++() _GLIBCXX_NOEXCEPT
287 _M_node
= _Rb_tree_increment(_M_node
);
292 operator++(int) _GLIBCXX_NOEXCEPT
295 _M_node
= _Rb_tree_increment(_M_node
);
300 operator--() _GLIBCXX_NOEXCEPT
302 _M_node
= _Rb_tree_decrement(_M_node
);
307 operator--(int) _GLIBCXX_NOEXCEPT
310 _M_node
= _Rb_tree_decrement(_M_node
);
315 operator==(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
316 { return _M_node
== __x
._M_node
; }
319 operator!=(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
320 { return _M_node
!= __x
._M_node
; }
325 template<typename _Tp
>
326 struct _Rb_tree_const_iterator
328 typedef _Tp value_type
;
329 typedef const _Tp
& reference
;
330 typedef const _Tp
* pointer
;
332 typedef _Rb_tree_iterator
<_Tp
> iterator
;
334 typedef bidirectional_iterator_tag iterator_category
;
335 typedef ptrdiff_t difference_type
;
337 typedef _Rb_tree_const_iterator
<_Tp
> _Self
;
338 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr
;
339 typedef const _Rb_tree_node
<_Tp
>* _Link_type
;
341 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
345 _Rb_tree_const_iterator(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
348 _Rb_tree_const_iterator(const iterator
& __it
) _GLIBCXX_NOEXCEPT
349 : _M_node(__it
._M_node
) { }
352 _M_const_cast() const _GLIBCXX_NOEXCEPT
353 { return iterator(const_cast<typename
iterator::_Base_ptr
>(_M_node
)); }
356 operator*() const _GLIBCXX_NOEXCEPT
357 { return *static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
360 operator->() const _GLIBCXX_NOEXCEPT
361 { return static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
364 operator++() _GLIBCXX_NOEXCEPT
366 _M_node
= _Rb_tree_increment(_M_node
);
371 operator++(int) _GLIBCXX_NOEXCEPT
374 _M_node
= _Rb_tree_increment(_M_node
);
379 operator--() _GLIBCXX_NOEXCEPT
381 _M_node
= _Rb_tree_decrement(_M_node
);
386 operator--(int) _GLIBCXX_NOEXCEPT
389 _M_node
= _Rb_tree_decrement(_M_node
);
394 operator==(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
395 { return _M_node
== __x
._M_node
; }
398 operator!=(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
399 { return _M_node
!= __x
._M_node
; }
404 template<typename _Val
>
406 operator==(const _Rb_tree_iterator
<_Val
>& __x
,
407 const _Rb_tree_const_iterator
<_Val
>& __y
) _GLIBCXX_NOEXCEPT
408 { return __x
._M_node
== __y
._M_node
; }
410 template<typename _Val
>
412 operator!=(const _Rb_tree_iterator
<_Val
>& __x
,
413 const _Rb_tree_const_iterator
<_Val
>& __y
) _GLIBCXX_NOEXCEPT
414 { return __x
._M_node
!= __y
._M_node
; }
417 _Rb_tree_insert_and_rebalance(const bool __insert_left
,
418 _Rb_tree_node_base
* __x
,
419 _Rb_tree_node_base
* __p
,
420 _Rb_tree_node_base
& __header
) throw ();
423 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
424 _Rb_tree_node_base
& __header
) throw ();
426 #if __cplusplus > 201103L
427 template<typename _Cmp
, typename _SfinaeType
, typename
= __void_t
<>>
428 struct __has_is_transparent
431 template<typename _Cmp
, typename _SfinaeType
>
432 struct __has_is_transparent
<_Cmp
, _SfinaeType
,
433 __void_t
<typename
_Cmp::is_transparent
>>
434 { typedef void type
; };
437 #if __cplusplus > 201402L
438 template<typename _Tree1
, typename _Cmp2
>
439 struct _Rb_tree_merge_helper
{ };
442 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
443 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
446 typedef typename
__gnu_cxx::__alloc_traits
<_Alloc
>::template
447 rebind
<_Rb_tree_node
<_Val
> >::other _Node_allocator
;
449 typedef __gnu_cxx::__alloc_traits
<_Node_allocator
> _Alloc_traits
;
451 #if __cplusplus >= 201103L
452 static_assert(__is_invocable
<_Compare
&, const _Key
&, const _Key
&>{},
453 "comparison object must be invocable with two arguments of key type");
454 # if __cplusplus >= 201703L
455 // _GLIBCXX_RESOLVE_LIB_DEFECTS
456 // 2542. Missing const requirements for associative containers
457 static_assert(is_invocable_v
<const _Compare
&, const _Key
&, const _Key
&>,
458 "comparison object must be invocable as const");
463 typedef _Rb_tree_node_base
* _Base_ptr
;
464 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
465 typedef _Rb_tree_node
<_Val
>* _Link_type
;
466 typedef const _Rb_tree_node
<_Val
>* _Const_Link_type
;
469 // Functor recycling a pool of nodes and using allocation once the pool
471 struct _Reuse_or_alloc_node
473 _Reuse_or_alloc_node(_Rb_tree
& __t
)
474 : _M_root(__t
._M_root()), _M_nodes(__t
._M_rightmost()), _M_t(__t
)
478 _M_root
->_M_parent
= 0;
480 if (_M_nodes
->_M_left
)
481 _M_nodes
= _M_nodes
->_M_left
;
487 #if __cplusplus >= 201103L
488 _Reuse_or_alloc_node(const _Reuse_or_alloc_node
&) = delete;
491 ~_Reuse_or_alloc_node()
492 { _M_t
._M_erase(static_cast<_Link_type
>(_M_root
)); }
494 template<typename _Arg
>
496 #if __cplusplus < 201103L
497 operator()(const _Arg
& __arg
)
499 operator()(_Arg
&& __arg
)
502 _Link_type __node
= static_cast<_Link_type
>(_M_extract());
505 _M_t
._M_destroy_node(__node
);
506 _M_t
._M_construct_node(__node
, _GLIBCXX_FORWARD(_Arg
, __arg
));
510 return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
));
520 _Base_ptr __node
= _M_nodes
;
521 _M_nodes
= _M_nodes
->_M_parent
;
524 if (_M_nodes
->_M_right
== __node
)
526 _M_nodes
->_M_right
= 0;
528 if (_M_nodes
->_M_left
)
530 _M_nodes
= _M_nodes
->_M_left
;
532 while (_M_nodes
->_M_right
)
533 _M_nodes
= _M_nodes
->_M_right
;
535 if (_M_nodes
->_M_left
)
536 _M_nodes
= _M_nodes
->_M_left
;
539 else // __node is on the left.
540 _M_nodes
->_M_left
= 0;
553 // Functor similar to the previous one but without any pool of nodes to
557 _Alloc_node(_Rb_tree
& __t
)
560 template<typename _Arg
>
562 #if __cplusplus < 201103L
563 operator()(const _Arg
& __arg
) const
565 operator()(_Arg
&& __arg
) const
567 { return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
)); }
574 typedef _Key key_type
;
575 typedef _Val value_type
;
576 typedef value_type
* pointer
;
577 typedef const value_type
* const_pointer
;
578 typedef value_type
& reference
;
579 typedef const value_type
& const_reference
;
580 typedef size_t size_type
;
581 typedef ptrdiff_t difference_type
;
582 typedef _Alloc allocator_type
;
585 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
586 { return this->_M_impl
; }
588 const _Node_allocator
&
589 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
590 { return this->_M_impl
; }
593 get_allocator() const _GLIBCXX_NOEXCEPT
594 { return allocator_type(_M_get_Node_allocator()); }
599 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
602 _M_put_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
603 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p
, 1); }
605 #if __cplusplus < 201103L
607 _M_construct_node(_Link_type __node
, const value_type
& __x
)
610 { get_allocator().construct(__node
->_M_valptr(), __x
); }
614 __throw_exception_again
;
619 _M_create_node(const value_type
& __x
)
621 _Link_type __tmp
= _M_get_node();
622 _M_construct_node(__tmp
, __x
);
627 _M_destroy_node(_Link_type __p
)
628 { get_allocator().destroy(__p
->_M_valptr()); }
630 template<typename
... _Args
>
632 _M_construct_node(_Link_type __node
, _Args
&&... __args
)
636 ::new(__node
) _Rb_tree_node
<_Val
>;
637 _Alloc_traits::construct(_M_get_Node_allocator(),
639 std::forward
<_Args
>(__args
)...);
643 __node
->~_Rb_tree_node
<_Val
>();
645 __throw_exception_again
;
649 template<typename
... _Args
>
651 _M_create_node(_Args
&&... __args
)
653 _Link_type __tmp
= _M_get_node();
654 _M_construct_node(__tmp
, std::forward
<_Args
>(__args
)...);
659 _M_destroy_node(_Link_type __p
) noexcept
661 _Alloc_traits::destroy(_M_get_Node_allocator(), __p
->_M_valptr());
662 __p
->~_Rb_tree_node
<_Val
>();
667 _M_drop_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
669 _M_destroy_node(__p
);
673 template<typename _NodeGen
>
675 _M_clone_node(_Const_Link_type __x
, _NodeGen
& __node_gen
)
677 _Link_type __tmp
= __node_gen(*__x
->_M_valptr());
678 __tmp
->_M_color
= __x
->_M_color
;
685 #if _GLIBCXX_INLINE_VERSION
686 template<typename _Key_compare
>
688 // Unused _Is_pod_comparator is kept as it is part of mangled name.
689 template<typename _Key_compare
,
690 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare
)>
693 : public _Node_allocator
694 , public _Rb_tree_key_compare
<_Key_compare
>
695 , public _Rb_tree_header
697 typedef _Rb_tree_key_compare
<_Key_compare
> _Base_key_compare
;
700 _GLIBCXX_NOEXCEPT_IF(
701 is_nothrow_default_constructible
<_Node_allocator
>::value
702 && is_nothrow_default_constructible
<_Base_key_compare
>::value
)
706 _Rb_tree_impl(const _Rb_tree_impl
& __x
)
707 : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x
))
708 , _Base_key_compare(__x
._M_key_compare
)
711 #if __cplusplus < 201103L
712 _Rb_tree_impl(const _Key_compare
& __comp
, const _Node_allocator
& __a
)
713 : _Node_allocator(__a
), _Base_key_compare(__comp
)
716 _Rb_tree_impl(_Rb_tree_impl
&&) = default;
718 _Rb_tree_impl(const _Key_compare
& __comp
, _Node_allocator
&& __a
)
719 : _Node_allocator(std::move(__a
)), _Base_key_compare(__comp
)
724 _Rb_tree_impl
<_Compare
> _M_impl
;
728 _M_root() _GLIBCXX_NOEXCEPT
729 { return this->_M_impl
._M_header
._M_parent
; }
732 _M_root() const _GLIBCXX_NOEXCEPT
733 { return this->_M_impl
._M_header
._M_parent
; }
736 _M_leftmost() _GLIBCXX_NOEXCEPT
737 { return this->_M_impl
._M_header
._M_left
; }
740 _M_leftmost() const _GLIBCXX_NOEXCEPT
741 { return this->_M_impl
._M_header
._M_left
; }
744 _M_rightmost() _GLIBCXX_NOEXCEPT
745 { return this->_M_impl
._M_header
._M_right
; }
748 _M_rightmost() const _GLIBCXX_NOEXCEPT
749 { return this->_M_impl
._M_header
._M_right
; }
752 _M_begin() _GLIBCXX_NOEXCEPT
753 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
756 _M_begin() const _GLIBCXX_NOEXCEPT
758 return static_cast<_Const_Link_type
>
759 (this->_M_impl
._M_header
._M_parent
);
763 _M_end() _GLIBCXX_NOEXCEPT
764 { return &this->_M_impl
._M_header
; }
767 _M_end() const _GLIBCXX_NOEXCEPT
768 { return &this->_M_impl
._M_header
; }
770 static const_reference
771 _S_value(_Const_Link_type __x
)
772 { return *__x
->_M_valptr(); }
775 _S_key(_Const_Link_type __x
)
776 { return _KeyOfValue()(_S_value(__x
)); }
779 _S_left(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
780 { return static_cast<_Link_type
>(__x
->_M_left
); }
782 static _Const_Link_type
783 _S_left(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
784 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
787 _S_right(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
788 { return static_cast<_Link_type
>(__x
->_M_right
); }
790 static _Const_Link_type
791 _S_right(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
792 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
794 static const_reference
795 _S_value(_Const_Base_ptr __x
)
796 { return *static_cast<_Const_Link_type
>(__x
)->_M_valptr(); }
799 _S_key(_Const_Base_ptr __x
)
800 { return _KeyOfValue()(_S_value(__x
)); }
803 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
804 { return _Rb_tree_node_base::_S_minimum(__x
); }
806 static _Const_Base_ptr
807 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
808 { return _Rb_tree_node_base::_S_minimum(__x
); }
811 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
812 { return _Rb_tree_node_base::_S_maximum(__x
); }
814 static _Const_Base_ptr
815 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
816 { return _Rb_tree_node_base::_S_maximum(__x
); }
819 typedef _Rb_tree_iterator
<value_type
> iterator
;
820 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
822 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
823 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
825 #if __cplusplus > 201402L
826 using node_type
= _Node_handle
<_Key
, _Val
, _Node_allocator
>;
827 using insert_return_type
= _Node_insert_return
<
828 conditional_t
<is_same_v
<_Key
, _Val
>, const_iterator
, iterator
>,
832 pair
<_Base_ptr
, _Base_ptr
>
833 _M_get_insert_unique_pos(const key_type
& __k
);
835 pair
<_Base_ptr
, _Base_ptr
>
836 _M_get_insert_equal_pos(const key_type
& __k
);
838 pair
<_Base_ptr
, _Base_ptr
>
839 _M_get_insert_hint_unique_pos(const_iterator __pos
,
840 const key_type
& __k
);
842 pair
<_Base_ptr
, _Base_ptr
>
843 _M_get_insert_hint_equal_pos(const_iterator __pos
,
844 const key_type
& __k
);
847 #if __cplusplus >= 201103L
848 template<typename _Arg
, typename _NodeGen
>
850 _M_insert_(_Base_ptr __x
, _Base_ptr __y
, _Arg
&& __v
, _NodeGen
&);
853 _M_insert_node(_Base_ptr __x
, _Base_ptr __y
, _Link_type __z
);
855 template<typename _Arg
>
857 _M_insert_lower(_Base_ptr __y
, _Arg
&& __v
);
859 template<typename _Arg
>
861 _M_insert_equal_lower(_Arg
&& __x
);
864 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
);
867 _M_insert_equal_lower_node(_Link_type __z
);
869 template<typename _NodeGen
>
871 _M_insert_(_Base_ptr __x
, _Base_ptr __y
,
872 const value_type
& __v
, _NodeGen
&);
874 // _GLIBCXX_RESOLVE_LIB_DEFECTS
875 // 233. Insertion hints in associative containers.
877 _M_insert_lower(_Base_ptr __y
, const value_type
& __v
);
880 _M_insert_equal_lower(const value_type
& __x
);
883 template<typename _NodeGen
>
885 _M_copy(_Const_Link_type __x
, _Base_ptr __p
, _NodeGen
&);
887 template<typename _NodeGen
>
889 _M_copy(const _Rb_tree
& __x
, _NodeGen
& __gen
)
891 _Link_type __root
= _M_copy(__x
._M_begin(), _M_end(), __gen
);
892 _M_leftmost() = _S_minimum(__root
);
893 _M_rightmost() = _S_maximum(__root
);
894 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
899 _M_copy(const _Rb_tree
& __x
)
901 _Alloc_node
__an(*this);
902 return _M_copy(__x
, __an
);
906 _M_erase(_Link_type __x
);
909 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
913 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
914 const _Key
& __k
) const;
917 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
921 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
922 const _Key
& __k
) const;
925 // allocation/deallocation
926 #if __cplusplus < 201103L
929 _Rb_tree() = default;
932 _Rb_tree(const _Compare
& __comp
,
933 const allocator_type
& __a
= allocator_type())
934 : _M_impl(__comp
, _Node_allocator(__a
)) { }
936 _Rb_tree(const _Rb_tree
& __x
)
937 : _M_impl(__x
._M_impl
)
939 if (__x
._M_root() != 0)
940 _M_root() = _M_copy(__x
);
943 #if __cplusplus >= 201103L
944 _Rb_tree(const allocator_type
& __a
)
945 : _M_impl(_Compare(), _Node_allocator(__a
))
948 _Rb_tree(const _Rb_tree
& __x
, const allocator_type
& __a
)
949 : _M_impl(__x
._M_impl
._M_key_compare
, _Node_allocator(__a
))
951 if (__x
._M_root() != nullptr)
952 _M_root() = _M_copy(__x
);
955 _Rb_tree(_Rb_tree
&&) = default;
957 _Rb_tree(_Rb_tree
&& __x
, const allocator_type
& __a
)
958 : _Rb_tree(std::move(__x
), _Node_allocator(__a
))
961 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
);
964 ~_Rb_tree() _GLIBCXX_NOEXCEPT
965 { _M_erase(_M_begin()); }
968 operator=(const _Rb_tree
& __x
);
973 { return _M_impl
._M_key_compare
; }
976 begin() _GLIBCXX_NOEXCEPT
977 { return iterator(this->_M_impl
._M_header
._M_left
); }
980 begin() const _GLIBCXX_NOEXCEPT
981 { return const_iterator(this->_M_impl
._M_header
._M_left
); }
984 end() _GLIBCXX_NOEXCEPT
985 { return iterator(&this->_M_impl
._M_header
); }
988 end() const _GLIBCXX_NOEXCEPT
989 { return const_iterator(&this->_M_impl
._M_header
); }
992 rbegin() _GLIBCXX_NOEXCEPT
993 { return reverse_iterator(end()); }
995 const_reverse_iterator
996 rbegin() const _GLIBCXX_NOEXCEPT
997 { return const_reverse_iterator(end()); }
1000 rend() _GLIBCXX_NOEXCEPT
1001 { return reverse_iterator(begin()); }
1003 const_reverse_iterator
1004 rend() const _GLIBCXX_NOEXCEPT
1005 { return const_reverse_iterator(begin()); }
1008 empty() const _GLIBCXX_NOEXCEPT
1009 { return _M_impl
._M_node_count
== 0; }
1012 size() const _GLIBCXX_NOEXCEPT
1013 { return _M_impl
._M_node_count
; }
1016 max_size() const _GLIBCXX_NOEXCEPT
1017 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
1021 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
);
1024 #if __cplusplus >= 201103L
1025 template<typename _Arg
>
1026 pair
<iterator
, bool>
1027 _M_insert_unique(_Arg
&& __x
);
1029 template<typename _Arg
>
1031 _M_insert_equal(_Arg
&& __x
);
1033 template<typename _Arg
, typename _NodeGen
>
1035 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
1037 template<typename _Arg
>
1039 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
)
1041 _Alloc_node
__an(*this);
1042 return _M_insert_unique_(__pos
, std::forward
<_Arg
>(__x
), __an
);
1045 template<typename _Arg
, typename _NodeGen
>
1047 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
1049 template<typename _Arg
>
1051 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
)
1053 _Alloc_node
__an(*this);
1054 return _M_insert_equal_(__pos
, std::forward
<_Arg
>(__x
), __an
);
1057 template<typename
... _Args
>
1058 pair
<iterator
, bool>
1059 _M_emplace_unique(_Args
&&... __args
);
1061 template<typename
... _Args
>
1063 _M_emplace_equal(_Args
&&... __args
);
1065 template<typename
... _Args
>
1067 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
);
1069 template<typename
... _Args
>
1071 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
);
1073 pair
<iterator
, bool>
1074 _M_insert_unique(const value_type
& __x
);
1077 _M_insert_equal(const value_type
& __x
);
1079 template<typename _NodeGen
>
1081 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
,
1085 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
)
1087 _Alloc_node
__an(*this);
1088 return _M_insert_unique_(__pos
, __x
, __an
);
1091 template<typename _NodeGen
>
1093 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
,
1096 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
)
1098 _Alloc_node
__an(*this);
1099 return _M_insert_equal_(__pos
, __x
, __an
);
1103 template<typename _InputIterator
>
1105 _M_insert_unique(_InputIterator __first
, _InputIterator __last
);
1107 template<typename _InputIterator
>
1109 _M_insert_equal(_InputIterator __first
, _InputIterator __last
);
1113 _M_erase_aux(const_iterator __position
);
1116 _M_erase_aux(const_iterator __first
, const_iterator __last
);
1119 #if __cplusplus >= 201103L
1120 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1121 // DR 130. Associative erase should return an iterator.
1122 _GLIBCXX_ABI_TAG_CXX11
1124 erase(const_iterator __position
)
1126 __glibcxx_assert(__position
!= end());
1127 const_iterator __result
= __position
;
1129 _M_erase_aux(__position
);
1130 return __result
._M_const_cast();
1134 _GLIBCXX_ABI_TAG_CXX11
1136 erase(iterator __position
)
1138 __glibcxx_assert(__position
!= end());
1139 iterator __result
= __position
;
1141 _M_erase_aux(__position
);
1146 erase(iterator __position
)
1148 __glibcxx_assert(__position
!= end());
1149 _M_erase_aux(__position
);
1153 erase(const_iterator __position
)
1155 __glibcxx_assert(__position
!= end());
1156 _M_erase_aux(__position
);
1160 erase(const key_type
& __x
);
1162 #if __cplusplus >= 201103L
1163 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1164 // DR 130. Associative erase should return an iterator.
1165 _GLIBCXX_ABI_TAG_CXX11
1167 erase(const_iterator __first
, const_iterator __last
)
1169 _M_erase_aux(__first
, __last
);
1170 return __last
._M_const_cast();
1174 erase(iterator __first
, iterator __last
)
1175 { _M_erase_aux(__first
, __last
); }
1178 erase(const_iterator __first
, const_iterator __last
)
1179 { _M_erase_aux(__first
, __last
); }
1182 erase(const key_type
* __first
, const key_type
* __last
);
1185 clear() _GLIBCXX_NOEXCEPT
1187 _M_erase(_M_begin());
1193 find(const key_type
& __k
);
1196 find(const key_type
& __k
) const;
1199 count(const key_type
& __k
) const;
1202 lower_bound(const key_type
& __k
)
1203 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1206 lower_bound(const key_type
& __k
) const
1207 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1210 upper_bound(const key_type
& __k
)
1211 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1214 upper_bound(const key_type
& __k
) const
1215 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1217 pair
<iterator
, iterator
>
1218 equal_range(const key_type
& __k
);
1220 pair
<const_iterator
, const_iterator
>
1221 equal_range(const key_type
& __k
) const;
1223 #if __cplusplus > 201103L
1224 template<typename _Kt
,
1226 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1228 _M_find_tr(const _Kt
& __k
)
1230 const _Rb_tree
* __const_this
= this;
1231 return __const_this
->_M_find_tr(__k
)._M_const_cast();
1234 template<typename _Kt
,
1236 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1238 _M_find_tr(const _Kt
& __k
) const
1240 auto __j
= _M_lower_bound_tr(__k
);
1241 if (__j
!= end() && _M_impl
._M_key_compare(__k
, _S_key(__j
._M_node
)))
1246 template<typename _Kt
,
1248 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1250 _M_count_tr(const _Kt
& __k
) const
1252 auto __p
= _M_equal_range_tr(__k
);
1253 return std::distance(__p
.first
, __p
.second
);
1256 template<typename _Kt
,
1258 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1260 _M_lower_bound_tr(const _Kt
& __k
)
1262 const _Rb_tree
* __const_this
= this;
1263 return __const_this
->_M_lower_bound_tr(__k
)._M_const_cast();
1266 template<typename _Kt
,
1268 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1270 _M_lower_bound_tr(const _Kt
& __k
) const
1272 auto __x
= _M_begin();
1273 auto __y
= _M_end();
1275 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1281 __x
= _S_right(__x
);
1282 return const_iterator(__y
);
1285 template<typename _Kt
,
1287 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1289 _M_upper_bound_tr(const _Kt
& __k
)
1291 const _Rb_tree
* __const_this
= this;
1292 return __const_this
->_M_upper_bound_tr(__k
)._M_const_cast();
1295 template<typename _Kt
,
1297 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1299 _M_upper_bound_tr(const _Kt
& __k
) const
1301 auto __x
= _M_begin();
1302 auto __y
= _M_end();
1304 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1310 __x
= _S_right(__x
);
1311 return const_iterator(__y
);
1314 template<typename _Kt
,
1316 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1317 pair
<iterator
, iterator
>
1318 _M_equal_range_tr(const _Kt
& __k
)
1320 const _Rb_tree
* __const_this
= this;
1321 auto __ret
= __const_this
->_M_equal_range_tr(__k
);
1322 return { __ret
.first
._M_const_cast(), __ret
.second
._M_const_cast() };
1325 template<typename _Kt
,
1327 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1328 pair
<const_iterator
, const_iterator
>
1329 _M_equal_range_tr(const _Kt
& __k
) const
1331 auto __low
= _M_lower_bound_tr(__k
);
1332 auto __high
= __low
;
1333 auto& __cmp
= _M_impl
._M_key_compare
;
1334 while (__high
!= end() && !__cmp(__k
, _S_key(__high
._M_node
)))
1336 return { __low
, __high
};
1342 __rb_verify() const;
1344 #if __cplusplus >= 201103L
1346 operator=(_Rb_tree
&&)
1347 noexcept(_Alloc_traits::_S_nothrow_move()
1348 && is_nothrow_move_assignable
<_Compare
>::value
);
1350 template<typename _Iterator
>
1352 _M_assign_unique(_Iterator
, _Iterator
);
1354 template<typename _Iterator
>
1356 _M_assign_equal(_Iterator
, _Iterator
);
1359 // Move elements from container with equal allocator.
1361 _M_move_data(_Rb_tree
& __x
, std::true_type
)
1362 { _M_impl
._M_move_data(__x
._M_impl
); }
1364 // Move elements from container with possibly non-equal allocator,
1365 // which might result in a copy not a move.
1367 _M_move_data(_Rb_tree
&, std::false_type
);
1369 // Move assignment from container with equal allocator.
1371 _M_move_assign(_Rb_tree
&, std::true_type
);
1373 // Move assignment from container with possibly non-equal allocator,
1374 // which might result in a copy not a move.
1376 _M_move_assign(_Rb_tree
&, std::false_type
);
1379 #if __cplusplus > 201402L
1381 /// Re-insert an extracted node.
1383 _M_reinsert_node_unique(node_type
&& __nh
)
1385 insert_return_type __ret
;
1387 __ret
.position
= end();
1390 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1392 auto __res
= _M_get_insert_unique_pos(__nh
._M_key());
1396 = _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1397 __nh
._M_ptr
= nullptr;
1398 __ret
.inserted
= true;
1402 __ret
.node
= std::move(__nh
);
1403 __ret
.position
= iterator(__res
.first
);
1404 __ret
.inserted
= false;
1410 /// Re-insert an extracted node.
1412 _M_reinsert_node_equal(node_type
&& __nh
)
1419 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1420 auto __res
= _M_get_insert_equal_pos(__nh
._M_key());
1422 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1424 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1425 __nh
._M_ptr
= nullptr;
1430 /// Re-insert an extracted node.
1432 _M_reinsert_node_hint_unique(const_iterator __hint
, node_type
&& __nh
)
1439 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1440 auto __res
= _M_get_insert_hint_unique_pos(__hint
, __nh
._M_key());
1443 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1444 __nh
._M_ptr
= nullptr;
1447 __ret
= iterator(__res
.first
);
1452 /// Re-insert an extracted node.
1454 _M_reinsert_node_hint_equal(const_iterator __hint
, node_type
&& __nh
)
1461 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1462 auto __res
= _M_get_insert_hint_equal_pos(__hint
, __nh
._M_key());
1464 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1466 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1467 __nh
._M_ptr
= nullptr;
1474 extract(const_iterator __pos
)
1476 auto __ptr
= _Rb_tree_rebalance_for_erase(
1477 __pos
._M_const_cast()._M_node
, _M_impl
._M_header
);
1478 --_M_impl
._M_node_count
;
1479 return { static_cast<_Link_type
>(__ptr
), _M_get_Node_allocator() };
1484 extract(const key_type
& __k
)
1487 auto __pos
= find(__k
);
1489 __nh
= extract(const_iterator(__pos
));
1493 template<typename _Compare2
>
1494 using _Compatible_tree
1495 = _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare2
, _Alloc
>;
1497 template<typename
, typename
>
1498 friend class _Rb_tree_merge_helper
;
1500 /// Merge from a compatible container into one with unique keys.
1501 template<typename _Compare2
>
1503 _M_merge_unique(_Compatible_tree
<_Compare2
>& __src
) noexcept
1505 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1506 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1509 auto __res
= _M_get_insert_unique_pos(_KeyOfValue()(*__pos
));
1512 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1513 auto __ptr
= _Rb_tree_rebalance_for_erase(
1514 __pos
._M_node
, __src_impl
._M_header
);
1515 --__src_impl
._M_node_count
;
1516 _M_insert_node(__res
.first
, __res
.second
,
1517 static_cast<_Link_type
>(__ptr
));
1522 /// Merge from a compatible container into one with equivalent keys.
1523 template<typename _Compare2
>
1525 _M_merge_equal(_Compatible_tree
<_Compare2
>& __src
) noexcept
1527 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1528 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1531 auto __res
= _M_get_insert_equal_pos(_KeyOfValue()(*__pos
));
1534 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1535 auto __ptr
= _Rb_tree_rebalance_for_erase(
1536 __pos
._M_node
, __src_impl
._M_header
);
1537 --__src_impl
._M_node_count
;
1538 _M_insert_node(__res
.first
, __res
.second
,
1539 static_cast<_Link_type
>(__ptr
));
1546 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1547 typename _Compare
, typename _Alloc
>
1549 operator==(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1550 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1552 return __x
.size() == __y
.size()
1553 && std::equal(__x
.begin(), __x
.end(), __y
.begin());
1556 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1557 typename _Compare
, typename _Alloc
>
1559 operator<(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1560 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1562 return std::lexicographical_compare(__x
.begin(), __x
.end(),
1563 __y
.begin(), __y
.end());
1566 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1567 typename _Compare
, typename _Alloc
>
1569 operator!=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1570 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1571 { return !(__x
== __y
); }
1573 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1574 typename _Compare
, typename _Alloc
>
1576 operator>(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1577 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1578 { return __y
< __x
; }
1580 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1581 typename _Compare
, typename _Alloc
>
1583 operator<=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1584 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1585 { return !(__y
< __x
); }
1587 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1588 typename _Compare
, typename _Alloc
>
1590 operator>=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1591 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1592 { return !(__x
< __y
); }
1594 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1595 typename _Compare
, typename _Alloc
>
1597 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1598 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1601 #if __cplusplus >= 201103L
1602 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1603 typename _Compare
, typename _Alloc
>
1604 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1605 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
)
1606 : _M_impl(__x
._M_impl
._M_key_compare
, std::move(__a
))
1608 using __eq
= typename
_Alloc_traits::is_always_equal
;
1609 if (__x
._M_root() != nullptr)
1610 _M_move_data(__x
, __eq());
1613 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1614 typename _Compare
, typename _Alloc
>
1616 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1617 _M_move_data(_Rb_tree
& __x
, std::false_type
)
1619 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1620 _M_move_data(__x
, std::true_type());
1623 _Alloc_node
__an(*this);
1625 [&__an
](const value_type
& __cval
)
1627 auto& __val
= const_cast<value_type
&>(__cval
);
1628 return __an(std::move_if_noexcept(__val
));
1630 _M_root() = _M_copy(__x
, __lbd
);
1634 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1635 typename _Compare
, typename _Alloc
>
1637 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1638 _M_move_assign(_Rb_tree
& __x
, true_type
)
1641 if (__x
._M_root() != nullptr)
1642 _M_move_data(__x
, std::true_type());
1643 std::__alloc_on_move(_M_get_Node_allocator(),
1644 __x
._M_get_Node_allocator());
1647 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1648 typename _Compare
, typename _Alloc
>
1650 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1651 _M_move_assign(_Rb_tree
& __x
, false_type
)
1653 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1654 return _M_move_assign(__x
, true_type
{});
1656 // Try to move each node reusing existing nodes and copying __x nodes
1658 _Reuse_or_alloc_node
__roan(*this);
1660 if (__x
._M_root() != nullptr)
1663 [&__roan
](const value_type
& __cval
)
1665 auto& __val
= const_cast<value_type
&>(__cval
);
1666 return __roan(std::move_if_noexcept(__val
));
1668 _M_root() = _M_copy(__x
, __lbd
);
1673 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1674 typename _Compare
, typename _Alloc
>
1675 inline _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1676 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1677 operator=(_Rb_tree
&& __x
)
1678 noexcept(_Alloc_traits::_S_nothrow_move()
1679 && is_nothrow_move_assignable
<_Compare
>::value
)
1681 _M_impl
._M_key_compare
= std::move(__x
._M_impl
._M_key_compare
);
1682 _M_move_assign(__x
, __bool_constant
<_Alloc_traits::_S_nothrow_move()>());
1686 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1687 typename _Compare
, typename _Alloc
>
1688 template<typename _Iterator
>
1690 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1691 _M_assign_unique(_Iterator __first
, _Iterator __last
)
1693 _Reuse_or_alloc_node
__roan(*this);
1695 for (; __first
!= __last
; ++__first
)
1696 _M_insert_unique_(end(), *__first
, __roan
);
1699 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1700 typename _Compare
, typename _Alloc
>
1701 template<typename _Iterator
>
1703 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1704 _M_assign_equal(_Iterator __first
, _Iterator __last
)
1706 _Reuse_or_alloc_node
__roan(*this);
1708 for (; __first
!= __last
; ++__first
)
1709 _M_insert_equal_(end(), *__first
, __roan
);
1713 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1714 typename _Compare
, typename _Alloc
>
1715 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1716 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1717 operator=(const _Rb_tree
& __x
)
1721 // Note that _Key may be a constant type.
1722 #if __cplusplus >= 201103L
1723 if (_Alloc_traits::_S_propagate_on_copy_assign())
1725 auto& __this_alloc
= this->_M_get_Node_allocator();
1726 auto& __that_alloc
= __x
._M_get_Node_allocator();
1727 if (!_Alloc_traits::_S_always_equal()
1728 && __this_alloc
!= __that_alloc
)
1730 // Replacement allocator cannot free existing storage, we need
1731 // to erase nodes first.
1733 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1738 _Reuse_or_alloc_node
__roan(*this);
1740 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
1741 if (__x
._M_root() != 0)
1742 _M_root() = _M_copy(__x
, __roan
);
1748 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1749 typename _Compare
, typename _Alloc
>
1750 #if __cplusplus >= 201103L
1751 template<typename _Arg
, typename _NodeGen
>
1753 template<typename _NodeGen
>
1755 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1756 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1757 _M_insert_(_Base_ptr __x
, _Base_ptr __p
,
1758 #if __cplusplus >= 201103L
1763 _NodeGen
& __node_gen
)
1765 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
1766 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
1769 _Link_type __z
= __node_gen(_GLIBCXX_FORWARD(_Arg
, __v
));
1771 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1772 this->_M_impl
._M_header
);
1773 ++_M_impl
._M_node_count
;
1774 return iterator(__z
);
1777 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1778 typename _Compare
, typename _Alloc
>
1779 #if __cplusplus >= 201103L
1780 template<typename _Arg
>
1782 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1783 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1784 #if __cplusplus >= 201103L
1785 _M_insert_lower(_Base_ptr __p
, _Arg
&& __v
)
1787 _M_insert_lower(_Base_ptr __p
, const _Val
& __v
)
1790 bool __insert_left
= (__p
== _M_end()
1791 || !_M_impl
._M_key_compare(_S_key(__p
),
1792 _KeyOfValue()(__v
)));
1794 _Link_type __z
= _M_create_node(_GLIBCXX_FORWARD(_Arg
, __v
));
1796 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1797 this->_M_impl
._M_header
);
1798 ++_M_impl
._M_node_count
;
1799 return iterator(__z
);
1802 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1803 typename _Compare
, typename _Alloc
>
1804 #if __cplusplus >= 201103L
1805 template<typename _Arg
>
1807 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1808 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1809 #if __cplusplus >= 201103L
1810 _M_insert_equal_lower(_Arg
&& __v
)
1812 _M_insert_equal_lower(const _Val
& __v
)
1815 _Link_type __x
= _M_begin();
1816 _Base_ptr __y
= _M_end();
1820 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _KeyOfValue()(__v
)) ?
1821 _S_left(__x
) : _S_right(__x
);
1823 return _M_insert_lower(__y
, _GLIBCXX_FORWARD(_Arg
, __v
));
1826 template<typename _Key
, typename _Val
, typename _KoV
,
1827 typename _Compare
, typename _Alloc
>
1828 template<typename _NodeGen
>
1829 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1830 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
1831 _M_copy(_Const_Link_type __x
, _Base_ptr __p
, _NodeGen
& __node_gen
)
1833 // Structural copy. __x and __p must be non-null.
1834 _Link_type __top
= _M_clone_node(__x
, __node_gen
);
1835 __top
->_M_parent
= __p
;
1840 __top
->_M_right
= _M_copy(_S_right(__x
), __top
, __node_gen
);
1846 _Link_type __y
= _M_clone_node(__x
, __node_gen
);
1848 __y
->_M_parent
= __p
;
1850 __y
->_M_right
= _M_copy(_S_right(__x
), __y
, __node_gen
);
1858 __throw_exception_again
;
1863 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1864 typename _Compare
, typename _Alloc
>
1866 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1867 _M_erase(_Link_type __x
)
1869 // Erase without rebalancing.
1872 _M_erase(_S_right(__x
));
1873 _Link_type __y
= _S_left(__x
);
1879 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1880 typename _Compare
, typename _Alloc
>
1881 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1882 _Compare
, _Alloc
>::iterator
1883 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1884 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
1888 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1889 __y
= __x
, __x
= _S_left(__x
);
1891 __x
= _S_right(__x
);
1892 return iterator(__y
);
1895 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1896 typename _Compare
, typename _Alloc
>
1897 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1898 _Compare
, _Alloc
>::const_iterator
1899 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1900 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1901 const _Key
& __k
) const
1904 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1905 __y
= __x
, __x
= _S_left(__x
);
1907 __x
= _S_right(__x
);
1908 return const_iterator(__y
);
1911 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1912 typename _Compare
, typename _Alloc
>
1913 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1914 _Compare
, _Alloc
>::iterator
1915 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1916 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
1920 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1921 __y
= __x
, __x
= _S_left(__x
);
1923 __x
= _S_right(__x
);
1924 return iterator(__y
);
1927 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1928 typename _Compare
, typename _Alloc
>
1929 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1930 _Compare
, _Alloc
>::const_iterator
1931 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1932 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1933 const _Key
& __k
) const
1936 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1937 __y
= __x
, __x
= _S_left(__x
);
1939 __x
= _S_right(__x
);
1940 return const_iterator(__y
);
1943 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1944 typename _Compare
, typename _Alloc
>
1945 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1946 _Compare
, _Alloc
>::iterator
,
1947 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1948 _Compare
, _Alloc
>::iterator
>
1949 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1950 equal_range(const _Key
& __k
)
1952 _Link_type __x
= _M_begin();
1953 _Base_ptr __y
= _M_end();
1956 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1957 __x
= _S_right(__x
);
1958 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1959 __y
= __x
, __x
= _S_left(__x
);
1962 _Link_type
__xu(__x
);
1963 _Base_ptr
__yu(__y
);
1964 __y
= __x
, __x
= _S_left(__x
);
1965 __xu
= _S_right(__xu
);
1966 return pair
<iterator
,
1967 iterator
>(_M_lower_bound(__x
, __y
, __k
),
1968 _M_upper_bound(__xu
, __yu
, __k
));
1971 return pair
<iterator
, iterator
>(iterator(__y
),
1975 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1976 typename _Compare
, typename _Alloc
>
1977 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1978 _Compare
, _Alloc
>::const_iterator
,
1979 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1980 _Compare
, _Alloc
>::const_iterator
>
1981 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1982 equal_range(const _Key
& __k
) const
1984 _Const_Link_type __x
= _M_begin();
1985 _Const_Base_ptr __y
= _M_end();
1988 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1989 __x
= _S_right(__x
);
1990 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1991 __y
= __x
, __x
= _S_left(__x
);
1994 _Const_Link_type
__xu(__x
);
1995 _Const_Base_ptr
__yu(__y
);
1996 __y
= __x
, __x
= _S_left(__x
);
1997 __xu
= _S_right(__xu
);
1998 return pair
<const_iterator
,
1999 const_iterator
>(_M_lower_bound(__x
, __y
, __k
),
2000 _M_upper_bound(__xu
, __yu
, __k
));
2003 return pair
<const_iterator
, const_iterator
>(const_iterator(__y
),
2004 const_iterator(__y
));
2007 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2008 typename _Compare
, typename _Alloc
>
2010 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2012 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
)
2016 if (__t
._M_root() != 0)
2017 _M_impl
._M_move_data(__t
._M_impl
);
2019 else if (__t
._M_root() == 0)
2020 __t
._M_impl
._M_move_data(_M_impl
);
2023 std::swap(_M_root(),__t
._M_root());
2024 std::swap(_M_leftmost(),__t
._M_leftmost());
2025 std::swap(_M_rightmost(),__t
._M_rightmost());
2027 _M_root()->_M_parent
= _M_end();
2028 __t
._M_root()->_M_parent
= __t
._M_end();
2029 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
2031 // No need to swap header's color as it does not change.
2032 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
2034 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2035 __t
._M_get_Node_allocator());
2038 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2039 typename _Compare
, typename _Alloc
>
2040 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2041 _Compare
, _Alloc
>::_Base_ptr
,
2042 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2043 _Compare
, _Alloc
>::_Base_ptr
>
2044 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2045 _M_get_insert_unique_pos(const key_type
& __k
)
2047 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2048 _Link_type __x
= _M_begin();
2049 _Base_ptr __y
= _M_end();
2054 __comp
= _M_impl
._M_key_compare(__k
, _S_key(__x
));
2055 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
2057 iterator __j
= iterator(__y
);
2061 return _Res(__x
, __y
);
2065 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), __k
))
2066 return _Res(__x
, __y
);
2067 return _Res(__j
._M_node
, 0);
2070 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2071 typename _Compare
, typename _Alloc
>
2072 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2073 _Compare
, _Alloc
>::_Base_ptr
,
2074 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2075 _Compare
, _Alloc
>::_Base_ptr
>
2076 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2077 _M_get_insert_equal_pos(const key_type
& __k
)
2079 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2080 _Link_type __x
= _M_begin();
2081 _Base_ptr __y
= _M_end();
2085 __x
= _M_impl
._M_key_compare(__k
, _S_key(__x
)) ?
2086 _S_left(__x
) : _S_right(__x
);
2088 return _Res(__x
, __y
);
2091 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2092 typename _Compare
, typename _Alloc
>
2093 #if __cplusplus >= 201103L
2094 template<typename _Arg
>
2096 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2097 _Compare
, _Alloc
>::iterator
, bool>
2098 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2099 #if __cplusplus >= 201103L
2100 _M_insert_unique(_Arg
&& __v
)
2102 _M_insert_unique(const _Val
& __v
)
2105 typedef pair
<iterator
, bool> _Res
;
2106 pair
<_Base_ptr
, _Base_ptr
> __res
2107 = _M_get_insert_unique_pos(_KeyOfValue()(__v
));
2111 _Alloc_node
__an(*this);
2112 return _Res(_M_insert_(__res
.first
, __res
.second
,
2113 _GLIBCXX_FORWARD(_Arg
, __v
), __an
),
2117 return _Res(iterator(__res
.first
), false);
2120 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2121 typename _Compare
, typename _Alloc
>
2122 #if __cplusplus >= 201103L
2123 template<typename _Arg
>
2125 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2126 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2127 #if __cplusplus >= 201103L
2128 _M_insert_equal(_Arg
&& __v
)
2130 _M_insert_equal(const _Val
& __v
)
2133 pair
<_Base_ptr
, _Base_ptr
> __res
2134 = _M_get_insert_equal_pos(_KeyOfValue()(__v
));
2135 _Alloc_node
__an(*this);
2136 return _M_insert_(__res
.first
, __res
.second
,
2137 _GLIBCXX_FORWARD(_Arg
, __v
), __an
);
2140 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2141 typename _Compare
, typename _Alloc
>
2142 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2143 _Compare
, _Alloc
>::_Base_ptr
,
2144 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2145 _Compare
, _Alloc
>::_Base_ptr
>
2146 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2147 _M_get_insert_hint_unique_pos(const_iterator __position
,
2148 const key_type
& __k
)
2150 iterator __pos
= __position
._M_const_cast();
2151 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2154 if (__pos
._M_node
== _M_end())
2157 && _M_impl
._M_key_compare(_S_key(_M_rightmost()), __k
))
2158 return _Res(0, _M_rightmost());
2160 return _M_get_insert_unique_pos(__k
);
2162 else if (_M_impl
._M_key_compare(__k
, _S_key(__pos
._M_node
)))
2164 // First, try before...
2165 iterator __before
= __pos
;
2166 if (__pos
._M_node
== _M_leftmost()) // begin()
2167 return _Res(_M_leftmost(), _M_leftmost());
2168 else if (_M_impl
._M_key_compare(_S_key((--__before
)._M_node
), __k
))
2170 if (_S_right(__before
._M_node
) == 0)
2171 return _Res(0, __before
._M_node
);
2173 return _Res(__pos
._M_node
, __pos
._M_node
);
2176 return _M_get_insert_unique_pos(__k
);
2178 else if (_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2180 // ... then try after.
2181 iterator __after
= __pos
;
2182 if (__pos
._M_node
== _M_rightmost())
2183 return _Res(0, _M_rightmost());
2184 else if (_M_impl
._M_key_compare(__k
, _S_key((++__after
)._M_node
)))
2186 if (_S_right(__pos
._M_node
) == 0)
2187 return _Res(0, __pos
._M_node
);
2189 return _Res(__after
._M_node
, __after
._M_node
);
2192 return _M_get_insert_unique_pos(__k
);
2196 return _Res(__pos
._M_node
, 0);
2199 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2200 typename _Compare
, typename _Alloc
>
2201 #if __cplusplus >= 201103L
2202 template<typename _Arg
, typename _NodeGen
>
2204 template<typename _NodeGen
>
2206 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2207 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2208 _M_insert_unique_(const_iterator __position
,
2209 #if __cplusplus >= 201103L
2214 _NodeGen
& __node_gen
)
2216 pair
<_Base_ptr
, _Base_ptr
> __res
2217 = _M_get_insert_hint_unique_pos(__position
, _KeyOfValue()(__v
));
2220 return _M_insert_(__res
.first
, __res
.second
,
2221 _GLIBCXX_FORWARD(_Arg
, __v
),
2223 return iterator(__res
.first
);
2226 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2227 typename _Compare
, typename _Alloc
>
2228 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2229 _Compare
, _Alloc
>::_Base_ptr
,
2230 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2231 _Compare
, _Alloc
>::_Base_ptr
>
2232 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2233 _M_get_insert_hint_equal_pos(const_iterator __position
, const key_type
& __k
)
2235 iterator __pos
= __position
._M_const_cast();
2236 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2239 if (__pos
._M_node
== _M_end())
2242 && !_M_impl
._M_key_compare(__k
, _S_key(_M_rightmost())))
2243 return _Res(0, _M_rightmost());
2245 return _M_get_insert_equal_pos(__k
);
2247 else if (!_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2249 // First, try before...
2250 iterator __before
= __pos
;
2251 if (__pos
._M_node
== _M_leftmost()) // begin()
2252 return _Res(_M_leftmost(), _M_leftmost());
2253 else if (!_M_impl
._M_key_compare(__k
, _S_key((--__before
)._M_node
)))
2255 if (_S_right(__before
._M_node
) == 0)
2256 return _Res(0, __before
._M_node
);
2258 return _Res(__pos
._M_node
, __pos
._M_node
);
2261 return _M_get_insert_equal_pos(__k
);
2265 // ... then try after.
2266 iterator __after
= __pos
;
2267 if (__pos
._M_node
== _M_rightmost())
2268 return _Res(0, _M_rightmost());
2269 else if (!_M_impl
._M_key_compare(_S_key((++__after
)._M_node
), __k
))
2271 if (_S_right(__pos
._M_node
) == 0)
2272 return _Res(0, __pos
._M_node
);
2274 return _Res(__after
._M_node
, __after
._M_node
);
2281 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2282 typename _Compare
, typename _Alloc
>
2283 #if __cplusplus >= 201103L
2284 template<typename _Arg
, typename _NodeGen
>
2286 template<typename _NodeGen
>
2288 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2289 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2290 _M_insert_equal_(const_iterator __position
,
2291 #if __cplusplus >= 201103L
2296 _NodeGen
& __node_gen
)
2298 pair
<_Base_ptr
, _Base_ptr
> __res
2299 = _M_get_insert_hint_equal_pos(__position
, _KeyOfValue()(__v
));
2302 return _M_insert_(__res
.first
, __res
.second
,
2303 _GLIBCXX_FORWARD(_Arg
, __v
),
2306 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg
, __v
));
2309 #if __cplusplus >= 201103L
2310 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2311 typename _Compare
, typename _Alloc
>
2312 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2313 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2314 _M_insert_node(_Base_ptr __x
, _Base_ptr __p
, _Link_type __z
)
2316 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
2317 || _M_impl
._M_key_compare(_S_key(__z
),
2320 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2321 this->_M_impl
._M_header
);
2322 ++_M_impl
._M_node_count
;
2323 return iterator(__z
);
2326 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2327 typename _Compare
, typename _Alloc
>
2328 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2329 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2330 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
)
2332 bool __insert_left
= (__p
== _M_end()
2333 || !_M_impl
._M_key_compare(_S_key(__p
),
2336 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2337 this->_M_impl
._M_header
);
2338 ++_M_impl
._M_node_count
;
2339 return iterator(__z
);
2342 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2343 typename _Compare
, typename _Alloc
>
2344 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2345 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2346 _M_insert_equal_lower_node(_Link_type __z
)
2348 _Link_type __x
= _M_begin();
2349 _Base_ptr __y
= _M_end();
2353 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _S_key(__z
)) ?
2354 _S_left(__x
) : _S_right(__x
);
2356 return _M_insert_lower_node(__y
, __z
);
2359 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2360 typename _Compare
, typename _Alloc
>
2361 template<typename
... _Args
>
2362 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2363 _Compare
, _Alloc
>::iterator
, bool>
2364 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2365 _M_emplace_unique(_Args
&&... __args
)
2367 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2371 typedef pair
<iterator
, bool> _Res
;
2372 auto __res
= _M_get_insert_unique_pos(_S_key(__z
));
2374 return _Res(_M_insert_node(__res
.first
, __res
.second
, __z
), true);
2377 return _Res(iterator(__res
.first
), false);
2382 __throw_exception_again
;
2386 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2387 typename _Compare
, typename _Alloc
>
2388 template<typename
... _Args
>
2389 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2390 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2391 _M_emplace_equal(_Args
&&... __args
)
2393 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2397 auto __res
= _M_get_insert_equal_pos(_S_key(__z
));
2398 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2403 __throw_exception_again
;
2407 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2408 typename _Compare
, typename _Alloc
>
2409 template<typename
... _Args
>
2410 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2411 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2412 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
)
2414 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2418 auto __res
= _M_get_insert_hint_unique_pos(__pos
, _S_key(__z
));
2421 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2424 return iterator(__res
.first
);
2429 __throw_exception_again
;
2433 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2434 typename _Compare
, typename _Alloc
>
2435 template<typename
... _Args
>
2436 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2437 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2438 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
)
2440 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2444 auto __res
= _M_get_insert_hint_equal_pos(__pos
, _S_key(__z
));
2447 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2449 return _M_insert_equal_lower_node(__z
);
2454 __throw_exception_again
;
2459 template<typename _Key
, typename _Val
, typename _KoV
,
2460 typename _Cmp
, typename _Alloc
>
2463 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
2464 _M_insert_unique(_II __first
, _II __last
)
2466 _Alloc_node
__an(*this);
2467 for (; __first
!= __last
; ++__first
)
2468 _M_insert_unique_(end(), *__first
, __an
);
2471 template<typename _Key
, typename _Val
, typename _KoV
,
2472 typename _Cmp
, typename _Alloc
>
2475 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
2476 _M_insert_equal(_II __first
, _II __last
)
2478 _Alloc_node
__an(*this);
2479 for (; __first
!= __last
; ++__first
)
2480 _M_insert_equal_(end(), *__first
, __an
);
2483 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2484 typename _Compare
, typename _Alloc
>
2486 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2487 _M_erase_aux(const_iterator __position
)
2490 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
2491 (const_cast<_Base_ptr
>(__position
._M_node
),
2492 this->_M_impl
._M_header
));
2494 --_M_impl
._M_node_count
;
2497 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2498 typename _Compare
, typename _Alloc
>
2500 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2501 _M_erase_aux(const_iterator __first
, const_iterator __last
)
2503 if (__first
== begin() && __last
== end())
2506 while (__first
!= __last
)
2507 _M_erase_aux(__first
++);
2510 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2511 typename _Compare
, typename _Alloc
>
2512 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2513 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2514 erase(const _Key
& __x
)
2516 pair
<iterator
, iterator
> __p
= equal_range(__x
);
2517 const size_type __old_size
= size();
2518 _M_erase_aux(__p
.first
, __p
.second
);
2519 return __old_size
- size();
2522 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2523 typename _Compare
, typename _Alloc
>
2525 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2526 erase(const _Key
* __first
, const _Key
* __last
)
2528 while (__first
!= __last
)
2532 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2533 typename _Compare
, typename _Alloc
>
2534 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2535 _Compare
, _Alloc
>::iterator
2536 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2537 find(const _Key
& __k
)
2539 iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2540 return (__j
== end()
2541 || _M_impl
._M_key_compare(__k
,
2542 _S_key(__j
._M_node
))) ? end() : __j
;
2545 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2546 typename _Compare
, typename _Alloc
>
2547 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2548 _Compare
, _Alloc
>::const_iterator
2549 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2550 find(const _Key
& __k
) const
2552 const_iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2553 return (__j
== end()
2554 || _M_impl
._M_key_compare(__k
,
2555 _S_key(__j
._M_node
))) ? end() : __j
;
2558 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2559 typename _Compare
, typename _Alloc
>
2560 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2561 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2562 count(const _Key
& __k
) const
2564 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
2565 const size_type __n
= std::distance(__p
.first
, __p
.second
);
2569 _GLIBCXX_PURE
unsigned int
2570 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
2571 const _Rb_tree_node_base
* __root
) throw ();
2573 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2574 typename _Compare
, typename _Alloc
>
2576 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
2578 if (_M_impl
._M_node_count
== 0 || begin() == end())
2579 return _M_impl
._M_node_count
== 0 && begin() == end()
2580 && this->_M_impl
._M_header
._M_left
== _M_end()
2581 && this->_M_impl
._M_header
._M_right
== _M_end();
2583 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
2584 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
2586 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
2587 _Const_Link_type __L
= _S_left(__x
);
2588 _Const_Link_type __R
= _S_right(__x
);
2590 if (__x
->_M_color
== _S_red
)
2591 if ((__L
&& __L
->_M_color
== _S_red
)
2592 || (__R
&& __R
->_M_color
== _S_red
))
2595 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
2597 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
2600 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
2604 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2606 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2611 #if __cplusplus > 201402L
2612 // Allow access to internals of compatible _Rb_tree specializations.
2613 template<typename _Key
, typename _Val
, typename _Sel
, typename _Cmp1
,
2614 typename _Alloc
, typename _Cmp2
>
2615 struct _Rb_tree_merge_helper
<_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>,
2619 friend class _Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>;
2622 _S_get_impl(_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp2
, _Alloc
>& __tree
)
2623 { return __tree
._M_impl
; }
2627 _GLIBCXX_END_NAMESPACE_VERSION