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