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