1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001-2016 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 template<typename _Val
>
141 struct _Rb_tree_node
: public _Rb_tree_node_base
143 typedef _Rb_tree_node
<_Val
>* _Link_type
;
145 #if __cplusplus < 201103L
150 { return std::__addressof(_M_value_field
); }
154 { return std::__addressof(_M_value_field
); }
156 __gnu_cxx::__aligned_membuf
<_Val
> _M_storage
;
160 { return _M_storage
._M_ptr(); }
164 { return _M_storage
._M_ptr(); }
168 _GLIBCXX_PURE _Rb_tree_node_base
*
169 _Rb_tree_increment(_Rb_tree_node_base
* __x
) throw ();
171 _GLIBCXX_PURE
const _Rb_tree_node_base
*
172 _Rb_tree_increment(const _Rb_tree_node_base
* __x
) throw ();
174 _GLIBCXX_PURE _Rb_tree_node_base
*
175 _Rb_tree_decrement(_Rb_tree_node_base
* __x
) throw ();
177 _GLIBCXX_PURE
const _Rb_tree_node_base
*
178 _Rb_tree_decrement(const _Rb_tree_node_base
* __x
) throw ();
180 template<typename _Tp
>
181 struct _Rb_tree_iterator
183 typedef _Tp value_type
;
184 typedef _Tp
& reference
;
185 typedef _Tp
* pointer
;
187 typedef bidirectional_iterator_tag iterator_category
;
188 typedef ptrdiff_t difference_type
;
190 typedef _Rb_tree_iterator
<_Tp
> _Self
;
191 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
192 typedef _Rb_tree_node
<_Tp
>* _Link_type
;
194 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
198 _Rb_tree_iterator(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
202 operator*() const _GLIBCXX_NOEXCEPT
203 { return *static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
206 operator->() const _GLIBCXX_NOEXCEPT
207 { return static_cast<_Link_type
> (_M_node
)->_M_valptr(); }
210 operator++() _GLIBCXX_NOEXCEPT
212 _M_node
= _Rb_tree_increment(_M_node
);
217 operator++(int) _GLIBCXX_NOEXCEPT
220 _M_node
= _Rb_tree_increment(_M_node
);
225 operator--() _GLIBCXX_NOEXCEPT
227 _M_node
= _Rb_tree_decrement(_M_node
);
232 operator--(int) _GLIBCXX_NOEXCEPT
235 _M_node
= _Rb_tree_decrement(_M_node
);
240 operator==(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
241 { return _M_node
== __x
._M_node
; }
244 operator!=(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
245 { return _M_node
!= __x
._M_node
; }
250 template<typename _Tp
>
251 struct _Rb_tree_const_iterator
253 typedef _Tp value_type
;
254 typedef const _Tp
& reference
;
255 typedef const _Tp
* pointer
;
257 typedef _Rb_tree_iterator
<_Tp
> iterator
;
259 typedef bidirectional_iterator_tag iterator_category
;
260 typedef ptrdiff_t difference_type
;
262 typedef _Rb_tree_const_iterator
<_Tp
> _Self
;
263 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr
;
264 typedef const _Rb_tree_node
<_Tp
>* _Link_type
;
266 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
270 _Rb_tree_const_iterator(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
273 _Rb_tree_const_iterator(const iterator
& __it
) _GLIBCXX_NOEXCEPT
274 : _M_node(__it
._M_node
) { }
277 _M_const_cast() const _GLIBCXX_NOEXCEPT
278 { return iterator(const_cast<typename
iterator::_Base_ptr
>(_M_node
)); }
281 operator*() const _GLIBCXX_NOEXCEPT
282 { return *static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
285 operator->() const _GLIBCXX_NOEXCEPT
286 { return static_cast<_Link_type
>(_M_node
)->_M_valptr(); }
289 operator++() _GLIBCXX_NOEXCEPT
291 _M_node
= _Rb_tree_increment(_M_node
);
296 operator++(int) _GLIBCXX_NOEXCEPT
299 _M_node
= _Rb_tree_increment(_M_node
);
304 operator--() _GLIBCXX_NOEXCEPT
306 _M_node
= _Rb_tree_decrement(_M_node
);
311 operator--(int) _GLIBCXX_NOEXCEPT
314 _M_node
= _Rb_tree_decrement(_M_node
);
319 operator==(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
320 { return _M_node
== __x
._M_node
; }
323 operator!=(const _Self
& __x
) const _GLIBCXX_NOEXCEPT
324 { return _M_node
!= __x
._M_node
; }
329 template<typename _Val
>
331 operator==(const _Rb_tree_iterator
<_Val
>& __x
,
332 const _Rb_tree_const_iterator
<_Val
>& __y
) _GLIBCXX_NOEXCEPT
333 { return __x
._M_node
== __y
._M_node
; }
335 template<typename _Val
>
337 operator!=(const _Rb_tree_iterator
<_Val
>& __x
,
338 const _Rb_tree_const_iterator
<_Val
>& __y
) _GLIBCXX_NOEXCEPT
339 { return __x
._M_node
!= __y
._M_node
; }
342 _Rb_tree_insert_and_rebalance(const bool __insert_left
,
343 _Rb_tree_node_base
* __x
,
344 _Rb_tree_node_base
* __p
,
345 _Rb_tree_node_base
& __header
) throw ();
348 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* const __z
,
349 _Rb_tree_node_base
& __header
) throw ();
351 #if __cplusplus > 201103L
352 template<typename _Cmp
, typename _SfinaeType
, typename
= __void_t
<>>
353 struct __has_is_transparent
356 template<typename _Cmp
, typename _SfinaeType
>
357 struct __has_is_transparent
<_Cmp
, _SfinaeType
,
358 __void_t
<typename
_Cmp::is_transparent
>>
359 { typedef void type
; };
362 #if __cplusplus > 201402L
363 template<typename _Tree1
, typename _Cmp2
>
364 struct _Rb_tree_merge_helper
{ };
367 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
368 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
371 typedef typename
__gnu_cxx::__alloc_traits
<_Alloc
>::template
372 rebind
<_Rb_tree_node
<_Val
> >::other _Node_allocator
;
374 typedef __gnu_cxx::__alloc_traits
<_Node_allocator
> _Alloc_traits
;
377 typedef _Rb_tree_node_base
* _Base_ptr
;
378 typedef const _Rb_tree_node_base
* _Const_Base_ptr
;
379 typedef _Rb_tree_node
<_Val
>* _Link_type
;
380 typedef const _Rb_tree_node
<_Val
>* _Const_Link_type
;
383 // Functor recycling a pool of nodes and using allocation once the pool
385 struct _Reuse_or_alloc_node
387 _Reuse_or_alloc_node(_Rb_tree
& __t
)
388 : _M_root(__t
._M_root()), _M_nodes(__t
._M_rightmost()), _M_t(__t
)
392 _M_root
->_M_parent
= 0;
394 if (_M_nodes
->_M_left
)
395 _M_nodes
= _M_nodes
->_M_left
;
401 #if __cplusplus >= 201103L
402 _Reuse_or_alloc_node(const _Reuse_or_alloc_node
&) = delete;
405 ~_Reuse_or_alloc_node()
406 { _M_t
._M_erase(static_cast<_Link_type
>(_M_root
)); }
408 template<typename _Arg
>
410 #if __cplusplus < 201103L
411 operator()(const _Arg
& __arg
)
413 operator()(_Arg
&& __arg
)
416 _Link_type __node
= static_cast<_Link_type
>(_M_extract());
419 _M_t
._M_destroy_node(__node
);
420 _M_t
._M_construct_node(__node
, _GLIBCXX_FORWARD(_Arg
, __arg
));
424 return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
));
434 _Base_ptr __node
= _M_nodes
;
435 _M_nodes
= _M_nodes
->_M_parent
;
438 if (_M_nodes
->_M_right
== __node
)
440 _M_nodes
->_M_right
= 0;
442 if (_M_nodes
->_M_left
)
444 _M_nodes
= _M_nodes
->_M_left
;
446 while (_M_nodes
->_M_right
)
447 _M_nodes
= _M_nodes
->_M_right
;
449 if (_M_nodes
->_M_left
)
450 _M_nodes
= _M_nodes
->_M_left
;
453 else // __node is on the left.
454 _M_nodes
->_M_left
= 0;
467 // Functor similar to the previous one but without any pool of nodes to
471 _Alloc_node(_Rb_tree
& __t
)
474 template<typename _Arg
>
476 #if __cplusplus < 201103L
477 operator()(const _Arg
& __arg
) const
479 operator()(_Arg
&& __arg
) const
481 { return _M_t
._M_create_node(_GLIBCXX_FORWARD(_Arg
, __arg
)); }
488 typedef _Key key_type
;
489 typedef _Val value_type
;
490 typedef value_type
* pointer
;
491 typedef const value_type
* const_pointer
;
492 typedef value_type
& reference
;
493 typedef const value_type
& const_reference
;
494 typedef size_t size_type
;
495 typedef ptrdiff_t difference_type
;
496 typedef _Alloc allocator_type
;
499 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
500 { return *static_cast<_Node_allocator
*>(&this->_M_impl
); }
502 const _Node_allocator
&
503 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
504 { return *static_cast<const _Node_allocator
*>(&this->_M_impl
); }
507 get_allocator() const _GLIBCXX_NOEXCEPT
508 { return allocator_type(_M_get_Node_allocator()); }
513 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
516 _M_put_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
517 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p
, 1); }
519 #if __cplusplus < 201103L
521 _M_construct_node(_Link_type __node
, const value_type
& __x
)
524 { get_allocator().construct(__node
->_M_valptr(), __x
); }
528 __throw_exception_again
;
533 _M_create_node(const value_type
& __x
)
535 _Link_type __tmp
= _M_get_node();
536 _M_construct_node(__tmp
, __x
);
541 _M_destroy_node(_Link_type __p
)
542 { get_allocator().destroy(__p
->_M_valptr()); }
544 template<typename
... _Args
>
546 _M_construct_node(_Link_type __node
, _Args
&&... __args
)
550 ::new(__node
) _Rb_tree_node
<_Val
>;
551 _Alloc_traits::construct(_M_get_Node_allocator(),
553 std::forward
<_Args
>(__args
)...);
557 __node
->~_Rb_tree_node
<_Val
>();
559 __throw_exception_again
;
563 template<typename
... _Args
>
565 _M_create_node(_Args
&&... __args
)
567 _Link_type __tmp
= _M_get_node();
568 _M_construct_node(__tmp
, std::forward
<_Args
>(__args
)...);
573 _M_destroy_node(_Link_type __p
) noexcept
575 _Alloc_traits::destroy(_M_get_Node_allocator(), __p
->_M_valptr());
576 __p
->~_Rb_tree_node
<_Val
>();
581 _M_drop_node(_Link_type __p
) _GLIBCXX_NOEXCEPT
583 _M_destroy_node(__p
);
587 template<typename _NodeGen
>
589 _M_clone_node(_Const_Link_type __x
, _NodeGen
& __node_gen
)
591 _Link_type __tmp
= __node_gen(*__x
->_M_valptr());
592 __tmp
->_M_color
= __x
->_M_color
;
599 // Unused _Is_pod_comparator is kept as it is part of mangled name.
600 template<typename _Key_compare
,
601 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare
)>
602 struct _Rb_tree_impl
: public _Node_allocator
604 _Key_compare _M_key_compare
;
605 _Rb_tree_node_base _M_header
;
606 size_type _M_node_count
; // Keeps track of size of tree.
609 : _Node_allocator(), _M_key_compare(), _M_header(),
613 _Rb_tree_impl(const _Key_compare
& __comp
, const _Node_allocator
& __a
)
614 : _Node_allocator(__a
), _M_key_compare(__comp
), _M_header(),
618 #if __cplusplus >= 201103L
619 _Rb_tree_impl(const _Key_compare
& __comp
, _Node_allocator
&& __a
)
620 : _Node_allocator(std::move(__a
)), _M_key_compare(__comp
),
621 _M_header(), _M_node_count(0)
628 this->_M_header
._M_parent
= 0;
629 this->_M_header
._M_left
= &this->_M_header
;
630 this->_M_header
._M_right
= &this->_M_header
;
631 this->_M_node_count
= 0;
638 this->_M_header
._M_color
= _S_red
;
639 this->_M_header
._M_parent
= 0;
640 this->_M_header
._M_left
= &this->_M_header
;
641 this->_M_header
._M_right
= &this->_M_header
;
645 _Rb_tree_impl
<_Compare
> _M_impl
;
649 _M_root() _GLIBCXX_NOEXCEPT
650 { return this->_M_impl
._M_header
._M_parent
; }
653 _M_root() const _GLIBCXX_NOEXCEPT
654 { return this->_M_impl
._M_header
._M_parent
; }
657 _M_leftmost() _GLIBCXX_NOEXCEPT
658 { return this->_M_impl
._M_header
._M_left
; }
661 _M_leftmost() const _GLIBCXX_NOEXCEPT
662 { return this->_M_impl
._M_header
._M_left
; }
665 _M_rightmost() _GLIBCXX_NOEXCEPT
666 { return this->_M_impl
._M_header
._M_right
; }
669 _M_rightmost() const _GLIBCXX_NOEXCEPT
670 { return this->_M_impl
._M_header
._M_right
; }
673 _M_begin() _GLIBCXX_NOEXCEPT
674 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
677 _M_begin() const _GLIBCXX_NOEXCEPT
679 return static_cast<_Const_Link_type
>
680 (this->_M_impl
._M_header
._M_parent
);
684 _M_end() _GLIBCXX_NOEXCEPT
685 { return &this->_M_impl
._M_header
; }
688 _M_end() const _GLIBCXX_NOEXCEPT
689 { return &this->_M_impl
._M_header
; }
691 static const_reference
692 _S_value(_Const_Link_type __x
)
693 { return *__x
->_M_valptr(); }
696 _S_key(_Const_Link_type __x
)
697 { return _KeyOfValue()(_S_value(__x
)); }
700 _S_left(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
701 { return static_cast<_Link_type
>(__x
->_M_left
); }
703 static _Const_Link_type
704 _S_left(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
705 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
708 _S_right(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
709 { return static_cast<_Link_type
>(__x
->_M_right
); }
711 static _Const_Link_type
712 _S_right(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
713 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
715 static const_reference
716 _S_value(_Const_Base_ptr __x
)
717 { return *static_cast<_Const_Link_type
>(__x
)->_M_valptr(); }
720 _S_key(_Const_Base_ptr __x
)
721 { return _KeyOfValue()(_S_value(__x
)); }
724 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
725 { return _Rb_tree_node_base::_S_minimum(__x
); }
727 static _Const_Base_ptr
728 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
729 { return _Rb_tree_node_base::_S_minimum(__x
); }
732 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
733 { return _Rb_tree_node_base::_S_maximum(__x
); }
735 static _Const_Base_ptr
736 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
737 { return _Rb_tree_node_base::_S_maximum(__x
); }
740 typedef _Rb_tree_iterator
<value_type
> iterator
;
741 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
743 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
744 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
746 #if __cplusplus > 201402L
747 using node_type
= _Node_handle
<_Key
, _Val
, _Node_allocator
>;
748 using insert_return_type
= _Node_insert_return
<iterator
, node_type
>;
751 pair
<_Base_ptr
, _Base_ptr
>
752 _M_get_insert_unique_pos(const key_type
& __k
);
754 pair
<_Base_ptr
, _Base_ptr
>
755 _M_get_insert_equal_pos(const key_type
& __k
);
757 pair
<_Base_ptr
, _Base_ptr
>
758 _M_get_insert_hint_unique_pos(const_iterator __pos
,
759 const key_type
& __k
);
761 pair
<_Base_ptr
, _Base_ptr
>
762 _M_get_insert_hint_equal_pos(const_iterator __pos
,
763 const key_type
& __k
);
766 #if __cplusplus >= 201103L
767 template<typename _Arg
, typename _NodeGen
>
769 _M_insert_(_Base_ptr __x
, _Base_ptr __y
, _Arg
&& __v
, _NodeGen
&);
772 _M_insert_node(_Base_ptr __x
, _Base_ptr __y
, _Link_type __z
);
774 template<typename _Arg
>
776 _M_insert_lower(_Base_ptr __y
, _Arg
&& __v
);
778 template<typename _Arg
>
780 _M_insert_equal_lower(_Arg
&& __x
);
783 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
);
786 _M_insert_equal_lower_node(_Link_type __z
);
788 template<typename _NodeGen
>
790 _M_insert_(_Base_ptr __x
, _Base_ptr __y
,
791 const value_type
& __v
, _NodeGen
&);
793 // _GLIBCXX_RESOLVE_LIB_DEFECTS
794 // 233. Insertion hints in associative containers.
796 _M_insert_lower(_Base_ptr __y
, const value_type
& __v
);
799 _M_insert_equal_lower(const value_type
& __x
);
802 template<typename _NodeGen
>
804 _M_copy(_Const_Link_type __x
, _Base_ptr __p
, _NodeGen
&);
807 _M_copy(_Const_Link_type __x
, _Base_ptr __p
)
809 _Alloc_node
__an(*this);
810 return _M_copy(__x
, __p
, __an
);
814 _M_erase(_Link_type __x
);
817 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
821 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
822 const _Key
& __k
) const;
825 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
829 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
830 const _Key
& __k
) const;
833 // allocation/deallocation
836 _Rb_tree(const _Compare
& __comp
,
837 const allocator_type
& __a
= allocator_type())
838 : _M_impl(__comp
, _Node_allocator(__a
)) { }
840 _Rb_tree(const _Rb_tree
& __x
)
841 : _M_impl(__x
._M_impl
._M_key_compare
,
842 _Alloc_traits::_S_select_on_copy(__x
._M_get_Node_allocator()))
844 if (__x
._M_root() != 0)
846 _M_root() = _M_copy(__x
._M_begin(), _M_end());
847 _M_leftmost() = _S_minimum(_M_root());
848 _M_rightmost() = _S_maximum(_M_root());
849 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
853 #if __cplusplus >= 201103L
854 _Rb_tree(const allocator_type
& __a
)
855 : _M_impl(_Compare(), _Node_allocator(__a
))
858 _Rb_tree(const _Rb_tree
& __x
, const allocator_type
& __a
)
859 : _M_impl(__x
._M_impl
._M_key_compare
, _Node_allocator(__a
))
861 if (__x
._M_root() != nullptr)
863 _M_root() = _M_copy(__x
._M_begin(), _M_end());
864 _M_leftmost() = _S_minimum(_M_root());
865 _M_rightmost() = _S_maximum(_M_root());
866 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
870 _Rb_tree(_Rb_tree
&& __x
)
871 : _M_impl(__x
._M_impl
._M_key_compare
,
872 std::move(__x
._M_get_Node_allocator()))
874 if (__x
._M_root() != 0)
875 _M_move_data(__x
, std::true_type());
878 _Rb_tree(_Rb_tree
&& __x
, const allocator_type
& __a
)
879 : _Rb_tree(std::move(__x
), _Node_allocator(__a
))
882 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
);
885 ~_Rb_tree() _GLIBCXX_NOEXCEPT
886 { _M_erase(_M_begin()); }
889 operator=(const _Rb_tree
& __x
);
894 { return _M_impl
._M_key_compare
; }
897 begin() _GLIBCXX_NOEXCEPT
898 { return iterator(this->_M_impl
._M_header
._M_left
); }
901 begin() const _GLIBCXX_NOEXCEPT
902 { return const_iterator(this->_M_impl
._M_header
._M_left
); }
905 end() _GLIBCXX_NOEXCEPT
906 { return iterator(&this->_M_impl
._M_header
); }
909 end() const _GLIBCXX_NOEXCEPT
910 { return const_iterator(&this->_M_impl
._M_header
); }
913 rbegin() _GLIBCXX_NOEXCEPT
914 { return reverse_iterator(end()); }
916 const_reverse_iterator
917 rbegin() const _GLIBCXX_NOEXCEPT
918 { return const_reverse_iterator(end()); }
921 rend() _GLIBCXX_NOEXCEPT
922 { return reverse_iterator(begin()); }
924 const_reverse_iterator
925 rend() const _GLIBCXX_NOEXCEPT
926 { return const_reverse_iterator(begin()); }
929 empty() const _GLIBCXX_NOEXCEPT
930 { return _M_impl
._M_node_count
== 0; }
933 size() const _GLIBCXX_NOEXCEPT
934 { return _M_impl
._M_node_count
; }
937 max_size() const _GLIBCXX_NOEXCEPT
938 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
942 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
);
945 #if __cplusplus >= 201103L
946 template<typename _Arg
>
948 _M_insert_unique(_Arg
&& __x
);
950 template<typename _Arg
>
952 _M_insert_equal(_Arg
&& __x
);
954 template<typename _Arg
, typename _NodeGen
>
956 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
958 template<typename _Arg
>
960 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
)
962 _Alloc_node
__an(*this);
963 return _M_insert_unique_(__pos
, std::forward
<_Arg
>(__x
), __an
);
966 template<typename _Arg
, typename _NodeGen
>
968 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
970 template<typename _Arg
>
972 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
)
974 _Alloc_node
__an(*this);
975 return _M_insert_equal_(__pos
, std::forward
<_Arg
>(__x
), __an
);
978 template<typename
... _Args
>
980 _M_emplace_unique(_Args
&&... __args
);
982 template<typename
... _Args
>
984 _M_emplace_equal(_Args
&&... __args
);
986 template<typename
... _Args
>
988 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
);
990 template<typename
... _Args
>
992 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
);
995 _M_insert_unique(const value_type
& __x
);
998 _M_insert_equal(const value_type
& __x
);
1000 template<typename _NodeGen
>
1002 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
,
1006 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
)
1008 _Alloc_node
__an(*this);
1009 return _M_insert_unique_(__pos
, __x
, __an
);
1012 template<typename _NodeGen
>
1014 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
,
1017 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
)
1019 _Alloc_node
__an(*this);
1020 return _M_insert_equal_(__pos
, __x
, __an
);
1024 template<typename _InputIterator
>
1026 _M_insert_unique(_InputIterator __first
, _InputIterator __last
);
1028 template<typename _InputIterator
>
1030 _M_insert_equal(_InputIterator __first
, _InputIterator __last
);
1034 _M_erase_aux(const_iterator __position
);
1037 _M_erase_aux(const_iterator __first
, const_iterator __last
);
1040 #if __cplusplus >= 201103L
1041 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1042 // DR 130. Associative erase should return an iterator.
1043 _GLIBCXX_ABI_TAG_CXX11
1045 erase(const_iterator __position
)
1047 const_iterator __result
= __position
;
1049 _M_erase_aux(__position
);
1050 return __result
._M_const_cast();
1054 _GLIBCXX_ABI_TAG_CXX11
1056 erase(iterator __position
)
1058 iterator __result
= __position
;
1060 _M_erase_aux(__position
);
1065 erase(iterator __position
)
1066 { _M_erase_aux(__position
); }
1069 erase(const_iterator __position
)
1070 { _M_erase_aux(__position
); }
1073 erase(const key_type
& __x
);
1075 #if __cplusplus >= 201103L
1076 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1077 // DR 130. Associative erase should return an iterator.
1078 _GLIBCXX_ABI_TAG_CXX11
1080 erase(const_iterator __first
, const_iterator __last
)
1082 _M_erase_aux(__first
, __last
);
1083 return __last
._M_const_cast();
1087 erase(iterator __first
, iterator __last
)
1088 { _M_erase_aux(__first
, __last
); }
1091 erase(const_iterator __first
, const_iterator __last
)
1092 { _M_erase_aux(__first
, __last
); }
1095 erase(const key_type
* __first
, const key_type
* __last
);
1098 clear() _GLIBCXX_NOEXCEPT
1100 _M_erase(_M_begin());
1106 find(const key_type
& __k
);
1109 find(const key_type
& __k
) const;
1112 count(const key_type
& __k
) const;
1115 lower_bound(const key_type
& __k
)
1116 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1119 lower_bound(const key_type
& __k
) const
1120 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1123 upper_bound(const key_type
& __k
)
1124 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1127 upper_bound(const key_type
& __k
) const
1128 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1130 pair
<iterator
, iterator
>
1131 equal_range(const key_type
& __k
);
1133 pair
<const_iterator
, const_iterator
>
1134 equal_range(const key_type
& __k
) const;
1136 #if __cplusplus > 201103L
1137 template<typename _Kt
,
1139 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1141 _M_find_tr(const _Kt
& __k
)
1143 const _Rb_tree
* __const_this
= this;
1144 return __const_this
->_M_find_tr(__k
)._M_const_cast();
1147 template<typename _Kt
,
1149 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1151 _M_find_tr(const _Kt
& __k
) const
1153 auto __j
= _M_lower_bound_tr(__k
);
1154 if (__j
!= end() && _M_impl
._M_key_compare(__k
, _S_key(__j
._M_node
)))
1159 template<typename _Kt
,
1161 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1163 _M_count_tr(const _Kt
& __k
) const
1165 auto __p
= _M_equal_range_tr(__k
);
1166 return std::distance(__p
.first
, __p
.second
);
1169 template<typename _Kt
,
1171 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1173 _M_lower_bound_tr(const _Kt
& __k
)
1175 const _Rb_tree
* __const_this
= this;
1176 return __const_this
->_M_lower_bound_tr(__k
)._M_const_cast();
1179 template<typename _Kt
,
1181 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1183 _M_lower_bound_tr(const _Kt
& __k
) const
1185 auto __x
= _M_begin();
1186 auto __y
= _M_end();
1188 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1194 __x
= _S_right(__x
);
1195 return const_iterator(__y
);
1198 template<typename _Kt
,
1200 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1202 _M_upper_bound_tr(const _Kt
& __k
)
1204 const _Rb_tree
* __const_this
= this;
1205 return __const_this
->_M_upper_bound_tr(__k
)._M_const_cast();
1208 template<typename _Kt
,
1210 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1212 _M_upper_bound_tr(const _Kt
& __k
) const
1214 auto __x
= _M_begin();
1215 auto __y
= _M_end();
1217 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1223 __x
= _S_right(__x
);
1224 return const_iterator(__y
);
1227 template<typename _Kt
,
1229 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1230 pair
<iterator
, iterator
>
1231 _M_equal_range_tr(const _Kt
& __k
)
1233 const _Rb_tree
* __const_this
= this;
1234 auto __ret
= __const_this
->_M_equal_range_tr(__k
);
1235 return { __ret
.first
._M_const_cast(), __ret
.second
._M_const_cast() };
1238 template<typename _Kt
,
1240 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1241 pair
<const_iterator
, const_iterator
>
1242 _M_equal_range_tr(const _Kt
& __k
) const
1244 auto __low
= _M_lower_bound_tr(__k
);
1245 auto __high
= __low
;
1246 auto& __cmp
= _M_impl
._M_key_compare
;
1247 while (__high
!= end() && !__cmp(__k
, _S_key(__high
._M_node
)))
1249 return { __low
, __high
};
1255 __rb_verify() const;
1257 #if __cplusplus >= 201103L
1259 operator=(_Rb_tree
&&)
1260 noexcept(_Alloc_traits::_S_nothrow_move()
1261 && is_nothrow_move_assignable
<_Compare
>::value
);
1263 template<typename _Iterator
>
1265 _M_assign_unique(_Iterator
, _Iterator
);
1267 template<typename _Iterator
>
1269 _M_assign_equal(_Iterator
, _Iterator
);
1272 // Move elements from container with equal allocator.
1274 _M_move_data(_Rb_tree
&, std::true_type
);
1276 // Move elements from container with possibly non-equal allocator,
1277 // which might result in a copy not a move.
1279 _M_move_data(_Rb_tree
&, std::false_type
);
1281 // Move assignment from container with equal allocator.
1283 _M_move_assign(_Rb_tree
&, std::true_type
);
1285 // Move assignment from container with possibly non-equal allocator,
1286 // which might result in a copy not a move.
1288 _M_move_assign(_Rb_tree
&, std::false_type
);
1291 #if __cplusplus > 201402L
1293 /// Re-insert an extracted node.
1295 _M_reinsert_node_unique(node_type
&& __nh
)
1297 insert_return_type __ret
;
1299 __ret
.position
= end();
1302 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1304 auto __res
= _M_get_insert_unique_pos(__nh
._M_key());
1308 = _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1309 __nh
._M_ptr
= nullptr;
1310 __ret
.inserted
= true;
1314 __ret
.node
= std::move(__nh
);
1315 __ret
.position
= iterator(__res
.first
);
1316 __ret
.inserted
= false;
1322 /// Re-insert an extracted node.
1324 _M_reinsert_node_equal(node_type
&& __nh
)
1331 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1332 auto __res
= _M_get_insert_equal_pos(__nh
._M_key());
1334 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1336 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1337 __nh
._M_ptr
= nullptr;
1342 /// Re-insert an extracted node.
1344 _M_reinsert_node_hint_unique(const_iterator __hint
, node_type
&& __nh
)
1351 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1352 auto __res
= _M_get_insert_hint_unique_pos(__hint
, __nh
._M_key());
1355 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1356 __nh
._M_ptr
= nullptr;
1359 __ret
= iterator(__res
.first
);
1364 /// Re-insert an extracted node.
1366 _M_reinsert_node_hint_equal(const_iterator __hint
, node_type
&& __nh
)
1373 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1374 auto __res
= _M_get_insert_hint_equal_pos(__hint
, __nh
._M_key());
1376 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1378 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1379 __nh
._M_ptr
= nullptr;
1386 extract(const_iterator __pos
)
1388 auto __ptr
= _Rb_tree_rebalance_for_erase(
1389 __pos
._M_const_cast()._M_node
, _M_impl
._M_header
);
1390 --_M_impl
._M_node_count
;
1391 return { static_cast<_Link_type
>(__ptr
), _M_get_Node_allocator() };
1396 extract(const key_type
& __k
)
1399 auto __pos
= find(__k
);
1401 __nh
= extract(const_iterator(__pos
));
1405 template<typename _Compare2
>
1406 using _Compatible_tree
1407 = _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare2
, _Alloc
>;
1409 template<typename
, typename
>
1410 friend class _Rb_tree_merge_helper
;
1412 /// Merge from a compatible container into one with unique keys.
1413 template<typename _Compare2
>
1415 _M_merge_unique(_Compatible_tree
<_Compare2
>& __src
) noexcept
1417 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1418 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1421 auto __res
= _M_get_insert_unique_pos(_KeyOfValue()(*__pos
));
1424 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1425 auto __ptr
= _Rb_tree_rebalance_for_erase(
1426 __pos
._M_node
, __src_impl
._M_header
);
1427 --__src_impl
._M_node_count
;
1428 _M_insert_node(__res
.first
, __res
.second
,
1429 static_cast<_Link_type
>(__ptr
));
1434 /// Merge from a compatible container into one with equivalent keys.
1435 template<typename _Compare2
>
1437 _M_merge_equal(_Compatible_tree
<_Compare2
>& __src
) noexcept
1439 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1440 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1443 auto __res
= _M_get_insert_equal_pos(_KeyOfValue()(*__pos
));
1446 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1447 auto __ptr
= _Rb_tree_rebalance_for_erase(
1448 __pos
._M_node
, __src_impl
._M_header
);
1449 --__src_impl
._M_node_count
;
1450 _M_insert_node(__res
.first
, __res
.second
,
1451 static_cast<_Link_type
>(__ptr
));
1458 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1459 typename _Compare
, typename _Alloc
>
1461 operator==(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1462 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1464 return __x
.size() == __y
.size()
1465 && std::equal(__x
.begin(), __x
.end(), __y
.begin());
1468 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1469 typename _Compare
, typename _Alloc
>
1471 operator<(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1472 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1474 return std::lexicographical_compare(__x
.begin(), __x
.end(),
1475 __y
.begin(), __y
.end());
1478 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1479 typename _Compare
, typename _Alloc
>
1481 operator!=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1482 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1483 { return !(__x
== __y
); }
1485 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1486 typename _Compare
, typename _Alloc
>
1488 operator>(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1489 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1490 { return __y
< __x
; }
1492 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1493 typename _Compare
, typename _Alloc
>
1495 operator<=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1496 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1497 { return !(__y
< __x
); }
1499 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1500 typename _Compare
, typename _Alloc
>
1502 operator>=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1503 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1504 { return !(__x
< __y
); }
1506 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1507 typename _Compare
, typename _Alloc
>
1509 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1510 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1513 #if __cplusplus >= 201103L
1514 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1515 typename _Compare
, typename _Alloc
>
1516 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1517 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
)
1518 : _M_impl(__x
._M_impl
._M_key_compare
, std::move(__a
))
1520 using __eq
= typename
_Alloc_traits::is_always_equal
;
1521 if (__x
._M_root() != nullptr)
1522 _M_move_data(__x
, __eq());
1525 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1526 typename _Compare
, typename _Alloc
>
1528 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1529 _M_move_data(_Rb_tree
& __x
, std::true_type
)
1531 _M_root() = __x
._M_root();
1532 _M_leftmost() = __x
._M_leftmost();
1533 _M_rightmost() = __x
._M_rightmost();
1534 _M_root()->_M_parent
= _M_end();
1537 __x
._M_leftmost() = __x
._M_end();
1538 __x
._M_rightmost() = __x
._M_end();
1540 this->_M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1541 __x
._M_impl
._M_node_count
= 0;
1544 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1545 typename _Compare
, typename _Alloc
>
1547 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1548 _M_move_data(_Rb_tree
& __x
, std::false_type
)
1550 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1551 _M_move_data(__x
, std::true_type());
1554 _Alloc_node
__an(*this);
1556 [&__an
](const value_type
& __cval
)
1558 auto& __val
= const_cast<value_type
&>(__cval
);
1559 return __an(std::move_if_noexcept(__val
));
1561 _M_root() = _M_copy(__x
._M_begin(), _M_end(), __lbd
);
1562 _M_leftmost() = _S_minimum(_M_root());
1563 _M_rightmost() = _S_maximum(_M_root());
1564 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1568 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1569 typename _Compare
, typename _Alloc
>
1571 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1572 _M_move_assign(_Rb_tree
& __x
, true_type
)
1575 if (__x
._M_root() != nullptr)
1576 _M_move_data(__x
, std::true_type());
1577 std::__alloc_on_move(_M_get_Node_allocator(),
1578 __x
._M_get_Node_allocator());
1581 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1582 typename _Compare
, typename _Alloc
>
1584 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1585 _M_move_assign(_Rb_tree
& __x
, false_type
)
1587 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1588 return _M_move_assign(__x
, true_type
{});
1590 // Try to move each node reusing existing nodes and copying __x nodes
1592 _Reuse_or_alloc_node
__roan(*this);
1594 if (__x
._M_root() != nullptr)
1597 [&__roan
](const value_type
& __cval
)
1599 auto& __val
= const_cast<value_type
&>(__cval
);
1600 return __roan(std::move_if_noexcept(__val
));
1602 _M_root() = _M_copy(__x
._M_begin(), _M_end(), __lbd
);
1603 _M_leftmost() = _S_minimum(_M_root());
1604 _M_rightmost() = _S_maximum(_M_root());
1605 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1610 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1611 typename _Compare
, typename _Alloc
>
1612 inline _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1613 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1614 operator=(_Rb_tree
&& __x
)
1615 noexcept(_Alloc_traits::_S_nothrow_move()
1616 && is_nothrow_move_assignable
<_Compare
>::value
)
1618 _M_impl
._M_key_compare
= std::move(__x
._M_impl
._M_key_compare
);
1619 constexpr bool __move_storage
=
1620 _Alloc_traits::_S_propagate_on_move_assign()
1621 || _Alloc_traits::_S_always_equal();
1622 _M_move_assign(__x
, __bool_constant
<__move_storage
>());
1626 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1627 typename _Compare
, typename _Alloc
>
1628 template<typename _Iterator
>
1630 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1631 _M_assign_unique(_Iterator __first
, _Iterator __last
)
1633 _Reuse_or_alloc_node
__roan(*this);
1635 for (; __first
!= __last
; ++__first
)
1636 _M_insert_unique_(end(), *__first
, __roan
);
1639 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1640 typename _Compare
, typename _Alloc
>
1641 template<typename _Iterator
>
1643 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1644 _M_assign_equal(_Iterator __first
, _Iterator __last
)
1646 _Reuse_or_alloc_node
__roan(*this);
1648 for (; __first
!= __last
; ++__first
)
1649 _M_insert_equal_(end(), *__first
, __roan
);
1653 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1654 typename _Compare
, typename _Alloc
>
1655 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1656 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1657 operator=(const _Rb_tree
& __x
)
1661 // Note that _Key may be a constant type.
1662 #if __cplusplus >= 201103L
1663 if (_Alloc_traits::_S_propagate_on_copy_assign())
1665 auto& __this_alloc
= this->_M_get_Node_allocator();
1666 auto& __that_alloc
= __x
._M_get_Node_allocator();
1667 if (!_Alloc_traits::_S_always_equal()
1668 && __this_alloc
!= __that_alloc
)
1670 // Replacement allocator cannot free existing storage, we need
1671 // to erase nodes first.
1673 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1678 _Reuse_or_alloc_node
__roan(*this);
1680 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
1681 if (__x
._M_root() != 0)
1683 _M_root() = _M_copy(__x
._M_begin(), _M_end(), __roan
);
1684 _M_leftmost() = _S_minimum(_M_root());
1685 _M_rightmost() = _S_maximum(_M_root());
1686 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1693 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1694 typename _Compare
, typename _Alloc
>
1695 #if __cplusplus >= 201103L
1696 template<typename _Arg
, typename _NodeGen
>
1698 template<typename _NodeGen
>
1700 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1701 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1702 _M_insert_(_Base_ptr __x
, _Base_ptr __p
,
1703 #if __cplusplus >= 201103L
1708 _NodeGen
& __node_gen
)
1710 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
1711 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
1714 _Link_type __z
= __node_gen(_GLIBCXX_FORWARD(_Arg
, __v
));
1716 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1717 this->_M_impl
._M_header
);
1718 ++_M_impl
._M_node_count
;
1719 return iterator(__z
);
1722 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1723 typename _Compare
, typename _Alloc
>
1724 #if __cplusplus >= 201103L
1725 template<typename _Arg
>
1727 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1728 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1729 #if __cplusplus >= 201103L
1730 _M_insert_lower(_Base_ptr __p
, _Arg
&& __v
)
1732 _M_insert_lower(_Base_ptr __p
, const _Val
& __v
)
1735 bool __insert_left
= (__p
== _M_end()
1736 || !_M_impl
._M_key_compare(_S_key(__p
),
1737 _KeyOfValue()(__v
)));
1739 _Link_type __z
= _M_create_node(_GLIBCXX_FORWARD(_Arg
, __v
));
1741 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1742 this->_M_impl
._M_header
);
1743 ++_M_impl
._M_node_count
;
1744 return iterator(__z
);
1747 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1748 typename _Compare
, typename _Alloc
>
1749 #if __cplusplus >= 201103L
1750 template<typename _Arg
>
1752 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1753 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1754 #if __cplusplus >= 201103L
1755 _M_insert_equal_lower(_Arg
&& __v
)
1757 _M_insert_equal_lower(const _Val
& __v
)
1760 _Link_type __x
= _M_begin();
1761 _Base_ptr __y
= _M_end();
1765 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _KeyOfValue()(__v
)) ?
1766 _S_left(__x
) : _S_right(__x
);
1768 return _M_insert_lower(__y
, _GLIBCXX_FORWARD(_Arg
, __v
));
1771 template<typename _Key
, typename _Val
, typename _KoV
,
1772 typename _Compare
, typename _Alloc
>
1773 template<typename _NodeGen
>
1774 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1775 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
1776 _M_copy(_Const_Link_type __x
, _Base_ptr __p
, _NodeGen
& __node_gen
)
1778 // Structural copy. __x and __p must be non-null.
1779 _Link_type __top
= _M_clone_node(__x
, __node_gen
);
1780 __top
->_M_parent
= __p
;
1785 __top
->_M_right
= _M_copy(_S_right(__x
), __top
, __node_gen
);
1791 _Link_type __y
= _M_clone_node(__x
, __node_gen
);
1793 __y
->_M_parent
= __p
;
1795 __y
->_M_right
= _M_copy(_S_right(__x
), __y
, __node_gen
);
1803 __throw_exception_again
;
1808 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1809 typename _Compare
, typename _Alloc
>
1811 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1812 _M_erase(_Link_type __x
)
1814 // Erase without rebalancing.
1817 _M_erase(_S_right(__x
));
1818 _Link_type __y
= _S_left(__x
);
1824 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1825 typename _Compare
, typename _Alloc
>
1826 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1827 _Compare
, _Alloc
>::iterator
1828 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1829 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
1833 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1834 __y
= __x
, __x
= _S_left(__x
);
1836 __x
= _S_right(__x
);
1837 return iterator(__y
);
1840 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1841 typename _Compare
, typename _Alloc
>
1842 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1843 _Compare
, _Alloc
>::const_iterator
1844 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1845 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1846 const _Key
& __k
) const
1849 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1850 __y
= __x
, __x
= _S_left(__x
);
1852 __x
= _S_right(__x
);
1853 return const_iterator(__y
);
1856 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1857 typename _Compare
, typename _Alloc
>
1858 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1859 _Compare
, _Alloc
>::iterator
1860 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1861 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
1865 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1866 __y
= __x
, __x
= _S_left(__x
);
1868 __x
= _S_right(__x
);
1869 return iterator(__y
);
1872 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1873 typename _Compare
, typename _Alloc
>
1874 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1875 _Compare
, _Alloc
>::const_iterator
1876 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1877 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1878 const _Key
& __k
) const
1881 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1882 __y
= __x
, __x
= _S_left(__x
);
1884 __x
= _S_right(__x
);
1885 return const_iterator(__y
);
1888 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1889 typename _Compare
, typename _Alloc
>
1890 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1891 _Compare
, _Alloc
>::iterator
,
1892 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1893 _Compare
, _Alloc
>::iterator
>
1894 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1895 equal_range(const _Key
& __k
)
1897 _Link_type __x
= _M_begin();
1898 _Base_ptr __y
= _M_end();
1901 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1902 __x
= _S_right(__x
);
1903 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1904 __y
= __x
, __x
= _S_left(__x
);
1907 _Link_type
__xu(__x
);
1908 _Base_ptr
__yu(__y
);
1909 __y
= __x
, __x
= _S_left(__x
);
1910 __xu
= _S_right(__xu
);
1911 return pair
<iterator
,
1912 iterator
>(_M_lower_bound(__x
, __y
, __k
),
1913 _M_upper_bound(__xu
, __yu
, __k
));
1916 return pair
<iterator
, iterator
>(iterator(__y
),
1920 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1921 typename _Compare
, typename _Alloc
>
1922 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1923 _Compare
, _Alloc
>::const_iterator
,
1924 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1925 _Compare
, _Alloc
>::const_iterator
>
1926 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1927 equal_range(const _Key
& __k
) const
1929 _Const_Link_type __x
= _M_begin();
1930 _Const_Base_ptr __y
= _M_end();
1933 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1934 __x
= _S_right(__x
);
1935 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1936 __y
= __x
, __x
= _S_left(__x
);
1939 _Const_Link_type
__xu(__x
);
1940 _Const_Base_ptr
__yu(__y
);
1941 __y
= __x
, __x
= _S_left(__x
);
1942 __xu
= _S_right(__xu
);
1943 return pair
<const_iterator
,
1944 const_iterator
>(_M_lower_bound(__x
, __y
, __k
),
1945 _M_upper_bound(__xu
, __yu
, __k
));
1948 return pair
<const_iterator
, const_iterator
>(const_iterator(__y
),
1949 const_iterator(__y
));
1952 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1953 typename _Compare
, typename _Alloc
>
1955 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1957 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
)
1961 if (__t
._M_root() != 0)
1963 _M_root() = __t
._M_root();
1964 _M_leftmost() = __t
._M_leftmost();
1965 _M_rightmost() = __t
._M_rightmost();
1966 _M_root()->_M_parent
= _M_end();
1967 _M_impl
._M_node_count
= __t
._M_impl
._M_node_count
;
1969 __t
._M_impl
._M_reset();
1972 else if (__t
._M_root() == 0)
1974 __t
._M_root() = _M_root();
1975 __t
._M_leftmost() = _M_leftmost();
1976 __t
._M_rightmost() = _M_rightmost();
1977 __t
._M_root()->_M_parent
= __t
._M_end();
1978 __t
._M_impl
._M_node_count
= _M_impl
._M_node_count
;
1984 std::swap(_M_root(),__t
._M_root());
1985 std::swap(_M_leftmost(),__t
._M_leftmost());
1986 std::swap(_M_rightmost(),__t
._M_rightmost());
1988 _M_root()->_M_parent
= _M_end();
1989 __t
._M_root()->_M_parent
= __t
._M_end();
1990 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
1992 // No need to swap header's color as it does not change.
1993 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
1995 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
1996 __t
._M_get_Node_allocator());
1999 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2000 typename _Compare
, typename _Alloc
>
2001 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2002 _Compare
, _Alloc
>::_Base_ptr
,
2003 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2004 _Compare
, _Alloc
>::_Base_ptr
>
2005 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2006 _M_get_insert_unique_pos(const key_type
& __k
)
2008 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2009 _Link_type __x
= _M_begin();
2010 _Base_ptr __y
= _M_end();
2015 __comp
= _M_impl
._M_key_compare(__k
, _S_key(__x
));
2016 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
2018 iterator __j
= iterator(__y
);
2022 return _Res(__x
, __y
);
2026 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), __k
))
2027 return _Res(__x
, __y
);
2028 return _Res(__j
._M_node
, 0);
2031 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2032 typename _Compare
, typename _Alloc
>
2033 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2034 _Compare
, _Alloc
>::_Base_ptr
,
2035 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2036 _Compare
, _Alloc
>::_Base_ptr
>
2037 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2038 _M_get_insert_equal_pos(const key_type
& __k
)
2040 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2041 _Link_type __x
= _M_begin();
2042 _Base_ptr __y
= _M_end();
2046 __x
= _M_impl
._M_key_compare(__k
, _S_key(__x
)) ?
2047 _S_left(__x
) : _S_right(__x
);
2049 return _Res(__x
, __y
);
2052 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2053 typename _Compare
, typename _Alloc
>
2054 #if __cplusplus >= 201103L
2055 template<typename _Arg
>
2057 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2058 _Compare
, _Alloc
>::iterator
, bool>
2059 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2060 #if __cplusplus >= 201103L
2061 _M_insert_unique(_Arg
&& __v
)
2063 _M_insert_unique(const _Val
& __v
)
2066 typedef pair
<iterator
, bool> _Res
;
2067 pair
<_Base_ptr
, _Base_ptr
> __res
2068 = _M_get_insert_unique_pos(_KeyOfValue()(__v
));
2072 _Alloc_node
__an(*this);
2073 return _Res(_M_insert_(__res
.first
, __res
.second
,
2074 _GLIBCXX_FORWARD(_Arg
, __v
), __an
),
2078 return _Res(iterator(__res
.first
), false);
2081 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2082 typename _Compare
, typename _Alloc
>
2083 #if __cplusplus >= 201103L
2084 template<typename _Arg
>
2086 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2087 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2088 #if __cplusplus >= 201103L
2089 _M_insert_equal(_Arg
&& __v
)
2091 _M_insert_equal(const _Val
& __v
)
2094 pair
<_Base_ptr
, _Base_ptr
> __res
2095 = _M_get_insert_equal_pos(_KeyOfValue()(__v
));
2096 _Alloc_node
__an(*this);
2097 return _M_insert_(__res
.first
, __res
.second
,
2098 _GLIBCXX_FORWARD(_Arg
, __v
), __an
);
2101 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2102 typename _Compare
, typename _Alloc
>
2103 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2104 _Compare
, _Alloc
>::_Base_ptr
,
2105 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2106 _Compare
, _Alloc
>::_Base_ptr
>
2107 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2108 _M_get_insert_hint_unique_pos(const_iterator __position
,
2109 const key_type
& __k
)
2111 iterator __pos
= __position
._M_const_cast();
2112 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2115 if (__pos
._M_node
== _M_end())
2118 && _M_impl
._M_key_compare(_S_key(_M_rightmost()), __k
))
2119 return _Res(0, _M_rightmost());
2121 return _M_get_insert_unique_pos(__k
);
2123 else if (_M_impl
._M_key_compare(__k
, _S_key(__pos
._M_node
)))
2125 // First, try before...
2126 iterator __before
= __pos
;
2127 if (__pos
._M_node
== _M_leftmost()) // begin()
2128 return _Res(_M_leftmost(), _M_leftmost());
2129 else if (_M_impl
._M_key_compare(_S_key((--__before
)._M_node
), __k
))
2131 if (_S_right(__before
._M_node
) == 0)
2132 return _Res(0, __before
._M_node
);
2134 return _Res(__pos
._M_node
, __pos
._M_node
);
2137 return _M_get_insert_unique_pos(__k
);
2139 else if (_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2141 // ... then try after.
2142 iterator __after
= __pos
;
2143 if (__pos
._M_node
== _M_rightmost())
2144 return _Res(0, _M_rightmost());
2145 else if (_M_impl
._M_key_compare(__k
, _S_key((++__after
)._M_node
)))
2147 if (_S_right(__pos
._M_node
) == 0)
2148 return _Res(0, __pos
._M_node
);
2150 return _Res(__after
._M_node
, __after
._M_node
);
2153 return _M_get_insert_unique_pos(__k
);
2157 return _Res(__pos
._M_node
, 0);
2160 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2161 typename _Compare
, typename _Alloc
>
2162 #if __cplusplus >= 201103L
2163 template<typename _Arg
, typename _NodeGen
>
2165 template<typename _NodeGen
>
2167 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2168 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2169 _M_insert_unique_(const_iterator __position
,
2170 #if __cplusplus >= 201103L
2175 _NodeGen
& __node_gen
)
2177 pair
<_Base_ptr
, _Base_ptr
> __res
2178 = _M_get_insert_hint_unique_pos(__position
, _KeyOfValue()(__v
));
2181 return _M_insert_(__res
.first
, __res
.second
,
2182 _GLIBCXX_FORWARD(_Arg
, __v
),
2184 return iterator(__res
.first
);
2187 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2188 typename _Compare
, typename _Alloc
>
2189 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2190 _Compare
, _Alloc
>::_Base_ptr
,
2191 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2192 _Compare
, _Alloc
>::_Base_ptr
>
2193 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2194 _M_get_insert_hint_equal_pos(const_iterator __position
, const key_type
& __k
)
2196 iterator __pos
= __position
._M_const_cast();
2197 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2200 if (__pos
._M_node
== _M_end())
2203 && !_M_impl
._M_key_compare(__k
, _S_key(_M_rightmost())))
2204 return _Res(0, _M_rightmost());
2206 return _M_get_insert_equal_pos(__k
);
2208 else if (!_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2210 // First, try before...
2211 iterator __before
= __pos
;
2212 if (__pos
._M_node
== _M_leftmost()) // begin()
2213 return _Res(_M_leftmost(), _M_leftmost());
2214 else if (!_M_impl
._M_key_compare(__k
, _S_key((--__before
)._M_node
)))
2216 if (_S_right(__before
._M_node
) == 0)
2217 return _Res(0, __before
._M_node
);
2219 return _Res(__pos
._M_node
, __pos
._M_node
);
2222 return _M_get_insert_equal_pos(__k
);
2226 // ... then try after.
2227 iterator __after
= __pos
;
2228 if (__pos
._M_node
== _M_rightmost())
2229 return _Res(0, _M_rightmost());
2230 else if (!_M_impl
._M_key_compare(_S_key((++__after
)._M_node
), __k
))
2232 if (_S_right(__pos
._M_node
) == 0)
2233 return _Res(0, __pos
._M_node
);
2235 return _Res(__after
._M_node
, __after
._M_node
);
2242 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2243 typename _Compare
, typename _Alloc
>
2244 #if __cplusplus >= 201103L
2245 template<typename _Arg
, typename _NodeGen
>
2247 template<typename _NodeGen
>
2249 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2250 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2251 _M_insert_equal_(const_iterator __position
,
2252 #if __cplusplus >= 201103L
2257 _NodeGen
& __node_gen
)
2259 pair
<_Base_ptr
, _Base_ptr
> __res
2260 = _M_get_insert_hint_equal_pos(__position
, _KeyOfValue()(__v
));
2263 return _M_insert_(__res
.first
, __res
.second
,
2264 _GLIBCXX_FORWARD(_Arg
, __v
),
2267 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg
, __v
));
2270 #if __cplusplus >= 201103L
2271 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2272 typename _Compare
, typename _Alloc
>
2273 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2274 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2275 _M_insert_node(_Base_ptr __x
, _Base_ptr __p
, _Link_type __z
)
2277 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
2278 || _M_impl
._M_key_compare(_S_key(__z
),
2281 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2282 this->_M_impl
._M_header
);
2283 ++_M_impl
._M_node_count
;
2284 return iterator(__z
);
2287 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2288 typename _Compare
, typename _Alloc
>
2289 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2290 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2291 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
)
2293 bool __insert_left
= (__p
== _M_end()
2294 || !_M_impl
._M_key_compare(_S_key(__p
),
2297 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2298 this->_M_impl
._M_header
);
2299 ++_M_impl
._M_node_count
;
2300 return iterator(__z
);
2303 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2304 typename _Compare
, typename _Alloc
>
2305 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2306 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2307 _M_insert_equal_lower_node(_Link_type __z
)
2309 _Link_type __x
= _M_begin();
2310 _Base_ptr __y
= _M_end();
2314 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _S_key(__z
)) ?
2315 _S_left(__x
) : _S_right(__x
);
2317 return _M_insert_lower_node(__y
, __z
);
2320 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2321 typename _Compare
, typename _Alloc
>
2322 template<typename
... _Args
>
2323 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2324 _Compare
, _Alloc
>::iterator
, bool>
2325 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2326 _M_emplace_unique(_Args
&&... __args
)
2328 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2332 typedef pair
<iterator
, bool> _Res
;
2333 auto __res
= _M_get_insert_unique_pos(_S_key(__z
));
2335 return _Res(_M_insert_node(__res
.first
, __res
.second
, __z
), true);
2338 return _Res(iterator(__res
.first
), false);
2343 __throw_exception_again
;
2347 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2348 typename _Compare
, typename _Alloc
>
2349 template<typename
... _Args
>
2350 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2351 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2352 _M_emplace_equal(_Args
&&... __args
)
2354 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2358 auto __res
= _M_get_insert_equal_pos(_S_key(__z
));
2359 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2364 __throw_exception_again
;
2368 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2369 typename _Compare
, typename _Alloc
>
2370 template<typename
... _Args
>
2371 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2372 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2373 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
)
2375 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2379 auto __res
= _M_get_insert_hint_unique_pos(__pos
, _S_key(__z
));
2382 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2385 return iterator(__res
.first
);
2390 __throw_exception_again
;
2394 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2395 typename _Compare
, typename _Alloc
>
2396 template<typename
... _Args
>
2397 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2398 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2399 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
)
2401 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2405 auto __res
= _M_get_insert_hint_equal_pos(__pos
, _S_key(__z
));
2408 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2410 return _M_insert_equal_lower_node(__z
);
2415 __throw_exception_again
;
2420 template<typename _Key
, typename _Val
, typename _KoV
,
2421 typename _Cmp
, typename _Alloc
>
2424 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
2425 _M_insert_unique(_II __first
, _II __last
)
2427 _Alloc_node
__an(*this);
2428 for (; __first
!= __last
; ++__first
)
2429 _M_insert_unique_(end(), *__first
, __an
);
2432 template<typename _Key
, typename _Val
, typename _KoV
,
2433 typename _Cmp
, typename _Alloc
>
2436 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
2437 _M_insert_equal(_II __first
, _II __last
)
2439 _Alloc_node
__an(*this);
2440 for (; __first
!= __last
; ++__first
)
2441 _M_insert_equal_(end(), *__first
, __an
);
2444 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2445 typename _Compare
, typename _Alloc
>
2447 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2448 _M_erase_aux(const_iterator __position
)
2451 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
2452 (const_cast<_Base_ptr
>(__position
._M_node
),
2453 this->_M_impl
._M_header
));
2455 --_M_impl
._M_node_count
;
2458 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2459 typename _Compare
, typename _Alloc
>
2461 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2462 _M_erase_aux(const_iterator __first
, const_iterator __last
)
2464 if (__first
== begin() && __last
== end())
2467 while (__first
!= __last
)
2471 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2472 typename _Compare
, typename _Alloc
>
2473 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2474 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2475 erase(const _Key
& __x
)
2477 pair
<iterator
, iterator
> __p
= equal_range(__x
);
2478 const size_type __old_size
= size();
2479 erase(__p
.first
, __p
.second
);
2480 return __old_size
- size();
2483 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2484 typename _Compare
, typename _Alloc
>
2486 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2487 erase(const _Key
* __first
, const _Key
* __last
)
2489 while (__first
!= __last
)
2493 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2494 typename _Compare
, typename _Alloc
>
2495 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2496 _Compare
, _Alloc
>::iterator
2497 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2498 find(const _Key
& __k
)
2500 iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2501 return (__j
== end()
2502 || _M_impl
._M_key_compare(__k
,
2503 _S_key(__j
._M_node
))) ? end() : __j
;
2506 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2507 typename _Compare
, typename _Alloc
>
2508 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2509 _Compare
, _Alloc
>::const_iterator
2510 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2511 find(const _Key
& __k
) const
2513 const_iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2514 return (__j
== end()
2515 || _M_impl
._M_key_compare(__k
,
2516 _S_key(__j
._M_node
))) ? end() : __j
;
2519 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2520 typename _Compare
, typename _Alloc
>
2521 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2522 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2523 count(const _Key
& __k
) const
2525 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
2526 const size_type __n
= std::distance(__p
.first
, __p
.second
);
2530 _GLIBCXX_PURE
unsigned int
2531 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
2532 const _Rb_tree_node_base
* __root
) throw ();
2534 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2535 typename _Compare
, typename _Alloc
>
2537 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
2539 if (_M_impl
._M_node_count
== 0 || begin() == end())
2540 return _M_impl
._M_node_count
== 0 && begin() == end()
2541 && this->_M_impl
._M_header
._M_left
== _M_end()
2542 && this->_M_impl
._M_header
._M_right
== _M_end();
2544 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
2545 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
2547 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
2548 _Const_Link_type __L
= _S_left(__x
);
2549 _Const_Link_type __R
= _S_right(__x
);
2551 if (__x
->_M_color
== _S_red
)
2552 if ((__L
&& __L
->_M_color
== _S_red
)
2553 || (__R
&& __R
->_M_color
== _S_red
))
2556 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
2558 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
2561 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
2565 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2567 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2572 #if __cplusplus > 201402L
2573 // Allow access to internals of compatible _Rb_tree specializations.
2574 template<typename _Key
, typename _Val
, typename _Sel
, typename _Cmp1
,
2575 typename _Alloc
, typename _Cmp2
>
2576 struct _Rb_tree_merge_helper
<_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>,
2580 friend class _Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>;
2583 _S_get_impl(_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp2
, _Alloc
>& __tree
)
2584 { return __tree
._M_impl
; }
2588 _GLIBCXX_END_NAMESPACE_VERSION