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 {
769#if __cplusplus >= 201103L
770 // If we're asking for the key we're presumably using the comparison
771 // object, and so this is a good place to sanity check it.
772 static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
773 "comparison object must be invocable "
774 "with two arguments of key type");
775# if __cplusplus >= 201703L
776 // _GLIBCXX_RESOLVE_LIB_DEFECTS
777 // 2542. Missing const requirements for associative containers
778 if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{})
779 static_assert(
780 is_invocable_v<const _Compare&, const _Key&, const _Key&>,
781 "comparison object must be invocable as const");
782# endif // C++17
783#endif // C++11
784
785 return _KeyOfValue()(*__x->_M_valptr());
786 }
787
788 static _Link_type
789 _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
790 { return static_cast<_Link_type>(__x->_M_left); }
791
792 static _Const_Link_type
793 _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
794 { return static_cast<_Const_Link_type>(__x->_M_left); }
795
796 static _Link_type
797 _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
798 { return static_cast<_Link_type>(__x->_M_right); }
799
800 static _Const_Link_type
801 _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
802 { return static_cast<_Const_Link_type>(__x->_M_right); }
803
804 static const_reference
805 _S_value(_Const_Base_ptr __x)
806 { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
807
808 static const _Key&
809 _S_key(_Const_Base_ptr __x)
810 { return _S_key(static_cast<_Const_Link_type>(__x)); }
811
812 static _Base_ptr
813 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
814 { return _Rb_tree_node_base::_S_minimum(__x); }
815
816 static _Const_Base_ptr
817 _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
818 { return _Rb_tree_node_base::_S_minimum(__x); }
819
820 static _Base_ptr
821 _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
822 { return _Rb_tree_node_base::_S_maximum(__x); }
823
824 static _Const_Base_ptr
825 _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
826 { return _Rb_tree_node_base::_S_maximum(__x); }
827
828 public:
829 typedef _Rb_tree_iterator<value_type> iterator;
830 typedef _Rb_tree_const_iterator<value_type> const_iterator;
831
832 typedef std::reverse_iterator<iterator> reverse_iterator;
833 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
834
835#if __cplusplus > 201402L
836 using node_type = _Node_handle<_Key, _Val, _Node_allocator>;
837 using insert_return_type = _Node_insert_return<
838 conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>,
839 node_type>;
840#endif
841
842 pair<_Base_ptr, _Base_ptr>
843 _M_get_insert_unique_pos(const key_type& __k);
844
845 pair<_Base_ptr, _Base_ptr>
846 _M_get_insert_equal_pos(const key_type& __k);
847
848 pair<_Base_ptr, _Base_ptr>
849 _M_get_insert_hint_unique_pos(const_iterator __pos,
850 const key_type& __k);
851
852 pair<_Base_ptr, _Base_ptr>
853 _M_get_insert_hint_equal_pos(const_iterator __pos,
854 const key_type& __k);
855
856 private:
857#if __cplusplus >= 201103L
858 template<typename _Arg, typename _NodeGen>
859 iterator
860 _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
861
862 iterator
863 _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
864
865 template<typename _Arg>
866 iterator
867 _M_insert_lower(_Base_ptr __y, _Arg&& __v);
868
869 template<typename _Arg>
870 iterator
871 _M_insert_equal_lower(_Arg&& __x);
872
873 iterator
874 _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
875
876 iterator
877 _M_insert_equal_lower_node(_Link_type __z);
878#else
879 template<typename _NodeGen>
880 iterator
881 _M_insert_(_Base_ptr __x, _Base_ptr __y,
882 const value_type& __v, _NodeGen&);
883
884 // _GLIBCXX_RESOLVE_LIB_DEFECTS
885 // 233. Insertion hints in associative containers.
886 iterator
887 _M_insert_lower(_Base_ptr __y, const value_type& __v);
888
889 iterator
890 _M_insert_equal_lower(const value_type& __x);
891#endif
892
893 template<typename _NodeGen>
894 _Link_type
895 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
896
897 template<typename _NodeGen>
898 _Link_type
899 _M_copy(const _Rb_tree& __x, _NodeGen& __gen)
900 {
901 _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
902 _M_leftmost() = _S_minimum(__root);
903 _M_rightmost() = _S_maximum(__root);
904 _M_impl._M_node_count = __x._M_impl._M_node_count;
905 return __root;
906 }
907
908 _Link_type
909 _M_copy(const _Rb_tree& __x)
910 {
911 _Alloc_node __an(*this);
912 return _M_copy(__x, __an);
913 }
914
915 void
916 _M_erase(_Link_type __x);
917
918 iterator
919 _M_lower_bound(_Link_type __x, _Base_ptr __y,
920 const _Key& __k);
921
922 const_iterator
923 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
924 const _Key& __k) const;
925
926 iterator
927 _M_upper_bound(_Link_type __x, _Base_ptr __y,
928 const _Key& __k);
929
930 const_iterator
931 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
932 const _Key& __k) const;
933
934 public:
935 // allocation/deallocation
936#if __cplusplus < 201103L
937 _Rb_tree() { }
938#else
939 _Rb_tree() = default;
940#endif
941
942 _Rb_tree(const _Compare& __comp,
943 const allocator_type& __a = allocator_type())
944 : _M_impl(__comp, _Node_allocator(__a)) { }
945
946 _Rb_tree(const _Rb_tree& __x)
947 : _M_impl(__x._M_impl)
948 {
949 if (__x._M_root() != 0)
950 _M_root() = _M_copy(__x);
951 }
952
953#if __cplusplus >= 201103L
954 _Rb_tree(const allocator_type& __a)
955 : _M_impl(_Node_allocator(__a))
956 { }
957
958 _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
959 : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
960 {
961 if (__x._M_root() != nullptr)
962 _M_root() = _M_copy(__x);
963 }
964
965 _Rb_tree(_Rb_tree&&) = default;
966
967 _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
968 : _Rb_tree(std::move(__x), _Node_allocator(__a))
969 { }
970
971 private:
972 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
973 noexcept(is_nothrow_default_constructible<_Compare>::value)
974 : _M_impl(std::move(__x._M_impl), std::move(__a))
975 { }
976
977 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
978 : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
979 {
980 if (__x._M_root() != nullptr)
981 _M_move_data(__x, false_type{});
982 }
983
984 public:
985 _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
986 noexcept( noexcept(
987 _Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(),
988 std::declval<typename _Alloc_traits::is_always_equal>())) )
989 : _Rb_tree(std::move(__x), std::move(__a),
990 typename _Alloc_traits::is_always_equal{})
991 { }
992#endif
993
994 ~_Rb_tree() _GLIBCXX_NOEXCEPT
995 { _M_erase(_M_begin()); }
996
997 _Rb_tree&
998 operator=(const _Rb_tree& __x);
999
1000 // Accessors.
1001 _Compare
1002 key_comp() const
1003 { return _M_impl._M_key_compare; }
1004
1005 iterator
1006 begin() _GLIBCXX_NOEXCEPT
1007 { return iterator(this->_M_impl._M_header._M_left); }
1008
1009 const_iterator
1010 begin() const _GLIBCXX_NOEXCEPT
1011 { return const_iterator(this->_M_impl._M_header._M_left); }
1012
1013 iterator
1014 end() _GLIBCXX_NOEXCEPT
1015 { return iterator(&this->_M_impl._M_header); }
1016
1017 const_iterator
1018 end() const _GLIBCXX_NOEXCEPT
1019 { return const_iterator(&this->_M_impl._M_header); }
1020
1021 reverse_iterator
1022 rbegin() _GLIBCXX_NOEXCEPT
1023 { return reverse_iterator(end()); }
1024
1025 const_reverse_iterator
1026 rbegin() const _GLIBCXX_NOEXCEPT
1027 { return const_reverse_iterator(end()); }
1028
1029 reverse_iterator
1030 rend() _GLIBCXX_NOEXCEPT
1031 { return reverse_iterator(begin()); }
1032
1033 const_reverse_iterator
1034 rend() const _GLIBCXX_NOEXCEPT
1035 { return const_reverse_iterator(begin()); }
1036
1037 _GLIBCXX_NODISCARD bool
1038 empty() const _GLIBCXX_NOEXCEPT
1039 { return _M_impl._M_node_count == 0; }
1040
1041 size_type
1042 size() const _GLIBCXX_NOEXCEPT
1043 { return _M_impl._M_node_count; }
1044
1045 size_type
1046 max_size() const _GLIBCXX_NOEXCEPT
1047 { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
1048
1049 void
1050 swap(_Rb_tree& __t)
1051 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
1052
1053 // Insert/erase.
1054#if __cplusplus >= 201103L
1055 template<typename _Arg>
1056 pair<iterator, bool>
1057 _M_insert_unique(_Arg&& __x);
1058
1059 template<typename _Arg>
1060 iterator
1061 _M_insert_equal(_Arg&& __x);
1062
1063 template<typename _Arg, typename _NodeGen>
1064 iterator
1065 _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1066
1067 template<typename _Arg>
1068 iterator
1069 _M_insert_unique_(const_iterator __pos, _Arg&& __x)
1070 {
1071 _Alloc_node __an(*this);
1072 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
1073 }
1074
1075 template<typename _Arg, typename _NodeGen>
1076 iterator
1077 _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1078
1079 template<typename _Arg>
1080 iterator
1081 _M_insert_equal_(const_iterator __pos, _Arg&& __x)
1082 {
1083 _Alloc_node __an(*this);
1084 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
1085 }
1086
1087 template<typename... _Args>
1088 pair<iterator, bool>
1089 _M_emplace_unique(_Args&&... __args);
1090
1091 template<typename... _Args>
1092 iterator
1093 _M_emplace_equal(_Args&&... __args);
1094
1095 template<typename... _Args>
1096 iterator
1097 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
1098
1099 template<typename... _Args>
1100 iterator
1101 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
1102
1103 template<typename _Iter>
1104 using __same_value_type
1105 = is_same<value_type, typename iterator_traits<_Iter>::value_type>;
1106
1107 template<typename _InputIterator>
1108 __enable_if_t<__same_value_type<_InputIterator>::value>
1109 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1110 {
1111 _Alloc_node __an(*this);
1112 for (; __first != __last; ++__first)
1113 _M_insert_unique_(end(), *__first, __an);
1114 }
1115
1116 template<typename _InputIterator>
1117 __enable_if_t<!__same_value_type<_InputIterator>::value>
1118 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1119 {
1120 for (; __first != __last; ++__first)
1121 _M_emplace_unique(*__first);
1122 }
1123
1124 template<typename _InputIterator>
1125 __enable_if_t<__same_value_type<_InputIterator>::value>
1126 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1127 {
1128 _Alloc_node __an(*this);
1129 for (; __first != __last; ++__first)
1130 _M_insert_equal_(end(), *__first, __an);
1131 }
1132
1133 template<typename _InputIterator>
1134 __enable_if_t<!__same_value_type<_InputIterator>::value>
1135 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1136 {
1137 _Alloc_node __an(*this);
1138 for (; __first != __last; ++__first)
1139 _M_emplace_equal(*__first);
1140 }
1141#else
1142 pair<iterator, bool>
1143 _M_insert_unique(const value_type& __x);
1144
1145 iterator
1146 _M_insert_equal(const value_type& __x);
1147
1148 template<typename _NodeGen>
1149 iterator
1150 _M_insert_unique_(const_iterator __pos, const value_type& __x,
1151 _NodeGen&);
1152
1153 iterator
1154 _M_insert_unique_(const_iterator __pos, const value_type& __x)
1155 {
1156 _Alloc_node __an(*this);
1157 return _M_insert_unique_(__pos, __x, __an);
1158 }
1159
1160 template<typename _NodeGen>
1161 iterator
1162 _M_insert_equal_(const_iterator __pos, const value_type& __x,
1163 _NodeGen&);
1164 iterator
1165 _M_insert_equal_(const_iterator __pos, const value_type& __x)
1166 {
1167 _Alloc_node __an(*this);
1168 return _M_insert_equal_(__pos, __x, __an);
1169 }
1170
1171 template<typename _InputIterator>
1172 void
1173 _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1174 {
1175 _Alloc_node __an(*this);
1176 for (; __first != __last; ++__first)
1177 _M_insert_unique_(end(), *__first, __an);
1178 }
1179
1180 template<typename _InputIterator>
1181 void
1182 _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1183 {
1184 _Alloc_node __an(*this);
1185 for (; __first != __last; ++__first)
1186 _M_insert_equal_(end(), *__first, __an);
1187 }
1188#endif
1189
1190 private:
1191 void
1192 _M_erase_aux(const_iterator __position);
1193
1194 void
1195 _M_erase_aux(const_iterator __first, const_iterator __last);
1196
1197 public:
1198#if __cplusplus >= 201103L
1199 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1200 // DR 130. Associative erase should return an iterator.
1201 _GLIBCXX_ABI_TAG_CXX11
1202 iterator
1203 erase(const_iterator __position)
1204 {
1205 __glibcxx_assert(__position != end());
1206 const_iterator __result = __position;
1207 ++__result;
1208 _M_erase_aux(__position);
1209 return __result._M_const_cast();
1210 }
1211
1212 // LWG 2059.
1213 _GLIBCXX_ABI_TAG_CXX11
1214 iterator
1215 erase(iterator __position)
1216 {
1217 __glibcxx_assert(__position != end());
1218 iterator __result = __position;
1219 ++__result;
1220 _M_erase_aux(__position);
1221 return __result;
1222 }
1223#else
1224 void
1225 erase(iterator __position)
1226 {
1227 __glibcxx_assert(__position != end());
1228 _M_erase_aux(__position);
1229 }
1230
1231 void
1232 erase(const_iterator __position)
1233 {
1234 __glibcxx_assert(__position != end());
1235 _M_erase_aux(__position);
1236 }
1237#endif
1238 size_type
1239 erase(const key_type& __x);
1240
1241#if __cplusplus >= 201103L
1242 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1243 // DR 130. Associative erase should return an iterator.
1244 _GLIBCXX_ABI_TAG_CXX11
1245 iterator
1246 erase(const_iterator __first, const_iterator __last)
1247 {
1248 _M_erase_aux(__first, __last);
1249 return __last._M_const_cast();
1250 }
1251#else
1252 void
1253 erase(iterator __first, iterator __last)
1254 { _M_erase_aux(__first, __last); }
1255
1256 void
1257 erase(const_iterator __first, const_iterator __last)
1258 { _M_erase_aux(__first, __last); }
1259#endif
1260 void
1261 erase(const key_type* __first, const key_type* __last);
1262
1263 void
1264 clear() _GLIBCXX_NOEXCEPT
1265 {
1266 _M_erase(_M_begin());
1267 _M_impl._M_reset();
1268 }
1269
1270 // Set operations.
1271 iterator
1272 find(const key_type& __k);
1273
1274 const_iterator
1275 find(const key_type& __k) const;
1276
1277 size_type
1278 count(const key_type& __k) const;
1279
1280 iterator
1281 lower_bound(const key_type& __k)
1282 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1283
1284 const_iterator
1285 lower_bound(const key_type& __k) const
1286 { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1287
1288 iterator
1289 upper_bound(const key_type& __k)
1290 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1291
1292 const_iterator
1293 upper_bound(const key_type& __k) const
1294 { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1295
1296 pair<iterator, iterator>
1297 equal_range(const key_type& __k);
1298
1299 pair<const_iterator, const_iterator>
1300 equal_range(const key_type& __k) const;
1301
1302#if __cplusplus >= 201402L
1303 template<typename _Kt,
1304 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1305 iterator
1306 _M_find_tr(const _Kt& __k)
1307 {
1308 const _Rb_tree* __const_this = this;
1309 return __const_this->_M_find_tr(__k)._M_const_cast();
1310 }
1311
1312 template<typename _Kt,
1313 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1314 const_iterator
1315 _M_find_tr(const _Kt& __k) const
1316 {
1317 auto __j = _M_lower_bound_tr(__k);
1318 if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1319 __j = end();
1320 return __j;
1321 }
1322
1323 template<typename _Kt,
1324 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1325 size_type
1326 _M_count_tr(const _Kt& __k) const
1327 {
1328 auto __p = _M_equal_range_tr(__k);
1329 return std::distance(__p.first, __p.second);
1330 }
1331
1332 template<typename _Kt,
1333 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1334 iterator
1335 _M_lower_bound_tr(const _Kt& __k)
1336 {
1337 const _Rb_tree* __const_this = this;
1338 return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
1339 }
1340
1341 template<typename _Kt,
1342 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1343 const_iterator
1344 _M_lower_bound_tr(const _Kt& __k) const
1345 {
1346 auto __x = _M_begin();
1347 auto __y = _M_end();
1348 while (__x != 0)
1349 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1350 {
1351 __y = __x;
1352 __x = _S_left(__x);
1353 }
1354 else
1355 __x = _S_right(__x);
1356 return const_iterator(__y);
1357 }
1358
1359 template<typename _Kt,
1360 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1361 iterator
1362 _M_upper_bound_tr(const _Kt& __k)
1363 {
1364 const _Rb_tree* __const_this = this;
1365 return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
1366 }
1367
1368 template<typename _Kt,
1369 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1370 const_iterator
1371 _M_upper_bound_tr(const _Kt& __k) const
1372 {
1373 auto __x = _M_begin();
1374 auto __y = _M_end();
1375 while (__x != 0)
1376 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1377 {
1378 __y = __x;
1379 __x = _S_left(__x);
1380 }
1381 else
1382 __x = _S_right(__x);
1383 return const_iterator(__y);
1384 }
1385
1386 template<typename _Kt,
1387 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1388 pair<iterator, iterator>
1389 _M_equal_range_tr(const _Kt& __k)
1390 {
1391 const _Rb_tree* __const_this = this;
1392 auto __ret = __const_this->_M_equal_range_tr(__k);
1393 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
1394 }
1395
1396 template<typename _Kt,
1397 typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1398 pair<const_iterator, const_iterator>
1399 _M_equal_range_tr(const _Kt& __k) const
1400 {
1401 auto __low = _M_lower_bound_tr(__k);
1402 auto __high = __low;
1403 auto& __cmp = _M_impl._M_key_compare;
1404 while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1405 ++__high;
1406 return { __low, __high };
1407 }
1408#endif
1409
1410 // Debugging.
1411 bool
1412 __rb_verify() const;
1413
1414#if __cplusplus >= 201103L
1415 _Rb_tree&
1416 operator=(_Rb_tree&&)
1417 noexcept(_Alloc_traits::_S_nothrow_move()
1418 && is_nothrow_move_assignable<_Compare>::value);
1419
1420 template<typename _Iterator>
1421 void
1422 _M_assign_unique(_Iterator, _Iterator);
1423
1424 template<typename _Iterator>
1425 void
1426 _M_assign_equal(_Iterator, _Iterator);
1427
1428 private:
1429 // Move elements from container with equal allocator.
1430 void
1431 _M_move_data(_Rb_tree& __x, true_type)
1432 { _M_impl._M_move_data(__x._M_impl); }
1433
1434 // Move elements from container with possibly non-equal allocator,
1435 // which might result in a copy not a move.
1436 void
1437 _M_move_data(_Rb_tree&, false_type);
1438
1439 // Move assignment from container with equal allocator.
1440 void
1441 _M_move_assign(_Rb_tree&, true_type);
1442
1443 // Move assignment from container with possibly non-equal allocator,
1444 // which might result in a copy not a move.
1445 void
1446 _M_move_assign(_Rb_tree&, false_type);
1447#endif
1448
1449#if __cplusplus > 201402L
1450 public:
1451 /// Re-insert an extracted node.
1452 insert_return_type
1453 _M_reinsert_node_unique(node_type&& __nh)
1454 {
1455 insert_return_type __ret;
1456 if (__nh.empty())
1457 __ret.position = end();
1458 else
1459 {
1460 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1461
1462 auto __res = _M_get_insert_unique_pos(__nh._M_key());
1463 if (__res.second)
1464 {
1465 __ret.position
1466 = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1467 __nh._M_ptr = nullptr;
1468 __ret.inserted = true;
1469 }
1470 else
1471 {
1472 __ret.node = std::move(__nh);
1473 __ret.position = iterator(__res.first);
1474 __ret.inserted = false;
1475 }
1476 }
1477 return __ret;
1478 }
1479
1480 /// Re-insert an extracted node.
1481 iterator
1482 _M_reinsert_node_equal(node_type&& __nh)
1483 {
1484 iterator __ret;
1485 if (__nh.empty())
1486 __ret = end();
1487 else
1488 {
1489 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1490 auto __res = _M_get_insert_equal_pos(__nh._M_key());
1491 if (__res.second)
1492 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1493 else
1494 __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1495 __nh._M_ptr = nullptr;
1496 }
1497 return __ret;
1498 }
1499
1500 /// Re-insert an extracted node.
1501 iterator
1502 _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
1503 {
1504 iterator __ret;
1505 if (__nh.empty())
1506 __ret = end();
1507 else
1508 {
1509 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1510 auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
1511 if (__res.second)
1512 {
1513 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1514 __nh._M_ptr = nullptr;
1515 }
1516 else
1517 __ret = iterator(__res.first);
1518 }
1519 return __ret;
1520 }
1521
1522 /// Re-insert an extracted node.
1523 iterator
1524 _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
1525 {
1526 iterator __ret;
1527 if (__nh.empty())
1528 __ret = end();
1529 else
1530 {
1531 __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
1532 auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
1533 if (__res.second)
1534 __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
1535 else
1536 __ret = _M_insert_equal_lower_node(__nh._M_ptr);
1537 __nh._M_ptr = nullptr;
1538 }
1539 return __ret;
1540 }
1541
1542 /// Extract a node.
1543 node_type
1544 extract(const_iterator __pos)
1545 {
1546 auto __ptr = _Rb_tree_rebalance_for_erase(
1547 __pos._M_const_cast()._M_node, _M_impl._M_header);
1548 --_M_impl._M_node_count;
1549 return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() };
1550 }
1551
1552 /// Extract a node.
1553 node_type
1554 extract(const key_type& __k)
1555 {
1556 node_type __nh;
1557 auto __pos = find(__k);
1558 if (__pos != end())
1559 __nh = extract(const_iterator(__pos));
1560 return __nh;
1561 }
1562
1563 template<typename _Compare2>
1564 using _Compatible_tree
1565 = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
1566
1567 template<typename, typename>
1568 friend class _Rb_tree_merge_helper;
1569
1570 /// Merge from a compatible container into one with unique keys.
1571 template<typename _Compare2>
1572 void
1573 _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept
1574 {
1575 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1576 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1577 {
1578 auto __pos = __i++;
1579 auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos));
1580 if (__res.second)
1581 {
1582 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1583 auto __ptr = _Rb_tree_rebalance_for_erase(
1584 __pos._M_node, __src_impl._M_header);
1585 --__src_impl._M_node_count;
1586 _M_insert_node(__res.first, __res.second,
1587 static_cast<_Link_type>(__ptr));
1588 }
1589 }
1590 }
1591
1592 /// Merge from a compatible container into one with equivalent keys.
1593 template<typename _Compare2>
1594 void
1595 _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept
1596 {
1597 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
1598 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1599 {
1600 auto __pos = __i++;
1601 auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos));
1602 if (__res.second)
1603 {
1604 auto& __src_impl = _Merge_helper::_S_get_impl(__src);
1605 auto __ptr = _Rb_tree_rebalance_for_erase(
1606 __pos._M_node, __src_impl._M_header);
1607 --__src_impl._M_node_count;
1608 _M_insert_node(__res.first, __res.second,
1609 static_cast<_Link_type>(__ptr));
1610 }
1611 }
1612 }
1613#endif // C++17
1614
1615 friend bool
1616 operator==(const _Rb_tree& __x, const _Rb_tree& __y)
1617 {
1618 return __x.size() == __y.size()
1619 && std::equal(__x.begin(), __x.end(), __y.begin());
1620 }
1621
1622 friend bool
1623 operator<(const _Rb_tree& __x, const _Rb_tree& __y)
1624 {
1625 return std::lexicographical_compare(__x.begin(), __x.end(),
1626 __y.begin(), __y.end());
1627 }
1628
1629 friend bool _GLIBCXX_DEPRECATED
1630 operator!=(const _Rb_tree& __x, const _Rb_tree& __y)
1631 { return !(__x == __y); }
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 !(__y < __x); }
1640
1641 friend bool _GLIBCXX_DEPRECATED
1642 operator>=(const _Rb_tree& __x, const _Rb_tree& __y)
1643 { return !(__x < __y); }
1644 };
1645
1646 template<typename _Key, typename _Val, typename _KeyOfValue,
1647 typename _Compare, typename _Alloc>
1648 inline void
1649 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1650 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1651 { __x.swap(__y); }
1652
1653#if __cplusplus >= 201103L
1654 template<typename _Key, typename _Val, typename _KeyOfValue,
1655 typename _Compare, typename _Alloc>
1656 void
1657 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1658 _M_move_data(_Rb_tree& __x, false_type)
1659 {
1660 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1661 _M_move_data(__x, true_type());
1662 else
1663 {
1664 _Alloc_node __an(*this);
1665 auto __lbd =
1666 [&__an](const value_type& __cval)
1667 {
1668 auto& __val = const_cast<value_type&>(__cval);
1669 return __an(std::move_if_noexcept(__val));
1670 };
1671 _M_root() = _M_copy(__x, __lbd);
1672 }
1673 }
1674
1675 template<typename _Key, typename _Val, typename _KeyOfValue,
1676 typename _Compare, typename _Alloc>
1677 inline void
1678 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1679 _M_move_assign(_Rb_tree& __x, true_type)
1680 {
1681 clear();
1682 if (__x._M_root() != nullptr)
1683 _M_move_data(__x, true_type());
1684 std::__alloc_on_move(_M_get_Node_allocator(),
1685 __x._M_get_Node_allocator());
1686 }
1687
1688 template<typename _Key, typename _Val, typename _KeyOfValue,
1689 typename _Compare, typename _Alloc>
1690 void
1691 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1692 _M_move_assign(_Rb_tree& __x, false_type)
1693 {
1694 if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1695 return _M_move_assign(__x, true_type{});
1696
1697 // Try to move each node reusing existing nodes and copying __x nodes
1698 // structure.
1699 _Reuse_or_alloc_node __roan(*this);
1700 _M_impl._M_reset();
1701 if (__x._M_root() != nullptr)
1702 {
1703 auto __lbd =
1704 [&__roan](const value_type& __cval)
1705 {
1706 auto& __val = const_cast<value_type&>(__cval);
1707 return __roan(std::move_if_noexcept(__val));
1708 };
1709 _M_root() = _M_copy(__x, __lbd);
1710 __x.clear();
1711 }
1712 }
1713
1714 template<typename _Key, typename _Val, typename _KeyOfValue,
1715 typename _Compare, typename _Alloc>
1716 inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1717 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1718 operator=(_Rb_tree&& __x)
1719 noexcept(_Alloc_traits::_S_nothrow_move()
1720 && is_nothrow_move_assignable<_Compare>::value)
1721 {
1722 _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
1723 _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());
1724 return *this;
1725 }
1726
1727 template<typename _Key, typename _Val, typename _KeyOfValue,
1728 typename _Compare, typename _Alloc>
1729 template<typename _Iterator>
1730 void
1731 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1732 _M_assign_unique(_Iterator __first, _Iterator __last)
1733 {
1734 _Reuse_or_alloc_node __roan(*this);
1735 _M_impl._M_reset();
1736 for (; __first != __last; ++__first)
1737 _M_insert_unique_(end(), *__first, __roan);
1738 }
1739
1740 template<typename _Key, typename _Val, typename _KeyOfValue,
1741 typename _Compare, typename _Alloc>
1742 template<typename _Iterator>
1743 void
1744 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1745 _M_assign_equal(_Iterator __first, _Iterator __last)
1746 {
1747 _Reuse_or_alloc_node __roan(*this);
1748 _M_impl._M_reset();
1749 for (; __first != __last; ++__first)
1750 _M_insert_equal_(end(), *__first, __roan);
1751 }
1752#endif
1753
1754 template<typename _Key, typename _Val, typename _KeyOfValue,
1755 typename _Compare, typename _Alloc>
1756 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1757 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1758 operator=(const _Rb_tree& __x)
1759 {
1760 if (this != &__x)
1761 {
1762 // Note that _Key may be a constant type.
1763#if __cplusplus >= 201103L
1764 if (_Alloc_traits::_S_propagate_on_copy_assign())
1765 {
1766 auto& __this_alloc = this->_M_get_Node_allocator();
1767 auto& __that_alloc = __x._M_get_Node_allocator();
1768 if (!_Alloc_traits::_S_always_equal()
1769 && __this_alloc != __that_alloc)
1770 {
1771 // Replacement allocator cannot free existing storage, we need
1772 // to erase nodes first.
1773 clear();
1774 std::__alloc_on_copy(__this_alloc, __that_alloc);
1775 }
1776 }
1777#endif
1778
1779 _Reuse_or_alloc_node __roan(*this);
1780 _M_impl._M_reset();
1781 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1782 if (__x._M_root() != 0)
1783 _M_root() = _M_copy(__x, __roan);
1784 }
1785
1786 return *this;
1787 }
1788
1789 template<typename _Key, typename _Val, typename _KeyOfValue,
1790 typename _Compare, typename _Alloc>
1791#if __cplusplus >= 201103L
1792 template<typename _Arg, typename _NodeGen>
1793#else
1794 template<typename _NodeGen>
1795#endif
1796 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1797 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1798 _M_insert_(_Base_ptr __x, _Base_ptr __p,
1799#if __cplusplus >= 201103L
1800 _Arg&& __v,
1801#else
1802 const _Val& __v,
1803#endif
1804 _NodeGen& __node_gen)
1805 {
1806 bool __insert_left = (__x != 0 || __p == _M_end()
1807 || _M_impl._M_key_compare(_KeyOfValue()(__v),
1808 _S_key(__p)));
1809
1810 _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1811
1812 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1813 this->_M_impl._M_header);
1814 ++_M_impl._M_node_count;
1815 return iterator(__z);
1816 }
1817
1818 template<typename _Key, typename _Val, typename _KeyOfValue,
1819 typename _Compare, typename _Alloc>
1820#if __cplusplus >= 201103L
1821 template<typename _Arg>
1822#endif
1823 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1824 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1825#if __cplusplus >= 201103L
1826 _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1827#else
1828 _M_insert_lower(_Base_ptr __p, const _Val& __v)
1829#endif
1830 {
1831 bool __insert_left = (__p == _M_end()
1832 || !_M_impl._M_key_compare(_S_key(__p),
1833 _KeyOfValue()(__v)));
1834
1835 _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1836
1837 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1838 this->_M_impl._M_header);
1839 ++_M_impl._M_node_count;
1840 return iterator(__z);
1841 }
1842
1843 template<typename _Key, typename _Val, typename _KeyOfValue,
1844 typename _Compare, typename _Alloc>
1845#if __cplusplus >= 201103L
1846 template<typename _Arg>
1847#endif
1848 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1849 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1850#if __cplusplus >= 201103L
1851 _M_insert_equal_lower(_Arg&& __v)
1852#else
1853 _M_insert_equal_lower(const _Val& __v)
1854#endif
1855 {
1856 _Link_type __x = _M_begin();
1857 _Base_ptr __y = _M_end();
1858 while (__x != 0)
1859 {
1860 __y = __x;
1861 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1862 _S_left(__x) : _S_right(__x);
1863 }
1864 return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1865 }
1866
1867 template<typename _Key, typename _Val, typename _KoV,
1868 typename _Compare, typename _Alloc>
1869 template<typename _NodeGen>
1870 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1871 _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1872 _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
1873 {
1874 // Structural copy. __x and __p must be non-null.
1875 _Link_type __top = _M_clone_node(__x, __node_gen);
1876 __top->_M_parent = __p;
1877
1878 __try
1879 {
1880 if (__x->_M_right)
1881 __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1882 __p = __top;
1883 __x = _S_left(__x);
1884
1885 while (__x != 0)
1886 {
1887 _Link_type __y = _M_clone_node(__x, __node_gen);
1888 __p->_M_left = __y;
1889 __y->_M_parent = __p;
1890 if (__x->_M_right)
1891 __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1892 __p = __y;
1893 __x = _S_left(__x);
1894 }
1895 }
1896 __catch(...)
1897 {
1898 _M_erase(__top);
1899 __throw_exception_again;
1900 }
1901 return __top;
1902 }
1903
1904 template<typename _Key, typename _Val, typename _KeyOfValue,
1905 typename _Compare, typename _Alloc>
1906 void
1907 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1908 _M_erase(_Link_type __x)
1909 {
1910 // Erase without rebalancing.
1911 while (__x != 0)
1912 {
1913 _M_erase(_S_right(__x));
1914 _Link_type __y = _S_left(__x);
1915 _M_drop_node(__x);
1916 __x = __y;
1917 }
1918 }
1919
1920 template<typename _Key, typename _Val, typename _KeyOfValue,
1921 typename _Compare, typename _Alloc>
1922 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1923 _Compare, _Alloc>::iterator
1924 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1925 _M_lower_bound(_Link_type __x, _Base_ptr __y,
1926 const _Key& __k)
1927 {
1928 while (__x != 0)
1929 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1930 __y = __x, __x = _S_left(__x);
1931 else
1932 __x = _S_right(__x);
1933 return iterator(__y);
1934 }
1935
1936 template<typename _Key, typename _Val, typename _KeyOfValue,
1937 typename _Compare, typename _Alloc>
1938 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1939 _Compare, _Alloc>::const_iterator
1940 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1941 _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1942 const _Key& __k) const
1943 {
1944 while (__x != 0)
1945 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1946 __y = __x, __x = _S_left(__x);
1947 else
1948 __x = _S_right(__x);
1949 return const_iterator(__y);
1950 }
1951
1952 template<typename _Key, typename _Val, typename _KeyOfValue,
1953 typename _Compare, typename _Alloc>
1954 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1955 _Compare, _Alloc>::iterator
1956 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1957 _M_upper_bound(_Link_type __x, _Base_ptr __y,
1958 const _Key& __k)
1959 {
1960 while (__x != 0)
1961 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1962 __y = __x, __x = _S_left(__x);
1963 else
1964 __x = _S_right(__x);
1965 return iterator(__y);
1966 }
1967
1968 template<typename _Key, typename _Val, typename _KeyOfValue,
1969 typename _Compare, typename _Alloc>
1970 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1971 _Compare, _Alloc>::const_iterator
1972 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1973 _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
1974 const _Key& __k) const
1975 {
1976 while (__x != 0)
1977 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1978 __y = __x, __x = _S_left(__x);
1979 else
1980 __x = _S_right(__x);
1981 return const_iterator(__y);
1982 }
1983
1984 template<typename _Key, typename _Val, typename _KeyOfValue,
1985 typename _Compare, typename _Alloc>
1986 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1987 _Compare, _Alloc>::iterator,
1988 typename _Rb_tree<_Key, _Val, _KeyOfValue,
1989 _Compare, _Alloc>::iterator>
1990 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1991 equal_range(const _Key& __k)
1992 {
1993 _Link_type __x = _M_begin();
1994 _Base_ptr __y = _M_end();
1995 while (__x != 0)
1996 {
1997 if (_M_impl._M_key_compare(_S_key(__x), __k))
1998 __x = _S_right(__x);
1999 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2000 __y = __x, __x = _S_left(__x);
2001 else
2002 {
2003 _Link_type __xu(__x);
2004 _Base_ptr __yu(__y);
2005 __y = __x, __x = _S_left(__x);
2006 __xu = _S_right(__xu);
2007 return pair<iterator,
2008 iterator>(_M_lower_bound(__x, __y, __k),
2009 _M_upper_bound(__xu, __yu, __k));
2010 }
2011 }
2012 return pair<iterator, iterator>(iterator(__y),
2013 iterator(__y));
2014 }
2015
2016 template<typename _Key, typename _Val, typename _KeyOfValue,
2017 typename _Compare, typename _Alloc>
2018 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2019 _Compare, _Alloc>::const_iterator,
2020 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2021 _Compare, _Alloc>::const_iterator>
2022 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2023 equal_range(const _Key& __k) const
2024 {
2025 _Const_Link_type __x = _M_begin();
2026 _Const_Base_ptr __y = _M_end();
2027 while (__x != 0)
2028 {
2029 if (_M_impl._M_key_compare(_S_key(__x), __k))
2030 __x = _S_right(__x);
2031 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2032 __y = __x, __x = _S_left(__x);
2033 else
2034 {
2035 _Const_Link_type __xu(__x);
2036 _Const_Base_ptr __yu(__y);
2037 __y = __x, __x = _S_left(__x);
2038 __xu = _S_right(__xu);
2039 return pair<const_iterator,
2040 const_iterator>(_M_lower_bound(__x, __y, __k),
2041 _M_upper_bound(__xu, __yu, __k));
2042 }
2043 }
2044 return pair<const_iterator, const_iterator>(const_iterator(__y),
2045 const_iterator(__y));
2046 }
2047
2048 template<typename _Key, typename _Val, typename _KeyOfValue,
2049 typename _Compare, typename _Alloc>
2050 void
2051 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2052 swap(_Rb_tree& __t)
2053 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
2054 {
2055 if (_M_root() == 0)
2056 {
2057 if (__t._M_root() != 0)
2058 _M_impl._M_move_data(__t._M_impl);
2059 }
2060 else if (__t._M_root() == 0)
2061 __t._M_impl._M_move_data(_M_impl);
2062 else
2063 {
2064 std::swap(_M_root(),__t._M_root());
2065 std::swap(_M_leftmost(),__t._M_leftmost());
2066 std::swap(_M_rightmost(),__t._M_rightmost());
2067
2068 _M_root()->_M_parent = _M_end();
2069 __t._M_root()->_M_parent = __t._M_end();
2070 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
2071 }
2072 // No need to swap header's color as it does not change.
2073 std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
2074
2075 _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2076 __t._M_get_Node_allocator());
2077 }
2078
2079 template<typename _Key, typename _Val, typename _KeyOfValue,
2080 typename _Compare, typename _Alloc>
2081 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2082 _Compare, _Alloc>::_Base_ptr,
2083 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2084 _Compare, _Alloc>::_Base_ptr>
2085 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2086 _M_get_insert_unique_pos(const key_type& __k)
2087 {
2088 typedef pair<_Base_ptr, _Base_ptr> _Res;
2089 _Link_type __x = _M_begin();
2090 _Base_ptr __y = _M_end();
2091 bool __comp = true;
2092 while (__x != 0)
2093 {
2094 __y = __x;
2095 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
2096 __x = __comp ? _S_left(__x) : _S_right(__x);
2097 }
2098 iterator __j = iterator(__y);
2099 if (__comp)
2100 {
2101 if (__j == begin())
2102 return _Res(__x, __y);
2103 else
2104 --__j;
2105 }
2106 if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
2107 return _Res(__x, __y);
2108 return _Res(__j._M_node, 0);
2109 }
2110
2111 template<typename _Key, typename _Val, typename _KeyOfValue,
2112 typename _Compare, typename _Alloc>
2113 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2114 _Compare, _Alloc>::_Base_ptr,
2115 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2116 _Compare, _Alloc>::_Base_ptr>
2117 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2118 _M_get_insert_equal_pos(const key_type& __k)
2119 {
2120 typedef pair<_Base_ptr, _Base_ptr> _Res;
2121 _Link_type __x = _M_begin();
2122 _Base_ptr __y = _M_end();
2123 while (__x != 0)
2124 {
2125 __y = __x;
2126 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
2127 _S_left(__x) : _S_right(__x);
2128 }
2129 return _Res(__x, __y);
2130 }
2131
2132 template<typename _Key, typename _Val, typename _KeyOfValue,
2133 typename _Compare, typename _Alloc>
2134#if __cplusplus >= 201103L
2135 template<typename _Arg>
2136#endif
2137 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2138 _Compare, _Alloc>::iterator, bool>
2139 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2140#if __cplusplus >= 201103L
2141 _M_insert_unique(_Arg&& __v)
2142#else
2143 _M_insert_unique(const _Val& __v)
2144#endif
2145 {
2146 typedef pair<iterator, bool> _Res;
2147 pair<_Base_ptr, _Base_ptr> __res
2148 = _M_get_insert_unique_pos(_KeyOfValue()(__v));
2149
2150 if (__res.second)
2151 {
2152 _Alloc_node __an(*this);
2153 return _Res(_M_insert_(__res.first, __res.second,
2154 _GLIBCXX_FORWARD(_Arg, __v), __an),
2155 true);
2156 }
2157
2158 return _Res(iterator(__res.first), false);
2159 }
2160
2161 template<typename _Key, typename _Val, typename _KeyOfValue,
2162 typename _Compare, typename _Alloc>
2163#if __cplusplus >= 201103L
2164 template<typename _Arg>
2165#endif
2166 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2167 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2168#if __cplusplus >= 201103L
2169 _M_insert_equal(_Arg&& __v)
2170#else
2171 _M_insert_equal(const _Val& __v)
2172#endif
2173 {
2174 pair<_Base_ptr, _Base_ptr> __res
2175 = _M_get_insert_equal_pos(_KeyOfValue()(__v));
2176 _Alloc_node __an(*this);
2177 return _M_insert_(__res.first, __res.second,
2178 _GLIBCXX_FORWARD(_Arg, __v), __an);
2179 }
2180
2181 template<typename _Key, typename _Val, typename _KeyOfValue,
2182 typename _Compare, typename _Alloc>
2183 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2184 _Compare, _Alloc>::_Base_ptr,
2185 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2186 _Compare, _Alloc>::_Base_ptr>
2187 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2188 _M_get_insert_hint_unique_pos(const_iterator __position,
2189 const key_type& __k)
2190 {
2191 iterator __pos = __position._M_const_cast();
2192 typedef pair<_Base_ptr, _Base_ptr> _Res;
2193
2194 // end()
2195 if (__pos._M_node == _M_end())
2196 {
2197 if (size() > 0
2198 && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
2199 return _Res(0, _M_rightmost());
2200 else
2201 return _M_get_insert_unique_pos(__k);
2202 }
2203 else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
2204 {
2205 // First, try before...
2206 iterator __before = __pos;
2207 if (__pos._M_node == _M_leftmost()) // begin()
2208 return _Res(_M_leftmost(), _M_leftmost());
2209 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
2210 {
2211 if (_S_right(__before._M_node) == 0)
2212 return _Res(0, __before._M_node);
2213 else
2214 return _Res(__pos._M_node, __pos._M_node);
2215 }
2216 else
2217 return _M_get_insert_unique_pos(__k);
2218 }
2219 else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2220 {
2221 // ... then try after.
2222 iterator __after = __pos;
2223 if (__pos._M_node == _M_rightmost())
2224 return _Res(0, _M_rightmost());
2225 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
2226 {
2227 if (_S_right(__pos._M_node) == 0)
2228 return _Res(0, __pos._M_node);
2229 else
2230 return _Res(__after._M_node, __after._M_node);
2231 }
2232 else
2233 return _M_get_insert_unique_pos(__k);
2234 }
2235 else
2236 // Equivalent keys.
2237 return _Res(__pos._M_node, 0);
2238 }
2239
2240 template<typename _Key, typename _Val, typename _KeyOfValue,
2241 typename _Compare, typename _Alloc>
2242#if __cplusplus >= 201103L
2243 template<typename _Arg, typename _NodeGen>
2244#else
2245 template<typename _NodeGen>
2246#endif
2247 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2248 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2249 _M_insert_unique_(const_iterator __position,
2250#if __cplusplus >= 201103L
2251 _Arg&& __v,
2252#else
2253 const _Val& __v,
2254#endif
2255 _NodeGen& __node_gen)
2256 {
2257 pair<_Base_ptr, _Base_ptr> __res
2258 = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
2259
2260 if (__res.second)
2261 return _M_insert_(__res.first, __res.second,
2262 _GLIBCXX_FORWARD(_Arg, __v),
2263 __node_gen);
2264 return iterator(__res.first);
2265 }
2266
2267 template<typename _Key, typename _Val, typename _KeyOfValue,
2268 typename _Compare, typename _Alloc>
2269 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2270 _Compare, _Alloc>::_Base_ptr,
2271 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2272 _Compare, _Alloc>::_Base_ptr>
2273 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2274 _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
2275 {
2276 iterator __pos = __position._M_const_cast();
2277 typedef pair<_Base_ptr, _Base_ptr> _Res;
2278
2279 // end()
2280 if (__pos._M_node == _M_end())
2281 {
2282 if (size() > 0
2283 && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2284 return _Res(0, _M_rightmost());
2285 else
2286 return _M_get_insert_equal_pos(__k);
2287 }
2288 else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2289 {
2290 // First, try before...
2291 iterator __before = __pos;
2292 if (__pos._M_node == _M_leftmost()) // begin()
2293 return _Res(_M_leftmost(), _M_leftmost());
2294 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2295 {
2296 if (_S_right(__before._M_node) == 0)
2297 return _Res(0, __before._M_node);
2298 else
2299 return _Res(__pos._M_node, __pos._M_node);
2300 }
2301 else
2302 return _M_get_insert_equal_pos(__k);
2303 }
2304 else
2305 {
2306 // ... then try after.
2307 iterator __after = __pos;
2308 if (__pos._M_node == _M_rightmost())
2309 return _Res(0, _M_rightmost());
2310 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2311 {
2312 if (_S_right(__pos._M_node) == 0)
2313 return _Res(0, __pos._M_node);
2314 else
2315 return _Res(__after._M_node, __after._M_node);
2316 }
2317 else
2318 return _Res(0, 0);
2319 }
2320 }
2321
2322 template<typename _Key, typename _Val, typename _KeyOfValue,
2323 typename _Compare, typename _Alloc>
2324#if __cplusplus >= 201103L
2325 template<typename _Arg, typename _NodeGen>
2326#else
2327 template<typename _NodeGen>
2328#endif
2329 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2330 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2331 _M_insert_equal_(const_iterator __position,
2332#if __cplusplus >= 201103L
2333 _Arg&& __v,
2334#else
2335 const _Val& __v,
2336#endif
2337 _NodeGen& __node_gen)
2338 {
2339 pair<_Base_ptr, _Base_ptr> __res
2340 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2341
2342 if (__res.second)
2343 return _M_insert_(__res.first, __res.second,
2344 _GLIBCXX_FORWARD(_Arg, __v),
2345 __node_gen);
2346
2347 return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2348 }
2349
2350#if __cplusplus >= 201103L
2351 template<typename _Key, typename _Val, typename _KeyOfValue,
2352 typename _Compare, typename _Alloc>
2353 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2354 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2355 _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2356 {
2357 bool __insert_left = (__x != 0 || __p == _M_end()
2358 || _M_impl._M_key_compare(_S_key(__z),
2359 _S_key(__p)));
2360
2361 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2362 this->_M_impl._M_header);
2363 ++_M_impl._M_node_count;
2364 return iterator(__z);
2365 }
2366
2367 template<typename _Key, typename _Val, typename _KeyOfValue,
2368 typename _Compare, typename _Alloc>
2369 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2370 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2371 _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2372 {
2373 bool __insert_left = (__p == _M_end()
2374 || !_M_impl._M_key_compare(_S_key(__p),
2375 _S_key(__z)));
2376
2377 _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2378 this->_M_impl._M_header);
2379 ++_M_impl._M_node_count;
2380 return iterator(__z);
2381 }
2382
2383 template<typename _Key, typename _Val, typename _KeyOfValue,
2384 typename _Compare, typename _Alloc>
2385 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2386 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2387 _M_insert_equal_lower_node(_Link_type __z)
2388 {
2389 _Link_type __x = _M_begin();
2390 _Base_ptr __y = _M_end();
2391 while (__x != 0)
2392 {
2393 __y = __x;
2394 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2395 _S_left(__x) : _S_right(__x);
2396 }
2397 return _M_insert_lower_node(__y, __z);
2398 }
2399
2400 template<typename _Key, typename _Val, typename _KeyOfValue,
2401 typename _Compare, typename _Alloc>
2402 template<typename... _Args>
2403 pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2404 _Compare, _Alloc>::iterator, bool>
2405 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2406 _M_emplace_unique(_Args&&... __args)
2407 {
2408 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2409
2410 __try
2411 {
2412 typedef pair<iterator, bool> _Res;
2413 auto __res = _M_get_insert_unique_pos(_S_key(__z));
2414 if (__res.second)
2415 return _Res(_M_insert_node(__res.first, __res.second, __z), true);
2416
2417 _M_drop_node(__z);
2418 return _Res(iterator(__res.first), false);
2419 }
2420 __catch(...)
2421 {
2422 _M_drop_node(__z);
2423 __throw_exception_again;
2424 }
2425 }
2426
2427 template<typename _Key, typename _Val, typename _KeyOfValue,
2428 typename _Compare, typename _Alloc>
2429 template<typename... _Args>
2430 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2431 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2432 _M_emplace_equal(_Args&&... __args)
2433 {
2434 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2435
2436 __try
2437 {
2438 auto __res = _M_get_insert_equal_pos(_S_key(__z));
2439 return _M_insert_node(__res.first, __res.second, __z);
2440 }
2441 __catch(...)
2442 {
2443 _M_drop_node(__z);
2444 __throw_exception_again;
2445 }
2446 }
2447
2448 template<typename _Key, typename _Val, typename _KeyOfValue,
2449 typename _Compare, typename _Alloc>
2450 template<typename... _Args>
2451 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2452 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2453 _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2454 {
2455 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2456
2457 __try
2458 {
2459 auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2460
2461 if (__res.second)
2462 return _M_insert_node(__res.first, __res.second, __z);
2463
2464 _M_drop_node(__z);
2465 return iterator(__res.first);
2466 }
2467 __catch(...)
2468 {
2469 _M_drop_node(__z);
2470 __throw_exception_again;
2471 }
2472 }
2473
2474 template<typename _Key, typename _Val, typename _KeyOfValue,
2475 typename _Compare, typename _Alloc>
2476 template<typename... _Args>
2477 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2478 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2479 _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2480 {
2481 _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2482
2483 __try
2484 {
2485 auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2486
2487 if (__res.second)
2488 return _M_insert_node(__res.first, __res.second, __z);
2489
2490 return _M_insert_equal_lower_node(__z);
2491 }
2492 __catch(...)
2493 {
2494 _M_drop_node(__z);
2495 __throw_exception_again;
2496 }
2497 }
2498#endif
2499
2500
2501 template<typename _Key, typename _Val, typename _KeyOfValue,
2502 typename _Compare, typename _Alloc>
2503 void
2504 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2505 _M_erase_aux(const_iterator __position)
2506 {
2507 _Link_type __y =
2508 static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
2509 (const_cast<_Base_ptr>(__position._M_node),
2510 this->_M_impl._M_header));
2511 _M_drop_node(__y);
2512 --_M_impl._M_node_count;
2513 }
2514
2515 template<typename _Key, typename _Val, typename _KeyOfValue,
2516 typename _Compare, typename _Alloc>
2517 void
2518 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2519 _M_erase_aux(const_iterator __first, const_iterator __last)
2520 {
2521 if (__first == begin() && __last == end())
2522 clear();
2523 else
2524 while (__first != __last)
2525 _M_erase_aux(__first++);
2526 }
2527
2528 template<typename _Key, typename _Val, typename _KeyOfValue,
2529 typename _Compare, typename _Alloc>
2530 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2531 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2532 erase(const _Key& __x)
2533 {
2534 pair<iterator, iterator> __p = equal_range(__x);
2535 const size_type __old_size = size();
2536 _M_erase_aux(__p.first, __p.second);
2537 return __old_size - size();
2538 }
2539
2540 template<typename _Key, typename _Val, typename _KeyOfValue,
2541 typename _Compare, typename _Alloc>
2542 void
2543 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2544 erase(const _Key* __first, const _Key* __last)
2545 {
2546 while (__first != __last)
2547 erase(*__first++);
2548 }
2549
2550 template<typename _Key, typename _Val, typename _KeyOfValue,
2551 typename _Compare, typename _Alloc>
2552 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2553 _Compare, _Alloc>::iterator
2554 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2555 find(const _Key& __k)
2556 {
2557 iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2558 return (__j == end()
2559 || _M_impl._M_key_compare(__k,
2560 _S_key(__j._M_node))) ? end() : __j;
2561 }
2562
2563 template<typename _Key, typename _Val, typename _KeyOfValue,
2564 typename _Compare, typename _Alloc>
2565 typename _Rb_tree<_Key, _Val, _KeyOfValue,
2566 _Compare, _Alloc>::const_iterator
2567 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2568 find(const _Key& __k) const
2569 {
2570 const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2571 return (__j == end()
2572 || _M_impl._M_key_compare(__k,
2573 _S_key(__j._M_node))) ? end() : __j;
2574 }
2575
2576 template<typename _Key, typename _Val, typename _KeyOfValue,
2577 typename _Compare, typename _Alloc>
2578 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2579 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2580 count(const _Key& __k) const
2581 {
2582 pair<const_iterator, const_iterator> __p = equal_range(__k);
2583 const size_type __n = std::distance(__p.first, __p.second);
2584 return __n;
2585 }
2586
2587 _GLIBCXX_PURE unsigned int
2588 _Rb_tree_black_count(const _Rb_tree_node_base* __node,
2589 const _Rb_tree_node_base* __root) throw ();
2590
2591 template<typename _Key, typename _Val, typename _KeyOfValue,
2592 typename _Compare, typename _Alloc>
2593 bool
2594 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
2595 {
2596 if (_M_impl._M_node_count == 0 || begin() == end())
2597 return _M_impl._M_node_count == 0 && begin() == end()
2598 && this->_M_impl._M_header._M_left == _M_end()
2599 && this->_M_impl._M_header._M_right == _M_end();
2600
2601 unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2602 for (const_iterator __it = begin(); __it != end(); ++__it)
2603 {
2604 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
2605 _Const_Link_type __L = _S_left(__x);
2606 _Const_Link_type __R = _S_right(__x);
2607
2608 if (__x->_M_color == _S_red)
2609 if ((__L && __L->_M_color == _S_red)
2610 || (__R && __R->_M_color == _S_red))
2611 return false;
2612
2613 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2614 return false;
2615 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2616 return false;
2617
2618 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2619 return false;
2620 }
2621
2622 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2623 return false;
2624 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2625 return false;
2626 return true;
2627 }
2628
2629#if __cplusplus > 201402L
2630 // Allow access to internals of compatible _Rb_tree specializations.
2631 template<typename _Key, typename _Val, typename _Sel, typename _Cmp1,
2632 typename _Alloc, typename _Cmp2>
2633 struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
2634 _Cmp2>
2635 {
2636 private:
2637 friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;
2638
2639 static auto&
2640 _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
2641 { return __tree._M_impl; }
2642 };
2643#endif // C++17
2644
2645_GLIBCXX_END_NAMESPACE_VERSION
2646} // namespace
2647
2648#endif
2649