1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001-2017 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
;
452 typedef _Rb_tree_node_base
* _Base_ptr
;
453 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
454 typedef _Rb_tree_node
<_Val
>* _Link_type
;
455 typedef const _Rb_tree_node
<_Val
>* _Const_Link_type
;
458 // Functor recycling a pool of nodes and using allocation once the pool
460 struct _Reuse_or_alloc_node
462 _Reuse_or_alloc_node(_Rb_tree
& __t
)
463 : _M_root(__t
._M_root()), _M_nodes(__t
._M_rightmost()), _M_t(__t
)
467 _M_root
->_M_parent
= 0;
469 if (_M_nodes
->_M_left
)
470 _M_nodes
= _M_nodes
->_M_left
;
476 #if __cplusplus >= 201103L
477 _Reuse_or_alloc_node(const _Reuse_or_alloc_node
&) = delete;
480 ~_Reuse_or_alloc_node()
481 { _M_t
._M_erase(static_cast<_Link_type
>(_M_root
)); }
483 template<typename _Arg
>
485 #if __cplusplus < 201103L
486 operator()(const _Arg
& __arg
)
488 operator()(_Arg
&& __arg
)
491 _Link_type __node
= static_cast<_Link_type
>(_M_extract());
494 _M_t
._M_destroy_node(__node
);
495 _M_t
._M_construct_node(__node
, _GLIBCXX_FORWARD(_Arg
, __arg
));
499 return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
));
509 _Base_ptr __node
= _M_nodes
;
510 _M_nodes
= _M_nodes
->_M_parent
;
513 if (_M_nodes
->_M_right
== __node
)
515 _M_nodes
->_M_right
= 0;
517 if (_M_nodes
->_M_left
)
519 _M_nodes
= _M_nodes
->_M_left
;
521 while (_M_nodes
->_M_right
)
522 _M_nodes
= _M_nodes
->_M_right
;
524 if (_M_nodes
->_M_left
)
525 _M_nodes
= _M_nodes
->_M_left
;
528 else // __node is on the left.
529 _M_nodes
->_M_left
= 0;
542 // Functor similar to the previous one but without any pool of nodes to
546 _Alloc_node(_Rb_tree
& __t
)
549 template<typename _Arg
>
551 #if __cplusplus < 201103L
552 operator()(const _Arg
& __arg
) const
554 operator()(_Arg
&& __arg
) const
556 { return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
)); }
563 typedef _Key key_type
;
564 typedef _Val value_type
;
565 typedef value_type
* pointer
;
566 typedef const value_type
* const_pointer
;
567 typedef value_type
& reference
;
568 typedef const value_type
& const_reference
;
569 typedef size_t size_type
;
570 typedef ptrdiff_t difference_type
;
571 typedef _Alloc allocator_type
;
574 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
575 { return this->_M_impl
; }
577 const _Node_allocator
&
578 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
579 { return this->_M_impl
; }
582 get_allocator() const _GLIBCXX_NOEXCEPT
583 { return allocator_type(_M_get_Node_allocator()); }
588 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
591 _M_put_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
592 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p
, 1); }
594 #if __cplusplus < 201103L
596 _M_construct_node(_Link_type __node
, const value_type
& __x
)
599 { get_allocator().construct(__node
->_M_valptr(), __x
); }
603 __throw_exception_again
;
608 _M_create_node(const value_type
& __x
)
610 _Link_type __tmp
= _M_get_node();
611 _M_construct_node(__tmp
, __x
);
616 _M_destroy_node(_Link_type __p
)
617 { get_allocator().destroy(__p
->_M_valptr()); }
619 template<typename
... _Args
>
621 _M_construct_node(_Link_type __node
, _Args
&&... __args
)
625 ::new(__node
) _Rb_tree_node
<_Val
>;
626 _Alloc_traits::construct(_M_get_Node_allocator(),
628 std::forward
<_Args
>(__args
)...);
632 __node
->~_Rb_tree_node
<_Val
>();
634 __throw_exception_again
;
638 template<typename
... _Args
>
640 _M_create_node(_Args
&&... __args
)
642 _Link_type __tmp
= _M_get_node();
643 _M_construct_node(__tmp
, std::forward
<_Args
>(__args
)...);
648 _M_destroy_node(_Link_type __p
) noexcept
650 _Alloc_traits::destroy(_M_get_Node_allocator(), __p
->_M_valptr());
651 __p
->~_Rb_tree_node
<_Val
>();
656 _M_drop_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
658 _M_destroy_node(__p
);
662 template<typename _NodeGen
>
664 _M_clone_node(_Const_Link_type __x
, _NodeGen
& __node_gen
)
666 _Link_type __tmp
= __node_gen(*__x
->_M_valptr());
667 __tmp
->_M_color
= __x
->_M_color
;
674 #if _GLIBCXX_INLINE_VERSION
675 template<typename _Key_compare
>
677 // Unused _Is_pod_comparator is kept as it is part of mangled name.
678 template<typename _Key_compare
,
679 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare
)>
682 : public _Node_allocator
683 , public _Rb_tree_key_compare
<_Key_compare
>
684 , public _Rb_tree_header
686 typedef _Rb_tree_key_compare
<_Key_compare
> _Base_key_compare
;
689 _GLIBCXX_NOEXCEPT_IF(
690 is_nothrow_default_constructible
<_Node_allocator
>::value
691 && is_nothrow_default_constructible
<_Base_key_compare
>::value
)
695 _Rb_tree_impl(const _Rb_tree_impl
& __x
)
696 : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x
))
697 , _Base_key_compare(__x
._M_key_compare
)
700 #if __cplusplus < 201103L
701 _Rb_tree_impl(const _Key_compare
& __comp
, const _Node_allocator
& __a
)
702 : _Node_allocator(__a
), _Base_key_compare(__comp
)
705 _Rb_tree_impl(_Rb_tree_impl
&&) = default;
707 _Rb_tree_impl(const _Key_compare
& __comp
, _Node_allocator
&& __a
)
708 : _Node_allocator(std::move(__a
)), _Base_key_compare(__comp
)
713 _Rb_tree_impl
<_Compare
> _M_impl
;
717 _M_root() _GLIBCXX_NOEXCEPT
718 { return this->_M_impl
._M_header
._M_parent
; }
721 _M_root() const _GLIBCXX_NOEXCEPT
722 { return this->_M_impl
._M_header
._M_parent
; }
725 _M_leftmost() _GLIBCXX_NOEXCEPT
726 { return this->_M_impl
._M_header
._M_left
; }
729 _M_leftmost() const _GLIBCXX_NOEXCEPT
730 { return this->_M_impl
._M_header
._M_left
; }
733 _M_rightmost() _GLIBCXX_NOEXCEPT
734 { return this->_M_impl
._M_header
._M_right
; }
737 _M_rightmost() const _GLIBCXX_NOEXCEPT
738 { return this->_M_impl
._M_header
._M_right
; }
741 _M_begin() _GLIBCXX_NOEXCEPT
742 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
745 _M_begin() const _GLIBCXX_NOEXCEPT
747 return static_cast<_Const_Link_type
>
748 (this->_M_impl
._M_header
._M_parent
);
752 _M_end() _GLIBCXX_NOEXCEPT
753 { return &this->_M_impl
._M_header
; }
756 _M_end() const _GLIBCXX_NOEXCEPT
757 { return &this->_M_impl
._M_header
; }
759 static const_reference
760 _S_value(_Const_Link_type __x
)
761 { return *__x
->_M_valptr(); }
764 _S_key(_Const_Link_type __x
)
765 { return _KeyOfValue()(_S_value(__x
)); }
768 _S_left(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
769 { return static_cast<_Link_type
>(__x
->_M_left
); }
771 static _Const_Link_type
772 _S_left(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
773 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
776 _S_right(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
777 { return static_cast<_Link_type
>(__x
->_M_right
); }
779 static _Const_Link_type
780 _S_right(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
781 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
783 static const_reference
784 _S_value(_Const_Base_ptr __x
)
785 { return *static_cast<_Const_Link_type
>(__x
)->_M_valptr(); }
788 _S_key(_Const_Base_ptr __x
)
789 { return _KeyOfValue()(_S_value(__x
)); }
792 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
793 { return _Rb_tree_node_base::_S_minimum(__x
); }
795 static _Const_Base_ptr
796 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
797 { return _Rb_tree_node_base::_S_minimum(__x
); }
800 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
801 { return _Rb_tree_node_base::_S_maximum(__x
); }
803 static _Const_Base_ptr
804 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
805 { return _Rb_tree_node_base::_S_maximum(__x
); }
808 typedef _Rb_tree_iterator
<value_type
> iterator
;
809 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
811 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
812 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
814 #if __cplusplus > 201402L
815 using node_type
= _Node_handle
<_Key
, _Val
, _Node_allocator
>;
816 using insert_return_type
= _Node_insert_return
<
817 conditional_t
<is_same_v
<_Key
, _Val
>, const_iterator
, iterator
>,
821 pair
<_Base_ptr
, _Base_ptr
>
822 _M_get_insert_unique_pos(const key_type
& __k
);
824 pair
<_Base_ptr
, _Base_ptr
>
825 _M_get_insert_equal_pos(const key_type
& __k
);
827 pair
<_Base_ptr
, _Base_ptr
>
828 _M_get_insert_hint_unique_pos(const_iterator __pos
,
829 const key_type
& __k
);
831 pair
<_Base_ptr
, _Base_ptr
>
832 _M_get_insert_hint_equal_pos(const_iterator __pos
,
833 const key_type
& __k
);
836 #if __cplusplus >= 201103L
837 template<typename _Arg
, typename _NodeGen
>
839 _M_insert_(_Base_ptr __x
, _Base_ptr __y
, _Arg
&& __v
, _NodeGen
&);
842 _M_insert_node(_Base_ptr __x
, _Base_ptr __y
, _Link_type __z
);
844 template<typename _Arg
>
846 _M_insert_lower(_Base_ptr __y
, _Arg
&& __v
);
848 template<typename _Arg
>
850 _M_insert_equal_lower(_Arg
&& __x
);
853 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
);
856 _M_insert_equal_lower_node(_Link_type __z
);
858 template<typename _NodeGen
>
860 _M_insert_(_Base_ptr __x
, _Base_ptr __y
,
861 const value_type
& __v
, _NodeGen
&);
863 // _GLIBCXX_RESOLVE_LIB_DEFECTS
864 // 233. Insertion hints in associative containers.
866 _M_insert_lower(_Base_ptr __y
, const value_type
& __v
);
869 _M_insert_equal_lower(const value_type
& __x
);
872 template<typename _NodeGen
>
874 _M_copy(_Const_Link_type __x
, _Base_ptr __p
, _NodeGen
&);
876 template<typename _NodeGen
>
878 _M_copy(const _Rb_tree
& __x
, _NodeGen
& __gen
)
880 _Link_type __root
= _M_copy(__x
._M_begin(), _M_end(), __gen
);
881 _M_leftmost() = _S_minimum(__root
);
882 _M_rightmost() = _S_maximum(__root
);
883 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
888 _M_copy(const _Rb_tree
& __x
)
890 _Alloc_node
__an(*this);
891 return _M_copy(__x
, __an
);
895 _M_erase(_Link_type __x
);
898 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
902 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
903 const _Key
& __k
) const;
906 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
910 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
911 const _Key
& __k
) const;
914 // allocation/deallocation
915 #if __cplusplus < 201103L
918 _Rb_tree() = default;
921 _Rb_tree(const _Compare
& __comp
,
922 const allocator_type
& __a
= allocator_type())
923 : _M_impl(__comp
, _Node_allocator(__a
)) { }
925 _Rb_tree(const _Rb_tree
& __x
)
926 : _M_impl(__x
._M_impl
)
928 if (__x
._M_root() != 0)
929 _M_root() = _M_copy(__x
);
932 #if __cplusplus >= 201103L
933 _Rb_tree(const allocator_type
& __a
)
934 : _M_impl(_Compare(), _Node_allocator(__a
))
937 _Rb_tree(const _Rb_tree
& __x
, const allocator_type
& __a
)
938 : _M_impl(__x
._M_impl
._M_key_compare
, _Node_allocator(__a
))
940 if (__x
._M_root() != nullptr)
941 _M_root() = _M_copy(__x
);
944 _Rb_tree(_Rb_tree
&&) = default;
946 _Rb_tree(_Rb_tree
&& __x
, const allocator_type
& __a
)
947 : _Rb_tree(std::move(__x
), _Node_allocator(__a
))
950 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
);
953 ~_Rb_tree() _GLIBCXX_NOEXCEPT
954 { _M_erase(_M_begin()); }
957 operator=(const _Rb_tree
& __x
);
962 { return _M_impl
._M_key_compare
; }
965 begin() _GLIBCXX_NOEXCEPT
966 { return iterator(this->_M_impl
._M_header
._M_left
); }
969 begin() const _GLIBCXX_NOEXCEPT
970 { return const_iterator(this->_M_impl
._M_header
._M_left
); }
973 end() _GLIBCXX_NOEXCEPT
974 { return iterator(&this->_M_impl
._M_header
); }
977 end() const _GLIBCXX_NOEXCEPT
978 { return const_iterator(&this->_M_impl
._M_header
); }
981 rbegin() _GLIBCXX_NOEXCEPT
982 { return reverse_iterator(end()); }
984 const_reverse_iterator
985 rbegin() const _GLIBCXX_NOEXCEPT
986 { return const_reverse_iterator(end()); }
989 rend() _GLIBCXX_NOEXCEPT
990 { return reverse_iterator(begin()); }
992 const_reverse_iterator
993 rend() const _GLIBCXX_NOEXCEPT
994 { return const_reverse_iterator(begin()); }
997 empty() const _GLIBCXX_NOEXCEPT
998 { return _M_impl
._M_node_count
== 0; }
1001 size() const _GLIBCXX_NOEXCEPT
1002 { return _M_impl
._M_node_count
; }
1005 max_size() const _GLIBCXX_NOEXCEPT
1006 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
1010 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
);
1013 #if __cplusplus >= 201103L
1014 template<typename _Arg
>
1015 pair
<iterator
, bool>
1016 _M_insert_unique(_Arg
&& __x
);
1018 template<typename _Arg
>
1020 _M_insert_equal(_Arg
&& __x
);
1022 template<typename _Arg
, typename _NodeGen
>
1024 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
1026 template<typename _Arg
>
1028 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
)
1030 _Alloc_node
__an(*this);
1031 return _M_insert_unique_(__pos
, std::forward
<_Arg
>(__x
), __an
);
1034 template<typename _Arg
, typename _NodeGen
>
1036 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
1038 template<typename _Arg
>
1040 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
)
1042 _Alloc_node
__an(*this);
1043 return _M_insert_equal_(__pos
, std::forward
<_Arg
>(__x
), __an
);
1046 template<typename
... _Args
>
1047 pair
<iterator
, bool>
1048 _M_emplace_unique(_Args
&&... __args
);
1050 template<typename
... _Args
>
1052 _M_emplace_equal(_Args
&&... __args
);
1054 template<typename
... _Args
>
1056 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
);
1058 template<typename
... _Args
>
1060 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
);
1062 pair
<iterator
, bool>
1063 _M_insert_unique(const value_type
& __x
);
1066 _M_insert_equal(const value_type
& __x
);
1068 template<typename _NodeGen
>
1070 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
,
1074 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
)
1076 _Alloc_node
__an(*this);
1077 return _M_insert_unique_(__pos
, __x
, __an
);
1080 template<typename _NodeGen
>
1082 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
,
1085 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
)
1087 _Alloc_node
__an(*this);
1088 return _M_insert_equal_(__pos
, __x
, __an
);
1092 template<typename _InputIterator
>
1094 _M_insert_unique(_InputIterator __first
, _InputIterator __last
);
1096 template<typename _InputIterator
>
1098 _M_insert_equal(_InputIterator __first
, _InputIterator __last
);
1102 _M_erase_aux(const_iterator __position
);
1105 _M_erase_aux(const_iterator __first
, const_iterator __last
);
1108 #if __cplusplus >= 201103L
1109 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1110 // DR 130. Associative erase should return an iterator.
1111 _GLIBCXX_ABI_TAG_CXX11
1113 erase(const_iterator __position
)
1115 __glibcxx_assert(__position
!= end());
1116 const_iterator __result
= __position
;
1118 _M_erase_aux(__position
);
1119 return __result
._M_const_cast();
1123 _GLIBCXX_ABI_TAG_CXX11
1125 erase(iterator __position
)
1127 __glibcxx_assert(__position
!= end());
1128 iterator __result
= __position
;
1130 _M_erase_aux(__position
);
1135 erase(iterator __position
)
1137 __glibcxx_assert(__position
!= end());
1138 _M_erase_aux(__position
);
1142 erase(const_iterator __position
)
1144 __glibcxx_assert(__position
!= end());
1145 _M_erase_aux(__position
);
1149 erase(const key_type
& __x
);
1151 #if __cplusplus >= 201103L
1152 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1153 // DR 130. Associative erase should return an iterator.
1154 _GLIBCXX_ABI_TAG_CXX11
1156 erase(const_iterator __first
, const_iterator __last
)
1158 _M_erase_aux(__first
, __last
);
1159 return __last
._M_const_cast();
1163 erase(iterator __first
, iterator __last
)
1164 { _M_erase_aux(__first
, __last
); }
1167 erase(const_iterator __first
, const_iterator __last
)
1168 { _M_erase_aux(__first
, __last
); }
1171 erase(const key_type
* __first
, const key_type
* __last
);
1174 clear() _GLIBCXX_NOEXCEPT
1176 _M_erase(_M_begin());
1182 find(const key_type
& __k
);
1185 find(const key_type
& __k
) const;
1188 count(const key_type
& __k
) const;
1191 lower_bound(const key_type
& __k
)
1192 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1195 lower_bound(const key_type
& __k
) const
1196 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1199 upper_bound(const key_type
& __k
)
1200 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1203 upper_bound(const key_type
& __k
) const
1204 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1206 pair
<iterator
, iterator
>
1207 equal_range(const key_type
& __k
);
1209 pair
<const_iterator
, const_iterator
>
1210 equal_range(const key_type
& __k
) const;
1212 #if __cplusplus > 201103L
1213 template<typename _Kt
,
1215 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1217 _M_find_tr(const _Kt
& __k
)
1219 const _Rb_tree
* __const_this
= this;
1220 return __const_this
->_M_find_tr(__k
)._M_const_cast();
1223 template<typename _Kt
,
1225 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1227 _M_find_tr(const _Kt
& __k
) const
1229 auto __j
= _M_lower_bound_tr(__k
);
1230 if (__j
!= end() && _M_impl
._M_key_compare(__k
, _S_key(__j
._M_node
)))
1235 template<typename _Kt
,
1237 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1239 _M_count_tr(const _Kt
& __k
) const
1241 auto __p
= _M_equal_range_tr(__k
);
1242 return std::distance(__p
.first
, __p
.second
);
1245 template<typename _Kt
,
1247 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1249 _M_lower_bound_tr(const _Kt
& __k
)
1251 const _Rb_tree
* __const_this
= this;
1252 return __const_this
->_M_lower_bound_tr(__k
)._M_const_cast();
1255 template<typename _Kt
,
1257 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1259 _M_lower_bound_tr(const _Kt
& __k
) const
1261 auto __x
= _M_begin();
1262 auto __y
= _M_end();
1264 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1270 __x
= _S_right(__x
);
1271 return const_iterator(__y
);
1274 template<typename _Kt
,
1276 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1278 _M_upper_bound_tr(const _Kt
& __k
)
1280 const _Rb_tree
* __const_this
= this;
1281 return __const_this
->_M_upper_bound_tr(__k
)._M_const_cast();
1284 template<typename _Kt
,
1286 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1288 _M_upper_bound_tr(const _Kt
& __k
) const
1290 auto __x
= _M_begin();
1291 auto __y
= _M_end();
1293 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1299 __x
= _S_right(__x
);
1300 return const_iterator(__y
);
1303 template<typename _Kt
,
1305 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1306 pair
<iterator
, iterator
>
1307 _M_equal_range_tr(const _Kt
& __k
)
1309 const _Rb_tree
* __const_this
= this;
1310 auto __ret
= __const_this
->_M_equal_range_tr(__k
);
1311 return { __ret
.first
._M_const_cast(), __ret
.second
._M_const_cast() };
1314 template<typename _Kt
,
1316 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1317 pair
<const_iterator
, const_iterator
>
1318 _M_equal_range_tr(const _Kt
& __k
) const
1320 auto __low
= _M_lower_bound_tr(__k
);
1321 auto __high
= __low
;
1322 auto& __cmp
= _M_impl
._M_key_compare
;
1323 while (__high
!= end() && !__cmp(__k
, _S_key(__high
._M_node
)))
1325 return { __low
, __high
};
1331 __rb_verify() const;
1333 #if __cplusplus >= 201103L
1335 operator=(_Rb_tree
&&)
1336 noexcept(_Alloc_traits::_S_nothrow_move()
1337 && is_nothrow_move_assignable
<_Compare
>::value
);
1339 template<typename _Iterator
>
1341 _M_assign_unique(_Iterator
, _Iterator
);
1343 template<typename _Iterator
>
1345 _M_assign_equal(_Iterator
, _Iterator
);
1348 // Move elements from container with equal allocator.
1350 _M_move_data(_Rb_tree
& __x
, std::true_type
)
1351 { _M_impl
._M_move_data(__x
._M_impl
); }
1353 // Move elements from container with possibly non-equal allocator,
1354 // which might result in a copy not a move.
1356 _M_move_data(_Rb_tree
&, std::false_type
);
1358 // Move assignment from container with equal allocator.
1360 _M_move_assign(_Rb_tree
&, std::true_type
);
1362 // Move assignment from container with possibly non-equal allocator,
1363 // which might result in a copy not a move.
1365 _M_move_assign(_Rb_tree
&, std::false_type
);
1368 #if __cplusplus > 201402L
1370 /// Re-insert an extracted node.
1372 _M_reinsert_node_unique(node_type
&& __nh
)
1374 insert_return_type __ret
;
1376 __ret
.position
= end();
1379 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1381 auto __res
= _M_get_insert_unique_pos(__nh
._M_key());
1385 = _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1386 __nh
._M_ptr
= nullptr;
1387 __ret
.inserted
= true;
1391 __ret
.node
= std::move(__nh
);
1392 __ret
.position
= iterator(__res
.first
);
1393 __ret
.inserted
= false;
1399 /// Re-insert an extracted node.
1401 _M_reinsert_node_equal(node_type
&& __nh
)
1408 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1409 auto __res
= _M_get_insert_equal_pos(__nh
._M_key());
1411 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1413 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1414 __nh
._M_ptr
= nullptr;
1419 /// Re-insert an extracted node.
1421 _M_reinsert_node_hint_unique(const_iterator __hint
, node_type
&& __nh
)
1428 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1429 auto __res
= _M_get_insert_hint_unique_pos(__hint
, __nh
._M_key());
1432 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1433 __nh
._M_ptr
= nullptr;
1436 __ret
= iterator(__res
.first
);
1441 /// Re-insert an extracted node.
1443 _M_reinsert_node_hint_equal(const_iterator __hint
, node_type
&& __nh
)
1450 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1451 auto __res
= _M_get_insert_hint_equal_pos(__hint
, __nh
._M_key());
1453 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1455 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1456 __nh
._M_ptr
= nullptr;
1463 extract(const_iterator __pos
)
1465 auto __ptr
= _Rb_tree_rebalance_for_erase(
1466 __pos
._M_const_cast()._M_node
, _M_impl
._M_header
);
1467 --_M_impl
._M_node_count
;
1468 return { static_cast<_Link_type
>(__ptr
), _M_get_Node_allocator() };
1473 extract(const key_type
& __k
)
1476 auto __pos
= find(__k
);
1478 __nh
= extract(const_iterator(__pos
));
1482 template<typename _Compare2
>
1483 using _Compatible_tree
1484 = _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare2
, _Alloc
>;
1486 template<typename
, typename
>
1487 friend class _Rb_tree_merge_helper
;
1489 /// Merge from a compatible container into one with unique keys.
1490 template<typename _Compare2
>
1492 _M_merge_unique(_Compatible_tree
<_Compare2
>& __src
) noexcept
1494 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1495 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1498 auto __res
= _M_get_insert_unique_pos(_KeyOfValue()(*__pos
));
1501 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1502 auto __ptr
= _Rb_tree_rebalance_for_erase(
1503 __pos
._M_node
, __src_impl
._M_header
);
1504 --__src_impl
._M_node_count
;
1505 _M_insert_node(__res
.first
, __res
.second
,
1506 static_cast<_Link_type
>(__ptr
));
1511 /// Merge from a compatible container into one with equivalent keys.
1512 template<typename _Compare2
>
1514 _M_merge_equal(_Compatible_tree
<_Compare2
>& __src
) noexcept
1516 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1517 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1520 auto __res
= _M_get_insert_equal_pos(_KeyOfValue()(*__pos
));
1523 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1524 auto __ptr
= _Rb_tree_rebalance_for_erase(
1525 __pos
._M_node
, __src_impl
._M_header
);
1526 --__src_impl
._M_node_count
;
1527 _M_insert_node(__res
.first
, __res
.second
,
1528 static_cast<_Link_type
>(__ptr
));
1535 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1536 typename _Compare
, typename _Alloc
>
1538 operator==(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1539 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1541 return __x
.size() == __y
.size()
1542 && std::equal(__x
.begin(), __x
.end(), __y
.begin());
1545 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1546 typename _Compare
, typename _Alloc
>
1548 operator<(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1549 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1551 return std::lexicographical_compare(__x
.begin(), __x
.end(),
1552 __y
.begin(), __y
.end());
1555 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1556 typename _Compare
, typename _Alloc
>
1558 operator!=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1559 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1560 { return !(__x
== __y
); }
1562 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1563 typename _Compare
, typename _Alloc
>
1565 operator>(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1566 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1567 { return __y
< __x
; }
1569 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1570 typename _Compare
, typename _Alloc
>
1572 operator<=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1573 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1574 { return !(__y
< __x
); }
1576 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1577 typename _Compare
, typename _Alloc
>
1579 operator>=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1580 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1581 { return !(__x
< __y
); }
1583 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1584 typename _Compare
, typename _Alloc
>
1586 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1587 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1590 #if __cplusplus >= 201103L
1591 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1592 typename _Compare
, typename _Alloc
>
1593 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1594 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
)
1595 : _M_impl(__x
._M_impl
._M_key_compare
, std::move(__a
))
1597 using __eq
= typename
_Alloc_traits::is_always_equal
;
1598 if (__x
._M_root() != nullptr)
1599 _M_move_data(__x
, __eq());
1602 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1603 typename _Compare
, typename _Alloc
>
1605 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1606 _M_move_data(_Rb_tree
& __x
, std::false_type
)
1608 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1609 _M_move_data(__x
, std::true_type());
1612 _Alloc_node
__an(*this);
1614 [&__an
](const value_type
& __cval
)
1616 auto& __val
= const_cast<value_type
&>(__cval
);
1617 return __an(std::move_if_noexcept(__val
));
1619 _M_root() = _M_copy(__x
, __lbd
);
1623 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1624 typename _Compare
, typename _Alloc
>
1626 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1627 _M_move_assign(_Rb_tree
& __x
, true_type
)
1630 if (__x
._M_root() != nullptr)
1631 _M_move_data(__x
, std::true_type());
1632 std::__alloc_on_move(_M_get_Node_allocator(),
1633 __x
._M_get_Node_allocator());
1636 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1637 typename _Compare
, typename _Alloc
>
1639 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1640 _M_move_assign(_Rb_tree
& __x
, false_type
)
1642 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1643 return _M_move_assign(__x
, true_type
{});
1645 // Try to move each node reusing existing nodes and copying __x nodes
1647 _Reuse_or_alloc_node
__roan(*this);
1649 if (__x
._M_root() != nullptr)
1652 [&__roan
](const value_type
& __cval
)
1654 auto& __val
= const_cast<value_type
&>(__cval
);
1655 return __roan(std::move_if_noexcept(__val
));
1657 _M_root() = _M_copy(__x
, __lbd
);
1662 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1663 typename _Compare
, typename _Alloc
>
1664 inline _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1665 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1666 operator=(_Rb_tree
&& __x
)
1667 noexcept(_Alloc_traits::_S_nothrow_move()
1668 && is_nothrow_move_assignable
<_Compare
>::value
)
1670 _M_impl
._M_key_compare
= std::move(__x
._M_impl
._M_key_compare
);
1671 _M_move_assign(__x
, __bool_constant
<_Alloc_traits::_S_nothrow_move()>());
1675 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1676 typename _Compare
, typename _Alloc
>
1677 template<typename _Iterator
>
1679 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1680 _M_assign_unique(_Iterator __first
, _Iterator __last
)
1682 _Reuse_or_alloc_node
__roan(*this);
1684 for (; __first
!= __last
; ++__first
)
1685 _M_insert_unique_(end(), *__first
, __roan
);
1688 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1689 typename _Compare
, typename _Alloc
>
1690 template<typename _Iterator
>
1692 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1693 _M_assign_equal(_Iterator __first
, _Iterator __last
)
1695 _Reuse_or_alloc_node
__roan(*this);
1697 for (; __first
!= __last
; ++__first
)
1698 _M_insert_equal_(end(), *__first
, __roan
);
1702 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1703 typename _Compare
, typename _Alloc
>
1704 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1705 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1706 operator=(const _Rb_tree
& __x
)
1710 // Note that _Key may be a constant type.
1711 #if __cplusplus >= 201103L
1712 if (_Alloc_traits::_S_propagate_on_copy_assign())
1714 auto& __this_alloc
= this->_M_get_Node_allocator();
1715 auto& __that_alloc
= __x
._M_get_Node_allocator();
1716 if (!_Alloc_traits::_S_always_equal()
1717 && __this_alloc
!= __that_alloc
)
1719 // Replacement allocator cannot free existing storage, we need
1720 // to erase nodes first.
1722 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1727 _Reuse_or_alloc_node
__roan(*this);
1729 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
1730 if (__x
._M_root() != 0)
1731 _M_root() = _M_copy(__x
, __roan
);
1737 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1738 typename _Compare
, typename _Alloc
>
1739 #if __cplusplus >= 201103L
1740 template<typename _Arg
, typename _NodeGen
>
1742 template<typename _NodeGen
>
1744 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1745 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1746 _M_insert_(_Base_ptr __x
, _Base_ptr __p
,
1747 #if __cplusplus >= 201103L
1752 _NodeGen
& __node_gen
)
1754 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
1755 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
1758 _Link_type __z
= __node_gen(_GLIBCXX_FORWARD(_Arg
, __v
));
1760 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1761 this->_M_impl
._M_header
);
1762 ++_M_impl
._M_node_count
;
1763 return iterator(__z
);
1766 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1767 typename _Compare
, typename _Alloc
>
1768 #if __cplusplus >= 201103L
1769 template<typename _Arg
>
1771 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1772 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1773 #if __cplusplus >= 201103L
1774 _M_insert_lower(_Base_ptr __p
, _Arg
&& __v
)
1776 _M_insert_lower(_Base_ptr __p
, const _Val
& __v
)
1779 bool __insert_left
= (__p
== _M_end()
1780 || !_M_impl
._M_key_compare(_S_key(__p
),
1781 _KeyOfValue()(__v
)));
1783 _Link_type __z
= _M_create_node(_GLIBCXX_FORWARD(_Arg
, __v
));
1785 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1786 this->_M_impl
._M_header
);
1787 ++_M_impl
._M_node_count
;
1788 return iterator(__z
);
1791 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1792 typename _Compare
, typename _Alloc
>
1793 #if __cplusplus >= 201103L
1794 template<typename _Arg
>
1796 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1797 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1798 #if __cplusplus >= 201103L
1799 _M_insert_equal_lower(_Arg
&& __v
)
1801 _M_insert_equal_lower(const _Val
& __v
)
1804 _Link_type __x
= _M_begin();
1805 _Base_ptr __y
= _M_end();
1809 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _KeyOfValue()(__v
)) ?
1810 _S_left(__x
) : _S_right(__x
);
1812 return _M_insert_lower(__y
, _GLIBCXX_FORWARD(_Arg
, __v
));
1815 template<typename _Key
, typename _Val
, typename _KoV
,
1816 typename _Compare
, typename _Alloc
>
1817 template<typename _NodeGen
>
1818 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1819 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
1820 _M_copy(_Const_Link_type __x
, _Base_ptr __p
, _NodeGen
& __node_gen
)
1822 // Structural copy. __x and __p must be non-null.
1823 _Link_type __top
= _M_clone_node(__x
, __node_gen
);
1824 __top
->_M_parent
= __p
;
1829 __top
->_M_right
= _M_copy(_S_right(__x
), __top
, __node_gen
);
1835 _Link_type __y
= _M_clone_node(__x
, __node_gen
);
1837 __y
->_M_parent
= __p
;
1839 __y
->_M_right
= _M_copy(_S_right(__x
), __y
, __node_gen
);
1847 __throw_exception_again
;
1852 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1853 typename _Compare
, typename _Alloc
>
1855 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1856 _M_erase(_Link_type __x
)
1858 // Erase without rebalancing.
1861 _M_erase(_S_right(__x
));
1862 _Link_type __y
= _S_left(__x
);
1868 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1869 typename _Compare
, typename _Alloc
>
1870 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1871 _Compare
, _Alloc
>::iterator
1872 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1873 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
1877 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1878 __y
= __x
, __x
= _S_left(__x
);
1880 __x
= _S_right(__x
);
1881 return iterator(__y
);
1884 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1885 typename _Compare
, typename _Alloc
>
1886 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1887 _Compare
, _Alloc
>::const_iterator
1888 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1889 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1890 const _Key
& __k
) const
1893 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1894 __y
= __x
, __x
= _S_left(__x
);
1896 __x
= _S_right(__x
);
1897 return const_iterator(__y
);
1900 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1901 typename _Compare
, typename _Alloc
>
1902 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1903 _Compare
, _Alloc
>::iterator
1904 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1905 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
1909 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1910 __y
= __x
, __x
= _S_left(__x
);
1912 __x
= _S_right(__x
);
1913 return iterator(__y
);
1916 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1917 typename _Compare
, typename _Alloc
>
1918 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1919 _Compare
, _Alloc
>::const_iterator
1920 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1921 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1922 const _Key
& __k
) const
1925 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1926 __y
= __x
, __x
= _S_left(__x
);
1928 __x
= _S_right(__x
);
1929 return const_iterator(__y
);
1932 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1933 typename _Compare
, typename _Alloc
>
1934 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1935 _Compare
, _Alloc
>::iterator
,
1936 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1937 _Compare
, _Alloc
>::iterator
>
1938 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1939 equal_range(const _Key
& __k
)
1941 _Link_type __x
= _M_begin();
1942 _Base_ptr __y
= _M_end();
1945 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1946 __x
= _S_right(__x
);
1947 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1948 __y
= __x
, __x
= _S_left(__x
);
1951 _Link_type
__xu(__x
);
1952 _Base_ptr
__yu(__y
);
1953 __y
= __x
, __x
= _S_left(__x
);
1954 __xu
= _S_right(__xu
);
1955 return pair
<iterator
,
1956 iterator
>(_M_lower_bound(__x
, __y
, __k
),
1957 _M_upper_bound(__xu
, __yu
, __k
));
1960 return pair
<iterator
, iterator
>(iterator(__y
),
1964 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1965 typename _Compare
, typename _Alloc
>
1966 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1967 _Compare
, _Alloc
>::const_iterator
,
1968 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1969 _Compare
, _Alloc
>::const_iterator
>
1970 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1971 equal_range(const _Key
& __k
) const
1973 _Const_Link_type __x
= _M_begin();
1974 _Const_Base_ptr __y
= _M_end();
1977 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1978 __x
= _S_right(__x
);
1979 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1980 __y
= __x
, __x
= _S_left(__x
);
1983 _Const_Link_type
__xu(__x
);
1984 _Const_Base_ptr
__yu(__y
);
1985 __y
= __x
, __x
= _S_left(__x
);
1986 __xu
= _S_right(__xu
);
1987 return pair
<const_iterator
,
1988 const_iterator
>(_M_lower_bound(__x
, __y
, __k
),
1989 _M_upper_bound(__xu
, __yu
, __k
));
1992 return pair
<const_iterator
, const_iterator
>(const_iterator(__y
),
1993 const_iterator(__y
));
1996 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1997 typename _Compare
, typename _Alloc
>
1999 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2001 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
)
2005 if (__t
._M_root() != 0)
2006 _M_impl
._M_move_data(__t
._M_impl
);
2008 else if (__t
._M_root() == 0)
2009 __t
._M_impl
._M_move_data(_M_impl
);
2012 std::swap(_M_root(),__t
._M_root());
2013 std::swap(_M_leftmost(),__t
._M_leftmost());
2014 std::swap(_M_rightmost(),__t
._M_rightmost());
2016 _M_root()->_M_parent
= _M_end();
2017 __t
._M_root()->_M_parent
= __t
._M_end();
2018 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
2020 // No need to swap header's color as it does not change.
2021 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
2023 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2024 __t
._M_get_Node_allocator());
2027 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2028 typename _Compare
, typename _Alloc
>
2029 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2030 _Compare
, _Alloc
>::_Base_ptr
,
2031 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2032 _Compare
, _Alloc
>::_Base_ptr
>
2033 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2034 _M_get_insert_unique_pos(const key_type
& __k
)
2036 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2037 _Link_type __x
= _M_begin();
2038 _Base_ptr __y
= _M_end();
2043 __comp
= _M_impl
._M_key_compare(__k
, _S_key(__x
));
2044 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
2046 iterator __j
= iterator(__y
);
2050 return _Res(__x
, __y
);
2054 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), __k
))
2055 return _Res(__x
, __y
);
2056 return _Res(__j
._M_node
, 0);
2059 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2060 typename _Compare
, typename _Alloc
>
2061 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2062 _Compare
, _Alloc
>::_Base_ptr
,
2063 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2064 _Compare
, _Alloc
>::_Base_ptr
>
2065 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2066 _M_get_insert_equal_pos(const key_type
& __k
)
2068 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2069 _Link_type __x
= _M_begin();
2070 _Base_ptr __y
= _M_end();
2074 __x
= _M_impl
._M_key_compare(__k
, _S_key(__x
)) ?
2075 _S_left(__x
) : _S_right(__x
);
2077 return _Res(__x
, __y
);
2080 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2081 typename _Compare
, typename _Alloc
>
2082 #if __cplusplus >= 201103L
2083 template<typename _Arg
>
2085 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2086 _Compare
, _Alloc
>::iterator
, bool>
2087 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2088 #if __cplusplus >= 201103L
2089 _M_insert_unique(_Arg
&& __v
)
2091 _M_insert_unique(const _Val
& __v
)
2094 typedef pair
<iterator
, bool> _Res
;
2095 pair
<_Base_ptr
, _Base_ptr
> __res
2096 = _M_get_insert_unique_pos(_KeyOfValue()(__v
));
2100 _Alloc_node
__an(*this);
2101 return _Res(_M_insert_(__res
.first
, __res
.second
,
2102 _GLIBCXX_FORWARD(_Arg
, __v
), __an
),
2106 return _Res(iterator(__res
.first
), false);
2109 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2110 typename _Compare
, typename _Alloc
>
2111 #if __cplusplus >= 201103L
2112 template<typename _Arg
>
2114 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2115 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2116 #if __cplusplus >= 201103L
2117 _M_insert_equal(_Arg
&& __v
)
2119 _M_insert_equal(const _Val
& __v
)
2122 pair
<_Base_ptr
, _Base_ptr
> __res
2123 = _M_get_insert_equal_pos(_KeyOfValue()(__v
));
2124 _Alloc_node
__an(*this);
2125 return _M_insert_(__res
.first
, __res
.second
,
2126 _GLIBCXX_FORWARD(_Arg
, __v
), __an
);
2129 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2130 typename _Compare
, typename _Alloc
>
2131 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2132 _Compare
, _Alloc
>::_Base_ptr
,
2133 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2134 _Compare
, _Alloc
>::_Base_ptr
>
2135 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2136 _M_get_insert_hint_unique_pos(const_iterator __position
,
2137 const key_type
& __k
)
2139 iterator __pos
= __position
._M_const_cast();
2140 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2143 if (__pos
._M_node
== _M_end())
2146 && _M_impl
._M_key_compare(_S_key(_M_rightmost()), __k
))
2147 return _Res(0, _M_rightmost());
2149 return _M_get_insert_unique_pos(__k
);
2151 else if (_M_impl
._M_key_compare(__k
, _S_key(__pos
._M_node
)))
2153 // First, try before...
2154 iterator __before
= __pos
;
2155 if (__pos
._M_node
== _M_leftmost()) // begin()
2156 return _Res(_M_leftmost(), _M_leftmost());
2157 else if (_M_impl
._M_key_compare(_S_key((--__before
)._M_node
), __k
))
2159 if (_S_right(__before
._M_node
) == 0)
2160 return _Res(0, __before
._M_node
);
2162 return _Res(__pos
._M_node
, __pos
._M_node
);
2165 return _M_get_insert_unique_pos(__k
);
2167 else if (_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2169 // ... then try after.
2170 iterator __after
= __pos
;
2171 if (__pos
._M_node
== _M_rightmost())
2172 return _Res(0, _M_rightmost());
2173 else if (_M_impl
._M_key_compare(__k
, _S_key((++__after
)._M_node
)))
2175 if (_S_right(__pos
._M_node
) == 0)
2176 return _Res(0, __pos
._M_node
);
2178 return _Res(__after
._M_node
, __after
._M_node
);
2181 return _M_get_insert_unique_pos(__k
);
2185 return _Res(__pos
._M_node
, 0);
2188 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2189 typename _Compare
, typename _Alloc
>
2190 #if __cplusplus >= 201103L
2191 template<typename _Arg
, typename _NodeGen
>
2193 template<typename _NodeGen
>
2195 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2196 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2197 _M_insert_unique_(const_iterator __position
,
2198 #if __cplusplus >= 201103L
2203 _NodeGen
& __node_gen
)
2205 pair
<_Base_ptr
, _Base_ptr
> __res
2206 = _M_get_insert_hint_unique_pos(__position
, _KeyOfValue()(__v
));
2209 return _M_insert_(__res
.first
, __res
.second
,
2210 _GLIBCXX_FORWARD(_Arg
, __v
),
2212 return iterator(__res
.first
);
2215 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2216 typename _Compare
, typename _Alloc
>
2217 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2218 _Compare
, _Alloc
>::_Base_ptr
,
2219 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2220 _Compare
, _Alloc
>::_Base_ptr
>
2221 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2222 _M_get_insert_hint_equal_pos(const_iterator __position
, const key_type
& __k
)
2224 iterator __pos
= __position
._M_const_cast();
2225 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2228 if (__pos
._M_node
== _M_end())
2231 && !_M_impl
._M_key_compare(__k
, _S_key(_M_rightmost())))
2232 return _Res(0, _M_rightmost());
2234 return _M_get_insert_equal_pos(__k
);
2236 else if (!_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2238 // First, try before...
2239 iterator __before
= __pos
;
2240 if (__pos
._M_node
== _M_leftmost()) // begin()
2241 return _Res(_M_leftmost(), _M_leftmost());
2242 else if (!_M_impl
._M_key_compare(__k
, _S_key((--__before
)._M_node
)))
2244 if (_S_right(__before
._M_node
) == 0)
2245 return _Res(0, __before
._M_node
);
2247 return _Res(__pos
._M_node
, __pos
._M_node
);
2250 return _M_get_insert_equal_pos(__k
);
2254 // ... then try after.
2255 iterator __after
= __pos
;
2256 if (__pos
._M_node
== _M_rightmost())
2257 return _Res(0, _M_rightmost());
2258 else if (!_M_impl
._M_key_compare(_S_key((++__after
)._M_node
), __k
))
2260 if (_S_right(__pos
._M_node
) == 0)
2261 return _Res(0, __pos
._M_node
);
2263 return _Res(__after
._M_node
, __after
._M_node
);
2270 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2271 typename _Compare
, typename _Alloc
>
2272 #if __cplusplus >= 201103L
2273 template<typename _Arg
, typename _NodeGen
>
2275 template<typename _NodeGen
>
2277 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2278 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2279 _M_insert_equal_(const_iterator __position
,
2280 #if __cplusplus >= 201103L
2285 _NodeGen
& __node_gen
)
2287 pair
<_Base_ptr
, _Base_ptr
> __res
2288 = _M_get_insert_hint_equal_pos(__position
, _KeyOfValue()(__v
));
2291 return _M_insert_(__res
.first
, __res
.second
,
2292 _GLIBCXX_FORWARD(_Arg
, __v
),
2295 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg
, __v
));
2298 #if __cplusplus >= 201103L
2299 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2300 typename _Compare
, typename _Alloc
>
2301 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2302 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2303 _M_insert_node(_Base_ptr __x
, _Base_ptr __p
, _Link_type __z
)
2305 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
2306 || _M_impl
._M_key_compare(_S_key(__z
),
2309 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2310 this->_M_impl
._M_header
);
2311 ++_M_impl
._M_node_count
;
2312 return iterator(__z
);
2315 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2316 typename _Compare
, typename _Alloc
>
2317 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2318 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2319 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
)
2321 bool __insert_left
= (__p
== _M_end()
2322 || !_M_impl
._M_key_compare(_S_key(__p
),
2325 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2326 this->_M_impl
._M_header
);
2327 ++_M_impl
._M_node_count
;
2328 return iterator(__z
);
2331 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2332 typename _Compare
, typename _Alloc
>
2333 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2334 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2335 _M_insert_equal_lower_node(_Link_type __z
)
2337 _Link_type __x
= _M_begin();
2338 _Base_ptr __y
= _M_end();
2342 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _S_key(__z
)) ?
2343 _S_left(__x
) : _S_right(__x
);
2345 return _M_insert_lower_node(__y
, __z
);
2348 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2349 typename _Compare
, typename _Alloc
>
2350 template<typename
... _Args
>
2351 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2352 _Compare
, _Alloc
>::iterator
, bool>
2353 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2354 _M_emplace_unique(_Args
&&... __args
)
2356 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2360 typedef pair
<iterator
, bool> _Res
;
2361 auto __res
= _M_get_insert_unique_pos(_S_key(__z
));
2363 return _Res(_M_insert_node(__res
.first
, __res
.second
, __z
), true);
2366 return _Res(iterator(__res
.first
), false);
2371 __throw_exception_again
;
2375 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2376 typename _Compare
, typename _Alloc
>
2377 template<typename
... _Args
>
2378 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2379 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2380 _M_emplace_equal(_Args
&&... __args
)
2382 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2386 auto __res
= _M_get_insert_equal_pos(_S_key(__z
));
2387 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2392 __throw_exception_again
;
2396 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2397 typename _Compare
, typename _Alloc
>
2398 template<typename
... _Args
>
2399 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2400 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2401 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
)
2403 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2407 auto __res
= _M_get_insert_hint_unique_pos(__pos
, _S_key(__z
));
2410 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2413 return iterator(__res
.first
);
2418 __throw_exception_again
;
2422 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2423 typename _Compare
, typename _Alloc
>
2424 template<typename
... _Args
>
2425 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2426 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2427 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
)
2429 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2433 auto __res
= _M_get_insert_hint_equal_pos(__pos
, _S_key(__z
));
2436 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2438 return _M_insert_equal_lower_node(__z
);
2443 __throw_exception_again
;
2448 template<typename _Key
, typename _Val
, typename _KoV
,
2449 typename _Cmp
, typename _Alloc
>
2452 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
2453 _M_insert_unique(_II __first
, _II __last
)
2455 _Alloc_node
__an(*this);
2456 for (; __first
!= __last
; ++__first
)
2457 _M_insert_unique_(end(), *__first
, __an
);
2460 template<typename _Key
, typename _Val
, typename _KoV
,
2461 typename _Cmp
, typename _Alloc
>
2464 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
2465 _M_insert_equal(_II __first
, _II __last
)
2467 _Alloc_node
__an(*this);
2468 for (; __first
!= __last
; ++__first
)
2469 _M_insert_equal_(end(), *__first
, __an
);
2472 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2473 typename _Compare
, typename _Alloc
>
2475 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2476 _M_erase_aux(const_iterator __position
)
2479 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
2480 (const_cast<_Base_ptr
>(__position
._M_node
),
2481 this->_M_impl
._M_header
));
2483 --_M_impl
._M_node_count
;
2486 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2487 typename _Compare
, typename _Alloc
>
2489 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2490 _M_erase_aux(const_iterator __first
, const_iterator __last
)
2492 if (__first
== begin() && __last
== end())
2495 while (__first
!= __last
)
2496 _M_erase_aux(__first
++);
2499 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2500 typename _Compare
, typename _Alloc
>
2501 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2502 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2503 erase(const _Key
& __x
)
2505 pair
<iterator
, iterator
> __p
= equal_range(__x
);
2506 const size_type __old_size
= size();
2507 _M_erase_aux(__p
.first
, __p
.second
);
2508 return __old_size
- size();
2511 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2512 typename _Compare
, typename _Alloc
>
2514 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2515 erase(const _Key
* __first
, const _Key
* __last
)
2517 while (__first
!= __last
)
2521 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2522 typename _Compare
, typename _Alloc
>
2523 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2524 _Compare
, _Alloc
>::iterator
2525 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2526 find(const _Key
& __k
)
2528 iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2529 return (__j
== end()
2530 || _M_impl
._M_key_compare(__k
,
2531 _S_key(__j
._M_node
))) ? end() : __j
;
2534 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2535 typename _Compare
, typename _Alloc
>
2536 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2537 _Compare
, _Alloc
>::const_iterator
2538 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2539 find(const _Key
& __k
) const
2541 const_iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2542 return (__j
== end()
2543 || _M_impl
._M_key_compare(__k
,
2544 _S_key(__j
._M_node
))) ? end() : __j
;
2547 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2548 typename _Compare
, typename _Alloc
>
2549 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2550 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2551 count(const _Key
& __k
) const
2553 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
2554 const size_type __n
= std::distance(__p
.first
, __p
.second
);
2558 _GLIBCXX_PURE
unsigned int
2559 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
2560 const _Rb_tree_node_base
* __root
) throw ();
2562 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2563 typename _Compare
, typename _Alloc
>
2565 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
2567 if (_M_impl
._M_node_count
== 0 || begin() == end())
2568 return _M_impl
._M_node_count
== 0 && begin() == end()
2569 && this->_M_impl
._M_header
._M_left
== _M_end()
2570 && this->_M_impl
._M_header
._M_right
== _M_end();
2572 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
2573 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
2575 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
2576 _Const_Link_type __L
= _S_left(__x
);
2577 _Const_Link_type __R
= _S_right(__x
);
2579 if (__x
->_M_color
== _S_red
)
2580 if ((__L
&& __L
->_M_color
== _S_red
)
2581 || (__R
&& __R
->_M_color
== _S_red
))
2584 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
2586 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
2589 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
2593 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2595 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2600 #if __cplusplus > 201402L
2601 // Allow access to internals of compatible _Rb_tree specializations.
2602 template<typename _Key
, typename _Val
, typename _Sel
, typename _Cmp1
,
2603 typename _Alloc
, typename _Cmp2
>
2604 struct _Rb_tree_merge_helper
<_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>,
2608 friend class _Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>;
2611 _S_get_impl(_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp2
, _Alloc
>& __tree
)
2612 { return __tree
._M_impl
; }
2616 _GLIBCXX_END_NAMESPACE_VERSION