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 _GLIBCXX_NOEXCEPT_IF(
610 is_nothrow_default_constructible
<_Node_allocator
>::value
611 && is_nothrow_default_constructible
<_Key_compare
>::value
)
612 : _Node_allocator(), _M_key_compare(), _M_header(),
616 _Rb_tree_impl(const _Key_compare
& __comp
, const _Node_allocator
& __a
)
617 : _Node_allocator(__a
), _M_key_compare(__comp
), _M_header(),
621 #if __cplusplus >= 201103L
622 _Rb_tree_impl(const _Key_compare
& __comp
, _Node_allocator
&& __a
)
623 : _Node_allocator(std::move(__a
)), _M_key_compare(__comp
),
624 _M_header(), _M_node_count(0)
631 this->_M_header
._M_parent
= 0;
632 this->_M_header
._M_left
= &this->_M_header
;
633 this->_M_header
._M_right
= &this->_M_header
;
634 this->_M_node_count
= 0;
641 this->_M_header
._M_color
= _S_red
;
642 this->_M_header
._M_parent
= 0;
643 this->_M_header
._M_left
= &this->_M_header
;
644 this->_M_header
._M_right
= &this->_M_header
;
648 _Rb_tree_impl
<_Compare
> _M_impl
;
652 _M_root() _GLIBCXX_NOEXCEPT
653 { return this->_M_impl
._M_header
._M_parent
; }
656 _M_root() const _GLIBCXX_NOEXCEPT
657 { return this->_M_impl
._M_header
._M_parent
; }
660 _M_leftmost() _GLIBCXX_NOEXCEPT
661 { return this->_M_impl
._M_header
._M_left
; }
664 _M_leftmost() const _GLIBCXX_NOEXCEPT
665 { return this->_M_impl
._M_header
._M_left
; }
668 _M_rightmost() _GLIBCXX_NOEXCEPT
669 { return this->_M_impl
._M_header
._M_right
; }
672 _M_rightmost() const _GLIBCXX_NOEXCEPT
673 { return this->_M_impl
._M_header
._M_right
; }
676 _M_begin() _GLIBCXX_NOEXCEPT
677 { return static_cast<_Link_type
>(this->_M_impl
._M_header
._M_parent
); }
680 _M_begin() const _GLIBCXX_NOEXCEPT
682 return static_cast<_Const_Link_type
>
683 (this->_M_impl
._M_header
._M_parent
);
687 _M_end() _GLIBCXX_NOEXCEPT
688 { return &this->_M_impl
._M_header
; }
691 _M_end() const _GLIBCXX_NOEXCEPT
692 { return &this->_M_impl
._M_header
; }
694 static const_reference
695 _S_value(_Const_Link_type __x
)
696 { return *__x
->_M_valptr(); }
699 _S_key(_Const_Link_type __x
)
700 { return _KeyOfValue()(_S_value(__x
)); }
703 _S_left(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
704 { return static_cast<_Link_type
>(__x
->_M_left
); }
706 static _Const_Link_type
707 _S_left(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
708 { return static_cast<_Const_Link_type
>(__x
->_M_left
); }
711 _S_right(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
712 { return static_cast<_Link_type
>(__x
->_M_right
); }
714 static _Const_Link_type
715 _S_right(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
716 { return static_cast<_Const_Link_type
>(__x
->_M_right
); }
718 static const_reference
719 _S_value(_Const_Base_ptr __x
)
720 { return *static_cast<_Const_Link_type
>(__x
)->_M_valptr(); }
723 _S_key(_Const_Base_ptr __x
)
724 { return _KeyOfValue()(_S_value(__x
)); }
727 _S_minimum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
728 { return _Rb_tree_node_base::_S_minimum(__x
); }
730 static _Const_Base_ptr
731 _S_minimum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
732 { return _Rb_tree_node_base::_S_minimum(__x
); }
735 _S_maximum(_Base_ptr __x
) _GLIBCXX_NOEXCEPT
736 { return _Rb_tree_node_base::_S_maximum(__x
); }
738 static _Const_Base_ptr
739 _S_maximum(_Const_Base_ptr __x
) _GLIBCXX_NOEXCEPT
740 { return _Rb_tree_node_base::_S_maximum(__x
); }
743 typedef _Rb_tree_iterator
<value_type
> iterator
;
744 typedef _Rb_tree_const_iterator
<value_type
> const_iterator
;
746 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
747 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
749 #if __cplusplus > 201402L
750 using node_type
= _Node_handle
<_Key
, _Val
, _Node_allocator
>;
751 using insert_return_type
= _Node_insert_return
<iterator
, node_type
>;
754 pair
<_Base_ptr
, _Base_ptr
>
755 _M_get_insert_unique_pos(const key_type
& __k
);
757 pair
<_Base_ptr
, _Base_ptr
>
758 _M_get_insert_equal_pos(const key_type
& __k
);
760 pair
<_Base_ptr
, _Base_ptr
>
761 _M_get_insert_hint_unique_pos(const_iterator __pos
,
762 const key_type
& __k
);
764 pair
<_Base_ptr
, _Base_ptr
>
765 _M_get_insert_hint_equal_pos(const_iterator __pos
,
766 const key_type
& __k
);
769 #if __cplusplus >= 201103L
770 template<typename _Arg
, typename _NodeGen
>
772 _M_insert_(_Base_ptr __x
, _Base_ptr __y
, _Arg
&& __v
, _NodeGen
&);
775 _M_insert_node(_Base_ptr __x
, _Base_ptr __y
, _Link_type __z
);
777 template<typename _Arg
>
779 _M_insert_lower(_Base_ptr __y
, _Arg
&& __v
);
781 template<typename _Arg
>
783 _M_insert_equal_lower(_Arg
&& __x
);
786 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
);
789 _M_insert_equal_lower_node(_Link_type __z
);
791 template<typename _NodeGen
>
793 _M_insert_(_Base_ptr __x
, _Base_ptr __y
,
794 const value_type
& __v
, _NodeGen
&);
796 // _GLIBCXX_RESOLVE_LIB_DEFECTS
797 // 233. Insertion hints in associative containers.
799 _M_insert_lower(_Base_ptr __y
, const value_type
& __v
);
802 _M_insert_equal_lower(const value_type
& __x
);
805 template<typename _NodeGen
>
807 _M_copy(_Const_Link_type __x
, _Base_ptr __p
, _NodeGen
&);
810 _M_copy(_Const_Link_type __x
, _Base_ptr __p
)
812 _Alloc_node
__an(*this);
813 return _M_copy(__x
, __p
, __an
);
817 _M_erase(_Link_type __x
);
820 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
824 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
825 const _Key
& __k
) const;
828 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
832 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
833 const _Key
& __k
) const;
836 // allocation/deallocation
837 #if __cplusplus < 201103L
840 _Rb_tree() = default;
843 _Rb_tree(const _Compare
& __comp
,
844 const allocator_type
& __a
= allocator_type())
845 : _M_impl(__comp
, _Node_allocator(__a
)) { }
847 _Rb_tree(const _Rb_tree
& __x
)
848 : _M_impl(__x
._M_impl
._M_key_compare
,
849 _Alloc_traits::_S_select_on_copy(__x
._M_get_Node_allocator()))
851 if (__x
._M_root() != 0)
853 _M_root() = _M_copy(__x
._M_begin(), _M_end());
854 _M_leftmost() = _S_minimum(_M_root());
855 _M_rightmost() = _S_maximum(_M_root());
856 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
860 #if __cplusplus >= 201103L
861 _Rb_tree(const allocator_type
& __a
)
862 : _M_impl(_Compare(), _Node_allocator(__a
))
865 _Rb_tree(const _Rb_tree
& __x
, const allocator_type
& __a
)
866 : _M_impl(__x
._M_impl
._M_key_compare
, _Node_allocator(__a
))
868 if (__x
._M_root() != nullptr)
870 _M_root() = _M_copy(__x
._M_begin(), _M_end());
871 _M_leftmost() = _S_minimum(_M_root());
872 _M_rightmost() = _S_maximum(_M_root());
873 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
877 _Rb_tree(_Rb_tree
&& __x
)
878 : _M_impl(__x
._M_impl
._M_key_compare
,
879 std::move(__x
._M_get_Node_allocator()))
881 if (__x
._M_root() != 0)
882 _M_move_data(__x
, std::true_type());
885 _Rb_tree(_Rb_tree
&& __x
, const allocator_type
& __a
)
886 : _Rb_tree(std::move(__x
), _Node_allocator(__a
))
889 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
);
892 ~_Rb_tree() _GLIBCXX_NOEXCEPT
893 { _M_erase(_M_begin()); }
896 operator=(const _Rb_tree
& __x
);
901 { return _M_impl
._M_key_compare
; }
904 begin() _GLIBCXX_NOEXCEPT
905 { return iterator(this->_M_impl
._M_header
._M_left
); }
908 begin() const _GLIBCXX_NOEXCEPT
909 { return const_iterator(this->_M_impl
._M_header
._M_left
); }
912 end() _GLIBCXX_NOEXCEPT
913 { return iterator(&this->_M_impl
._M_header
); }
916 end() const _GLIBCXX_NOEXCEPT
917 { return const_iterator(&this->_M_impl
._M_header
); }
920 rbegin() _GLIBCXX_NOEXCEPT
921 { return reverse_iterator(end()); }
923 const_reverse_iterator
924 rbegin() const _GLIBCXX_NOEXCEPT
925 { return const_reverse_iterator(end()); }
928 rend() _GLIBCXX_NOEXCEPT
929 { return reverse_iterator(begin()); }
931 const_reverse_iterator
932 rend() const _GLIBCXX_NOEXCEPT
933 { return const_reverse_iterator(begin()); }
936 empty() const _GLIBCXX_NOEXCEPT
937 { return _M_impl
._M_node_count
== 0; }
940 size() const _GLIBCXX_NOEXCEPT
941 { return _M_impl
._M_node_count
; }
944 max_size() const _GLIBCXX_NOEXCEPT
945 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
949 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
);
952 #if __cplusplus >= 201103L
953 template<typename _Arg
>
955 _M_insert_unique(_Arg
&& __x
);
957 template<typename _Arg
>
959 _M_insert_equal(_Arg
&& __x
);
961 template<typename _Arg
, typename _NodeGen
>
963 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
965 template<typename _Arg
>
967 _M_insert_unique_(const_iterator __pos
, _Arg
&& __x
)
969 _Alloc_node
__an(*this);
970 return _M_insert_unique_(__pos
, std::forward
<_Arg
>(__x
), __an
);
973 template<typename _Arg
, typename _NodeGen
>
975 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
, _NodeGen
&);
977 template<typename _Arg
>
979 _M_insert_equal_(const_iterator __pos
, _Arg
&& __x
)
981 _Alloc_node
__an(*this);
982 return _M_insert_equal_(__pos
, std::forward
<_Arg
>(__x
), __an
);
985 template<typename
... _Args
>
987 _M_emplace_unique(_Args
&&... __args
);
989 template<typename
... _Args
>
991 _M_emplace_equal(_Args
&&... __args
);
993 template<typename
... _Args
>
995 _M_emplace_hint_unique(const_iterator __pos
, _Args
&&... __args
);
997 template<typename
... _Args
>
999 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
);
1001 pair
<iterator
, bool>
1002 _M_insert_unique(const value_type
& __x
);
1005 _M_insert_equal(const value_type
& __x
);
1007 template<typename _NodeGen
>
1009 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
,
1013 _M_insert_unique_(const_iterator __pos
, const value_type
& __x
)
1015 _Alloc_node
__an(*this);
1016 return _M_insert_unique_(__pos
, __x
, __an
);
1019 template<typename _NodeGen
>
1021 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
,
1024 _M_insert_equal_(const_iterator __pos
, const value_type
& __x
)
1026 _Alloc_node
__an(*this);
1027 return _M_insert_equal_(__pos
, __x
, __an
);
1031 template<typename _InputIterator
>
1033 _M_insert_unique(_InputIterator __first
, _InputIterator __last
);
1035 template<typename _InputIterator
>
1037 _M_insert_equal(_InputIterator __first
, _InputIterator __last
);
1041 _M_erase_aux(const_iterator __position
);
1044 _M_erase_aux(const_iterator __first
, const_iterator __last
);
1047 #if __cplusplus >= 201103L
1048 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1049 // DR 130. Associative erase should return an iterator.
1050 _GLIBCXX_ABI_TAG_CXX11
1052 erase(const_iterator __position
)
1054 const_iterator __result
= __position
;
1056 _M_erase_aux(__position
);
1057 return __result
._M_const_cast();
1061 _GLIBCXX_ABI_TAG_CXX11
1063 erase(iterator __position
)
1065 iterator __result
= __position
;
1067 _M_erase_aux(__position
);
1072 erase(iterator __position
)
1073 { _M_erase_aux(__position
); }
1076 erase(const_iterator __position
)
1077 { _M_erase_aux(__position
); }
1080 erase(const key_type
& __x
);
1082 #if __cplusplus >= 201103L
1083 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1084 // DR 130. Associative erase should return an iterator.
1085 _GLIBCXX_ABI_TAG_CXX11
1087 erase(const_iterator __first
, const_iterator __last
)
1089 _M_erase_aux(__first
, __last
);
1090 return __last
._M_const_cast();
1094 erase(iterator __first
, iterator __last
)
1095 { _M_erase_aux(__first
, __last
); }
1098 erase(const_iterator __first
, const_iterator __last
)
1099 { _M_erase_aux(__first
, __last
); }
1102 erase(const key_type
* __first
, const key_type
* __last
);
1105 clear() _GLIBCXX_NOEXCEPT
1107 _M_erase(_M_begin());
1113 find(const key_type
& __k
);
1116 find(const key_type
& __k
) const;
1119 count(const key_type
& __k
) const;
1122 lower_bound(const key_type
& __k
)
1123 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1126 lower_bound(const key_type
& __k
) const
1127 { return _M_lower_bound(_M_begin(), _M_end(), __k
); }
1130 upper_bound(const key_type
& __k
)
1131 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1134 upper_bound(const key_type
& __k
) const
1135 { return _M_upper_bound(_M_begin(), _M_end(), __k
); }
1137 pair
<iterator
, iterator
>
1138 equal_range(const key_type
& __k
);
1140 pair
<const_iterator
, const_iterator
>
1141 equal_range(const key_type
& __k
) const;
1143 #if __cplusplus > 201103L
1144 template<typename _Kt
,
1146 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1148 _M_find_tr(const _Kt
& __k
)
1150 const _Rb_tree
* __const_this
= this;
1151 return __const_this
->_M_find_tr(__k
)._M_const_cast();
1154 template<typename _Kt
,
1156 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1158 _M_find_tr(const _Kt
& __k
) const
1160 auto __j
= _M_lower_bound_tr(__k
);
1161 if (__j
!= end() && _M_impl
._M_key_compare(__k
, _S_key(__j
._M_node
)))
1166 template<typename _Kt
,
1168 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1170 _M_count_tr(const _Kt
& __k
) const
1172 auto __p
= _M_equal_range_tr(__k
);
1173 return std::distance(__p
.first
, __p
.second
);
1176 template<typename _Kt
,
1178 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1180 _M_lower_bound_tr(const _Kt
& __k
)
1182 const _Rb_tree
* __const_this
= this;
1183 return __const_this
->_M_lower_bound_tr(__k
)._M_const_cast();
1186 template<typename _Kt
,
1188 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1190 _M_lower_bound_tr(const _Kt
& __k
) const
1192 auto __x
= _M_begin();
1193 auto __y
= _M_end();
1195 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1201 __x
= _S_right(__x
);
1202 return const_iterator(__y
);
1205 template<typename _Kt
,
1207 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1209 _M_upper_bound_tr(const _Kt
& __k
)
1211 const _Rb_tree
* __const_this
= this;
1212 return __const_this
->_M_upper_bound_tr(__k
)._M_const_cast();
1215 template<typename _Kt
,
1217 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1219 _M_upper_bound_tr(const _Kt
& __k
) const
1221 auto __x
= _M_begin();
1222 auto __y
= _M_end();
1224 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1230 __x
= _S_right(__x
);
1231 return const_iterator(__y
);
1234 template<typename _Kt
,
1236 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1237 pair
<iterator
, iterator
>
1238 _M_equal_range_tr(const _Kt
& __k
)
1240 const _Rb_tree
* __const_this
= this;
1241 auto __ret
= __const_this
->_M_equal_range_tr(__k
);
1242 return { __ret
.first
._M_const_cast(), __ret
.second
._M_const_cast() };
1245 template<typename _Kt
,
1247 typename __has_is_transparent
<_Compare
, _Kt
>::type
>
1248 pair
<const_iterator
, const_iterator
>
1249 _M_equal_range_tr(const _Kt
& __k
) const
1251 auto __low
= _M_lower_bound_tr(__k
);
1252 auto __high
= __low
;
1253 auto& __cmp
= _M_impl
._M_key_compare
;
1254 while (__high
!= end() && !__cmp(__k
, _S_key(__high
._M_node
)))
1256 return { __low
, __high
};
1262 __rb_verify() const;
1264 #if __cplusplus >= 201103L
1266 operator=(_Rb_tree
&&)
1267 noexcept(_Alloc_traits::_S_nothrow_move()
1268 && is_nothrow_move_assignable
<_Compare
>::value
);
1270 template<typename _Iterator
>
1272 _M_assign_unique(_Iterator
, _Iterator
);
1274 template<typename _Iterator
>
1276 _M_assign_equal(_Iterator
, _Iterator
);
1279 // Move elements from container with equal allocator.
1281 _M_move_data(_Rb_tree
&, std::true_type
);
1283 // Move elements from container with possibly non-equal allocator,
1284 // which might result in a copy not a move.
1286 _M_move_data(_Rb_tree
&, std::false_type
);
1288 // Move assignment from container with equal allocator.
1290 _M_move_assign(_Rb_tree
&, std::true_type
);
1292 // Move assignment from container with possibly non-equal allocator,
1293 // which might result in a copy not a move.
1295 _M_move_assign(_Rb_tree
&, std::false_type
);
1298 #if __cplusplus > 201402L
1300 /// Re-insert an extracted node.
1302 _M_reinsert_node_unique(node_type
&& __nh
)
1304 insert_return_type __ret
;
1306 __ret
.position
= end();
1309 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1311 auto __res
= _M_get_insert_unique_pos(__nh
._M_key());
1315 = _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1316 __nh
._M_ptr
= nullptr;
1317 __ret
.inserted
= true;
1321 __ret
.node
= std::move(__nh
);
1322 __ret
.position
= iterator(__res
.first
);
1323 __ret
.inserted
= false;
1329 /// Re-insert an extracted node.
1331 _M_reinsert_node_equal(node_type
&& __nh
)
1338 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1339 auto __res
= _M_get_insert_equal_pos(__nh
._M_key());
1341 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1343 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1344 __nh
._M_ptr
= nullptr;
1349 /// Re-insert an extracted node.
1351 _M_reinsert_node_hint_unique(const_iterator __hint
, node_type
&& __nh
)
1358 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1359 auto __res
= _M_get_insert_hint_unique_pos(__hint
, __nh
._M_key());
1362 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1363 __nh
._M_ptr
= nullptr;
1366 __ret
= iterator(__res
.first
);
1371 /// Re-insert an extracted node.
1373 _M_reinsert_node_hint_equal(const_iterator __hint
, node_type
&& __nh
)
1380 __glibcxx_assert(_M_get_Node_allocator() == *__nh
._M_alloc
);
1381 auto __res
= _M_get_insert_hint_equal_pos(__hint
, __nh
._M_key());
1383 __ret
= _M_insert_node(__res
.first
, __res
.second
, __nh
._M_ptr
);
1385 __ret
= _M_insert_equal_lower_node(__nh
._M_ptr
);
1386 __nh
._M_ptr
= nullptr;
1393 extract(const_iterator __pos
)
1395 auto __ptr
= _Rb_tree_rebalance_for_erase(
1396 __pos
._M_const_cast()._M_node
, _M_impl
._M_header
);
1397 --_M_impl
._M_node_count
;
1398 return { static_cast<_Link_type
>(__ptr
), _M_get_Node_allocator() };
1403 extract(const key_type
& __k
)
1406 auto __pos
= find(__k
);
1408 __nh
= extract(const_iterator(__pos
));
1412 template<typename _Compare2
>
1413 using _Compatible_tree
1414 = _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare2
, _Alloc
>;
1416 template<typename
, typename
>
1417 friend class _Rb_tree_merge_helper
;
1419 /// Merge from a compatible container into one with unique keys.
1420 template<typename _Compare2
>
1422 _M_merge_unique(_Compatible_tree
<_Compare2
>& __src
) noexcept
1424 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1425 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1428 auto __res
= _M_get_insert_unique_pos(_KeyOfValue()(*__pos
));
1431 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1432 auto __ptr
= _Rb_tree_rebalance_for_erase(
1433 __pos
._M_node
, __src_impl
._M_header
);
1434 --__src_impl
._M_node_count
;
1435 _M_insert_node(__res
.first
, __res
.second
,
1436 static_cast<_Link_type
>(__ptr
));
1441 /// Merge from a compatible container into one with equivalent keys.
1442 template<typename _Compare2
>
1444 _M_merge_equal(_Compatible_tree
<_Compare2
>& __src
) noexcept
1446 using _Merge_helper
= _Rb_tree_merge_helper
<_Rb_tree
, _Compare2
>;
1447 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
1450 auto __res
= _M_get_insert_equal_pos(_KeyOfValue()(*__pos
));
1453 auto& __src_impl
= _Merge_helper::_S_get_impl(__src
);
1454 auto __ptr
= _Rb_tree_rebalance_for_erase(
1455 __pos
._M_node
, __src_impl
._M_header
);
1456 --__src_impl
._M_node_count
;
1457 _M_insert_node(__res
.first
, __res
.second
,
1458 static_cast<_Link_type
>(__ptr
));
1465 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1466 typename _Compare
, typename _Alloc
>
1468 operator==(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1469 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1471 return __x
.size() == __y
.size()
1472 && std::equal(__x
.begin(), __x
.end(), __y
.begin());
1475 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1476 typename _Compare
, typename _Alloc
>
1478 operator<(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1479 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1481 return std::lexicographical_compare(__x
.begin(), __x
.end(),
1482 __y
.begin(), __y
.end());
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 !(__x
== __y
); }
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 !(__y
< __x
); }
1506 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1507 typename _Compare
, typename _Alloc
>
1509 operator>=(const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1510 const _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1511 { return !(__x
< __y
); }
1513 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1514 typename _Compare
, typename _Alloc
>
1516 swap(_Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __x
,
1517 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>& __y
)
1520 #if __cplusplus >= 201103L
1521 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1522 typename _Compare
, typename _Alloc
>
1523 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1524 _Rb_tree(_Rb_tree
&& __x
, _Node_allocator
&& __a
)
1525 : _M_impl(__x
._M_impl
._M_key_compare
, std::move(__a
))
1527 using __eq
= typename
_Alloc_traits::is_always_equal
;
1528 if (__x
._M_root() != nullptr)
1529 _M_move_data(__x
, __eq());
1532 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1533 typename _Compare
, typename _Alloc
>
1535 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1536 _M_move_data(_Rb_tree
& __x
, std::true_type
)
1538 _M_root() = __x
._M_root();
1539 _M_leftmost() = __x
._M_leftmost();
1540 _M_rightmost() = __x
._M_rightmost();
1541 _M_root()->_M_parent
= _M_end();
1544 __x
._M_leftmost() = __x
._M_end();
1545 __x
._M_rightmost() = __x
._M_end();
1547 this->_M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1548 __x
._M_impl
._M_node_count
= 0;
1551 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1552 typename _Compare
, typename _Alloc
>
1554 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1555 _M_move_data(_Rb_tree
& __x
, std::false_type
)
1557 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1558 _M_move_data(__x
, std::true_type());
1561 _Alloc_node
__an(*this);
1563 [&__an
](const value_type
& __cval
)
1565 auto& __val
= const_cast<value_type
&>(__cval
);
1566 return __an(std::move_if_noexcept(__val
));
1568 _M_root() = _M_copy(__x
._M_begin(), _M_end(), __lbd
);
1569 _M_leftmost() = _S_minimum(_M_root());
1570 _M_rightmost() = _S_maximum(_M_root());
1571 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1575 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1576 typename _Compare
, typename _Alloc
>
1578 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1579 _M_move_assign(_Rb_tree
& __x
, true_type
)
1582 if (__x
._M_root() != nullptr)
1583 _M_move_data(__x
, std::true_type());
1584 std::__alloc_on_move(_M_get_Node_allocator(),
1585 __x
._M_get_Node_allocator());
1588 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1589 typename _Compare
, typename _Alloc
>
1591 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1592 _M_move_assign(_Rb_tree
& __x
, false_type
)
1594 if (_M_get_Node_allocator() == __x
._M_get_Node_allocator())
1595 return _M_move_assign(__x
, true_type
{});
1597 // Try to move each node reusing existing nodes and copying __x nodes
1599 _Reuse_or_alloc_node
__roan(*this);
1601 if (__x
._M_root() != nullptr)
1604 [&__roan
](const value_type
& __cval
)
1606 auto& __val
= const_cast<value_type
&>(__cval
);
1607 return __roan(std::move_if_noexcept(__val
));
1609 _M_root() = _M_copy(__x
._M_begin(), _M_end(), __lbd
);
1610 _M_leftmost() = _S_minimum(_M_root());
1611 _M_rightmost() = _S_maximum(_M_root());
1612 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1617 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1618 typename _Compare
, typename _Alloc
>
1619 inline _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1620 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1621 operator=(_Rb_tree
&& __x
)
1622 noexcept(_Alloc_traits::_S_nothrow_move()
1623 && is_nothrow_move_assignable
<_Compare
>::value
)
1625 _M_impl
._M_key_compare
= std::move(__x
._M_impl
._M_key_compare
);
1626 constexpr bool __move_storage
=
1627 _Alloc_traits::_S_propagate_on_move_assign()
1628 || _Alloc_traits::_S_always_equal();
1629 _M_move_assign(__x
, __bool_constant
<__move_storage
>());
1633 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1634 typename _Compare
, typename _Alloc
>
1635 template<typename _Iterator
>
1637 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1638 _M_assign_unique(_Iterator __first
, _Iterator __last
)
1640 _Reuse_or_alloc_node
__roan(*this);
1642 for (; __first
!= __last
; ++__first
)
1643 _M_insert_unique_(end(), *__first
, __roan
);
1646 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1647 typename _Compare
, typename _Alloc
>
1648 template<typename _Iterator
>
1650 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1651 _M_assign_equal(_Iterator __first
, _Iterator __last
)
1653 _Reuse_or_alloc_node
__roan(*this);
1655 for (; __first
!= __last
; ++__first
)
1656 _M_insert_equal_(end(), *__first
, __roan
);
1660 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1661 typename _Compare
, typename _Alloc
>
1662 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>&
1663 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1664 operator=(const _Rb_tree
& __x
)
1668 // Note that _Key may be a constant type.
1669 #if __cplusplus >= 201103L
1670 if (_Alloc_traits::_S_propagate_on_copy_assign())
1672 auto& __this_alloc
= this->_M_get_Node_allocator();
1673 auto& __that_alloc
= __x
._M_get_Node_allocator();
1674 if (!_Alloc_traits::_S_always_equal()
1675 && __this_alloc
!= __that_alloc
)
1677 // Replacement allocator cannot free existing storage, we need
1678 // to erase nodes first.
1680 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1685 _Reuse_or_alloc_node
__roan(*this);
1687 _M_impl
._M_key_compare
= __x
._M_impl
._M_key_compare
;
1688 if (__x
._M_root() != 0)
1690 _M_root() = _M_copy(__x
._M_begin(), _M_end(), __roan
);
1691 _M_leftmost() = _S_minimum(_M_root());
1692 _M_rightmost() = _S_maximum(_M_root());
1693 _M_impl
._M_node_count
= __x
._M_impl
._M_node_count
;
1700 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1701 typename _Compare
, typename _Alloc
>
1702 #if __cplusplus >= 201103L
1703 template<typename _Arg
, typename _NodeGen
>
1705 template<typename _NodeGen
>
1707 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1708 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1709 _M_insert_(_Base_ptr __x
, _Base_ptr __p
,
1710 #if __cplusplus >= 201103L
1715 _NodeGen
& __node_gen
)
1717 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
1718 || _M_impl
._M_key_compare(_KeyOfValue()(__v
),
1721 _Link_type __z
= __node_gen(_GLIBCXX_FORWARD(_Arg
, __v
));
1723 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1724 this->_M_impl
._M_header
);
1725 ++_M_impl
._M_node_count
;
1726 return iterator(__z
);
1729 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1730 typename _Compare
, typename _Alloc
>
1731 #if __cplusplus >= 201103L
1732 template<typename _Arg
>
1734 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1735 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1736 #if __cplusplus >= 201103L
1737 _M_insert_lower(_Base_ptr __p
, _Arg
&& __v
)
1739 _M_insert_lower(_Base_ptr __p
, const _Val
& __v
)
1742 bool __insert_left
= (__p
== _M_end()
1743 || !_M_impl
._M_key_compare(_S_key(__p
),
1744 _KeyOfValue()(__v
)));
1746 _Link_type __z
= _M_create_node(_GLIBCXX_FORWARD(_Arg
, __v
));
1748 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
1749 this->_M_impl
._M_header
);
1750 ++_M_impl
._M_node_count
;
1751 return iterator(__z
);
1754 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1755 typename _Compare
, typename _Alloc
>
1756 #if __cplusplus >= 201103L
1757 template<typename _Arg
>
1759 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1760 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1761 #if __cplusplus >= 201103L
1762 _M_insert_equal_lower(_Arg
&& __v
)
1764 _M_insert_equal_lower(const _Val
& __v
)
1767 _Link_type __x
= _M_begin();
1768 _Base_ptr __y
= _M_end();
1772 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _KeyOfValue()(__v
)) ?
1773 _S_left(__x
) : _S_right(__x
);
1775 return _M_insert_lower(__y
, _GLIBCXX_FORWARD(_Arg
, __v
));
1778 template<typename _Key
, typename _Val
, typename _KoV
,
1779 typename _Compare
, typename _Alloc
>
1780 template<typename _NodeGen
>
1781 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1782 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::
1783 _M_copy(_Const_Link_type __x
, _Base_ptr __p
, _NodeGen
& __node_gen
)
1785 // Structural copy. __x and __p must be non-null.
1786 _Link_type __top
= _M_clone_node(__x
, __node_gen
);
1787 __top
->_M_parent
= __p
;
1792 __top
->_M_right
= _M_copy(_S_right(__x
), __top
, __node_gen
);
1798 _Link_type __y
= _M_clone_node(__x
, __node_gen
);
1800 __y
->_M_parent
= __p
;
1802 __y
->_M_right
= _M_copy(_S_right(__x
), __y
, __node_gen
);
1810 __throw_exception_again
;
1815 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1816 typename _Compare
, typename _Alloc
>
1818 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1819 _M_erase(_Link_type __x
)
1821 // Erase without rebalancing.
1824 _M_erase(_S_right(__x
));
1825 _Link_type __y
= _S_left(__x
);
1831 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1832 typename _Compare
, typename _Alloc
>
1833 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1834 _Compare
, _Alloc
>::iterator
1835 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1836 _M_lower_bound(_Link_type __x
, _Base_ptr __y
,
1840 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1841 __y
= __x
, __x
= _S_left(__x
);
1843 __x
= _S_right(__x
);
1844 return iterator(__y
);
1847 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1848 typename _Compare
, typename _Alloc
>
1849 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1850 _Compare
, _Alloc
>::const_iterator
1851 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1852 _M_lower_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1853 const _Key
& __k
) const
1856 if (!_M_impl
._M_key_compare(_S_key(__x
), __k
))
1857 __y
= __x
, __x
= _S_left(__x
);
1859 __x
= _S_right(__x
);
1860 return const_iterator(__y
);
1863 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1864 typename _Compare
, typename _Alloc
>
1865 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1866 _Compare
, _Alloc
>::iterator
1867 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1868 _M_upper_bound(_Link_type __x
, _Base_ptr __y
,
1872 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1873 __y
= __x
, __x
= _S_left(__x
);
1875 __x
= _S_right(__x
);
1876 return iterator(__y
);
1879 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1880 typename _Compare
, typename _Alloc
>
1881 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1882 _Compare
, _Alloc
>::const_iterator
1883 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1884 _M_upper_bound(_Const_Link_type __x
, _Const_Base_ptr __y
,
1885 const _Key
& __k
) const
1888 if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1889 __y
= __x
, __x
= _S_left(__x
);
1891 __x
= _S_right(__x
);
1892 return const_iterator(__y
);
1895 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1896 typename _Compare
, typename _Alloc
>
1897 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1898 _Compare
, _Alloc
>::iterator
,
1899 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1900 _Compare
, _Alloc
>::iterator
>
1901 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1902 equal_range(const _Key
& __k
)
1904 _Link_type __x
= _M_begin();
1905 _Base_ptr __y
= _M_end();
1908 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1909 __x
= _S_right(__x
);
1910 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1911 __y
= __x
, __x
= _S_left(__x
);
1914 _Link_type
__xu(__x
);
1915 _Base_ptr
__yu(__y
);
1916 __y
= __x
, __x
= _S_left(__x
);
1917 __xu
= _S_right(__xu
);
1918 return pair
<iterator
,
1919 iterator
>(_M_lower_bound(__x
, __y
, __k
),
1920 _M_upper_bound(__xu
, __yu
, __k
));
1923 return pair
<iterator
, iterator
>(iterator(__y
),
1927 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1928 typename _Compare
, typename _Alloc
>
1929 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1930 _Compare
, _Alloc
>::const_iterator
,
1931 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
1932 _Compare
, _Alloc
>::const_iterator
>
1933 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1934 equal_range(const _Key
& __k
) const
1936 _Const_Link_type __x
= _M_begin();
1937 _Const_Base_ptr __y
= _M_end();
1940 if (_M_impl
._M_key_compare(_S_key(__x
), __k
))
1941 __x
= _S_right(__x
);
1942 else if (_M_impl
._M_key_compare(__k
, _S_key(__x
)))
1943 __y
= __x
, __x
= _S_left(__x
);
1946 _Const_Link_type
__xu(__x
);
1947 _Const_Base_ptr
__yu(__y
);
1948 __y
= __x
, __x
= _S_left(__x
);
1949 __xu
= _S_right(__xu
);
1950 return pair
<const_iterator
,
1951 const_iterator
>(_M_lower_bound(__x
, __y
, __k
),
1952 _M_upper_bound(__xu
, __yu
, __k
));
1955 return pair
<const_iterator
, const_iterator
>(const_iterator(__y
),
1956 const_iterator(__y
));
1959 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1960 typename _Compare
, typename _Alloc
>
1962 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1964 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable
<_Compare
>::value
)
1968 if (__t
._M_root() != 0)
1970 _M_root() = __t
._M_root();
1971 _M_leftmost() = __t
._M_leftmost();
1972 _M_rightmost() = __t
._M_rightmost();
1973 _M_root()->_M_parent
= _M_end();
1974 _M_impl
._M_node_count
= __t
._M_impl
._M_node_count
;
1976 __t
._M_impl
._M_reset();
1979 else if (__t
._M_root() == 0)
1981 __t
._M_root() = _M_root();
1982 __t
._M_leftmost() = _M_leftmost();
1983 __t
._M_rightmost() = _M_rightmost();
1984 __t
._M_root()->_M_parent
= __t
._M_end();
1985 __t
._M_impl
._M_node_count
= _M_impl
._M_node_count
;
1991 std::swap(_M_root(),__t
._M_root());
1992 std::swap(_M_leftmost(),__t
._M_leftmost());
1993 std::swap(_M_rightmost(),__t
._M_rightmost());
1995 _M_root()->_M_parent
= _M_end();
1996 __t
._M_root()->_M_parent
= __t
._M_end();
1997 std::swap(this->_M_impl
._M_node_count
, __t
._M_impl
._M_node_count
);
1999 // No need to swap header's color as it does not change.
2000 std::swap(this->_M_impl
._M_key_compare
, __t
._M_impl
._M_key_compare
);
2002 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2003 __t
._M_get_Node_allocator());
2006 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2007 typename _Compare
, typename _Alloc
>
2008 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2009 _Compare
, _Alloc
>::_Base_ptr
,
2010 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2011 _Compare
, _Alloc
>::_Base_ptr
>
2012 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2013 _M_get_insert_unique_pos(const key_type
& __k
)
2015 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2016 _Link_type __x
= _M_begin();
2017 _Base_ptr __y
= _M_end();
2022 __comp
= _M_impl
._M_key_compare(__k
, _S_key(__x
));
2023 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
2025 iterator __j
= iterator(__y
);
2029 return _Res(__x
, __y
);
2033 if (_M_impl
._M_key_compare(_S_key(__j
._M_node
), __k
))
2034 return _Res(__x
, __y
);
2035 return _Res(__j
._M_node
, 0);
2038 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2039 typename _Compare
, typename _Alloc
>
2040 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2041 _Compare
, _Alloc
>::_Base_ptr
,
2042 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2043 _Compare
, _Alloc
>::_Base_ptr
>
2044 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2045 _M_get_insert_equal_pos(const key_type
& __k
)
2047 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2048 _Link_type __x
= _M_begin();
2049 _Base_ptr __y
= _M_end();
2053 __x
= _M_impl
._M_key_compare(__k
, _S_key(__x
)) ?
2054 _S_left(__x
) : _S_right(__x
);
2056 return _Res(__x
, __y
);
2059 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2060 typename _Compare
, typename _Alloc
>
2061 #if __cplusplus >= 201103L
2062 template<typename _Arg
>
2064 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2065 _Compare
, _Alloc
>::iterator
, bool>
2066 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2067 #if __cplusplus >= 201103L
2068 _M_insert_unique(_Arg
&& __v
)
2070 _M_insert_unique(const _Val
& __v
)
2073 typedef pair
<iterator
, bool> _Res
;
2074 pair
<_Base_ptr
, _Base_ptr
> __res
2075 = _M_get_insert_unique_pos(_KeyOfValue()(__v
));
2079 _Alloc_node
__an(*this);
2080 return _Res(_M_insert_(__res
.first
, __res
.second
,
2081 _GLIBCXX_FORWARD(_Arg
, __v
), __an
),
2085 return _Res(iterator(__res
.first
), false);
2088 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2089 typename _Compare
, typename _Alloc
>
2090 #if __cplusplus >= 201103L
2091 template<typename _Arg
>
2093 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2094 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2095 #if __cplusplus >= 201103L
2096 _M_insert_equal(_Arg
&& __v
)
2098 _M_insert_equal(const _Val
& __v
)
2101 pair
<_Base_ptr
, _Base_ptr
> __res
2102 = _M_get_insert_equal_pos(_KeyOfValue()(__v
));
2103 _Alloc_node
__an(*this);
2104 return _M_insert_(__res
.first
, __res
.second
,
2105 _GLIBCXX_FORWARD(_Arg
, __v
), __an
);
2108 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2109 typename _Compare
, typename _Alloc
>
2110 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2111 _Compare
, _Alloc
>::_Base_ptr
,
2112 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2113 _Compare
, _Alloc
>::_Base_ptr
>
2114 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2115 _M_get_insert_hint_unique_pos(const_iterator __position
,
2116 const key_type
& __k
)
2118 iterator __pos
= __position
._M_const_cast();
2119 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2122 if (__pos
._M_node
== _M_end())
2125 && _M_impl
._M_key_compare(_S_key(_M_rightmost()), __k
))
2126 return _Res(0, _M_rightmost());
2128 return _M_get_insert_unique_pos(__k
);
2130 else if (_M_impl
._M_key_compare(__k
, _S_key(__pos
._M_node
)))
2132 // First, try before...
2133 iterator __before
= __pos
;
2134 if (__pos
._M_node
== _M_leftmost()) // begin()
2135 return _Res(_M_leftmost(), _M_leftmost());
2136 else if (_M_impl
._M_key_compare(_S_key((--__before
)._M_node
), __k
))
2138 if (_S_right(__before
._M_node
) == 0)
2139 return _Res(0, __before
._M_node
);
2141 return _Res(__pos
._M_node
, __pos
._M_node
);
2144 return _M_get_insert_unique_pos(__k
);
2146 else if (_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2148 // ... then try after.
2149 iterator __after
= __pos
;
2150 if (__pos
._M_node
== _M_rightmost())
2151 return _Res(0, _M_rightmost());
2152 else if (_M_impl
._M_key_compare(__k
, _S_key((++__after
)._M_node
)))
2154 if (_S_right(__pos
._M_node
) == 0)
2155 return _Res(0, __pos
._M_node
);
2157 return _Res(__after
._M_node
, __after
._M_node
);
2160 return _M_get_insert_unique_pos(__k
);
2164 return _Res(__pos
._M_node
, 0);
2167 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2168 typename _Compare
, typename _Alloc
>
2169 #if __cplusplus >= 201103L
2170 template<typename _Arg
, typename _NodeGen
>
2172 template<typename _NodeGen
>
2174 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2175 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2176 _M_insert_unique_(const_iterator __position
,
2177 #if __cplusplus >= 201103L
2182 _NodeGen
& __node_gen
)
2184 pair
<_Base_ptr
, _Base_ptr
> __res
2185 = _M_get_insert_hint_unique_pos(__position
, _KeyOfValue()(__v
));
2188 return _M_insert_(__res
.first
, __res
.second
,
2189 _GLIBCXX_FORWARD(_Arg
, __v
),
2191 return iterator(__res
.first
);
2194 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2195 typename _Compare
, typename _Alloc
>
2196 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2197 _Compare
, _Alloc
>::_Base_ptr
,
2198 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2199 _Compare
, _Alloc
>::_Base_ptr
>
2200 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2201 _M_get_insert_hint_equal_pos(const_iterator __position
, const key_type
& __k
)
2203 iterator __pos
= __position
._M_const_cast();
2204 typedef pair
<_Base_ptr
, _Base_ptr
> _Res
;
2207 if (__pos
._M_node
== _M_end())
2210 && !_M_impl
._M_key_compare(__k
, _S_key(_M_rightmost())))
2211 return _Res(0, _M_rightmost());
2213 return _M_get_insert_equal_pos(__k
);
2215 else if (!_M_impl
._M_key_compare(_S_key(__pos
._M_node
), __k
))
2217 // First, try before...
2218 iterator __before
= __pos
;
2219 if (__pos
._M_node
== _M_leftmost()) // begin()
2220 return _Res(_M_leftmost(), _M_leftmost());
2221 else if (!_M_impl
._M_key_compare(__k
, _S_key((--__before
)._M_node
)))
2223 if (_S_right(__before
._M_node
) == 0)
2224 return _Res(0, __before
._M_node
);
2226 return _Res(__pos
._M_node
, __pos
._M_node
);
2229 return _M_get_insert_equal_pos(__k
);
2233 // ... then try after.
2234 iterator __after
= __pos
;
2235 if (__pos
._M_node
== _M_rightmost())
2236 return _Res(0, _M_rightmost());
2237 else if (!_M_impl
._M_key_compare(_S_key((++__after
)._M_node
), __k
))
2239 if (_S_right(__pos
._M_node
) == 0)
2240 return _Res(0, __pos
._M_node
);
2242 return _Res(__after
._M_node
, __after
._M_node
);
2249 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2250 typename _Compare
, typename _Alloc
>
2251 #if __cplusplus >= 201103L
2252 template<typename _Arg
, typename _NodeGen
>
2254 template<typename _NodeGen
>
2256 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2257 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2258 _M_insert_equal_(const_iterator __position
,
2259 #if __cplusplus >= 201103L
2264 _NodeGen
& __node_gen
)
2266 pair
<_Base_ptr
, _Base_ptr
> __res
2267 = _M_get_insert_hint_equal_pos(__position
, _KeyOfValue()(__v
));
2270 return _M_insert_(__res
.first
, __res
.second
,
2271 _GLIBCXX_FORWARD(_Arg
, __v
),
2274 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg
, __v
));
2277 #if __cplusplus >= 201103L
2278 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2279 typename _Compare
, typename _Alloc
>
2280 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2281 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2282 _M_insert_node(_Base_ptr __x
, _Base_ptr __p
, _Link_type __z
)
2284 bool __insert_left
= (__x
!= 0 || __p
== _M_end()
2285 || _M_impl
._M_key_compare(_S_key(__z
),
2288 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2289 this->_M_impl
._M_header
);
2290 ++_M_impl
._M_node_count
;
2291 return iterator(__z
);
2294 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2295 typename _Compare
, typename _Alloc
>
2296 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2297 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2298 _M_insert_lower_node(_Base_ptr __p
, _Link_type __z
)
2300 bool __insert_left
= (__p
== _M_end()
2301 || !_M_impl
._M_key_compare(_S_key(__p
),
2304 _Rb_tree_insert_and_rebalance(__insert_left
, __z
, __p
,
2305 this->_M_impl
._M_header
);
2306 ++_M_impl
._M_node_count
;
2307 return iterator(__z
);
2310 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2311 typename _Compare
, typename _Alloc
>
2312 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2313 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2314 _M_insert_equal_lower_node(_Link_type __z
)
2316 _Link_type __x
= _M_begin();
2317 _Base_ptr __y
= _M_end();
2321 __x
= !_M_impl
._M_key_compare(_S_key(__x
), _S_key(__z
)) ?
2322 _S_left(__x
) : _S_right(__x
);
2324 return _M_insert_lower_node(__y
, __z
);
2327 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2328 typename _Compare
, typename _Alloc
>
2329 template<typename
... _Args
>
2330 pair
<typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2331 _Compare
, _Alloc
>::iterator
, bool>
2332 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2333 _M_emplace_unique(_Args
&&... __args
)
2335 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2339 typedef pair
<iterator
, bool> _Res
;
2340 auto __res
= _M_get_insert_unique_pos(_S_key(__z
));
2342 return _Res(_M_insert_node(__res
.first
, __res
.second
, __z
), true);
2345 return _Res(iterator(__res
.first
), false);
2350 __throw_exception_again
;
2354 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2355 typename _Compare
, typename _Alloc
>
2356 template<typename
... _Args
>
2357 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2358 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2359 _M_emplace_equal(_Args
&&... __args
)
2361 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2365 auto __res
= _M_get_insert_equal_pos(_S_key(__z
));
2366 return _M_insert_node(__res
.first
, __res
.second
, __z
);
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_hint_unique(const_iterator __pos
, _Args
&&... __args
)
2382 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2386 auto __res
= _M_get_insert_hint_unique_pos(__pos
, _S_key(__z
));
2389 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2392 return iterator(__res
.first
);
2397 __throw_exception_again
;
2401 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2402 typename _Compare
, typename _Alloc
>
2403 template<typename
... _Args
>
2404 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
2405 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2406 _M_emplace_hint_equal(const_iterator __pos
, _Args
&&... __args
)
2408 _Link_type __z
= _M_create_node(std::forward
<_Args
>(__args
)...);
2412 auto __res
= _M_get_insert_hint_equal_pos(__pos
, _S_key(__z
));
2415 return _M_insert_node(__res
.first
, __res
.second
, __z
);
2417 return _M_insert_equal_lower_node(__z
);
2422 __throw_exception_again
;
2427 template<typename _Key
, typename _Val
, typename _KoV
,
2428 typename _Cmp
, typename _Alloc
>
2431 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
2432 _M_insert_unique(_II __first
, _II __last
)
2434 _Alloc_node
__an(*this);
2435 for (; __first
!= __last
; ++__first
)
2436 _M_insert_unique_(end(), *__first
, __an
);
2439 template<typename _Key
, typename _Val
, typename _KoV
,
2440 typename _Cmp
, typename _Alloc
>
2443 _Rb_tree
<_Key
, _Val
, _KoV
, _Cmp
, _Alloc
>::
2444 _M_insert_equal(_II __first
, _II __last
)
2446 _Alloc_node
__an(*this);
2447 for (; __first
!= __last
; ++__first
)
2448 _M_insert_equal_(end(), *__first
, __an
);
2451 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2452 typename _Compare
, typename _Alloc
>
2454 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2455 _M_erase_aux(const_iterator __position
)
2458 static_cast<_Link_type
>(_Rb_tree_rebalance_for_erase
2459 (const_cast<_Base_ptr
>(__position
._M_node
),
2460 this->_M_impl
._M_header
));
2462 --_M_impl
._M_node_count
;
2465 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2466 typename _Compare
, typename _Alloc
>
2468 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2469 _M_erase_aux(const_iterator __first
, const_iterator __last
)
2471 if (__first
== begin() && __last
== end())
2474 while (__first
!= __last
)
2478 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2479 typename _Compare
, typename _Alloc
>
2480 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2481 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2482 erase(const _Key
& __x
)
2484 pair
<iterator
, iterator
> __p
= equal_range(__x
);
2485 const size_type __old_size
= size();
2486 erase(__p
.first
, __p
.second
);
2487 return __old_size
- size();
2490 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2491 typename _Compare
, typename _Alloc
>
2493 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2494 erase(const _Key
* __first
, const _Key
* __last
)
2496 while (__first
!= __last
)
2500 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2501 typename _Compare
, typename _Alloc
>
2502 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2503 _Compare
, _Alloc
>::iterator
2504 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2505 find(const _Key
& __k
)
2507 iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2508 return (__j
== end()
2509 || _M_impl
._M_key_compare(__k
,
2510 _S_key(__j
._M_node
))) ? end() : __j
;
2513 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2514 typename _Compare
, typename _Alloc
>
2515 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
,
2516 _Compare
, _Alloc
>::const_iterator
2517 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2518 find(const _Key
& __k
) const
2520 const_iterator __j
= _M_lower_bound(_M_begin(), _M_end(), __k
);
2521 return (__j
== end()
2522 || _M_impl
._M_key_compare(__k
,
2523 _S_key(__j
._M_node
))) ? end() : __j
;
2526 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2527 typename _Compare
, typename _Alloc
>
2528 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::size_type
2529 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
2530 count(const _Key
& __k
) const
2532 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
2533 const size_type __n
= std::distance(__p
.first
, __p
.second
);
2537 _GLIBCXX_PURE
unsigned int
2538 _Rb_tree_black_count(const _Rb_tree_node_base
* __node
,
2539 const _Rb_tree_node_base
* __root
) throw ();
2541 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
2542 typename _Compare
, typename _Alloc
>
2544 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
2546 if (_M_impl
._M_node_count
== 0 || begin() == end())
2547 return _M_impl
._M_node_count
== 0 && begin() == end()
2548 && this->_M_impl
._M_header
._M_left
== _M_end()
2549 && this->_M_impl
._M_header
._M_right
== _M_end();
2551 unsigned int __len
= _Rb_tree_black_count(_M_leftmost(), _M_root());
2552 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
2554 _Const_Link_type __x
= static_cast<_Const_Link_type
>(__it
._M_node
);
2555 _Const_Link_type __L
= _S_left(__x
);
2556 _Const_Link_type __R
= _S_right(__x
);
2558 if (__x
->_M_color
== _S_red
)
2559 if ((__L
&& __L
->_M_color
== _S_red
)
2560 || (__R
&& __R
->_M_color
== _S_red
))
2563 if (__L
&& _M_impl
._M_key_compare(_S_key(__x
), _S_key(__L
)))
2565 if (__R
&& _M_impl
._M_key_compare(_S_key(__R
), _S_key(__x
)))
2568 if (!__L
&& !__R
&& _Rb_tree_black_count(__x
, _M_root()) != __len
)
2572 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2574 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2579 #if __cplusplus > 201402L
2580 // Allow access to internals of compatible _Rb_tree specializations.
2581 template<typename _Key
, typename _Val
, typename _Sel
, typename _Cmp1
,
2582 typename _Alloc
, typename _Cmp2
>
2583 struct _Rb_tree_merge_helper
<_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>,
2587 friend class _Rb_tree
<_Key
, _Val
, _Sel
, _Cmp1
, _Alloc
>;
2590 _S_get_impl(_Rb_tree
<_Key
, _Val
, _Sel
, _Cmp2
, _Alloc
>& __tree
)
2591 { return __tree
._M_impl
; }
2595 _GLIBCXX_END_NAMESPACE_VERSION