1// RB tree implementation -*- C++ -*-
2
3// Copyright (C) 2001-2019 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
25/*
26 *
27 * Copyright (c) 1996,1997
28 * Silicon Graphics Computer Systems, Inc.
29 *
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.
37 *
38 *
39 * Copyright (c) 1994
40 * Hewlett-Packard Company
41 *
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.
49 *
50 *
51 */
52
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}
56 */
57
58#ifndef _STL_TREE_H
59#define _STL_TREE_H 1
60
61#pragma GCC system_header
62
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>
70#endif
71#if __cplusplus > 201402L
72# include <bits/node_handle.h>
73#endif
74
75namespace std _GLIBCXX_VISIBILITY(default)
76{
77_GLIBCXX_BEGIN_NAMESPACE_VERSION
78
79#if __cplusplus > 201103L
80# define __cpp_lib_generic_associative_lookup 201304
81#endif
82
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,
87 // 1990), except that
88 //
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
93 // (set_union, etc.)
94 //
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.
98
99 enum _Rb_tree_color { _S_red = false, _S_black = true };
100
101 struct _Rb_tree_node_base
102 {
103 typedef _Rb_tree_node_base* _Base_ptr;
104 typedef const _Rb_tree_node_base* _Const_Base_ptr;
105
106 _Rb_tree_color _M_color;
107 _Base_ptr _M_parent;
108 _Base_ptr _M_left;
109 _Base_ptr _M_right;
110
111 static _Base_ptr
112 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
113 {
114 while (__x->_M_left != 0) __x = __x->_M_left;
115 return __x;
116 }
117
118 static _Const_Base_ptr
119 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
120 {
121 while (__x->_M_left != 0) __x = __x->_M_left;
122 return __x;
123 }
124
125 static _Base_ptr
126 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
127 {
128 while (__x->_M_right != 0) __x = __x->_M_right;
129 return __x;
130 }
131
132 static _Const_Base_ptr
133 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
134 {
135 while (__x->_M_right != 0) __x = __x->_M_right;
136 return __x;
137 }
138 };
139
140 // Helper type offering value initialization guarantee on the compare functor.
141 template<typename _Key_compare>
142 struct _Rb_tree_key_compare
143 {
144 _Key_compare _M_key_compare;
145
146 _Rb_tree_key_compare()
147 _GLIBCXX_NOEXCEPT_IF(
148 is_nothrow_default_constructible<_Key_compare>::value)
149 : _M_key_compare()
150 { }
151
152 _Rb_tree_key_compare(const _Key_compare& __comp)
153 : _M_key_compare(__comp)
154 { }
155
156#if __cplusplus >= 201103L
157 // Copy constructor added for consistency with C++98 mode.
158 _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default;
159
160 _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
161 noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
162 : _M_key_compare(__x._M_key_compare)
163 { }
164#endif
165 };
166
167 // Helper type to manage default initialization of node count and header.
168 struct _Rb_tree_header
169 {
170 _Rb_tree_node_base _M_header;
171 size_t _M_node_count; // Keeps track of size of tree.
172
173 _Rb_tree_header() _GLIBCXX_NOEXCEPT
174 {
175 _M_header._M_color = _S_red;
176 _M_reset();
177 }
178
179#if __cplusplus >= 201103L
180 _Rb_tree_header(_Rb_tree_header&& __x) noexcept
181 {
182 if (__x._M_header._M_parent != nullptr)
183 _M_move_data(__x);
184 else
185 {
186 _M_header._M_color = _S_red;
187 _M_reset();
188 }
189 }
190#endif
191
192 void
193 _M_move_data(_Rb_tree_header& __from)
194 {
195 _M_header._M_color = __from._M_header._M_color;
196 _M_header._M_parent = __from._M_header._M_parent;
197 _M_header._M_left = __from._M_header._M_left;
198 _M_header._M_right = __from._M_header._M_right;
199 _M_header._M_parent->_M_parent = &_M_header;
200 _M_node_count = __from._M_node_count;
201
202 __from._M_reset();
203 }
204
205 void
206 _M_reset()
207 {
208 _M_header._M_parent = 0;
209 _M_header._M_left = &_M_header;
210 _M_header._M_right = &_M_header;
211 _M_node_count = 0;
212 }
213 };
214
215 template<typename _Val>
216 struct _Rb_tree_node : public _Rb_tree_node_base
217 {
218 typedef _Rb_tree_node<_Val>* _Link_type;
219
220#if __cplusplus < 201103L
221 _Val _M_value_field;
222
223 _Val*
224 _M_valptr()
225 { return std::__addressof(_M_value_field); }
226
227 const _Val*
228 _M_valptr() const
229 { return std::__addressof(_M_value_field); }
230#else
231 __gnu_cxx::__aligned_membuf<_Val> _M_storage;
232
233 _Val*
234 _M_valptr()
235 { return _M_storage._M_ptr(); }
236
237 const _Val*
238 _M_valptr() const
239 { return _M_storage._M_ptr(); }
240#endif
241 };
242
243 _GLIBCXX_PURE _Rb_tree_node_base*
244 _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
245
246 _GLIBCXX_PURE const _Rb_tree_node_base*
247 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
248
249 _GLIBCXX_PURE _Rb_tree_node_base*
250 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
251
252 _GLIBCXX_PURE const _Rb_tree_node_base*
253 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
254
255 template<typename _Tp>
256 struct _Rb_tree_iterator
257 {
258 typedef _Tp value_type;
259 typedef _Tp& reference;
260 typedef _Tp* pointer;
261
262 typedef bidirectional_iterator_tag iterator_category;
263 typedef ptrdiff_t difference_type;
264
265 typedef _Rb_tree_iterator<_Tp> _Self;
266 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
267 typedef _Rb_tree_node<_Tp>* _Link_type;
268
269 _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
270 : _M_node() { }
271
272 explicit
273 _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
274 : _M_node(__x) { }
275
276 reference
277 operator*() const _GLIBCXX_NOEXCEPT
278 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
279
280 pointer
281 operator->() const _GLIBCXX_NOEXCEPT
282 { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
283
284 _Self&
285 operator++() _GLIBCXX_NOEXCEPT
286 {
287 _M_node = _Rb_tree_increment(_M_node);
288 return *this;
289 }
290
291 _Self
292 operator++(int) _GLIBCXX_NOEXCEPT
293 {
294 _Self __tmp = *this;
295 _M_node = _Rb_tree_increment(_M_node);
296 return __tmp;
297 }
298
299 _Self&
300 operator--() _GLIBCXX_NOEXCEPT
301 {
302 _M_node = _Rb_tree_decrement(_M_node);
303 return *this;
304 }
305
306 _Self
307 operator--(int) _GLIBCXX_NOEXCEPT
308 {
309 _Self __tmp = *this;
310 _M_node = _Rb_tree_decrement(_M_node);
311 return __tmp;
312 }
313
314 friend bool
315 operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
316 { return __x._M_node == __y._M_node; }
317
318 friend bool
319 operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
320 { return __x._M_node != __y._M_node; }
321
322 _Base_ptr _M_node;
323 };
324
325 template<typename _Tp>
326 struct _Rb_tree_const_iterator
327 {
328 typedef _Tp value_type;
329 typedef const _Tp& reference;
330 typedef const _Tp* pointer;
331
332 typedef _Rb_tree_iterator<_Tp> iterator;
333
334 typedef bidirectional_iterator_tag iterator_category;
335 typedef ptrdiff_t difference_type;
336
337 typedef _Rb_tree_const_iterator<_Tp> _Self;
338 typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
339 typedef const _Rb_tree_node<_Tp>* _Link_type;
340
341 _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
342 : _M_node() { }
343
344 explicit
345 _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
346 : _M_node(__x) { }
347
348 _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
349 : _M_node(__it._M_node) { }
350
351 iterator
352 _M_const_cast() const _GLIBCXX_NOEXCEPT
353 { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
354
355 reference
356 operator*() const _GLIBCXX_NOEXCEPT
357 { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
358
359 pointer
360 operator->() const _GLIBCXX_NOEXCEPT
361 { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
362
363 _Self&
364 operator++() _GLIBCXX_NOEXCEPT
365 {
366 _M_node = _Rb_tree_increment(_M_node);
367 return *this;
368 }
369
370 _Self
371 operator++(int) _GLIBCXX_NOEXCEPT
372 {
373 _Self __tmp = *this;
374 _M_node = _Rb_tree_increment(_M_node);
375 return __tmp;
376 }
377
378 _Self&
379 operator--() _GLIBCXX_NOEXCEPT
380 {
381 _M_node = _Rb_tree_decrement(_M_node);
382 return *this;
383 }
384
385 _Self
386 operator--(int) _GLIBCXX_NOEXCEPT
387 {
388 _Self __tmp = *this;
389 _M_node = _Rb_tree_decrement(_M_node);
390 return __tmp;
391 }
392
393 friend bool
394 operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
395 { return __x._M_node == __y._M_node; }
396
397 friend bool
398 operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
399 { return __x._M_node != __y._M_node; }
400
401 _Base_ptr _M_node;
402 };
403
404 void
405 _Rb_tree_insert_and_rebalance(const bool __insert_left,
406 _Rb_tree_node_base* __x,
407 _Rb_tree_node_base* __p,
408 _Rb_tree_node_base& __header) throw ();
409
410 _Rb_tree_node_base*
411 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
412 _Rb_tree_node_base& __header) throw ();
413
414#if __cplusplus >= 201402L
415 template<typename _Cmp, typename _SfinaeType, typename = __void_t<>>
416 struct __has_is_transparent
417 { };
418
419 template<typename _Cmp, typename _SfinaeType>
420 struct __has_is_transparent<_Cmp, _SfinaeType,
421 __void_t<typename _Cmp::is_transparent>>
422 { typedef void type; };
423
424 template<typename _Cmp, typename _SfinaeType>
425 using __has_is_transparent_t
426 = typename __has_is_transparent<_Cmp, _SfinaeType>::type;
427#endif
428
429#if __cplusplus > 201402L
430 template<typename _Tree1, typename _Cmp2>
431 struct _Rb_tree_merge_helper { };
432#endif
433
434 template<typename _Key, typename _Val, typename _KeyOfValue,
435 typename _Compare, typename _Alloc = allocator<_Val> >
436 class _Rb_tree
437 {
438 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
439 rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
440
441 typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
442
443 protected:
444 typedef _Rb_tree_node_base* _Base_ptr;
445 typedef const _Rb_tree_node_base* _Const_Base_ptr;
446 typedef _Rb_tree_node<_Val>* _Link_type;
447 typedef const _Rb_tree_node<_Val>* _Const_Link_type;
448
449 private:
450 // Functor recycling a pool of nodes and using allocation once the pool
451 // is empty.
452 struct _Reuse_or_alloc_node
453 {
454 _Reuse_or_alloc_node(_Rb_tree& __t)
455 : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
456 {
457 if (_M_root)
458 {
459 _M_root->_M_parent = 0;
460
461 if (_M_nodes->_M_left)
462 _M_nodes = _M_nodes->_M_left;
463 }
464 else
465 _M_nodes = 0;
466 }
467
468#if __cplusplus >= 201103L
469 _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
470#endif
471
472 ~_Reuse_or_alloc_node()
473 { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
474
475 template<typename _Arg>
476 _Link_type
477#if __cplusplus < 201103L
478 operator()(const _Arg& __arg)
479#else
480 operator()(_Arg&& __arg)
481#endif
482 {
483 _Link_type __node = static_cast<_Link_type>(_M_extract());
484 if (__node)
485 {
486 _M_t._M_destroy_node(__node);
487 _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
488 return __node;
489 }
490
491 return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
492 }
493
494 private:
495 _Base_ptr
496 _M_extract()
497 {
498 if (!_M_nodes)
499 return _M_nodes;
500
501 _Base_ptr __node = _M_nodes;
502 _M_nodes = _M_nodes->_M_parent;
503 if (_M_nodes)
504 {
505 if (_M_nodes->_M_right == __node)
506 {
507 _M_nodes->_M_right = 0;
508
509 if (_M_nodes->_M_left)
510 {
511 _M_nodes = _M_nodes->_M_left;
512
513 while (_M_nodes->_M_right)
514 _M_nodes = _M_nodes->_M_right;
515
516 if (_M_nodes->_M_left)
517 _M_nodes = _M_nodes->_M_left;
518 }
519 }
520 else // __node is on the left.
521 _M_nodes->_M_left = 0;
522 }
523 else
524 _M_root = 0;
525
526 return __node;
527 }
528
529 _Base_ptr _M_root;
530 _Base_ptr _M_nodes;
531 _Rb_tree& _M_t;
532 };
533
534 // Functor similar to the previous one but without any pool of nodes to
535 // recycle.
536 struct _Alloc_node
537 {
538 _Alloc_node(_Rb_tree& __t)
539 : _M_t(__t) { }
540
541 template<typename _Arg>
542 _Link_type
543#if __cplusplus < 201103L
544 operator()(const _Arg& __arg) const
545#else
546 operator()(_Arg&& __arg) const
547#endif
548 { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
549
550 private:
551 _Rb_tree& _M_t;
552 };
553
554 public:
555 typedef _Key key_type;
556 typedef _Val value_type;
557 typedef value_type* pointer;
558 typedef const value_type* const_pointer;
559 typedef value_type& reference;
560 typedef const value_type& const_reference;
561 typedef size_t size_type;
562 typedef ptrdiff_t difference_type;
563 typedef _Alloc allocator_type;
564
565 _Node_allocator&
566 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
567 { return this->_M_impl; }
568
569 const _Node_allocator&
570 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
571 { return this->_M_impl; }
572
573 allocator_type
574 get_allocator() const _GLIBCXX_NOEXCEPT
575 { return allocator_type(_M_get_Node_allocator()); }
576
577 protected:
578 _Link_type
579 _M_get_node()
580 { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
581
582 void
583 _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
584 { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
585
586#if __cplusplus < 201103L
587 void
588 _M_construct_node(_Link_type __node, const value_type& __x)
589 {
590 __try
591 { get_allocator().construct(__node->_M_valptr(), __x); }
592 __catch(...)
593 {
594 _M_put_node(__node);
595 __throw_exception_again;
596 }
597 }
598
599 _Link_type
600 _M_create_node(const value_type& __x)
601 {
602 _Link_type __tmp = _M_get_node();
603 _M_construct_node(__tmp, __x);
604 return __tmp;
605 }
606#else
607 template<typename... _Args>
608 void
609 _M_construct_node(_Link_type __node, _Args&&... __args)
610 {
611 __try
612 {
613 ::new(__node) _Rb_tree_node<_Val>;
614 _Alloc_traits::construct(_M_get_Node_allocator(),
615 __node->_M_valptr(),
616 std::forward<_Args>(__args)...);
617 }
618 __catch(...)
619 {
620 __node->~_Rb_tree_node<_Val>();
621 _M_put_node(__node);
622 __throw_exception_again;
623 }
624 }
625
626 template<typename... _Args>
627 _Link_type
628 _M_create_node(_Args&&... __args)
629 {
630 _Link_type __tmp = _M_get_node();
631 _M_construct_node(__tmp, std::forward<_Args>(__args)...);
632 return __tmp;
633 }
634#endif
635
636 void
637 _M_destroy_node(_Link_type __p) _GLIBCXX_NOEXCEPT
638 {
639#if __cplusplus < 201103L
640 get_allocator().destroy(__p->_M_valptr());
641#else
642 _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
643 __p->~_Rb_tree_node<_Val>();
644#endif
645 }
646
647 void
648 _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
649 {
650 _M_destroy_node(__p);
651 _M_put_node(__p);
652 }
653
654 template<typename _NodeGen>
655 _Link_type
656 _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
657 {
658 _Link_type __tmp = __node_gen(*__x->_M_valptr());
659 __tmp->_M_color = __x->_M_color;
660 __tmp->_M_left = 0;
661 __tmp->_M_right = 0;
662 return __tmp;
663 }
664
665 protected:
666#if _GLIBCXX_INLINE_VERSION
667 template<typename _Key_compare>
668#else
669 // Unused _Is_pod_comparator is kept as it is part of mangled name.
670 template<typename _Key_compare,
671 bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
672#endif
673 struct _Rb_tree_impl
674 : public _Node_allocator
675 , public _Rb_tree_key_compare<_Key_compare>
676 , public _Rb_tree_header
677 {
678 typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
679
680 _Rb_tree_impl()
681 _GLIBCXX_NOEXCEPT_IF(
682 is_nothrow_default_constructible<_Node_allocator>::value
683 && is_nothrow_default_constructible<_Base_key_compare>::value )
684 : _Node_allocator()
685 { }
686
687 _Rb_tree_impl(const _Rb_tree_impl& __x)
688 : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
689 , _Base_key_compare(__x._M_key_compare)
690 { }
691
692#if __cplusplus < 201103L
693 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
694 : _Node_allocator(__a), _Base_key_compare(__comp)
695 { }
696#else
697 _Rb_tree_impl(_Rb_tree_impl&&) = default;
698
699 explicit
700 _Rb_tree_impl(_Node_allocator&& __a)
701 : _Node_allocator(std::move(__a))
702 { }
703
704 _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
705 : _Node_allocator(std::move(__a)),
706 _Base_key_compare(std::move(__x)),
707 _Rb_tree_header(std::move(__x))
708 { }
709
710 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
711 : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
712 { }
713#endif
714 };
715
716 _Rb_tree_impl<_Compare> _M_impl;
717
718 protected:
719 _Base_ptr&
720 _M_root() _GLIBCXX_NOEXCEPT
721 { return this->_M_impl._M_header._M_parent; }
722
723 _Const_Base_ptr
724 _M_root() const _GLIBCXX_NOEXCEPT
725 { return this->_M_impl._M_header._M_parent; }
726
727 _Base_ptr&
728 _M_leftmost() _GLIBCXX_NOEXCEPT
729 { return this->_M_impl._M_header._M_left; }
730
731 _Const_Base_ptr
732 _M_leftmost() const _GLIBCXX_NOEXCEPT
733 { return this->_M_impl._M_header._M_left; }
734
735 _Base_ptr&
736 _M_rightmost() _GLIBCXX_NOEXCEPT
737 { return this->_M_impl._M_header._M_right; }
738
739 _Const_Base_ptr
740 _M_rightmost() const _GLIBCXX_NOEXCEPT
741 { return this->_M_impl._M_header._M_right; }
742
743 _Link_type
744 _M_begin() _GLIBCXX_NOEXCEPT
745 { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
746
747 _Const_Link_type
748 _M_begin() const _GLIBCXX_NOEXCEPT
749 {
750 return static_cast<_Const_Link_type>
751 (this->_M_impl._M_header._M_parent);
752 }
753
754 _Base_ptr
755 _M_end() _GLIBCXX_NOEXCEPT
756 { return &this->_M_impl._M_header; }
757
758 _Const_Base_ptr
759 _M_end() const _GLIBCXX_NOEXCEPT
760 { return &this->_M_impl._M_header; }
761
762 static const_reference
763 _S_value(_Const_Link_type __x)
764 { return *__x->_M_valptr(); }
765
766 static const _Key&
767 _S_key(_Const_Link_type __x)
768 { return _KeyOfValue()(_S_value(__x)); }
769
770 static _Link_type
771 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
772 { return static_cast<_Link_type>(__x->_M_left); }
773
774 static _Const_Link_type
775 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
776 { return static_cast<_Const_Link_type>(__x->_M_left); }
777
778 static _Link_type
779 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
780 { return static_cast<_Link_type>(__x->_M_right); }
781
782 static _Const_Link_type
783 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
784 { return static_cast<_Const_Link_type>(__x->_M_right); }
785
786 static const_reference
787 _S_value(_Const_Base_ptr __x)
788 { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
789
790 static const _Key&
791 _S_key(_Const_Base_ptr __x)
792 { return _KeyOfValue()(_S_value(__x)); }
793
794 static _Base_ptr
795 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
796 { return _Rb_tree_node_base::_S_minimum(__x); }
797
798 static _Const_Base_ptr
799 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
800 { return _Rb_tree_node_base::_S_minimum(__x); }
801
802 static _Base_ptr
803 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
804 { return _Rb_tree_node_base::_S_maximum(__x); }
805
806 static _Const_Base_ptr
807 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
808 { return _Rb_tree_node_base::_S_maximum(__x); }
809
810 public:
811 typedef _Rb_tree_iterator<value_type> iterator;
812 typedef _Rb_tree_const_iterator<value_type> const_iterator;
813
814 typedef std::reverse_iterator<iterator> reverse_iterator;
815 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
816
817#if __cplusplus > 201402L
818 using node_type = _Node_handle<_Key, _Val, _Node_allocator>;
819 using insert_return_type = _Node_insert_return<
820 conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>,
821 node_type>;
822#endif
823
824 pair<_Base_ptr, _Base_ptr>
825 _M_get_insert_unique_pos(const key_type& __k);
826
827 pair<_Base_ptr, _Base_ptr>
828 _M_get_insert_equal_pos(const key_type& __k);
829
830 pair<_Base_ptr, _Base_ptr>
831 _M_get_insert_hint_unique_pos(const_iterator __pos,
832 const key_type& __k);
833
834 pair<_Base_ptr, _Base_ptr>
835 _M_get_insert_hint_equal_pos(const_iterator __pos,
836 const key_type& __k);
837
838 private:
839#if __cplusplus >= 201103L
840 template<typename _Arg, typename _NodeGen>
841 iterator
842 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
843
844 iterator
845 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
846
847 template<typename _Arg>
848 iterator
849 _M_insert_lower(_Base_ptr __y, _Arg&& __v);
850
851 template<typename _Arg>
852 iterator
853 _M_insert_equal_lower(_Arg&& __x);
854
855 iterator
856 _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
857
858 iterator
859 _M_insert_equal_lower_node(_Link_type __z);
860#else
861 template<typename _NodeGen>
862 iterator
863 _M_insert_(_Base_ptr __x, _Base_ptr __y,
864 const value_type& __v, _NodeGen&);
865
866 // _GLIBCXX_RESOLVE_LIB_DEFECTS
867 // 233. Insertion hints in associative containers.
868 iterator
869 _M_insert_lower(_Base_ptr __y, const value_type& __v);
870
871 iterator
872 _M_insert_equal_lower(const value_type& __x);
873#endif
874
875 template<typename _NodeGen>
876 _Link_type
877 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
878
879 template<typename _NodeGen>
880 _Link_type
881 _M_copy(const _Rb_tree& __x, _NodeGen& __gen)
882 {
883 _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
884 _M_leftmost() = _S_minimum(__root);
885 _M_rightmost() = _S_maximum(__root);
886 _M_impl._M_node_count = __x._M_impl._M_node_count;
887 return __root;
888 }
889
890 _Link_type
891 _M_copy(const _Rb_tree& __x)
892 {
893 _Alloc_node __an(*this);
894 return _M_copy(__x, __an);
895 }
896
897 void
898 _M_erase(_Link_type __x);
899
900 iterator
901 _M_lower_bound(_Link_type __x, _Base_ptr __y,
902 const _Key& __k);
903
904 const_iterator
905 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
906 const _Key& __k) const;
907
908 iterator
909 _M_upper_bound(_Link_type __x, _Base_ptr __y,
910 const _Key& __k);
911
912 const_iterator
913 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
914 const _Key& __k) const;
915
916 public:
917 // allocation/deallocation
918#if __cplusplus < 201103L
919 _Rb_tree() { }
920#else
921 _Rb_tree() = default;
922#endif
923
924 _Rb_tree(const _Compare& __comp,
925 const allocator_type& __a = allocator_type())
926 : _M_impl(__comp, _Node_allocator(__a)) { }
927
928 _Rb_tree(const _Rb_tree& __x)
929 : _M_impl(__x._M_impl)
930 {
931 if (__x._M_root() != 0)
932 _M_root() = _M_copy(__x);
933 }
934
935#if __cplusplus >= 201103L
936 _Rb_tree(const allocator_type& __a)
937 : _M_impl(_Node_allocator(__a))
938 { }
939
940 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
941 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
942 {
943 if (__x._M_root() != nullptr)
944 _M_root() = _M_copy(__x);
945 }
946
947 _Rb_tree(_Rb_tree&&) = default;
948
949 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
950 : _Rb_tree(std::move(__x), _Node_allocator(__a))
951 { }
952
953 private:
954 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
955 noexcept(is_nothrow_default_constructible<_Compare>::value)
956 : _M_impl(std::move(__x._M_impl), std::move(__a))
957 { }
958
959 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
960 : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
961 {
962 if (__x._M_root() != nullptr)
963 _M_move_data(__x, false_type{});
964 }
965
966 public:
967 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
968 noexcept( noexcept(
969 _Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(),
970 std::declval<typename _Alloc_traits::is_always_equal>())) )
971 : _Rb_tree(std::move(__x), std::move(__a),
972 typename _Alloc_traits::is_always_equal{})
973 { }
974#endif
975
976 ~_Rb_tree() _GLIBCXX_NOEXCEPT
977 {
978 _M_erase(_M_begin());
979
980#if __cplusplus >= 201103L
981 static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
982 "comparison object must be invocable "
983 "with two arguments of key type");
984# if __cplusplus >= 201703L
985 // _GLIBCXX_RESOLVE_LIB_DEFECTS
986 // 2542. Missing const requirements for associative containers
987 static_assert(is_invocable_v<const _Compare&, const _Key&, const _Key&>,
988 "comparison object must be invocable as const");
989# endif // C++17
990#endif // C++11
991 }
992
993 _Rb_tree&
994 operator=(const _Rb_tree& __x);
995
996 // Accessors.
997 _Compare
998 key_comp() const
999 { return _M_impl._M_key_compare; }
1000
1001 iterator
1002 begin() _GLIBCXX_NOEXCEPT
1003 { return iterator(this->_M_impl._M_header._M_left); }
1004
1005 const_iterator
1006 begin() const _GLIBCXX_NOEXCEPT
1007 { return const_iterator(this->_M_impl._M_header._M_left); }
1008
1009 iterator
1010 end() _GLIBCXX_NOEXCEPT
1011 { return iterator(&this->_M_impl._M_header); }
1012
1013 const_iterator
1014 end() const _GLIBCXX_NOEXCEPT
1015 { return const_iterator(&this->_M_impl._M_header); }
1016
1017 reverse_iterator
1018 rbegin() _GLIBCXX_NOEXCEPT
1019 { return reverse_iterator(end()); }
1020
1021 const_reverse_iterator
1022 rbegin() const _GLIBCXX_NOEXCEPT
1023 { return const_reverse_iterator(end()); }
1024
1025 reverse_iterator
1026 rend() _GLIBCXX_NOEXCEPT
1027 { return reverse_iterator(begin()); }
1028
1029 const_reverse_iterator
1030 rend() const _GLIBCXX_NOEXCEPT
1031 { return const_reverse_iterator(begin()); }
1032
1033 _GLIBCXX_NODISCARD bool
1034 empty() const _GLIBCXX_NOEXCEPT
1035 { return _M_impl._M_node_count == 0; }
1036
1037 size_type
1038 size() const _GLIBCXX_NOEXCEPT
1039 { return _M_impl._M_node_count; }
1040
1041 size_type
1042 max_size() const _GLIBCXX_NOEXCEPT
1043 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
1044
1045 void
1046 swap(_Rb_tree& __t)
1047 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
1048
1049 // Insert/erase.
1050#if __cplusplus >= 201103L
1051 template<typename _Arg>
1052 pair<iterator, bool>
1053 _M_insert_unique(_Arg&& __x);
1054
1055 template<typename _Arg>
1056 iterator
1057 _M_insert_equal(_Arg&& __x);
1058
1059 template<typename _Arg, typename _NodeGen>
1060 iterator
1061 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1062
1063 template<typename _Arg>
1064 iterator
1065 _M_insert_unique_(const_iterator __pos, _Arg&& __x)
1066 {
1067 _Alloc_node __an(*this);
1068 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
1069 }
1070
1071 template<typename _Arg, typename _NodeGen>
1072 iterator
1073 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1074
1075 template<typename _Arg>
1076 iterator
1077 _M_insert_equal_(const_iterator __pos, _Arg&& __x)
1078 {
1079 _Alloc_node __an(*this);
1080 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
1081 }
1082
1083 template<typename... _Args>
1084 pair<iterator, bool>
1085 _M_emplace_unique(_Args&&... __args);
1086
1087 template<typename... _Args>
1088 iterator
1089 _M_emplace_equal(_Args&&... __args);
1090
1091 template<typename... _Args>
1092 iterator
1093 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
1094
1095 template<typename... _Args>
1096 iterator
1097 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
1098
1099 template<typename _Iter>
1100 using __same_value_type
1101 = is_same<value_type, typename iterator_traits<_Iter>::value_type>;
1102
1103 template<typename _InputIterator>
1104 __enable_if_t<__same_value_type<_InputIterator>::value>
1105 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1106 {
1107 _Alloc_node __an(*this);
1108 for (; __first != __last; ++__first)
1109 _M_insert_unique_(end(), *__first, __an);
1110 }
1111
1112 template<typename _InputIterator>
1113 __enable_if_t<!__same_value_type<_InputIterator>::value>
1114 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1115 {
1116 for (; __first != __last; ++__first)
1117 _M_emplace_unique(*__first);
1118 }
1119
1120 template<typename _InputIterator>
1121 __enable_if_t<__same_value_type<_InputIterator>::value>
1122 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1123 {
1124 _Alloc_node __an(*this);
1125 for (; __first != __last; ++__first)
1126 _M_insert_equal_(end(), *__first, __an);
1127 }
1128
1129 template<typename _InputIterator>
1130 __enable_if_t<!__same_value_type<_InputIterator>::value>
1131 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1132 {
1133 _Alloc_node __an(*this);
1134 for (; __first != __last; ++__first)
1135 _M_emplace_equal(*__first);
1136 }
1137#else
1138 pair<iterator, bool>
1139 _M_insert_unique(const value_type& __x);
1140
1141 iterator
1142 _M_insert_equal(const value_type& __x);
1143
1144 template<typename _NodeGen>
1145 iterator
1146 _M_insert_unique_(const_iterator __pos, const value_type& __x,
1147 _NodeGen&);
1148
1149 iterator
1150 _M_insert_unique_(const_iterator __pos, const value_type& __x)
1151 {
1152 _Alloc_node __an(*this);
1153 return _M_insert_unique_(__pos, __x, __an);
1154 }
1155
1156 template<typename _NodeGen>
1157 iterator
1158 _M_insert_equal_(const_iterator __pos, const value_type& __x,
1159 _NodeGen&);
1160 iterator
1161 _M_insert_equal_(const_iterator __pos, const value_type& __x)
1162 {
1163 _Alloc_node __an(*this);
1164 return _M_insert_equal_(__pos, __x, __an);
1165 }
1166
1167 template<typename _InputIterator>
1168 void
1169 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1170 {
1171 _Alloc_node __an(*this);
1172 for (; __first != __last; ++__first)
1173 _M_insert_unique_(end(), *__first, __an);
1174 }
1175
1176 template<typename _InputIterator>
1177 void
1178 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1179 {
1180 _Alloc_node __an(*this);
1181 for (; __first != __last; ++__first)
1182 _M_insert_equal_(end(), *__first, __an);
1183 }
1184#endif
1185
1186 private:
1187 void
1188 _M_erase_aux(const_iterator __position);
1189
1190 void
1191 _M_erase_aux(const_iterator __first, const_iterator __last);
1192
1193 public:
1194#if __cplusplus >= 201103L
1195 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1196 // DR 130. Associative erase should return an iterator.
1197 _GLIBCXX_ABI_TAG_CXX11
1198 iterator
1199 erase(const_iterator __position)
1200 {
1201 __glibcxx_assert(__position != end());
1202 const_iterator __result = __position;
1203 ++__result;
1204 _M_erase_aux(__position);
1205 return __result._M_const_cast();
1206 }
1207
1208 // LWG 2059.
1209 _GLIBCXX_ABI_TAG_CXX11
1210 iterator
1211 erase(iterator __position)
1212 {
1213 __glibcxx_assert(__position != end());
1214 iterator __result = __position;
1215 ++__result;
1216 _M_erase_aux(__position);
1217 return __result;
1218 }
1219#else
1220 void
1221 erase(iterator __position)
1222 {
1223 __glibcxx_assert(__position != end());
1224 _M_erase_aux(__position);
1225 }
1226
1227 void
1228 erase(const_iterator __position)
1229 {
1230 __glibcxx_assert(__position != end());
1231 _M_erase_aux(__position);
1232 }
1233#endif
1234 size_type
1235 erase(const key_type& __x);
1236
1237#if __cplusplus >= 201103L
1238 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1239 // DR 130. Associative erase should return an iterator.
1240 _GLIBCXX_ABI_TAG_CXX11
1241 iterator
1242 erase(const_iterator __first, const_iterator __last)
1243 {
1244 _M_erase_aux(__first, __last);
1245 return __last._M_const_cast();
1246 }
1247#else
1248 void
1249 erase(iterator __first, iterator __last)
1250 { _M_erase_aux(__first, __last); }
1251
1252 void
1253 erase(const_iterator __first, const_iterator __last)
1254 { _M_erase_aux(__first, __last); }
1255#endif
1256 void
1257 erase(const key_type* __first, const key_type* __last);
1258
1259 void
1260 clear() _GLIBCXX_NOEXCEPT
1261 {
1262 _M_erase(_M_begin());
1263 _M_impl._M_reset();
1264 }
1265
1266 // Set operations.
1267 iterator
1268 find(const key_type& __k);
1269
1270 const_iterator
1271 find(const key_type& __k) const;
1272
1273 size_type
1274 count(const key_type& __k) const;
1275
1276 iterator
1277 lower_bound(const key_type& __k)
1278 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1279
1280 const_iterator
1281 lower_bound(const key_type& __k) const
1282 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1283
1284 iterator
1285 upper_bound(const key_type& __k)
1286 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1287
1288 const_iterator
1289 upper_bound(const key_type& __k) const
1290 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1291
1292 pair<iterator, iterator>
1293 equal_range(const key_type& __k);
1294
1295 pair<const_iterator, const_iterator>
1296 equal_range(const key_type& __k) const;
1297
1298#if __cplusplus >= 201402L
1299 template<typename _Kt,
1300 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1301 iterator
1302 _M_find_tr(const _Kt& __k)
1303 {
1304 const _Rb_tree* __const_this = this;
1305 return __const_this->_M_find_tr(__k)._M_const_cast();
1306 }
1307
1308 template<typename _Kt,
1309 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1310 const_iterator
1311 _M_find_tr(const _Kt& __k) const
1312 {
1313 auto __j = _M_lower_bound_tr(__k);
1314 if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1315 __j = end();
1316 return __j;
1317 }
1318
1319 template<typename _Kt,
1320 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1321 size_type
1322 _M_count_tr(const _Kt& __k) const
1323 {
1324 auto __p = _M_equal_range_tr(__k);
1325 return std::distance(__p.first, __p.second);
1326 }
1327
1328 template<typename _Kt,
1329 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1330 iterator
1331 _M_lower_bound_tr(const _Kt& __k)
1332 {
1333 const _Rb_tree* __const_this = this;
1334 return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
1335 }
1336
1337 template<typename _Kt,
1338 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1339 const_iterator
1340 _M_lower_bound_tr(const _Kt& __k) const
1341 {
1342 auto __x = _M_begin();
1343 auto __y = _M_end();
1344 while (__x != 0)
1345 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1346 {
1347 __y = __x;
1348 __x = _S_left(__x);
1349 }
1350 else
1351 __x = _S_right(__x);
1352 return const_iterator(__y);
1353 }
1354
1355 template<typename _Kt,
1356 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1357 iterator
1358 _M_upper_bound_tr(const _Kt& __k)
1359 {
1360 const _Rb_tree* __const_this = this;
1361 return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
1362 }
1363
1364 template<typename _Kt,
1365 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1366 const_iterator
1367 _M_upper_bound_tr(const _Kt& __k) const
1368 {
1369 auto __x = _M_begin();
1370 auto __y = _M_end();
1371 while (__x != 0)
1372 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1373 {
1374 __y = __x;
1375 __x = _S_left(__x);
1376 }
1377 else
1378 __x = _S_right(__x);
1379 return const_iterator(__y);
1380 }
1381
1382 template<typename _Kt,
1383 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1384 pair<iterator, iterator>
1385 _M_equal_range_tr(const _Kt& __k)
1386 {
1387 const _Rb_tree* __const_this = this;
1388 auto __ret = __const_this->_M_equal_range_tr(__k);
1389 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
1390 }
1391
1392 template<typename _Kt,
1393 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1394 pair<const_iterator, const_iterator>
1395 _M_equal_range_tr(const _Kt& __k) const
1396 {
1397 auto __low = _M_lower_bound_tr(__k);
1398 auto __high = __low;
1399 auto& __cmp = _M_impl._M_key_compare;
1400 while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1401 ++__high;
1402 return { __low, __high };
1403 }
1404#endif
1405
1406 // Debugging.
1407 bool
1408 __rb_verify() const;
1409
1410#if __cplusplus >= 201103L
1411 _Rb_tree&
1412 operator=(_Rb_tree&&)
1413 noexcept(_Alloc_traits::_S_nothrow_move()
1414 && is_nothrow_move_assignable<_Compare>::value);
1415
1416 template<typename _Iterator>
1417 void
1418 _M_assign_unique(_Iterator, _Iterator);
1419
1420 template<typename _Iterator>
1421 void
1422 _M_assign_equal(_Iterator, _Iterator);
1423
1424 private:
1425 // Move elements from container with equal allocator.
1426 void
1427 _M_move_data(_Rb_tree& __x, true_type)
1428 { _M_impl._M_move_data(__x._M_impl); }
1429
1430 // Move elements from container with possibly non-equal allocator,
1431 // which might result in a copy not a move.
1432 void
1433 _M_move_data(_Rb_tree&, false_type);
1434
1435 // Move assignment from container with equal allocator.
1436 void
1437 _M_move_assign(_Rb_tree&, true_type);
1438
1439 // Move assignment from container with possibly non-equal allocator,
1440 // which might result in a copy not a move.
1441 void
1442 _M_move_assign(_Rb_tree&, false_type);
1443#endif
1444
1445#if __cplusplus > 201402L
1446 public:
1447 /// Re-insert an extracted node.
1448 insert_return_type
1449 _M_reinsert_node_unique(node_type&& __nh)
1450 {
1451 insert_return_type __ret;
1452 if (__nh.empty())
1453 __ret.position = end();
1454 else
1455 {
1456 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1457
1458 auto __res = _M_get_insert_unique_pos(__nh._M_key());
1459 if (__res.second)
1460 {
1461 __ret.position
1462 = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1463 __nh._M_ptr = nullptr;
1464 __ret.inserted = true;
1465 }
1466 else
1467 {
1468 __ret.node = std::move(__nh);
1469 __ret.position = iterator(__res.first);
1470 __ret.inserted = false;
1471 }
1472 }
1473 return __ret;
1474 }
1475
1476 /// Re-insert an extracted node.
1477 iterator
1478 _M_reinsert_node_equal(node_type&& __nh)
1479 {
1480 iterator __ret;
1481 if (__nh.empty())
1482 __ret = end();
1483 else
1484 {
1485 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1486 auto __res = _M_get_insert_equal_pos(__nh._M_key());
1487 if (__res.second)
1488 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1489 else
1490 __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1491 __nh._M_ptr = nullptr;
1492 }
1493 return __ret;
1494 }
1495
1496 /// Re-insert an extracted node.
1497 iterator
1498 _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
1499 {
1500 iterator __ret;
1501 if (__nh.empty())
1502 __ret = end();
1503 else
1504 {
1505 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1506 auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
1507 if (__res.second)
1508 {
1509 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1510 __nh._M_ptr = nullptr;
1511 }
1512 else
1513 __ret = iterator(__res.first);
1514 }
1515 return __ret;
1516 }
1517
1518 /// Re-insert an extracted node.
1519 iterator
1520 _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
1521 {
1522 iterator __ret;
1523 if (__nh.empty())
1524 __ret = end();
1525 else
1526 {
1527 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1528 auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
1529 if (__res.second)
1530 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1531 else
1532 __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1533 __nh._M_ptr = nullptr;
1534 }
1535 return __ret;
1536 }
1537
1538 /// Extract a node.
1539 node_type
1540 extract(const_iterator __pos)
1541 {
1542 auto __ptr = _Rb_tree_rebalance_for_erase(
1543 __pos._M_const_cast()._M_node, _M_impl._M_header);
1544 --_M_impl._M_node_count;
1545 return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() };
1546 }
1547
1548 /// Extract a node.
1549 node_type
1550 extract(const key_type& __k)
1551 {
1552 node_type __nh;
1553 auto __pos = find(__k);
1554 if (__pos != end())
1555 __nh = extract(const_iterator(__pos));
1556 return __nh;
1557 }
1558
1559 template<typename _Compare2>
1560 using _Compatible_tree
1561 = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
1562
1563 template<typename, typename>
1564 friend class _Rb_tree_merge_helper;
1565
1566 /// Merge from a compatible container into one with unique keys.
1567 template<typename _Compare2>
1568 void
1569 _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept
1570 {
1571 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1572 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1573 {
1574 auto __pos = __i++;
1575 auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos));
1576 if (__res.second)
1577 {
1578 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1579 auto __ptr = _Rb_tree_rebalance_for_erase(
1580 __pos._M_node, __src_impl._M_header);
1581 --__src_impl._M_node_count;
1582 _M_insert_node(__res.first, __res.second,
1583 static_cast<_Link_type>(__ptr));
1584 }
1585 }
1586 }
1587
1588 /// Merge from a compatible container into one with equivalent keys.
1589 template<typename _Compare2>
1590 void
1591 _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept
1592 {
1593 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1594 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1595 {
1596 auto __pos = __i++;
1597 auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos));
1598 if (__res.second)
1599 {
1600 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1601 auto __ptr = _Rb_tree_rebalance_for_erase(
1602 __pos._M_node, __src_impl._M_header);
1603 --__src_impl._M_node_count;
1604 _M_insert_node(__res.first, __res.second,
1605 static_cast<_Link_type>(__ptr));
1606 }
1607 }
1608 }
1609#endif // C++17
1610
1611 friend bool
1612 operator==(const _Rb_tree& __x, const _Rb_tree& __y)
1613 {
1614 return __x.size() == __y.size()
1615 && std::equal(__x.begin(), __x.end(), __y.begin());
1616 }
1617
1618 friend bool
1619 operator<(const _Rb_tree& __x, const _Rb_tree& __y)
1620 {
1621 return std::lexicographical_compare(__x.begin(), __x.end(),
1622 __y.begin(), __y.end());
1623 }
1624
1625 friend bool _GLIBCXX_DEPRECATED
1626 operator!=(const _Rb_tree& __x, const _Rb_tree& __y)
1627 { return !(__x == __y); }
1628
1629 friend bool _GLIBCXX_DEPRECATED
1630 operator>(const _Rb_tree& __x, const _Rb_tree& __y)
1631 { return __y < __x; }
1632
1633 friend bool _GLIBCXX_DEPRECATED
1634 operator<=(const _Rb_tree& __x, const _Rb_tree& __y)
1635 { return !(__y < __x); }
1636
1637 friend bool _GLIBCXX_DEPRECATED
1638 operator>=(const _Rb_tree& __x, const _Rb_tree& __y)
1639 { return !(__x < __y); }
1640 };
1641
1642 template<typename _Key, typename _Val, typename _KeyOfValue,
1643 typename _Compare, typename _Alloc>
1644 inline void
1645 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1646 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1647 { __x.swap(__y); }
1648
1649#if __cplusplus >= 201103L
1650 template<typename _Key, typename _Val, typename _KeyOfValue,
1651 typename _Compare, typename _Alloc>
1652 void
1653 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1654 _M_move_data(_Rb_tree& __x, false_type)
1655 {
1656 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1657 _M_move_data(__x, true_type());
1658 else
1659 {
1660 _Alloc_node __an(*this);
1661 auto __lbd =
1662 [&__an](const value_type& __cval)
1663 {
1664 auto& __val = const_cast<value_type&>(__cval);
1665 return __an(std::move_if_noexcept(__val));
1666 };
1667 _M_root() = _M_copy(__x, __lbd);
1668 }
1669 }
1670
1671 template<typename _Key, typename _Val, typename _KeyOfValue,
1672 typename _Compare, typename _Alloc>
1673 inline void
1674 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1675 _M_move_assign(_Rb_tree& __x, true_type)
1676 {
1677 clear();
1678 if (__x._M_root() != nullptr)
1679 _M_move_data(__x, true_type());
1680 std::__alloc_on_move(_M_get_Node_allocator(),
1681 __x._M_get_Node_allocator());
1682 }
1683
1684 template<typename _Key, typename _Val, typename _KeyOfValue,
1685 typename _Compare, typename _Alloc>
1686 void
1687 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1688 _M_move_assign(_Rb_tree& __x, false_type)
1689 {
1690 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1691 return _M_move_assign(__x, true_type{});
1692
1693 // Try to move each node reusing existing nodes and copying __x nodes
1694 // structure.
1695 _Reuse_or_alloc_node __roan(*this);
1696 _M_impl._M_reset();
1697 if (__x._M_root() != nullptr)
1698 {
1699 auto __lbd =
1700 [&__roan](const value_type& __cval)
1701 {
1702 auto& __val = const_cast<value_type&>(__cval);
1703 return __roan(std::move_if_noexcept(__val));
1704 };
1705 _M_root() = _M_copy(__x, __lbd);
1706 __x.clear();
1707 }
1708 }
1709
1710 template<typename _Key, typename _Val, typename _KeyOfValue,
1711 typename _Compare, typename _Alloc>
1712 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1713 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1714 operator=(_Rb_tree&& __x)
1715 noexcept(_Alloc_traits::_S_nothrow_move()
1716 && is_nothrow_move_assignable<_Compare>::value)
1717 {
1718 _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
1719 _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());
1720 return *this;
1721 }
1722
1723 template<typename _Key, typename _Val, typename _KeyOfValue,
1724 typename _Compare, typename _Alloc>
1725 template<typename _Iterator>
1726 void
1727 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1728 _M_assign_unique(_Iterator __first, _Iterator __last)
1729 {
1730 _Reuse_or_alloc_node __roan(*this);
1731 _M_impl._M_reset();
1732 for (; __first != __last; ++__first)
1733 _M_insert_unique_(end(), *__first, __roan);
1734 }
1735
1736 template<typename _Key, typename _Val, typename _KeyOfValue,
1737 typename _Compare, typename _Alloc>
1738 template<typename _Iterator>
1739 void
1740 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1741 _M_assign_equal(_Iterator __first, _Iterator __last)
1742 {
1743 _Reuse_or_alloc_node __roan(*this);
1744 _M_impl._M_reset();
1745 for (; __first != __last; ++__first)
1746 _M_insert_equal_(end(), *__first, __roan);
1747 }
1748#endif
1749
1750 template<typename _Key, typename _Val, typename _KeyOfValue,
1751 typename _Compare, typename _Alloc>
1752 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1753 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1754 operator=(const _Rb_tree& __x)
1755 {
1756 if (this != &__x)
1757 {
1758 // Note that _Key may be a constant type.
1759#if __cplusplus >= 201103L
1760 if (_Alloc_traits::_S_propagate_on_copy_assign())
1761 {
1762 auto& __this_alloc = this->_M_get_Node_allocator();
1763 auto& __that_alloc = __x._M_get_Node_allocator();
1764 if (!_Alloc_traits::_S_always_equal()
1765 && __this_alloc != __that_alloc)
1766 {
1767 // Replacement allocator cannot free existing storage, we need
1768 // to erase nodes first.
1769 clear();
1770 std::__alloc_on_copy(__this_alloc, __that_alloc);
1771 }
1772 }
1773#endif
1774
1775 _Reuse_or_alloc_node __roan(*this);
1776 _M_impl._M_reset();
1777 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1778 if (__x._M_root() != 0)
1779 _M_root() = _M_copy(__x, __roan);
1780 }
1781
1782 return *this;
1783 }
1784
1785 template<typename _Key, typename _Val, typename _KeyOfValue,
1786 typename _Compare, typename _Alloc>
1787#if __cplusplus >= 201103L
1788 template<typename _Arg, typename _NodeGen>
1789#else
1790 template<typename _NodeGen>
1791#endif
1792 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1793 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1794 _M_insert_(_Base_ptr __x, _Base_ptr __p,
1795#if __cplusplus >= 201103L
1796 _Arg&& __v,
1797#else
1798 const _Val& __v,
1799#endif
1800 _NodeGen& __node_gen)
1801 {
1802 bool __insert_left = (__x != 0 || __p == _M_end()
1803 || _M_impl._M_key_compare(_KeyOfValue()(__v),
1804 _S_key(__p)));
1805
1806 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1807
1808 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1809 this->_M_impl._M_header);
1810 ++_M_impl._M_node_count;
1811 return iterator(__z);
1812 }
1813
1814 template<typename _Key, typename _Val, typename _KeyOfValue,
1815 typename _Compare, typename _Alloc>
1816#if __cplusplus >= 201103L
1817 template<typename _Arg>
1818#endif
1819 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1820 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1821#if __cplusplus >= 201103L
1822 _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1823#else
1824 _M_insert_lower(_Base_ptr __p, const _Val& __v)
1825#endif
1826 {
1827 bool __insert_left = (__p == _M_end()
1828 || !_M_impl._M_key_compare(_S_key(__p),
1829 _KeyOfValue()(__v)));
1830
1831 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1832
1833 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1834 this->_M_impl._M_header);
1835 ++_M_impl._M_node_count;
1836 return iterator(__z);
1837 }
1838
1839 template<typename _Key, typename _Val, typename _KeyOfValue,
1840 typename _Compare, typename _Alloc>
1841#if __cplusplus >= 201103L
1842 template<typename _Arg>
1843#endif
1844 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1845 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1846#if __cplusplus >= 201103L
1847 _M_insert_equal_lower(_Arg&& __v)
1848#else
1849 _M_insert_equal_lower(const _Val& __v)
1850#endif
1851 {
1852 _Link_type __x = _M_begin();
1853 _Base_ptr __y = _M_end();
1854 while (__x != 0)
1855 {
1856 __y = __x;
1857 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1858 _S_left(__x) : _S_right(__x);
1859 }
1860 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1861 }
1862
1863 template<typename _Key, typename _Val, typename _KoV,
1864 typename _Compare, typename _Alloc>
1865 template<typename _NodeGen>
1866 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1867 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1868 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
1869 {
1870 // Structural copy. __x and __p must be non-null.
1871 _Link_type __top = _M_clone_node(__x, __node_gen);
1872 __top->_M_parent = __p;
1873
1874 __try
1875 {
1876 if (__x->_M_right)
1877 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1878 __p = __top;
1879 __x = _S_left(__x);
1880
1881 while (__x != 0)
1882 {
1883 _Link_type __y = _M_clone_node(__x, __node_gen);
1884 __p->_M_left = __y;
1885 __y->_M_parent = __p;
1886 if (__x->_M_right)
1887 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1888 __p = __y;
1889 __x = _S_left(__x);
1890 }
1891 }
1892 __catch(...)
1893 {
1894 _M_erase(__top);
1895 __throw_exception_again;
1896 }
1897 return __top;
1898 }
1899
1900 template<typename _Key, typename _Val, typename _KeyOfValue,
1901 typename _Compare, typename _Alloc>
1902 void
1903 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1904 _M_erase(_Link_type __x)
1905 {
1906 // Erase without rebalancing.
1907 while (__x != 0)
1908 {
1909 _M_erase(_S_right(__x));
1910 _Link_type __y = _S_left(__x);
1911 _M_drop_node(__x);
1912 __x = __y;
1913 }
1914 }
1915
1916 template<typename _Key, typename _Val, typename _KeyOfValue,
1917 typename _Compare, typename _Alloc>
1918 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1919 _Compare, _Alloc>::iterator
1920 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1921 _M_lower_bound(_Link_type __x, _Base_ptr __y,
1922 const _Key& __k)
1923 {
1924 while (__x != 0)
1925 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1926 __y = __x, __x = _S_left(__x);
1927 else
1928 __x = _S_right(__x);
1929 return iterator(__y);
1930 }
1931
1932 template<typename _Key, typename _Val, typename _KeyOfValue,
1933 typename _Compare, typename _Alloc>
1934 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1935 _Compare, _Alloc>::const_iterator
1936 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1937 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1938 const _Key& __k) const
1939 {
1940 while (__x != 0)
1941 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1942 __y = __x, __x = _S_left(__x);
1943 else
1944 __x = _S_right(__x);
1945 return const_iterator(__y);
1946 }
1947
1948 template<typename _Key, typename _Val, typename _KeyOfValue,
1949 typename _Compare, typename _Alloc>
1950 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1951 _Compare, _Alloc>::iterator
1952 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1953 _M_upper_bound(_Link_type __x, _Base_ptr __y,
1954 const _Key& __k)
1955 {
1956 while (__x != 0)
1957 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1958 __y = __x, __x = _S_left(__x);
1959 else
1960 __x = _S_right(__x);
1961 return iterator(__y);
1962 }
1963
1964 template<typename _Key, typename _Val, typename _KeyOfValue,
1965 typename _Compare, typename _Alloc>
1966 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1967 _Compare, _Alloc>::const_iterator
1968 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1969 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1970 const _Key& __k) const
1971 {
1972 while (__x != 0)
1973 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1974 __y = __x, __x = _S_left(__x);
1975 else
1976 __x = _S_right(__x);
1977 return const_iterator(__y);
1978 }
1979
1980 template<typename _Key, typename _Val, typename _KeyOfValue,
1981 typename _Compare, typename _Alloc>
1982 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1983 _Compare, _Alloc>::iterator,
1984 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1985 _Compare, _Alloc>::iterator>
1986 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1987 equal_range(const _Key& __k)
1988 {
1989 _Link_type __x = _M_begin();
1990 _Base_ptr __y = _M_end();
1991 while (__x != 0)
1992 {
1993 if (_M_impl._M_key_compare(_S_key(__x), __k))
1994 __x = _S_right(__x);
1995 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1996 __y = __x, __x = _S_left(__x);
1997 else
1998 {
1999 _Link_type __xu(__x);
2000 _Base_ptr __yu(__y);
2001 __y = __x, __x = _S_left(__x);
2002 __xu = _S_right(__xu);
2003 return pair<iterator,
2004 iterator>(_M_lower_bound(__x, __y, __k),
2005 _M_upper_bound(__xu, __yu, __k));
2006 }
2007 }
2008 return pair<iterator, iterator>(iterator(__y),
2009 iterator(__y));
2010 }
2011
2012 template<typename _Key, typename _Val, typename _KeyOfValue,
2013 typename _Compare, typename _Alloc>
2014 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2015 _Compare, _Alloc>::const_iterator,
2016 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2017 _Compare, _Alloc>::const_iterator>
2018 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2019 equal_range(const _Key& __k) const
2020 {
2021 _Const_Link_type __x = _M_begin();
2022 _Const_Base_ptr __y = _M_end();
2023 while (__x != 0)
2024 {
2025 if (_M_impl._M_key_compare(_S_key(__x), __k))
2026 __x = _S_right(__x);
2027 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2028 __y = __x, __x = _S_left(__x);
2029 else
2030 {
2031 _Const_Link_type __xu(__x);
2032 _Const_Base_ptr __yu(__y);
2033 __y = __x, __x = _S_left(__x);
2034 __xu = _S_right(__xu);
2035 return pair<const_iterator,
2036 const_iterator>(_M_lower_bound(__x, __y, __k),
2037 _M_upper_bound(__xu, __yu, __k));
2038 }
2039 }
2040 return pair<const_iterator, const_iterator>(const_iterator(__y),
2041 const_iterator(__y));
2042 }
2043
2044 template<typename _Key, typename _Val, typename _KeyOfValue,
2045 typename _Compare, typename _Alloc>
2046 void
2047 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2048 swap(_Rb_tree& __t)
2049 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
2050 {
2051 if (_M_root() == 0)
2052 {
2053 if (__t._M_root() != 0)
2054 _M_impl._M_move_data(__t._M_impl);
2055 }
2056 else if (__t._M_root() == 0)
2057 __t._M_impl._M_move_data(_M_impl);
2058 else
2059 {
2060 std::swap(_M_root(),__t._M_root());
2061 std::swap(_M_leftmost(),__t._M_leftmost());
2062 std::swap(_M_rightmost(),__t._M_rightmost());
2063
2064 _M_root()->_M_parent = _M_end();
2065 __t._M_root()->_M_parent = __t._M_end();
2066 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
2067 }
2068 // No need to swap header's color as it does not change.
2069 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
2070
2071 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2072 __t._M_get_Node_allocator());
2073 }
2074
2075 template<typename _Key, typename _Val, typename _KeyOfValue,
2076 typename _Compare, typename _Alloc>
2077 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2078 _Compare, _Alloc>::_Base_ptr,
2079 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2080 _Compare, _Alloc>::_Base_ptr>
2081 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2082 _M_get_insert_unique_pos(const key_type& __k)
2083 {
2084 typedef pair<_Base_ptr, _Base_ptr> _Res;
2085 _Link_type __x = _M_begin();
2086 _Base_ptr __y = _M_end();
2087 bool __comp = true;
2088 while (__x != 0)
2089 {
2090 __y = __x;
2091 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
2092 __x = __comp ? _S_left(__x) : _S_right(__x);
2093 }
2094 iterator __j = iterator(__y);
2095 if (__comp)
2096 {
2097 if (__j == begin())
2098 return _Res(__x, __y);
2099 else
2100 --__j;
2101 }
2102 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
2103 return _Res(__x, __y);
2104 return _Res(__j._M_node, 0);
2105 }
2106
2107 template<typename _Key, typename _Val, typename _KeyOfValue,
2108 typename _Compare, typename _Alloc>
2109 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2110 _Compare, _Alloc>::_Base_ptr,
2111 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2112 _Compare, _Alloc>::_Base_ptr>
2113 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2114 _M_get_insert_equal_pos(const key_type& __k)
2115 {
2116 typedef pair<_Base_ptr, _Base_ptr> _Res;
2117 _Link_type __x = _M_begin();
2118 _Base_ptr __y = _M_end();
2119 while (__x != 0)
2120 {
2121 __y = __x;
2122 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
2123 _S_left(__x) : _S_right(__x);
2124 }
2125 return _Res(__x, __y);
2126 }
2127
2128 template<typename _Key, typename _Val, typename _KeyOfValue,
2129 typename _Compare, typename _Alloc>
2130#if __cplusplus >= 201103L
2131 template<typename _Arg>
2132#endif
2133 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2134 _Compare, _Alloc>::iterator, bool>
2135 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2136#if __cplusplus >= 201103L
2137 _M_insert_unique(_Arg&& __v)
2138#else
2139 _M_insert_unique(const _Val& __v)
2140#endif
2141 {
2142 typedef pair<iterator, bool> _Res;
2143 pair<_Base_ptr, _Base_ptr> __res
2144 = _M_get_insert_unique_pos(_KeyOfValue()(__v));
2145
2146 if (__res.second)
2147 {
2148 _Alloc_node __an(*this);
2149 return _Res(_M_insert_(__res.first, __res.second,
2150 _GLIBCXX_FORWARD(_Arg, __v), __an),
2151 true);
2152 }
2153
2154 return _Res(iterator(__res.first), false);
2155 }
2156
2157 template<typename _Key, typename _Val, typename _KeyOfValue,
2158 typename _Compare, typename _Alloc>
2159#if __cplusplus >= 201103L
2160 template<typename _Arg>
2161#endif
2162 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2163 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2164#if __cplusplus >= 201103L
2165 _M_insert_equal(_Arg&& __v)
2166#else
2167 _M_insert_equal(const _Val& __v)
2168#endif
2169 {
2170 pair<_Base_ptr, _Base_ptr> __res
2171 = _M_get_insert_equal_pos(_KeyOfValue()(__v));
2172 _Alloc_node __an(*this);
2173 return _M_insert_(__res.first, __res.second,
2174 _GLIBCXX_FORWARD(_Arg, __v), __an);
2175 }
2176
2177 template<typename _Key, typename _Val, typename _KeyOfValue,
2178 typename _Compare, typename _Alloc>
2179 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2180 _Compare, _Alloc>::_Base_ptr,
2181 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2182 _Compare, _Alloc>::_Base_ptr>
2183 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2184 _M_get_insert_hint_unique_pos(const_iterator __position,
2185 const key_type& __k)
2186 {
2187 iterator __pos = __position._M_const_cast();
2188 typedef pair<_Base_ptr, _Base_ptr> _Res;
2189
2190 // end()
2191 if (__pos._M_node == _M_end())
2192 {
2193 if (size() > 0
2194 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
2195 return _Res(0, _M_rightmost());
2196 else
2197 return _M_get_insert_unique_pos(__k);
2198 }
2199 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
2200 {
2201 // First, try before...
2202 iterator __before = __pos;
2203 if (__pos._M_node == _M_leftmost()) // begin()
2204 return _Res(_M_leftmost(), _M_leftmost());
2205 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
2206 {
2207 if (_S_right(__before._M_node) == 0)
2208 return _Res(0, __before._M_node);
2209 else
2210 return _Res(__pos._M_node, __pos._M_node);
2211 }
2212 else
2213 return _M_get_insert_unique_pos(__k);
2214 }
2215 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2216 {
2217 // ... then try after.
2218 iterator __after = __pos;
2219 if (__pos._M_node == _M_rightmost())
2220 return _Res(0, _M_rightmost());
2221 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
2222 {
2223 if (_S_right(__pos._M_node) == 0)
2224 return _Res(0, __pos._M_node);
2225 else
2226 return _Res(__after._M_node, __after._M_node);
2227 }
2228 else
2229 return _M_get_insert_unique_pos(__k);
2230 }
2231 else
2232 // Equivalent keys.
2233 return _Res(__pos._M_node, 0);
2234 }
2235
2236 template<typename _Key, typename _Val, typename _KeyOfValue,
2237 typename _Compare, typename _Alloc>
2238#if __cplusplus >= 201103L
2239 template<typename _Arg, typename _NodeGen>
2240#else
2241 template<typename _NodeGen>
2242#endif
2243 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2244 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2245 _M_insert_unique_(const_iterator __position,
2246#if __cplusplus >= 201103L
2247 _Arg&& __v,
2248#else
2249 const _Val& __v,
2250#endif
2251 _NodeGen& __node_gen)
2252 {
2253 pair<_Base_ptr, _Base_ptr> __res
2254 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
2255
2256 if (__res.second)
2257 return _M_insert_(__res.first, __res.second,
2258 _GLIBCXX_FORWARD(_Arg, __v),
2259 __node_gen);
2260 return iterator(__res.first);
2261 }
2262
2263 template<typename _Key, typename _Val, typename _KeyOfValue,
2264 typename _Compare, typename _Alloc>
2265 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2266 _Compare, _Alloc>::_Base_ptr,
2267 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2268 _Compare, _Alloc>::_Base_ptr>
2269 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2270 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
2271 {
2272 iterator __pos = __position._M_const_cast();
2273 typedef pair<_Base_ptr, _Base_ptr> _Res;
2274
2275 // end()
2276 if (__pos._M_node == _M_end())
2277 {
2278 if (size() > 0
2279 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2280 return _Res(0, _M_rightmost());
2281 else
2282 return _M_get_insert_equal_pos(__k);
2283 }
2284 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2285 {
2286 // First, try before...
2287 iterator __before = __pos;
2288 if (__pos._M_node == _M_leftmost()) // begin()
2289 return _Res(_M_leftmost(), _M_leftmost());
2290 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2291 {
2292 if (_S_right(__before._M_node) == 0)
2293 return _Res(0, __before._M_node);
2294 else
2295 return _Res(__pos._M_node, __pos._M_node);
2296 }
2297 else
2298 return _M_get_insert_equal_pos(__k);
2299 }
2300 else
2301 {
2302 // ... then try after.
2303 iterator __after = __pos;
2304 if (__pos._M_node == _M_rightmost())
2305 return _Res(0, _M_rightmost());
2306 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2307 {
2308 if (_S_right(__pos._M_node) == 0)
2309 return _Res(0, __pos._M_node);
2310 else
2311 return _Res(__after._M_node, __after._M_node);
2312 }
2313 else
2314 return _Res(0, 0);
2315 }
2316 }
2317
2318 template<typename _Key, typename _Val, typename _KeyOfValue,
2319 typename _Compare, typename _Alloc>
2320#if __cplusplus >= 201103L
2321 template<typename _Arg, typename _NodeGen>
2322#else
2323 template<typename _NodeGen>
2324#endif
2325 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2326 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2327 _M_insert_equal_(const_iterator __position,
2328#if __cplusplus >= 201103L
2329 _Arg&& __v,
2330#else
2331 const _Val& __v,
2332#endif
2333 _NodeGen& __node_gen)
2334 {
2335 pair<_Base_ptr, _Base_ptr> __res
2336 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2337
2338 if (__res.second)
2339 return _M_insert_(__res.first, __res.second,
2340 _GLIBCXX_FORWARD(_Arg, __v),
2341 __node_gen);
2342
2343 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2344 }
2345
2346#if __cplusplus >= 201103L
2347 template<typename _Key, typename _Val, typename _KeyOfValue,
2348 typename _Compare, typename _Alloc>
2349 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2350 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2351 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2352 {
2353 bool __insert_left = (__x != 0 || __p == _M_end()
2354 || _M_impl._M_key_compare(_S_key(__z),
2355 _S_key(__p)));
2356
2357 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2358 this->_M_impl._M_header);
2359 ++_M_impl._M_node_count;
2360 return iterator(__z);
2361 }
2362
2363 template<typename _Key, typename _Val, typename _KeyOfValue,
2364 typename _Compare, typename _Alloc>
2365 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2366 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2367 _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2368 {
2369 bool __insert_left = (__p == _M_end()
2370 || !_M_impl._M_key_compare(_S_key(__p),
2371 _S_key(__z)));
2372
2373 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2374 this->_M_impl._M_header);
2375 ++_M_impl._M_node_count;
2376 return iterator(__z);
2377 }
2378
2379 template<typename _Key, typename _Val, typename _KeyOfValue,
2380 typename _Compare, typename _Alloc>
2381 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2382 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2383 _M_insert_equal_lower_node(_Link_type __z)
2384 {
2385 _Link_type __x = _M_begin();
2386 _Base_ptr __y = _M_end();
2387 while (__x != 0)
2388 {
2389 __y = __x;
2390 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2391 _S_left(__x) : _S_right(__x);
2392 }
2393 return _M_insert_lower_node(__y, __z);
2394 }
2395
2396 template<typename _Key, typename _Val, typename _KeyOfValue,
2397 typename _Compare, typename _Alloc>
2398 template<typename... _Args>
2399 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2400 _Compare, _Alloc>::iterator, bool>
2401 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2402 _M_emplace_unique(_Args&&... __args)
2403 {
2404 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2405
2406 __try
2407 {
2408 typedef pair<iterator, bool> _Res;
2409 auto __res = _M_get_insert_unique_pos(_S_key(__z));
2410 if (__res.second)
2411 return _Res(_M_insert_node(__res.first, __res.second, __z), true);
2412
2413 _M_drop_node(__z);
2414 return _Res(iterator(__res.first), false);
2415 }
2416 __catch(...)
2417 {
2418 _M_drop_node(__z);
2419 __throw_exception_again;
2420 }
2421 }
2422
2423 template<typename _Key, typename _Val, typename _KeyOfValue,
2424 typename _Compare, typename _Alloc>
2425 template<typename... _Args>
2426 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2427 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2428 _M_emplace_equal(_Args&&... __args)
2429 {
2430 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2431
2432 __try
2433 {
2434 auto __res = _M_get_insert_equal_pos(_S_key(__z));
2435 return _M_insert_node(__res.first, __res.second, __z);
2436 }
2437 __catch(...)
2438 {
2439 _M_drop_node(__z);
2440 __throw_exception_again;
2441 }
2442 }
2443
2444 template<typename _Key, typename _Val, typename _KeyOfValue,
2445 typename _Compare, typename _Alloc>
2446 template<typename... _Args>
2447 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2448 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2449 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2450 {
2451 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2452
2453 __try
2454 {
2455 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2456
2457 if (__res.second)
2458 return _M_insert_node(__res.first, __res.second, __z);
2459
2460 _M_drop_node(__z);
2461 return iterator(__res.first);
2462 }
2463 __catch(...)
2464 {
2465 _M_drop_node(__z);
2466 __throw_exception_again;
2467 }
2468 }
2469
2470 template<typename _Key, typename _Val, typename _KeyOfValue,
2471 typename _Compare, typename _Alloc>
2472 template<typename... _Args>
2473 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2474 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2475 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2476 {
2477 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2478
2479 __try
2480 {
2481 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2482
2483 if (__res.second)
2484 return _M_insert_node(__res.first, __res.second, __z);
2485
2486 return _M_insert_equal_lower_node(__z);
2487 }
2488 __catch(...)
2489 {
2490 _M_drop_node(__z);
2491 __throw_exception_again;
2492 }
2493 }
2494#endif
2495
2496
2497 template<typename _Key, typename _Val, typename _KeyOfValue,
2498 typename _Compare, typename _Alloc>
2499 void
2500 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2501 _M_erase_aux(const_iterator __position)
2502 {
2503 _Link_type __y =
2504 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
2505 (const_cast<_Base_ptr>(__position._M_node),
2506 this->_M_impl._M_header));
2507 _M_drop_node(__y);
2508 --_M_impl._M_node_count;
2509 }
2510
2511 template<typename _Key, typename _Val, typename _KeyOfValue,
2512 typename _Compare, typename _Alloc>
2513 void
2514 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2515 _M_erase_aux(const_iterator __first, const_iterator __last)
2516 {
2517 if (__first == begin() && __last == end())
2518 clear();
2519 else
2520 while (__first != __last)
2521 _M_erase_aux(__first++);
2522 }
2523
2524 template<typename _Key, typename _Val, typename _KeyOfValue,
2525 typename _Compare, typename _Alloc>
2526 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2527 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2528 erase(const _Key& __x)
2529 {
2530 pair<iterator, iterator> __p = equal_range(__x);
2531 const size_type __old_size = size();
2532 _M_erase_aux(__p.first, __p.second);
2533 return __old_size - size();
2534 }
2535
2536 template<typename _Key, typename _Val, typename _KeyOfValue,
2537 typename _Compare, typename _Alloc>
2538 void
2539 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2540 erase(const _Key* __first, const _Key* __last)
2541 {
2542 while (__first != __last)
2543 erase(*__first++);
2544 }
2545
2546 template<typename _Key, typename _Val, typename _KeyOfValue,
2547 typename _Compare, typename _Alloc>
2548 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2549 _Compare, _Alloc>::iterator
2550 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2551 find(const _Key& __k)
2552 {
2553 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2554 return (__j == end()
2555 || _M_impl._M_key_compare(__k,
2556 _S_key(__j._M_node))) ? end() : __j;
2557 }
2558
2559 template<typename _Key, typename _Val, typename _KeyOfValue,
2560 typename _Compare, typename _Alloc>
2561 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2562 _Compare, _Alloc>::const_iterator
2563 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2564 find(const _Key& __k) const
2565 {
2566 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2567 return (__j == end()
2568 || _M_impl._M_key_compare(__k,
2569 _S_key(__j._M_node))) ? end() : __j;
2570 }
2571
2572 template<typename _Key, typename _Val, typename _KeyOfValue,
2573 typename _Compare, typename _Alloc>
2574 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2575 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2576 count(const _Key& __k) const
2577 {
2578 pair<const_iterator, const_iterator> __p = equal_range(__k);
2579 const size_type __n = std::distance(__p.first, __p.second);
2580 return __n;
2581 }
2582
2583 _GLIBCXX_PURE unsigned int
2584 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
2585 const _Rb_tree_node_base* __root) throw ();
2586
2587 template<typename _Key, typename _Val, typename _KeyOfValue,
2588 typename _Compare, typename _Alloc>
2589 bool
2590 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
2591 {
2592 if (_M_impl._M_node_count == 0 || begin() == end())
2593 return _M_impl._M_node_count == 0 && begin() == end()
2594 && this->_M_impl._M_header._M_left == _M_end()
2595 && this->_M_impl._M_header._M_right == _M_end();
2596
2597 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2598 for (const_iterator __it = begin(); __it != end(); ++__it)
2599 {
2600 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
2601 _Const_Link_type __L = _S_left(__x);
2602 _Const_Link_type __R = _S_right(__x);
2603
2604 if (__x->_M_color == _S_red)
2605 if ((__L && __L->_M_color == _S_red)
2606 || (__R && __R->_M_color == _S_red))
2607 return false;
2608
2609 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2610 return false;
2611 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2612 return false;
2613
2614 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2615 return false;
2616 }
2617
2618 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2619 return false;
2620 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2621 return false;
2622 return true;
2623 }
2624
2625#if __cplusplus > 201402L
2626 // Allow access to internals of compatible _Rb_tree specializations.
2627 template<typename _Key, typename _Val, typename _Sel, typename _Cmp1,
2628 typename _Alloc, typename _Cmp2>
2629 struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
2630 _Cmp2>
2631 {
2632 private:
2633 friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;
2634
2635 static auto&
2636 _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
2637 { return __tree._M_impl; }
2638 };
2639#endif // C++17
2640
2641_GLIBCXX_END_NAMESPACE_VERSION
2642} // namespace
2643
2644#endif
2645