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 >= 201402L
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
; };
436 template<typename _Cmp
, typename _SfinaeType
>
437 using __has_is_transparent_t
438 = typename __has_is_transparent
<_Cmp
, _SfinaeType
>::type
;
441 #if __cplusplus > 201402L
442 template<typename _Tree1
, typename _Cmp2
>
443 struct _Rb_tree_merge_helper
{ };
446 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
447 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
450 typedef typename
__gnu_cxx::__alloc_traits
<_Alloc
>::template
451 rebind
<_Rb_tree_node
<_Val
> >::other _Node_allocator
;
453 typedef __gnu_cxx::__alloc_traits
<_Node_allocator
> _Alloc_traits
;
455 #if __cplusplus >= 201103L
456 static_assert(__is_invocable
<_Compare
&, const _Key
&, const _Key
&>{},
457 "comparison object must be invocable with two arguments of key type");
458 # if __cplusplus >= 201703L
459 // _GLIBCXX_RESOLVE_LIB_DEFECTS
460 // 2542. Missing const requirements for associative containers
461 static_assert(is_invocable_v
<const _Compare
&, const _Key
&, const _Key
&>,
462 "comparison object must be invocable as const");
467 typedef _Rb_tree_node_base
* _Base_ptr
;
468 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
469 typedef _Rb_tree_node
<_Val
>* _Link_type
;
470 typedef const _Rb_tree_node
<_Val
>* _Const_Link_type
;
473 // Functor recycling a pool of nodes and using allocation once the pool
475 struct _Reuse_or_alloc_node
477 _Reuse_or_alloc_node(_Rb_tree
& __t
)
478 : _M_root(__t
._M_root()), _M_nodes(__t
._M_rightmost()), _M_t(__t
)
482 _M_root
->_M_parent
= 0;
484 if (_M_nodes
->_M_left
)
485 _M_nodes
= _M_nodes
->_M_left
;
491 #if __cplusplus >= 201103L
492 _Reuse_or_alloc_node(const _Reuse_or_alloc_node
&) = delete;
495 ~_Reuse_or_alloc_node()
496 { _M_t
._M_erase(static_cast<_Link_type
>(_M_root
)); }
498 template<typename _Arg
>
500 #if __cplusplus < 201103L
501 operator()(const _Arg
& __arg
)
503 operator()(_Arg
&& __arg
)
506 _Link_type __node
= static_cast<_Link_type
>(_M_extract());
509 _M_t
._M_destroy_node(__node
);
510 _M_t
._M_construct_node(__node
, _GLIBCXX_FORWARD(_Arg
, __arg
));
514 return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
));
524 _Base_ptr __node
= _M_nodes
;
525 _M_nodes
= _M_nodes
->_M_parent
;
528 if (_M_nodes
->_M_right
== __node
)
530 _M_nodes
->_M_right
= 0;
532 if (_M_nodes
->_M_left
)
534 _M_nodes
= _M_nodes
->_M_left
;
536 while (_M_nodes
->_M_right
)
537 _M_nodes
= _M_nodes
->_M_right
;
539 if (_M_nodes
->_M_left
)
540 _M_nodes
= _M_nodes
->_M_left
;
543 else // __node is on the left.
544 _M_nodes
->_M_left
= 0;
557 // Functor similar to the previous one but without any pool of nodes to
561 _Alloc_node(_Rb_tree
& __t
)
564 template<typename _Arg
>
566 #if __cplusplus < 201103L
567 operator()(const _Arg
& __arg
) const
569 operator()(_Arg
&& __arg
) const
571 { return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
)); }
578 typedef _Key key_type
;
579 typedef _Val value_type
;
580 typedef value_type
* pointer
;
581 typedef const value_type
* const_pointer
;
582 typedef value_type
& reference
;
583 typedef const value_type
& const_reference
;
584 typedef size_t size_type
;
585 typedef ptrdiff_t difference_type
;
586 typedef _Alloc allocator_type
;
589 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
590 { return this->_M_impl
; }
592 const _Node_allocator
&
593 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
594 { return this->_M_impl
; }
597 get_allocator() const _GLIBCXX_NOEXCEPT
598 { return allocator_type(_M_get_Node_allocator()); }
603 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
606 _M_put_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
607 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p
, 1); }
609 #if __cplusplus < 201103L
611 _M_construct_node(_Link_type __node
, const value_type
& __x
)
614 { get_allocator().construct(__node
->_M_valptr(), __x
); }
618 __throw_exception_again
;
623 _M_create_node(const value_type
& __x
)
625 _Link_type __tmp
= _M_get_node();
626 _M_construct_node(__tmp
, __x
);
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
)...);
660 _M_destroy_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
662 #if __cplusplus < 201103L
663 get_allocator().destroy(__p
->_M_valptr());
665 _Alloc_traits::destroy(_M_get_Node_allocator(), __p
->_M_valptr());
666 __p
->~_Rb_tree_node
<_Val
>();
671 _M_drop_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
673 _M_destroy_node(__p
);
677 template<typename _NodeGen
>
679 _M_clone_node(_Const_Link_type __x
, _NodeGen
& __node_gen
)
681 _Link_type __tmp
= __node_gen(*__x
->_M_valptr());
682 __tmp
->_M_color
= __x
->_M_color
;
689 #if _GLIBCXX_INLINE_VERSION
690 template<typename _Key_compare
>
692 // Unused _Is_pod_comparator is kept as it is part of mangled name.
693 template<typename _Key_compare
,
694 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare
)>
697 : public _Node_allocator
698 , public _Rb_tree_key_compare
<_Key_compare
>
699 , public _Rb_tree_header
701 typedef _Rb_tree_key_compare
<_Key_compare
> _Base_key_compare
;
704 _GLIBCXX_NOEXCEPT_IF(
705 is_nothrow_default_constructible
<_Node_allocator
>::value
706 && is_nothrow_default_constructible
<_Base_key_compare
>::value
)
710 _Rb_tree_impl(const _Rb_tree_impl
& __x
)
711 : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x
))
712 , _Base_key_compare(__x
._M_key_compare
)
715 #if __cplusplus < 201103L
716 _Rb_tree_impl(const _Key_compare
& __comp
, const _Node_allocator
& __a
)
717 : _Node_allocator(__a
), _Base_key_compare(__comp
)
720 _Rb_tree_impl(_Rb_tree_impl
&&) = default;
723 _Rb_tree_impl(_Node_allocator
&& __a
)
724 : _Node_allocator(std::move(__a
))
727 _Rb_tree_impl(_Rb_tree_impl
&& __x
, _Node_allocator
&& __a
)
728 : _Node_allocator(std::move(__a
)),
729 _Base_key_compare(std::move(__x
)),
730 _Rb_tree_header(std::move(__x
))
733 _Rb_tree_impl(const _Key_compare
& __comp
, _Node_allocator
&& __a
)
734 : _Node_allocator(std::move(__a
)), _Base_key_compare(__comp
)
739 _Rb_tree_impl
<_Compare
> _M_impl
;
743 _M_root() _GLIBCXX_NOEXCEPT
744 { return this->_M_impl
._M_header
._M_parent
; }
747 _M_root() const _GLIBCXX_NOEXCEPT
748 { return this->_M_impl
._M_header
._M_parent
; }
751 _M_leftmost() _GLIBCXX_NOEXCEPT
752 { return this->_M_impl
._M_header
._M_left
; }
755 _M_leftmost() const _GLIBCXX_NOEXCEPT
756 { return this->_M_impl
._M_header
._M_left
; }
759 _M_rightmost() _GLIBCXX_NOEXCEPT
760 { return this->_M_impl
._M_header
._M_right
; }
763 _M_rightmost() const _GLIBCXX_NOEXCEPT
764 { return this->_M_impl
._M_header
._M_right
; }
767 _M_begin() _GLIBCXX_NOEXCEPT
768 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
771 _M_begin() const _GLIBCXX_NOEXCEPT
773 return static_cast<_Const_Link_type
>
774 (this->_M_impl
._M_header
._M_parent
);
778 _M_end() _GLIBCXX_NOEXCEPT
779 { return &this->_M_impl
._M_header
; }
782 _M_end() const _GLIBCXX_NOEXCEPT
783 { return &this->_M_impl
._M_header
; }
785 static const_reference
786 _S_value(_Const_Link_type __x
)
787 { return *__x
->_M_valptr(); }
790 _S_key(_Const_Link_type __x
)
791 { return _KeyOfValue()(_S_value(__x
)); }
794 _S_left(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
795 { return static_cast<_Link_type
>(__x
->_M_left
); }
797 static _Const_Link_type
798 _S_left(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
799 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
802 _S_right(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
803 { return static_cast<_Link_type
>(__x
->_M_right
); }
805 static _Const_Link_type
806 _S_right(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
807 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
809 static const_reference
810 _S_value(_Const_Base_ptr __x
)
811 { return *static_cast<_Const_Link_type
>(__x
)->_M_valptr(); }
814 _S_key(_Const_Base_ptr __x
)
815 { return _KeyOfValue()(_S_value(__x
)); }
818 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
819 { return _Rb_tree_node_base::_S_minimum(__x
); }
821 static _Const_Base_ptr
822 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
823 { return _Rb_tree_node_base::_S_minimum(__x
); }
826 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
827 { return _Rb_tree_node_base::_S_maximum(__x
); }
829 static _Const_Base_ptr
830 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
831 { return _Rb_tree_node_base::_S_maximum(__x
); }
834 typedef _Rb_tree_iterator
<value_type
> iterator
;
835 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
837 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
838 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
840 #if __cplusplus > 201402L
841 using node_type
= _Node_handle
<_Key
, _Val
, _Node_allocator
>;
842 using insert_return_type
= _Node_insert_return
<
843 conditional_t
<is_same_v
<_Key
, _Val
>, const_iterator
, iterator
>,
847 pair
<_Base_ptr
, _Base_ptr
>
848 _M_get_insert_unique_pos(const key_type
& __k
);
850 pair
<_Base_ptr
, _Base_ptr
>
851 _M_get_insert_equal_pos(const key_type
& __k
);
853 pair
<_Base_ptr
, _Base_ptr
>
854 _M_get_insert_hint_unique_pos(const_iterator __pos
,
855 const key_type
& __k
);
857 pair
<_Base_ptr
, _Base_ptr
>
858 _M_get_insert_hint_equal_pos(const_iterator __pos
,
859 const key_type
& __k
);
862 #if __cplusplus >= 201103L
863 template<typename _Arg
, typename _NodeGen
>
865 _M_insert_(_Base_ptr __x
, _Base_ptr __y
, _Arg
&& __v
, _NodeGen
&);
868 _M_insert_node(_Base_ptr __x
, _Base_ptr __y
, _Link_type __z
);
870 template<typename _Arg
>
872 _M_insert_lower(_Base_ptr __y
, _Arg
&& __v
);
874 template<typename _Arg
>
876 _M_insert_equal_lower(_Arg
&& __x
);
879 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
);
882 _M_insert_equal_lower_node(_Link_type __z
);
884 template<typename _NodeGen
>
886 _M_insert_(_Base_ptr __x
, _Base_ptr __y
,
887 const value_type
& __v
, _NodeGen
&);
889 // _GLIBCXX_RESOLVE_LIB_DEFECTS
890 // 233. Insertion hints in associative containers.
892 _M_insert_lower(_Base_ptr __y
, const value_type
& __v
);
895 _M_insert_equal_lower(const value_type
& __x
);
898 template<typename _NodeGen
>
900 _M_copy(_Const_Link_type __x
, _Base_ptr __p
, _NodeGen
&);
902 template<typename _NodeGen
>
904 _M_copy(const _Rb_tree
& __x
, _NodeGen
& __gen
)
906 _Link_type __root
= _M_copy(__x
._M_begin(), _M_end(), __gen
);
907 _M_leftmost() = _S_minimum(__root
);
908 _M_rightmost() = _S_maximum(__root
);
909 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
914 _M_copy(const _Rb_tree
& __x
)
916 _Alloc_node
__an(*this);
917 return _M_copy(__x
, __an
);
921 _M_erase(_Link_type __x
);
924 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
928 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
929 const _Key
& __k
) const;
932 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
936 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
937 const _Key
& __k
) const;
940 // allocation/deallocation
941 #if __cplusplus < 201103L
944 _Rb_tree() = default;
947 _Rb_tree(const _Compare
& __comp
,
948 const allocator_type
& __a
= allocator_type())
949 : _M_impl(__comp
, _Node_allocator(__a
)) { }
951 _Rb_tree(const _Rb_tree
& __x
)
952 : _M_impl(__x
._M_impl
)
954 if (__x
._M_root() != 0)
955 _M_root() = _M_copy(__x
);
958 #if __cplusplus >= 201103L
959 _Rb_tree(const allocator_type
& __a
)
960 : _M_impl(_Node_allocator(__a
))
963 _Rb_tree(const _Rb_tree
& __x
, const allocator_type
& __a
)
964 : _M_impl(__x
._M_impl
._M_key_compare
, _Node_allocator(__a
))
966 if (__x
._M_root() != nullptr)
967 _M_root() = _M_copy(__x
);
970 _Rb_tree(_Rb_tree
&&) = default;
972 _Rb_tree(_Rb_tree
&& __x
, const allocator_type
& __a
)
973 : _Rb_tree(std::move(__x
), _Node_allocator(__a
))
977 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
, true_type
)
978 noexcept(is_nothrow_default_constructible
<_Compare
>::value
)
979 : _M_impl(std::move(__x
._M_impl
), std::move(__a
))
982 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
, false_type
)
983 : _M_impl(__x
._M_impl
._M_key_compare
, std::move(__a
))
985 if (__x
._M_root() != nullptr)
986 _M_move_data(__x
, false_type
{});
990 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
)
992 _Rb_tree(std::declval
<_Rb_tree
&&>(), std::declval
<_Node_allocator
&&>(),
993 std::declval
<typename
_Alloc_traits::is_always_equal
>())) )
994 : _Rb_tree(std::move(__x
), std::move(__a
),
995 typename
_Alloc_traits::is_always_equal
{})
999 ~_Rb_tree() _GLIBCXX_NOEXCEPT
1000 { _M_erase(_M_begin()); }
1003 operator=(const _Rb_tree
& __x
);
1008 { return _M_impl
._M_key_compare
; }
1011 begin() _GLIBCXX_NOEXCEPT
1012 { return iterator(this->_M_impl
._M_header
._M_left
); }
1015 begin() const _GLIBCXX_NOEXCEPT
1016 { return const_iterator(this->_M_impl
._M_header
._M_left
); }
1019 end() _GLIBCXX_NOEXCEPT
1020 { return iterator(&this->_M_impl
._M_header
); }
1023 end() const _GLIBCXX_NOEXCEPT
1024 { return const_iterator(&this->_M_impl
._M_header
); }
1027 rbegin() _GLIBCXX_NOEXCEPT
1028 { return reverse_iterator(end()); }
1030 const_reverse_iterator
1031 rbegin() const _GLIBCXX_NOEXCEPT
1032 { return const_reverse_iterator(end()); }
1035 rend() _GLIBCXX_NOEXCEPT
1036 { return reverse_iterator(begin()); }
1038 const_reverse_iterator
1039 rend() const _GLIBCXX_NOEXCEPT
1040 { return const_reverse_iterator(begin()); }
1043 empty() const _GLIBCXX_NOEXCEPT
1044 { return _M_impl
._M_node_count
== 0; }
1047 size() const _GLIBCXX_NOEXCEPT
1048 { return _M_impl
._M_node_count
; }
1051 max_size() const _GLIBCXX_NOEXCEPT
1052 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
1056 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
);
1059 #if __cplusplus >= 201103L
1060 template<typename _Arg
>
1061 pair
<iterator
, bool>
1062 _M_insert_unique(_Arg
&& __x
);
1064 template<typename _Arg
>
1066 _M_insert_equal(_Arg
&& __x
);
1068 template<typename _Arg
, typename _NodeGen
>
1070 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
1072 template<typename _Arg
>
1074 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
)
1076 _Alloc_node
__an(*this);
1077 return _M_insert_unique_(__pos
, std::forward
<_Arg
>(__x
), __an
);
1080 template<typename _Arg
, typename _NodeGen
>
1082 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
1084 template<typename _Arg
>
1086 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
)
1088 _Alloc_node
__an(*this);
1089 return _M_insert_equal_(__pos
, std::forward
<_Arg
>(__x
), __an
);
1092 template<typename
... _Args
>
1093 pair
<iterator
, bool>
1094 _M_emplace_unique(_Args
&&... __args
);
1096 template<typename
... _Args
>
1098 _M_emplace_equal(_Args
&&... __args
);
1100 template<typename
... _Args
>
1102 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
);
1104 template<typename
... _Args
>
1106 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
);
1108 template<typename _Iter
>
1109 using __same_value_type
1110 = is_same
<value_type
, typename iterator_traits
<_Iter
>::value_type
>;
1112 template<typename _InputIterator
>
1113 __enable_if_t
<__same_value_type
<_InputIterator
>::value
>
1114 _M_insert_range_unique(_InputIterator __first
, _InputIterator __last
)
1116 _Alloc_node
__an(*this);
1117 for (; __first
!= __last
; ++__first
)
1118 _M_insert_unique_(end(), *__first
, __an
);
1121 template<typename _InputIterator
>
1122 __enable_if_t
<!__same_value_type
<_InputIterator
>::value
>
1123 _M_insert_range_unique(_InputIterator __first
, _InputIterator __last
)
1125 for (; __first
!= __last
; ++__first
)
1126 _M_emplace_unique(*__first
);
1129 template<typename _InputIterator
>
1130 __enable_if_t
<__same_value_type
<_InputIterator
>::value
>
1131 _M_insert_range_equal(_InputIterator __first
, _InputIterator __last
)
1133 _Alloc_node
__an(*this);
1134 for (; __first
!= __last
; ++__first
)
1135 _M_insert_equal_(end(), *__first
, __an
);
1138 template<typename _InputIterator
>
1139 __enable_if_t
<!__same_value_type
<_InputIterator
>::value
>
1140 _M_insert_range_equal(_InputIterator __first
, _InputIterator __last
)
1142 _Alloc_node
__an(*this);
1143 for (; __first
!= __last
; ++__first
)
1144 _M_emplace_equal(*__first
);
1147 pair
<iterator
, bool>
1148 _M_insert_unique(const value_type
& __x
);
1151 _M_insert_equal(const value_type
& __x
);
1153 template<typename _NodeGen
>
1155 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
,
1159 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
)
1161 _Alloc_node
__an(*this);
1162 return _M_insert_unique_(__pos
, __x
, __an
);
1165 template<typename _NodeGen
>
1167 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
,
1170 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
)
1172 _Alloc_node
__an(*this);
1173 return _M_insert_equal_(__pos
, __x
, __an
);
1176 template<typename _InputIterator
>
1178 _M_insert_range_unique(_InputIterator __first
, _InputIterator __last
)
1180 _Alloc_node
__an(*this);
1181 for (; __first
!= __last
; ++__first
)
1182 _M_insert_unique_(end(), *__first
, __an
);
1185 template<typename _InputIterator
>
1187 _M_insert_range_equal(_InputIterator __first
, _InputIterator __last
)
1189 _Alloc_node
__an(*this);
1190 for (; __first
!= __last
; ++__first
)
1191 _M_insert_equal_(end(), *__first
, __an
);
1197 _M_erase_aux(const_iterator __position
);
1200 _M_erase_aux(const_iterator __first
, const_iterator __last
);
1203 #if __cplusplus >= 201103L
1204 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1205 // DR 130. Associative erase should return an iterator.
1206 _GLIBCXX_ABI_TAG_CXX11
1208 erase(const_iterator __position
)
1210 __glibcxx_assert(__position
!= end());
1211 const_iterator __result
= __position
;
1213 _M_erase_aux(__position
);
1214 return __result
._M_const_cast();
1218 _GLIBCXX_ABI_TAG_CXX11
1220 erase(iterator __position
)
1222 __glibcxx_assert(__position
!= end());
1223 iterator __result
= __position
;
1225 _M_erase_aux(__position
);
1230 erase(iterator __position
)
1232 __glibcxx_assert(__position
!= end());
1233 _M_erase_aux(__position
);
1237 erase(const_iterator __position
)
1239 __glibcxx_assert(__position
!= end());
1240 _M_erase_aux(__position
);
1244 erase(const key_type
& __x
);
1246 #if __cplusplus >= 201103L
1247 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1248 // DR 130. Associative erase should return an iterator.
1249 _GLIBCXX_ABI_TAG_CXX11
1251 erase(const_iterator __first
, const_iterator __last
)
1253 _M_erase_aux(__first
, __last
);
1254 return __last
._M_const_cast();
1258 erase(iterator __first
, iterator __last
)
1259 { _M_erase_aux(__first
, __last
); }
1262 erase(const_iterator __first
, const_iterator __last
)
1263 { _M_erase_aux(__first
, __last
); }
1266 erase(const key_type
* __first
, const key_type
* __last
);
1269 clear() _GLIBCXX_NOEXCEPT
1271 _M_erase(_M_begin());
1277 find(const key_type
& __k
);
1280 find(const key_type
& __k
) const;
1283 count(const key_type
& __k
) const;
1286 lower_bound(const key_type
& __k
)
1287 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1290 lower_bound(const key_type
& __k
) const
1291 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1294 upper_bound(const key_type
& __k
)
1295 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1298 upper_bound(const key_type
& __k
) const
1299 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1301 pair
<iterator
, iterator
>
1302 equal_range(const key_type
& __k
);
1304 pair
<const_iterator
, const_iterator
>
1305 equal_range(const key_type
& __k
) const;
1307 #if __cplusplus >= 201402L
1308 template<typename _Kt
,
1309 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1311 _M_find_tr(const _Kt
& __k
)
1313 const _Rb_tree
* __const_this
= this;
1314 return __const_this
->_M_find_tr(__k
)._M_const_cast();
1317 template<typename _Kt
,
1318 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1320 _M_find_tr(const _Kt
& __k
) const
1322 auto __j
= _M_lower_bound_tr(__k
);
1323 if (__j
!= end() && _M_impl
._M_key_compare(__k
, _S_key(__j
._M_node
)))
1328 template<typename _Kt
,
1329 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1331 _M_count_tr(const _Kt
& __k
) const
1333 auto __p
= _M_equal_range_tr(__k
);
1334 return std::distance(__p
.first
, __p
.second
);
1337 template<typename _Kt
,
1338 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1340 _M_lower_bound_tr(const _Kt
& __k
)
1342 const _Rb_tree
* __const_this
= this;
1343 return __const_this
->_M_lower_bound_tr(__k
)._M_const_cast();
1346 template<typename _Kt
,
1347 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1349 _M_lower_bound_tr(const _Kt
& __k
) const
1351 auto __x
= _M_begin();
1352 auto __y
= _M_end();
1354 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1360 __x
= _S_right(__x
);
1361 return const_iterator(__y
);
1364 template<typename _Kt
,
1365 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1367 _M_upper_bound_tr(const _Kt
& __k
)
1369 const _Rb_tree
* __const_this
= this;
1370 return __const_this
->_M_upper_bound_tr(__k
)._M_const_cast();
1373 template<typename _Kt
,
1374 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1376 _M_upper_bound_tr(const _Kt
& __k
) const
1378 auto __x
= _M_begin();
1379 auto __y
= _M_end();
1381 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1387 __x
= _S_right(__x
);
1388 return const_iterator(__y
);
1391 template<typename _Kt
,
1392 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1393 pair
<iterator
, iterator
>
1394 _M_equal_range_tr(const _Kt
& __k
)
1396 const _Rb_tree
* __const_this
= this;
1397 auto __ret
= __const_this
->_M_equal_range_tr(__k
);
1398 return { __ret
.first
._M_const_cast(), __ret
.second
._M_const_cast() };
1401 template<typename _Kt
,
1402 typename _Req
= __has_is_transparent_t
<_Compare
, _Kt
>>
1403 pair
<const_iterator
, const_iterator
>
1404 _M_equal_range_tr(const _Kt
& __k
) const
1406 auto __low
= _M_lower_bound_tr(__k
);
1407 auto __high
= __low
;
1408 auto& __cmp
= _M_impl
._M_key_compare
;
1409 while (__high
!= end() && !__cmp(__k
, _S_key(__high
._M_node
)))
1411 return { __low
, __high
};
1417 __rb_verify() const;
1419 #if __cplusplus >= 201103L
1421 operator=(_Rb_tree
&&)
1422 noexcept(_Alloc_traits::_S_nothrow_move()
1423 && is_nothrow_move_assignable
<_Compare
>::value
);
1425 template<typename _Iterator
>
1427 _M_assign_unique(_Iterator
, _Iterator
);
1429 template<typename _Iterator
>
1431 _M_assign_equal(_Iterator
, _Iterator
);
1434 // Move elements from container with equal allocator.
1436 _M_move_data(_Rb_tree
& __x
, true_type
)
1437 { _M_impl
._M_move_data(__x
._M_impl
); }
1439 // Move elements from container with possibly non-equal allocator,
1440 // which might result in a copy not a move.
1442 _M_move_data(_Rb_tree
&, false_type
);
1444 // Move assignment from container with equal allocator.
1446 _M_move_assign(_Rb_tree
&, true_type
);
1448 // Move assignment from container with possibly non-equal allocator,
1449 // which might result in a copy not a move.
1451 _M_move_assign(_Rb_tree
&, false_type
);
1454 #if __cplusplus > 201402L
1456 /// Re-insert an extracted node.
1458 _M_reinsert_node_unique(node_type
&& __nh
)
1460 insert_return_type __ret
;
1462 __ret
.position
= end();
1465 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1467 auto __res
= _M_get_insert_unique_pos(__nh
._M_key());
1471 = _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1472 __nh
._M_ptr
= nullptr;
1473 __ret
.inserted
= true;
1477 __ret
.node
= std::move(__nh
);
1478 __ret
.position
= iterator(__res
.first
);
1479 __ret
.inserted
= false;
1485 /// Re-insert an extracted node.
1487 _M_reinsert_node_equal(node_type
&& __nh
)
1494 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1495 auto __res
= _M_get_insert_equal_pos(__nh
._M_key());
1497 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1499 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1500 __nh
._M_ptr
= nullptr;
1505 /// Re-insert an extracted node.
1507 _M_reinsert_node_hint_unique(const_iterator __hint
, node_type
&& __nh
)
1514 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1515 auto __res
= _M_get_insert_hint_unique_pos(__hint
, __nh
._M_key());
1518 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1519 __nh
._M_ptr
= nullptr;
1522 __ret
= iterator(__res
.first
);
1527 /// Re-insert an extracted node.
1529 _M_reinsert_node_hint_equal(const_iterator __hint
, node_type
&& __nh
)
1536 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1537 auto __res
= _M_get_insert_hint_equal_pos(__hint
, __nh
._M_key());
1539 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1541 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1542 __nh
._M_ptr
= nullptr;
1549 extract(const_iterator __pos
)
1551 auto __ptr
= _Rb_tree_rebalance_for_erase(
1552 __pos
._M_const_cast()._M_node
, _M_impl
._M_header
);
1553 --_M_impl
._M_node_count
;
1554 return { static_cast<_Link_type
>(__ptr
), _M_get_Node_allocator() };
1559 extract(const key_type
& __k
)
1562 auto __pos
= find(__k
);
1564 __nh
= extract(const_iterator(__pos
));
1568 template<typename _Compare2
>
1569 using _Compatible_tree
1570 = _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare2
, _Alloc
>;
1572 template<typename
, typename
>
1573 friend class _Rb_tree_merge_helper
;
1575 /// Merge from a compatible container into one with unique keys.
1576 template<typename _Compare2
>
1578 _M_merge_unique(_Compatible_tree
<_Compare2
>& __src
) noexcept
1580 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1581 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1584 auto __res
= _M_get_insert_unique_pos(_KeyOfValue()(*__pos
));
1587 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1588 auto __ptr
= _Rb_tree_rebalance_for_erase(
1589 __pos
._M_node
, __src_impl
._M_header
);
1590 --__src_impl
._M_node_count
;
1591 _M_insert_node(__res
.first
, __res
.second
,
1592 static_cast<_Link_type
>(__ptr
));
1597 /// Merge from a compatible container into one with equivalent keys.
1598 template<typename _Compare2
>
1600 _M_merge_equal(_Compatible_tree
<_Compare2
>& __src
) noexcept
1602 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1603 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1606 auto __res
= _M_get_insert_equal_pos(_KeyOfValue()(*__pos
));
1609 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1610 auto __ptr
= _Rb_tree_rebalance_for_erase(
1611 __pos
._M_node
, __src_impl
._M_header
);
1612 --__src_impl
._M_node_count
;
1613 _M_insert_node(__res
.first
, __res
.second
,
1614 static_cast<_Link_type
>(__ptr
));
1621 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1622 typename _Compare
, typename _Alloc
>
1624 operator==(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1625 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1627 return __x
.size() == __y
.size()
1628 && std::equal(__x
.begin(), __x
.end(), __y
.begin());
1631 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1632 typename _Compare
, typename _Alloc
>
1634 operator<(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1635 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1637 return std::lexicographical_compare(__x
.begin(), __x
.end(),
1638 __y
.begin(), __y
.end());
1641 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1642 typename _Compare
, typename _Alloc
>
1644 operator!=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1645 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1646 { return !(__x
== __y
); }
1648 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1649 typename _Compare
, typename _Alloc
>
1651 operator>(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1652 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1653 { return __y
< __x
; }
1655 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1656 typename _Compare
, typename _Alloc
>
1658 operator<=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1659 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1660 { return !(__y
< __x
); }
1662 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1663 typename _Compare
, typename _Alloc
>
1665 operator>=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1666 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1667 { return !(__x
< __y
); }
1669 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1670 typename _Compare
, typename _Alloc
>
1672 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1673 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1676 #if __cplusplus >= 201103L
1677 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1678 typename _Compare
, typename _Alloc
>
1680 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1681 _M_move_data(_Rb_tree
& __x
, false_type
)
1683 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1684 _M_move_data(__x
, true_type());
1687 _Alloc_node
__an(*this);
1689 [&__an
](const value_type
& __cval
)
1691 auto& __val
= const_cast<value_type
&>(__cval
);
1692 return __an(std::move_if_noexcept(__val
));
1694 _M_root() = _M_copy(__x
, __lbd
);
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)
1727 [&__roan
](const value_type
& __cval
)
1729 auto& __val
= const_cast<value_type
&>(__cval
);
1730 return __roan(std::move_if_noexcept(__val
));
1732 _M_root() = _M_copy(__x
, __lbd
);
1737 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1738 typename _Compare
, typename _Alloc
>
1739 inline _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1740 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1741 operator=(_Rb_tree
&& __x
)
1742 noexcept(_Alloc_traits::_S_nothrow_move()
1743 && is_nothrow_move_assignable
<_Compare
>::value
)
1745 _M_impl
._M_key_compare
= std::move(__x
._M_impl
._M_key_compare
);
1746 _M_move_assign(__x
, __bool_constant
<_Alloc_traits::_S_nothrow_move()>());
1750 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1751 typename _Compare
, typename _Alloc
>
1752 template<typename _Iterator
>
1754 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1755 _M_assign_unique(_Iterator __first
, _Iterator __last
)
1757 _Reuse_or_alloc_node
__roan(*this);
1759 for (; __first
!= __last
; ++__first
)
1760 _M_insert_unique_(end(), *__first
, __roan
);
1763 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1764 typename _Compare
, typename _Alloc
>
1765 template<typename _Iterator
>
1767 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1768 _M_assign_equal(_Iterator __first
, _Iterator __last
)
1770 _Reuse_or_alloc_node
__roan(*this);
1772 for (; __first
!= __last
; ++__first
)
1773 _M_insert_equal_(end(), *__first
, __roan
);
1777 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1778 typename _Compare
, typename _Alloc
>
1779 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1780 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1781 operator=(const _Rb_tree
& __x
)
1785 // Note that _Key may be a constant type.
1786 #if __cplusplus >= 201103L
1787 if (_Alloc_traits::_S_propagate_on_copy_assign())
1789 auto& __this_alloc
= this->_M_get_Node_allocator();
1790 auto& __that_alloc
= __x
._M_get_Node_allocator();
1791 if (!_Alloc_traits::_S_always_equal()
1792 && __this_alloc
!= __that_alloc
)
1794 // Replacement allocator cannot free existing storage, we need
1795 // to erase nodes first.
1797 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1802 _Reuse_or_alloc_node
__roan(*this);
1804 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
1805 if (__x
._M_root() != 0)
1806 _M_root() = _M_copy(__x
, __roan
);
1812 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1813 typename _Compare
, typename _Alloc
>
1814 #if __cplusplus >= 201103L
1815 template<typename _Arg
, typename _NodeGen
>
1817 template<typename _NodeGen
>
1819 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1820 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1821 _M_insert_(_Base_ptr __x
, _Base_ptr __p
,
1822 #if __cplusplus >= 201103L
1827 _NodeGen
& __node_gen
)
1829 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
1830 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
1833 _Link_type __z
= __node_gen(_GLIBCXX_FORWARD(_Arg
, __v
));
1835 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1836 this->_M_impl
._M_header
);
1837 ++_M_impl
._M_node_count
;
1838 return iterator(__z
);
1841 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1842 typename _Compare
, typename _Alloc
>
1843 #if __cplusplus >= 201103L
1844 template<typename _Arg
>
1846 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1847 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1848 #if __cplusplus >= 201103L
1849 _M_insert_lower(_Base_ptr __p
, _Arg
&& __v
)
1851 _M_insert_lower(_Base_ptr __p
, const _Val
& __v
)
1854 bool __insert_left
= (__p
== _M_end()
1855 || !_M_impl
._M_key_compare(_S_key(__p
),
1856 _KeyOfValue()(__v
)));
1858 _Link_type __z
= _M_create_node(_GLIBCXX_FORWARD(_Arg
, __v
));
1860 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1861 this->_M_impl
._M_header
);
1862 ++_M_impl
._M_node_count
;
1863 return iterator(__z
);
1866 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1867 typename _Compare
, typename _Alloc
>
1868 #if __cplusplus >= 201103L
1869 template<typename _Arg
>
1871 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1872 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1873 #if __cplusplus >= 201103L
1874 _M_insert_equal_lower(_Arg
&& __v
)
1876 _M_insert_equal_lower(const _Val
& __v
)
1879 _Link_type __x
= _M_begin();
1880 _Base_ptr __y
= _M_end();
1884 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _KeyOfValue()(__v
)) ?
1885 _S_left(__x
) : _S_right(__x
);
1887 return _M_insert_lower(__y
, _GLIBCXX_FORWARD(_Arg
, __v
));
1890 template<typename _Key
, typename _Val
, typename _KoV
,
1891 typename _Compare
, typename _Alloc
>
1892 template<typename _NodeGen
>
1893 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1894 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
1895 _M_copy(_Const_Link_type __x
, _Base_ptr __p
, _NodeGen
& __node_gen
)
1897 // Structural copy. __x and __p must be non-null.
1898 _Link_type __top
= _M_clone_node(__x
, __node_gen
);
1899 __top
->_M_parent
= __p
;
1904 __top
->_M_right
= _M_copy(_S_right(__x
), __top
, __node_gen
);
1910 _Link_type __y
= _M_clone_node(__x
, __node_gen
);
1912 __y
->_M_parent
= __p
;
1914 __y
->_M_right
= _M_copy(_S_right(__x
), __y
, __node_gen
);
1922 __throw_exception_again
;
1927 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1928 typename _Compare
, typename _Alloc
>
1930 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1931 _M_erase(_Link_type __x
)
1933 // Erase without rebalancing.
1936 _M_erase(_S_right(__x
));
1937 _Link_type __y
= _S_left(__x
);
1943 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1944 typename _Compare
, typename _Alloc
>
1945 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1946 _Compare
, _Alloc
>::iterator
1947 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1948 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
1952 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1953 __y
= __x
, __x
= _S_left(__x
);
1955 __x
= _S_right(__x
);
1956 return iterator(__y
);
1959 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1960 typename _Compare
, typename _Alloc
>
1961 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1962 _Compare
, _Alloc
>::const_iterator
1963 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1964 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1965 const _Key
& __k
) const
1968 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1969 __y
= __x
, __x
= _S_left(__x
);
1971 __x
= _S_right(__x
);
1972 return const_iterator(__y
);
1975 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1976 typename _Compare
, typename _Alloc
>
1977 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1978 _Compare
, _Alloc
>::iterator
1979 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1980 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
1984 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1985 __y
= __x
, __x
= _S_left(__x
);
1987 __x
= _S_right(__x
);
1988 return iterator(__y
);
1991 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1992 typename _Compare
, typename _Alloc
>
1993 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1994 _Compare
, _Alloc
>::const_iterator
1995 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1996 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1997 const _Key
& __k
) const
2000 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
2001 __y
= __x
, __x
= _S_left(__x
);
2003 __x
= _S_right(__x
);
2004 return const_iterator(__y
);
2007 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2008 typename _Compare
, typename _Alloc
>
2009 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2010 _Compare
, _Alloc
>::iterator
,
2011 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2012 _Compare
, _Alloc
>::iterator
>
2013 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2014 equal_range(const _Key
& __k
)
2016 _Link_type __x
= _M_begin();
2017 _Base_ptr __y
= _M_end();
2020 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
2021 __x
= _S_right(__x
);
2022 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
2023 __y
= __x
, __x
= _S_left(__x
);
2026 _Link_type
__xu(__x
);
2027 _Base_ptr
__yu(__y
);
2028 __y
= __x
, __x
= _S_left(__x
);
2029 __xu
= _S_right(__xu
);
2030 return pair
<iterator
,
2031 iterator
>(_M_lower_bound(__x
, __y
, __k
),
2032 _M_upper_bound(__xu
, __yu
, __k
));
2035 return pair
<iterator
, iterator
>(iterator(__y
),
2039 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2040 typename _Compare
, typename _Alloc
>
2041 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2042 _Compare
, _Alloc
>::const_iterator
,
2043 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2044 _Compare
, _Alloc
>::const_iterator
>
2045 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2046 equal_range(const _Key
& __k
) const
2048 _Const_Link_type __x
= _M_begin();
2049 _Const_Base_ptr __y
= _M_end();
2052 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
2053 __x
= _S_right(__x
);
2054 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
2055 __y
= __x
, __x
= _S_left(__x
);
2058 _Const_Link_type
__xu(__x
);
2059 _Const_Base_ptr
__yu(__y
);
2060 __y
= __x
, __x
= _S_left(__x
);
2061 __xu
= _S_right(__xu
);
2062 return pair
<const_iterator
,
2063 const_iterator
>(_M_lower_bound(__x
, __y
, __k
),
2064 _M_upper_bound(__xu
, __yu
, __k
));
2067 return pair
<const_iterator
, const_iterator
>(const_iterator(__y
),
2068 const_iterator(__y
));
2071 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2072 typename _Compare
, typename _Alloc
>
2074 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2076 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
)
2080 if (__t
._M_root() != 0)
2081 _M_impl
._M_move_data(__t
._M_impl
);
2083 else if (__t
._M_root() == 0)
2084 __t
._M_impl
._M_move_data(_M_impl
);
2087 std::swap(_M_root(),__t
._M_root());
2088 std::swap(_M_leftmost(),__t
._M_leftmost());
2089 std::swap(_M_rightmost(),__t
._M_rightmost());
2091 _M_root()->_M_parent
= _M_end();
2092 __t
._M_root()->_M_parent
= __t
._M_end();
2093 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
2095 // No need to swap header's color as it does not change.
2096 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
2098 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2099 __t
._M_get_Node_allocator());
2102 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2103 typename _Compare
, typename _Alloc
>
2104 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2105 _Compare
, _Alloc
>::_Base_ptr
,
2106 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2107 _Compare
, _Alloc
>::_Base_ptr
>
2108 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2109 _M_get_insert_unique_pos(const key_type
& __k
)
2111 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2112 _Link_type __x
= _M_begin();
2113 _Base_ptr __y
= _M_end();
2118 __comp
= _M_impl
._M_key_compare(__k
, _S_key(__x
));
2119 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
2121 iterator __j
= iterator(__y
);
2125 return _Res(__x
, __y
);
2129 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), __k
))
2130 return _Res(__x
, __y
);
2131 return _Res(__j
._M_node
, 0);
2134 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2135 typename _Compare
, typename _Alloc
>
2136 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2137 _Compare
, _Alloc
>::_Base_ptr
,
2138 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2139 _Compare
, _Alloc
>::_Base_ptr
>
2140 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2141 _M_get_insert_equal_pos(const key_type
& __k
)
2143 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2144 _Link_type __x
= _M_begin();
2145 _Base_ptr __y
= _M_end();
2149 __x
= _M_impl
._M_key_compare(__k
, _S_key(__x
)) ?
2150 _S_left(__x
) : _S_right(__x
);
2152 return _Res(__x
, __y
);
2155 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2156 typename _Compare
, typename _Alloc
>
2157 #if __cplusplus >= 201103L
2158 template<typename _Arg
>
2160 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2161 _Compare
, _Alloc
>::iterator
, bool>
2162 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2163 #if __cplusplus >= 201103L
2164 _M_insert_unique(_Arg
&& __v
)
2166 _M_insert_unique(const _Val
& __v
)
2169 typedef pair
<iterator
, bool> _Res
;
2170 pair
<_Base_ptr
, _Base_ptr
> __res
2171 = _M_get_insert_unique_pos(_KeyOfValue()(__v
));
2175 _Alloc_node
__an(*this);
2176 return _Res(_M_insert_(__res
.first
, __res
.second
,
2177 _GLIBCXX_FORWARD(_Arg
, __v
), __an
),
2181 return _Res(iterator(__res
.first
), false);
2184 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2185 typename _Compare
, typename _Alloc
>
2186 #if __cplusplus >= 201103L
2187 template<typename _Arg
>
2189 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2190 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2191 #if __cplusplus >= 201103L
2192 _M_insert_equal(_Arg
&& __v
)
2194 _M_insert_equal(const _Val
& __v
)
2197 pair
<_Base_ptr
, _Base_ptr
> __res
2198 = _M_get_insert_equal_pos(_KeyOfValue()(__v
));
2199 _Alloc_node
__an(*this);
2200 return _M_insert_(__res
.first
, __res
.second
,
2201 _GLIBCXX_FORWARD(_Arg
, __v
), __an
);
2204 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2205 typename _Compare
, typename _Alloc
>
2206 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2207 _Compare
, _Alloc
>::_Base_ptr
,
2208 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2209 _Compare
, _Alloc
>::_Base_ptr
>
2210 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2211 _M_get_insert_hint_unique_pos(const_iterator __position
,
2212 const key_type
& __k
)
2214 iterator __pos
= __position
._M_const_cast();
2215 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2218 if (__pos
._M_node
== _M_end())
2221 && _M_impl
._M_key_compare(_S_key(_M_rightmost()), __k
))
2222 return _Res(0, _M_rightmost());
2224 return _M_get_insert_unique_pos(__k
);
2226 else if (_M_impl
._M_key_compare(__k
, _S_key(__pos
._M_node
)))
2228 // First, try before...
2229 iterator __before
= __pos
;
2230 if (__pos
._M_node
== _M_leftmost()) // begin()
2231 return _Res(_M_leftmost(), _M_leftmost());
2232 else if (_M_impl
._M_key_compare(_S_key((--__before
)._M_node
), __k
))
2234 if (_S_right(__before
._M_node
) == 0)
2235 return _Res(0, __before
._M_node
);
2237 return _Res(__pos
._M_node
, __pos
._M_node
);
2240 return _M_get_insert_unique_pos(__k
);
2242 else if (_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2244 // ... then try after.
2245 iterator __after
= __pos
;
2246 if (__pos
._M_node
== _M_rightmost())
2247 return _Res(0, _M_rightmost());
2248 else if (_M_impl
._M_key_compare(__k
, _S_key((++__after
)._M_node
)))
2250 if (_S_right(__pos
._M_node
) == 0)
2251 return _Res(0, __pos
._M_node
);
2253 return _Res(__after
._M_node
, __after
._M_node
);
2256 return _M_get_insert_unique_pos(__k
);
2260 return _Res(__pos
._M_node
, 0);
2263 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2264 typename _Compare
, typename _Alloc
>
2265 #if __cplusplus >= 201103L
2266 template<typename _Arg
, typename _NodeGen
>
2268 template<typename _NodeGen
>
2270 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2271 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2272 _M_insert_unique_(const_iterator __position
,
2273 #if __cplusplus >= 201103L
2278 _NodeGen
& __node_gen
)
2280 pair
<_Base_ptr
, _Base_ptr
> __res
2281 = _M_get_insert_hint_unique_pos(__position
, _KeyOfValue()(__v
));
2284 return _M_insert_(__res
.first
, __res
.second
,
2285 _GLIBCXX_FORWARD(_Arg
, __v
),
2287 return iterator(__res
.first
);
2290 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2291 typename _Compare
, typename _Alloc
>
2292 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2293 _Compare
, _Alloc
>::_Base_ptr
,
2294 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2295 _Compare
, _Alloc
>::_Base_ptr
>
2296 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2297 _M_get_insert_hint_equal_pos(const_iterator __position
, const key_type
& __k
)
2299 iterator __pos
= __position
._M_const_cast();
2300 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2303 if (__pos
._M_node
== _M_end())
2306 && !_M_impl
._M_key_compare(__k
, _S_key(_M_rightmost())))
2307 return _Res(0, _M_rightmost());
2309 return _M_get_insert_equal_pos(__k
);
2311 else if (!_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2313 // First, try before...
2314 iterator __before
= __pos
;
2315 if (__pos
._M_node
== _M_leftmost()) // begin()
2316 return _Res(_M_leftmost(), _M_leftmost());
2317 else if (!_M_impl
._M_key_compare(__k
, _S_key((--__before
)._M_node
)))
2319 if (_S_right(__before
._M_node
) == 0)
2320 return _Res(0, __before
._M_node
);
2322 return _Res(__pos
._M_node
, __pos
._M_node
);
2325 return _M_get_insert_equal_pos(__k
);
2329 // ... then try after.
2330 iterator __after
= __pos
;
2331 if (__pos
._M_node
== _M_rightmost())
2332 return _Res(0, _M_rightmost());
2333 else if (!_M_impl
._M_key_compare(_S_key((++__after
)._M_node
), __k
))
2335 if (_S_right(__pos
._M_node
) == 0)
2336 return _Res(0, __pos
._M_node
);
2338 return _Res(__after
._M_node
, __after
._M_node
);
2345 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2346 typename _Compare
, typename _Alloc
>
2347 #if __cplusplus >= 201103L
2348 template<typename _Arg
, typename _NodeGen
>
2350 template<typename _NodeGen
>
2352 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2353 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2354 _M_insert_equal_(const_iterator __position
,
2355 #if __cplusplus >= 201103L
2360 _NodeGen
& __node_gen
)
2362 pair
<_Base_ptr
, _Base_ptr
> __res
2363 = _M_get_insert_hint_equal_pos(__position
, _KeyOfValue()(__v
));
2366 return _M_insert_(__res
.first
, __res
.second
,
2367 _GLIBCXX_FORWARD(_Arg
, __v
),
2370 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg
, __v
));
2373 #if __cplusplus >= 201103L
2374 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2375 typename _Compare
, typename _Alloc
>
2376 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2377 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2378 _M_insert_node(_Base_ptr __x
, _Base_ptr __p
, _Link_type __z
)
2380 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
2381 || _M_impl
._M_key_compare(_S_key(__z
),
2384 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2385 this->_M_impl
._M_header
);
2386 ++_M_impl
._M_node_count
;
2387 return iterator(__z
);
2390 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2391 typename _Compare
, typename _Alloc
>
2392 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2393 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2394 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
)
2396 bool __insert_left
= (__p
== _M_end()
2397 || !_M_impl
._M_key_compare(_S_key(__p
),
2400 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2401 this->_M_impl
._M_header
);
2402 ++_M_impl
._M_node_count
;
2403 return iterator(__z
);
2406 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2407 typename _Compare
, typename _Alloc
>
2408 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2409 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2410 _M_insert_equal_lower_node(_Link_type __z
)
2412 _Link_type __x
= _M_begin();
2413 _Base_ptr __y
= _M_end();
2417 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _S_key(__z
)) ?
2418 _S_left(__x
) : _S_right(__x
);
2420 return _M_insert_lower_node(__y
, __z
);
2423 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2424 typename _Compare
, typename _Alloc
>
2425 template<typename
... _Args
>
2426 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2427 _Compare
, _Alloc
>::iterator
, bool>
2428 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2429 _M_emplace_unique(_Args
&&... __args
)
2431 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2435 typedef pair
<iterator
, bool> _Res
;
2436 auto __res
= _M_get_insert_unique_pos(_S_key(__z
));
2438 return _Res(_M_insert_node(__res
.first
, __res
.second
, __z
), true);
2441 return _Res(iterator(__res
.first
), false);
2446 __throw_exception_again
;
2450 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2451 typename _Compare
, typename _Alloc
>
2452 template<typename
... _Args
>
2453 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2454 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2455 _M_emplace_equal(_Args
&&... __args
)
2457 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2461 auto __res
= _M_get_insert_equal_pos(_S_key(__z
));
2462 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2467 __throw_exception_again
;
2471 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2472 typename _Compare
, typename _Alloc
>
2473 template<typename
... _Args
>
2474 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2475 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2476 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
)
2478 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2482 auto __res
= _M_get_insert_hint_unique_pos(__pos
, _S_key(__z
));
2485 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2488 return iterator(__res
.first
);
2493 __throw_exception_again
;
2497 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2498 typename _Compare
, typename _Alloc
>
2499 template<typename
... _Args
>
2500 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2501 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2502 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
)
2504 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2508 auto __res
= _M_get_insert_hint_equal_pos(__pos
, _S_key(__z
));
2511 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2513 return _M_insert_equal_lower_node(__z
);
2518 __throw_exception_again
;
2524 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2525 typename _Compare
, typename _Alloc
>
2527 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2528 _M_erase_aux(const_iterator __position
)
2531 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
2532 (const_cast<_Base_ptr
>(__position
._M_node
),
2533 this->_M_impl
._M_header
));
2535 --_M_impl
._M_node_count
;
2538 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2539 typename _Compare
, typename _Alloc
>
2541 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2542 _M_erase_aux(const_iterator __first
, const_iterator __last
)
2544 if (__first
== begin() && __last
== end())
2547 while (__first
!= __last
)
2548 _M_erase_aux(__first
++);
2551 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2552 typename _Compare
, typename _Alloc
>
2553 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2554 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2555 erase(const _Key
& __x
)
2557 pair
<iterator
, iterator
> __p
= equal_range(__x
);
2558 const size_type __old_size
= size();
2559 _M_erase_aux(__p
.first
, __p
.second
);
2560 return __old_size
- size();
2563 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2564 typename _Compare
, typename _Alloc
>
2566 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2567 erase(const _Key
* __first
, const _Key
* __last
)
2569 while (__first
!= __last
)
2573 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2574 typename _Compare
, typename _Alloc
>
2575 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2576 _Compare
, _Alloc
>::iterator
2577 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2578 find(const _Key
& __k
)
2580 iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2581 return (__j
== end()
2582 || _M_impl
._M_key_compare(__k
,
2583 _S_key(__j
._M_node
))) ? end() : __j
;
2586 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2587 typename _Compare
, typename _Alloc
>
2588 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2589 _Compare
, _Alloc
>::const_iterator
2590 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2591 find(const _Key
& __k
) const
2593 const_iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2594 return (__j
== end()
2595 || _M_impl
._M_key_compare(__k
,
2596 _S_key(__j
._M_node
))) ? end() : __j
;
2599 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2600 typename _Compare
, typename _Alloc
>
2601 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2602 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2603 count(const _Key
& __k
) const
2605 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
2606 const size_type __n
= std::distance(__p
.first
, __p
.second
);
2610 _GLIBCXX_PURE
unsigned int
2611 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
2612 const _Rb_tree_node_base
* __root
) throw ();
2614 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2615 typename _Compare
, typename _Alloc
>
2617 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
2619 if (_M_impl
._M_node_count
== 0 || begin() == end())
2620 return _M_impl
._M_node_count
== 0 && begin() == end()
2621 && this->_M_impl
._M_header
._M_left
== _M_end()
2622 && this->_M_impl
._M_header
._M_right
== _M_end();
2624 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
2625 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
2627 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
2628 _Const_Link_type __L
= _S_left(__x
);
2629 _Const_Link_type __R
= _S_right(__x
);
2631 if (__x
->_M_color
== _S_red
)
2632 if ((__L
&& __L
->_M_color
== _S_red
)
2633 || (__R
&& __R
->_M_color
== _S_red
))
2636 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
2638 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
2641 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
2645 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2647 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2652 #if __cplusplus > 201402L
2653 // Allow access to internals of compatible _Rb_tree specializations.
2654 template<typename _Key
, typename _Val
, typename _Sel
, typename _Cmp1
,
2655 typename _Alloc
, typename _Cmp2
>
2656 struct _Rb_tree_merge_helper
<_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>,
2660 friend class _Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>;
2663 _S_get_impl(_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp2
, _Alloc
>& __tree
)
2664 { return __tree
._M_impl
; }
2668 _GLIBCXX_END_NAMESPACE_VERSION