libstdc++
stl_tree.h
Go to the documentation of this file.
1 // RB tree implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2025 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 #ifdef _GLIBCXX_SYSHDR
62 #pragma GCC system_header
63 #endif
64 
65 #include <bits/stl_algobase.h>
66 #include <bits/allocator.h>
67 #include <bits/stl_function.h>
68 #include <bits/cpp_type_traits.h>
69 #include <bits/ptr_traits.h>
70 #include <ext/alloc_traits.h>
71 #if __cplusplus >= 201103L
72 # include <ext/aligned_buffer.h>
73 #endif
74 #ifdef __glibcxx_node_extract // >= C++17
75 # include <bits/node_handle.h>
76 #endif
77 
78 #if __cplusplus < 201103L
79 # undef _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
80 # define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 0
81 #elif ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
82 # define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 1
83 #endif
84 
85 namespace std _GLIBCXX_VISIBILITY(default)
86 {
87 _GLIBCXX_BEGIN_NAMESPACE_VERSION
88 
89  // Red-black tree class, designed for use in implementing STL
90  // associative containers (set, multiset, map, and multimap). The
91  // insertion and deletion algorithms are based on those in Cormen,
92  // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
93  // 1990), except that
94  //
95  // (1) the header cell is maintained with links not only to the root
96  // but also to the leftmost node of the tree, to enable constant
97  // time begin(), and to the rightmost node of the tree, to enable
98  // linear time performance when used with the generic set algorithms
99  // (set_union, etc.)
100  //
101  // (2) when a node being deleted has two children its successor node
102  // is relinked into its place, rather than copied, so that the only
103  // iterators invalidated are those referring to the deleted node.
104 
105  enum _Rb_tree_color { _S_red = false, _S_black = true };
106 
107  struct _Rb_tree_node_base
108  {
109  typedef _Rb_tree_node_base* _Base_ptr;
110 
111  _Rb_tree_color _M_color;
112  _Base_ptr _M_parent;
113  _Base_ptr _M_left;
114  _Base_ptr _M_right;
115 
116  static _Base_ptr
117  _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
118  {
119  while (__x->_M_left != 0) __x = __x->_M_left;
120  return __x;
121  }
122 
123  static _Base_ptr
124  _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
125  {
126  while (__x->_M_right != 0) __x = __x->_M_right;
127  return __x;
128  }
129 
130  // This is not const-correct, but it's only used in a const access path
131  // by std::_Rb_tree::_M_end() where the pointer is used to initialize a
132  // const_iterator and so constness is restored.
133  _Base_ptr
134  _M_base_ptr() const _GLIBCXX_NOEXCEPT
135  { return const_cast<_Rb_tree_node_base*>(this); }
136  };
137 
138  // Helper type offering value initialization guarantee on the compare functor.
139  template<typename _Key_compare>
140  struct _Rb_tree_key_compare
141  {
142  _Key_compare _M_key_compare;
143 
144  _Rb_tree_key_compare()
145  _GLIBCXX_NOEXCEPT_IF(
146  is_nothrow_default_constructible<_Key_compare>::value)
147  : _M_key_compare()
148  { }
149 
150  _Rb_tree_key_compare(const _Key_compare& __comp)
151  : _M_key_compare(__comp)
152  { }
153 
154 #if __cplusplus >= 201103L
155  // Copy constructor added for consistency with C++98 mode.
156  _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default;
157 
158  _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
159  noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
160  : _M_key_compare(__x._M_key_compare)
161  { }
162 #endif
163  };
164 
165  // Helper type to manage default initialization of node count and header.
166  struct _Rb_tree_header
167  {
168  _Rb_tree_node_base _M_header;
169  size_t _M_node_count; // Keeps track of size of tree.
170 
171  _Rb_tree_header() _GLIBCXX_NOEXCEPT
172  {
173  _M_header._M_color = _S_red;
174  _M_reset();
175  }
176 
177 #if __cplusplus >= 201103L
178  _Rb_tree_header(_Rb_tree_header&& __x) noexcept
179  {
180  if (__x._M_header._M_parent != nullptr)
181  _M_move_data(__x);
182  else
183  {
184  _M_header._M_color = _S_red;
185  _M_reset();
186  }
187  }
188 #endif
189 
190  void
191  _M_move_data(_Rb_tree_header& __from)
192  {
193  _M_header._M_color = __from._M_header._M_color;
194  _M_header._M_parent = __from._M_header._M_parent;
195  _M_header._M_left = __from._M_header._M_left;
196  _M_header._M_right = __from._M_header._M_right;
197  _M_header._M_parent->_M_parent = &_M_header;
198  _M_node_count = __from._M_node_count;
199 
200  __from._M_reset();
201  }
202 
203  void
204  _M_reset()
205  {
206  _M_header._M_parent = 0;
207  _M_header._M_left = &_M_header;
208  _M_header._M_right = &_M_header;
209  _M_node_count = 0;
210  }
211  };
212 
213  template<typename _Val>
214  struct _Rb_tree_node : public _Rb_tree_node_base
215  {
216 #if __cplusplus < 201103L
217  _Val _M_value_field;
218 
219  _Val*
220  _M_valptr()
221  { return std::__addressof(_M_value_field); }
222 
223  const _Val*
224  _M_valptr() const
225  { return std::__addressof(_M_value_field); }
226 #else
227  __gnu_cxx::__aligned_membuf<_Val> _M_storage;
228 
229  _Val*
230  _M_valptr()
231  { return _M_storage._M_ptr(); }
232 
233  const _Val*
234  _M_valptr() const
235  { return _M_storage._M_ptr(); }
236 #endif
237 
238  _Rb_tree_node*
239  _M_node_ptr() _GLIBCXX_NOEXCEPT
240  { return this; }
241  };
242 
243 #if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
244 namespace __rb_tree
245 {
246  template<typename _VoidPtr>
247  struct _Node_base
248  {
249  using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>;
250 
251  _Rb_tree_color _M_color;
252  _Base_ptr _M_parent;
253  _Base_ptr _M_left;
254  _Base_ptr _M_right;
255 
256  static _Base_ptr
257  _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
258  {
259  while (__x->_M_left) __x = __x->_M_left;
260  return __x;
261  }
262 
263  static _Base_ptr
264  _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
265  {
266  while (__x->_M_right) __x = __x->_M_right;
267  return __x;
268  }
269 
270  // This is not const-correct, but it's only used in a const access path
271  // by std::_Rb_tree::_M_end() where the pointer is used to initialize a
272  // const_iterator and so constness is restored.
273  _Base_ptr
274  _M_base_ptr() const noexcept
275  {
276  return pointer_traits<_Base_ptr>::pointer_to
277  (*const_cast<_Node_base*>(this));
278  }
279  };
280 
281  // Helper type to manage default initialization of node count and header.
282  template<typename _NodeBase>
283  struct _Header
284  {
285  private:
286  using _Base_ptr = typename _NodeBase::_Base_ptr;
287 
288  public:
289  _NodeBase _M_header;
290  size_t _M_node_count; // Keeps track of size of tree.
291 
292  _Header() noexcept
293  {
294  _M_header._M_color = _S_red;
295  _M_reset();
296  }
297 
298  _Header(_Header&& __x) noexcept
299  {
300  if (__x._M_header._M_parent)
301  _M_move_data(__x);
302  else
303  {
304  _M_header._M_color = _S_red;
305  _M_reset();
306  }
307  }
308 
309  void
310  _M_move_data(_Header& __from)
311  {
312  _M_header._M_color = __from._M_header._M_color;
313  _M_header._M_parent = __from._M_header._M_parent;
314  _M_header._M_left = __from._M_header._M_left;
315  _M_header._M_right = __from._M_header._M_right;
316  _M_header._M_parent->_M_parent = _M_header._M_base_ptr();
317  _M_node_count = __from._M_node_count;
318 
319  __from._M_reset();
320  }
321 
322  void
323  _M_reset()
324  {
325  _M_header._M_parent = nullptr;
326  _M_header._M_left = _M_header._M_right = _M_header._M_base_ptr();
327  _M_node_count = 0;
328  }
329  };
330 
331  template<typename _ValPtr>
332  struct _Node : public __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>
333  {
334  using value_type = typename pointer_traits<_ValPtr>::element_type;
335  using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
336 
337  _Node() noexcept { }
338  ~_Node() { }
339  _Node(_Node&&) = delete;
340 
341  union _Uninit_storage
342  {
343  _Uninit_storage() noexcept { }
344  ~_Uninit_storage() { }
345 
346  value_type _M_data;
347  };
348  _Uninit_storage _M_u;
349 
350  value_type*
351  _M_valptr()
352  { return std::addressof(_M_u._M_data); }
353 
354  value_type const*
355  _M_valptr() const
356  { return std::addressof(_M_u._M_data); }
357 
358  _Node_ptr
359  _M_node_ptr() noexcept
360  { return pointer_traits<_Node_ptr>::pointer_to(*this); }
361  };
362 } // namespace __rb_tree
363 #endif // _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
364 
365  _GLIBCXX_PURE _Rb_tree_node_base*
366  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
367 
368  _GLIBCXX_PURE _Rb_tree_node_base*
369  _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
370 
371  template<typename _Tp>
372  struct _Rb_tree_iterator
373  {
374  typedef _Tp value_type;
375  typedef _Tp& reference;
376  typedef _Tp* pointer;
377 
378  typedef bidirectional_iterator_tag iterator_category;
379  typedef ptrdiff_t difference_type;
380 
381  typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
382  typedef _Rb_tree_node<_Tp>* _Node_ptr;
383 
384  _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
385  : _M_node() { }
386 
387  explicit
388  _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
389  : _M_node(__x) { }
390 
391  reference
392  operator*() const _GLIBCXX_NOEXCEPT
393  { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
394 
395  pointer
396  operator->() const _GLIBCXX_NOEXCEPT
397  { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
398 
399  _Rb_tree_iterator&
400  operator++() _GLIBCXX_NOEXCEPT
401  {
402  _M_node = _Rb_tree_increment(_M_node);
403  return *this;
404  }
405 
406  _Rb_tree_iterator
407  operator++(int) _GLIBCXX_NOEXCEPT
408  {
409  _Rb_tree_iterator __tmp = *this;
410  _M_node = _Rb_tree_increment(_M_node);
411  return __tmp;
412  }
413 
414  _Rb_tree_iterator&
415  operator--() _GLIBCXX_NOEXCEPT
416  {
417  _M_node = _Rb_tree_decrement(_M_node);
418  return *this;
419  }
420 
421  _Rb_tree_iterator
422  operator--(int) _GLIBCXX_NOEXCEPT
423  {
424  _Rb_tree_iterator __tmp = *this;
425  _M_node = _Rb_tree_decrement(_M_node);
426  return __tmp;
427  }
428 
429  friend bool
430  operator==(const _Rb_tree_iterator& __x,
431  const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT
432  { return __x._M_node == __y._M_node; }
433 
434 #if ! __cpp_lib_three_way_comparison
435  friend bool
436  operator!=(const _Rb_tree_iterator& __x,
437  const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT
438  { return __x._M_node != __y._M_node; }
439 #endif
440 
441  _Base_ptr _M_node;
442  };
443 
444  template<typename _Tp>
445  struct _Rb_tree_const_iterator
446  {
447  typedef _Tp value_type;
448  typedef const _Tp& reference;
449  typedef const _Tp* pointer;
450 
451  typedef _Rb_tree_iterator<_Tp> iterator;
452 
453  typedef bidirectional_iterator_tag iterator_category;
454  typedef ptrdiff_t difference_type;
455 
456  typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
457  typedef const _Rb_tree_node<_Tp>* _Node_ptr;
458 
459  _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
460  : _M_node() { }
461 
462  explicit
463  _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
464  : _M_node(__x) { }
465 
466  _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
467  : _M_node(__it._M_node) { }
468 
469  reference
470  operator*() const _GLIBCXX_NOEXCEPT
471  { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
472 
473  pointer
474  operator->() const _GLIBCXX_NOEXCEPT
475  { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); }
476 
477  _Rb_tree_const_iterator&
478  operator++() _GLIBCXX_NOEXCEPT
479  {
480  _M_node = _Rb_tree_increment(_M_node);
481  return *this;
482  }
483 
484  _Rb_tree_const_iterator
485  operator++(int) _GLIBCXX_NOEXCEPT
486  {
487  _Rb_tree_const_iterator __tmp = *this;
488  _M_node = _Rb_tree_increment(_M_node);
489  return __tmp;
490  }
491 
492  _Rb_tree_const_iterator&
493  operator--() _GLIBCXX_NOEXCEPT
494  {
495  _M_node = _Rb_tree_decrement(_M_node);
496  return *this;
497  }
498 
499  _Rb_tree_const_iterator
500  operator--(int) _GLIBCXX_NOEXCEPT
501  {
502  _Rb_tree_const_iterator __tmp = *this;
503  _M_node = _Rb_tree_decrement(_M_node);
504  return __tmp;
505  }
506 
507  friend bool
508  operator==(const _Rb_tree_const_iterator& __x,
509  const _Rb_tree_const_iterator& __y) _GLIBCXX_NOEXCEPT
510  { return __x._M_node == __y._M_node; }
511 
512 #if ! __cpp_lib_three_way_comparison
513  friend bool
514  operator!=(const _Rb_tree_const_iterator& __x,
515  const _Rb_tree_const_iterator& __y) _GLIBCXX_NOEXCEPT
516  { return __x._M_node != __y._M_node; }
517 #endif
518 
519  _Base_ptr _M_node;
520  };
521 
522  __attribute__((__nonnull__))
523  void
524  _Rb_tree_insert_and_rebalance(const bool __insert_left,
525  _Rb_tree_node_base* __x,
526  _Rb_tree_node_base* __p,
527  _Rb_tree_node_base& __header) throw ();
528 
529  __attribute__((__nonnull__,__returns_nonnull__))
530  _Rb_tree_node_base*
531  _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
532  _Rb_tree_node_base& __header) throw ();
533 
534 namespace __rb_tree
535 {
536 #if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
537  template<bool _Const, typename _ValPtr>
538  struct _Iterator
539  {
540  template<typename _Tp>
541  using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>;
542 
543  using __ptr_traits = pointer_traits<_ValPtr>;
544  using value_type = typename __ptr_traits::element_type;
545  using reference = __maybe_const<value_type>&;
546  using pointer = __maybe_const<value_type>*;
547 
548  using iterator_category = bidirectional_iterator_tag;
549  using difference_type = ptrdiff_t;
550 
551  using _Node = __rb_tree::_Node<_ValPtr>;
552  using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>;
553  using _Base_ptr = typename _Node_base::_Base_ptr;
554 
555  _Iterator() noexcept
556  : _M_node() { }
557 
558  constexpr explicit
559  _Iterator(_Base_ptr __x) noexcept
560  : _M_node(__x) { }
561 
562  _Iterator(const _Iterator&) = default;
563  _Iterator& operator=(const _Iterator&) = default;
564 
565 #ifdef __glibcxx_concepts
566  constexpr
567  _Iterator(const _Iterator<false, _ValPtr>& __it) requires _Const
568 #else
569  template<bool _OtherConst,
570  typename = __enable_if_t<_Const && !_OtherConst>>
571  constexpr
572  _Iterator(const _Iterator<_OtherConst, _ValPtr>& __it)
573 #endif
574  : _M_node(__it._M_node) { }
575 
576  [[__nodiscard__]]
577  reference
578  operator*() const noexcept
579  { return *static_cast<_Node&>(*_M_node)._M_valptr(); }
580 
581  [[__nodiscard__]]
582  pointer
583  operator->() const noexcept
584  { return static_cast<_Node&>(*_M_node)._M_valptr(); }
585 
586  _GLIBCXX14_CONSTEXPR _Iterator&
587  operator++() noexcept
588  {
589  if (_M_node->_M_right)
590  {
591  _M_node = _M_node->_M_right;
592  while (_M_node->_M_left)
593  _M_node = _M_node->_M_left;
594  }
595  else
596  {
597  _Base_ptr __y = _M_node->_M_parent;
598  while (_M_node == __y->_M_right)
599  {
600  _M_node = __y;
601  __y = __y->_M_parent;
602  }
603  if (_M_node->_M_right != __y)
604  _M_node = __y;
605  }
606 
607  return *this;
608  }
609 
610  _GLIBCXX14_CONSTEXPR _Iterator
611  operator++(int) noexcept
612  {
613  _Iterator __tmp(this->_M_node);
614  ++*this;
615  return __tmp;
616  }
617 
618  _GLIBCXX14_CONSTEXPR _Iterator&
619  operator--() noexcept
620  {
621  if (_M_node->_M_color == _S_red
622  && _M_node->_M_parent->_M_parent == _M_node)
623  _M_node = _M_node->_M_right;
624  else if (_M_node->_M_left)
625  {
626  _Base_ptr __y = _M_node->_M_left;
627  while (__y->_M_right)
628  __y = __y->_M_right;
629  _M_node = __y;
630  }
631  else
632  {
633  _Base_ptr __y = _M_node->_M_parent;
634  while (_M_node == __y->_M_left)
635  {
636  _M_node = __y;
637  __y = __y->_M_parent;
638  }
639  _M_node = __y;
640  }
641  return *this;
642  }
643 
644  _GLIBCXX14_CONSTEXPR _Iterator
645  operator--(int) noexcept
646  {
647  _Iterator __tmp(this->_M_node);
648  --*this;
649  return __tmp;
650  }
651 
652  [[__nodiscard__]]
653  friend bool
654  operator==(const _Iterator& __x, const _Iterator& __y) _GLIBCXX_NOEXCEPT
655  { return __x._M_node == __y._M_node; }
656 
657 #if ! __cpp_lib_three_way_comparison
658  [[__nodiscard__]]
659  friend bool
660  operator!=(const _Iterator& __x, const _Iterator& __y) _GLIBCXX_NOEXCEPT
661  { return __x._M_node != __y._M_node; }
662 #endif
663 
664  _Base_ptr _M_node;
665  };
666 #endif // USE_ALLOC_PTR_FOR_RB_TREE
667 
668  // Determine the node and iterator types used by std::_Rb_tree.
669  template<typename _Val, typename _Ptr>
670  struct _Node_traits;
671 
672 #if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE <= 9000
673  // Specialization for the simple case where the allocator's pointer type
674  // is the same type as value_type*.
675  // For ABI compatibility we can't change the types used for this case.
676  template<typename _Val>
677  struct _Node_traits<_Val, _Val*>
678  {
679  typedef _Rb_tree_node<_Val> _Node;
680  typedef _Node* _Node_ptr;
681  typedef _Rb_tree_node_base _Node_base;
682  typedef _Node_base* _Base_ptr;
683  typedef _Rb_tree_header _Header_t;
684  typedef _Rb_tree_iterator<_Val> _Iterator;
685  typedef _Rb_tree_const_iterator<_Val> _Const_iterator;
686 
687  __attribute__((__nonnull__))
688  static void
689  _S_insert_and_rebalance(const bool __insert_left,
690  _Node_base* __x, _Node_base* __p,
691  _Node_base& __header) _GLIBCXX_USE_NOEXCEPT
692  {
693  return _Rb_tree_insert_and_rebalance(__insert_left, __x, __p, __header);
694  }
695 
696  __attribute__((__nonnull__,__returns_nonnull__))
697  static _Node_base*
698  _S_rebalance_for_erase(_Node_base* const __z,
699  _Node_base& __header) _GLIBCXX_USE_NOEXCEPT
700  { return _Rb_tree_rebalance_for_erase(__z, __header); }
701  };
702 #endif
703 
704 #if ! _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
705  // Always use the T* specialization.
706  template<typename _Val, typename _Ptr>
707  struct _Node_traits
708  : _Node_traits<_Val, _Val*>
709  { };
710 #else
711  // Primary template used when the allocator uses fancy pointers.
712  template<typename _Val, typename _ValPtr>
713  struct _Node_traits
714  {
715  using _Node = __rb_tree::_Node<_ValPtr>;
716  using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
717  using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>;
718  using _Base_ptr = __ptr_rebind<_ValPtr, _Node_base>;
719  using _Header_t = __rb_tree::_Header<_Node_base>;
720  using _Iterator = __rb_tree::_Iterator<false, _ValPtr>;
721  using _Const_iterator = __rb_tree::_Iterator<true, _ValPtr>;
722 
723  static void
724  _Rotate_left(_Base_ptr __x, _Base_ptr& __root)
725  {
726  const _Base_ptr __y = __x->_M_right;
727 
728  __x->_M_right = __y->_M_left;
729  if (__y->_M_left)
730  __y->_M_left->_M_parent = __x;
731  __y->_M_parent = __x->_M_parent;
732 
733  if (__x == __root)
734  __root = __y;
735  else if (__x == __x->_M_parent->_M_left)
736  __x->_M_parent->_M_left = __y;
737  else
738  __x->_M_parent->_M_right = __y;
739  __y->_M_left = __x;
740  __x->_M_parent = __y;
741  }
742 
743  static void
744  _Rotate_right(_Base_ptr __x, _Base_ptr& __root)
745  {
746  const _Base_ptr __y = __x->_M_left;
747 
748  __x->_M_left = __y->_M_right;
749  if (__y->_M_right)
750  __y->_M_right->_M_parent = __x;
751  __y->_M_parent = __x->_M_parent;
752 
753  if (__x == __root)
754  __root = __y;
755  else if (__x == __x->_M_parent->_M_right)
756  __x->_M_parent->_M_right = __y;
757  else
758  __x->_M_parent->_M_left = __y;
759  __y->_M_right = __x;
760  __x->_M_parent = __y;
761  }
762 
763  static void
764  _S_insert_and_rebalance(const bool __insert_left,
765  _Base_ptr __x, _Base_ptr __p,
766  _Node_base& __header)
767  {
768  _Base_ptr& __root = __header._M_parent;
769 
770  // Initialize fields in new node to insert.
771  __x->_M_parent = __p;
772  __x->_M_left = __x->_M_right = nullptr;
773  __x->_M_color = _S_red;
774 
775  // Insert.
776  // Make new node child of parent and maintain root, leftmost and
777  // rightmost nodes.
778  // N.B. First node is always inserted left.
779  if (__insert_left)
780  {
781  __p->_M_left = __x; // also makes leftmost = __x when __p == &__header
782 
783  if (std::__to_address(__p) == std::addressof(__header))
784  {
785  __header._M_parent = __x;
786  __header._M_right = __x;
787  }
788  else if (__p == __header._M_left)
789  __header._M_left = __x; // maintain leftmost pointing to min node
790  }
791  else
792  {
793  __p->_M_right = __x;
794 
795  if (__p == __header._M_right)
796  __header._M_right = __x; // maintain rightmost pointing to max node
797  }
798  // Rebalance.
799  while (__x != __root
800  && __x->_M_parent->_M_color == _S_red)
801  {
802  const _Base_ptr __xpp = __x->_M_parent->_M_parent;
803 
804  if (__x->_M_parent == __xpp->_M_left)
805  {
806  const _Base_ptr __y = __xpp->_M_right;
807  if (__y && __y->_M_color == _S_red)
808  {
809  __x->_M_parent->_M_color = _S_black;
810  __y->_M_color = _S_black;
811  __xpp->_M_color = _S_red;
812  __x = __xpp;
813  }
814  else
815  {
816  if (__x == __x->_M_parent->_M_right)
817  {
818  __x = __x->_M_parent;
819  _Rotate_left(__x, __root);
820  }
821  __x->_M_parent->_M_color = _S_black;
822  __xpp->_M_color = _S_red;
823  _Rotate_right(__xpp, __root);
824  }
825  }
826  else
827  {
828  const _Base_ptr __y = __xpp->_M_left;
829  if (__y && __y->_M_color == _S_red)
830  {
831  __x->_M_parent->_M_color = _S_black;
832  __y->_M_color = _S_black;
833  __xpp->_M_color = _S_red;
834  __x = __xpp;
835  }
836  else
837  {
838  if (__x == __x->_M_parent->_M_left)
839  {
840  __x = __x->_M_parent;
841  _Rotate_right(__x, __root);
842  }
843  __x->_M_parent->_M_color = _S_black;
844  __xpp->_M_color = _S_red;
845  _Rotate_left(__xpp, __root);
846  }
847  }
848  }
849  __root->_M_color = _S_black;
850  }
851 
852  static _Base_ptr
853  _S_rebalance_for_erase(_Base_ptr __z, _Node_base& __header)
854  {
855  _Base_ptr& __root = __header._M_parent;
856  _Base_ptr& __leftmost = __header._M_left;
857  _Base_ptr& __rightmost = __header._M_right;
858  _Base_ptr __y = __z;
859  _Base_ptr __x{};
860  _Base_ptr __x_parent{};
861 
862  if (!__y->_M_left) // __z has at most one non-null child. y == z.
863  __x = __y->_M_right; // __x might be null.
864  else
865  if (!__y->_M_right) // __z has exactly one non-null child. y == z.
866  __x = __y->_M_left; // __x is not null.
867  else
868  {
869  // __z has two non-null children. Set __y to
870  __y = __y->_M_right; // __z's successor. __x might be null.
871  while (__y->_M_left)
872  __y = __y->_M_left;
873  __x = __y->_M_right;
874  }
875  if (__y != __z)
876  {
877  // relink y in place of z. y is z's successor
878  __z->_M_left->_M_parent = __y;
879  __y->_M_left = __z->_M_left;
880  if (__y != __z->_M_right)
881  {
882  __x_parent = __y->_M_parent;
883  if (__x)
884  __x->_M_parent = __y->_M_parent;
885  __y->_M_parent->_M_left = __x; // __y must be a child of _M_left
886  __y->_M_right = __z->_M_right;
887  __z->_M_right->_M_parent = __y;
888  }
889  else
890  __x_parent = __y;
891  if (__root == __z)
892  __root = __y;
893  else if (__z->_M_parent->_M_left == __z)
894  __z->_M_parent->_M_left = __y;
895  else
896  __z->_M_parent->_M_right = __y;
897  __y->_M_parent = __z->_M_parent;
898  std::swap(__y->_M_color, __z->_M_color);
899  __y = __z;
900  // __y now points to node to be actually deleted
901  }
902  else
903  { // __y == __z
904  __x_parent = __y->_M_parent;
905  if (__x)
906  __x->_M_parent = __y->_M_parent;
907  if (__root == __z)
908  __root = __x;
909  else
910  if (__z->_M_parent->_M_left == __z)
911  __z->_M_parent->_M_left = __x;
912  else
913  __z->_M_parent->_M_right = __x;
914  if (__leftmost == __z)
915  {
916  if (!__z->_M_right) // __z->_M_left must be null also
917  __leftmost = __z->_M_parent;
918  // makes __leftmost == _M_header if __z == __root
919  else
920  __leftmost = _Node_base::_S_minimum(__x);
921  }
922  if (__rightmost == __z)
923  {
924  if (__z->_M_left == 0) // __z->_M_right must be null also
925  __rightmost = __z->_M_parent;
926  // makes __rightmost == _M_header if __z == __root
927  else // __x == __z->_M_left
928  __rightmost = _Node_base::_S_maximum(__x);
929  }
930  }
931  if (__y->_M_color != _S_red)
932  {
933  while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
934  if (__x == __x_parent->_M_left)
935  {
936  _Base_ptr __w = __x_parent->_M_right;
937  if (__w->_M_color == _S_red)
938  {
939  __w->_M_color = _S_black;
940  __x_parent->_M_color = _S_red;
941  _Rotate_left(__x_parent, __root);
942  __w = __x_parent->_M_right;
943  }
944  if ((!__w->_M_left || __w->_M_left->_M_color == _S_black) &&
945  (!__w->_M_right || __w->_M_right->_M_color == _S_black))
946  {
947  __w->_M_color = _S_red;
948  __x = __x_parent;
949  __x_parent = __x_parent->_M_parent;
950  }
951  else
952  {
953  if (!__w->_M_right || __w->_M_right->_M_color == _S_black)
954  {
955  __w->_M_left->_M_color = _S_black;
956  __w->_M_color = _S_red;
957  _Rotate_right(__w, __root);
958  __w = __x_parent->_M_right;
959  }
960  __w->_M_color = __x_parent->_M_color;
961  __x_parent->_M_color = _S_black;
962  if (__w->_M_right)
963  __w->_M_right->_M_color = _S_black;
964  _Rotate_left(__x_parent, __root);
965  break;
966  }
967  }
968  else
969  {
970  // same as above, with _M_right <-> _M_left.
971  _Base_ptr __w = __x_parent->_M_left;
972  if (__w->_M_color == _S_red)
973  {
974  __w->_M_color = _S_black;
975  __x_parent->_M_color = _S_red;
976  _Rotate_right(__x_parent, __root);
977  __w = __x_parent->_M_left;
978  }
979  if ((!__w->_M_right || __w->_M_right->_M_color == _S_black) &&
980  (!__w->_M_left || __w->_M_left->_M_color == _S_black))
981  {
982  __w->_M_color = _S_red;
983  __x = __x_parent;
984  __x_parent = __x_parent->_M_parent;
985  }
986  else
987  {
988  if (!__w->_M_left || __w->_M_left->_M_color == _S_black)
989  {
990  __w->_M_right->_M_color = _S_black;
991  __w->_M_color = _S_red;
992  _Rotate_left(__w, __root);
993  __w = __x_parent->_M_left;
994  }
995  __w->_M_color = __x_parent->_M_color;
996  __x_parent->_M_color = _S_black;
997  if (__w->_M_left)
998  __w->_M_left->_M_color = _S_black;
999  _Rotate_right(__x_parent, __root);
1000  break;
1001  }
1002  }
1003  if (__x)
1004  __x->_M_color = _S_black;
1005  }
1006 
1007  return __y;
1008  }
1009  };
1010 #endif
1011 } // namespace __rb_tree
1012 
1013 #ifdef __glibcxx_node_extract // >= C++17
1014  template<typename _Tree1, typename _Cmp2>
1015  struct _Rb_tree_merge_helper { };
1016 #endif
1017 
1018  template<typename _Key, typename _Val, typename _KeyOfValue,
1019  typename _Compare, typename _Alloc = allocator<_Val> >
1020  class _Rb_tree
1021  {
1023  rebind<_Val>::other _Val_alloc_type;
1024 
1025  typedef __gnu_cxx::__alloc_traits<_Val_alloc_type> _Val_alloc_traits;
1026  typedef typename _Val_alloc_traits::pointer _ValPtr;
1027  typedef __rb_tree::_Node_traits<_Val, _ValPtr> _Node_traits;
1028 
1029  typedef typename _Node_traits::_Node_base _Node_base;
1030  typedef typename _Node_traits::_Node _Node;
1031 
1033  rebind<_Node>::other _Node_allocator;
1034 
1035  typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Node_alloc_traits;
1036 
1037  protected:
1038  typedef typename _Node_traits::_Base_ptr _Base_ptr;
1039  typedef typename _Node_traits::_Node_ptr _Node_ptr;
1040 
1041  private:
1042  // Functor recycling a pool of nodes and using allocation once the pool
1043  // is empty.
1044  struct _Reuse_or_alloc_node
1045  {
1046  _Reuse_or_alloc_node(_Rb_tree& __t)
1047  : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
1048  {
1049  if (_M_root)
1050  {
1051  _M_root->_M_parent = _Base_ptr();
1052 
1053  if (_M_nodes->_M_left)
1054  _M_nodes = _M_nodes->_M_left;
1055  }
1056  else
1057  _M_nodes = _Base_ptr();
1058  }
1059 
1060 #if __cplusplus >= 201103L
1061  _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
1062 #endif
1063 
1064  ~_Reuse_or_alloc_node()
1065  {
1066  if (_M_root)
1067  _M_t._M_erase(static_cast<_Node&>(*_M_root)._M_node_ptr());
1068  }
1069 
1070  template<typename _Arg>
1071  _Node_ptr
1072  operator()(_GLIBCXX_FWDREF(_Arg) __arg)
1073  {
1074  _Base_ptr __base = _M_extract();
1075  if (__base)
1076  {
1077  _Node_ptr __node = static_cast<_Node&>(*__base)._M_node_ptr();
1078  _M_t._M_destroy_node(__node);
1079  _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
1080  return __node;
1081  }
1082 
1083  return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
1084  }
1085 
1086  private:
1087  _Base_ptr
1088  _M_extract()
1089  {
1090  if (!_M_nodes)
1091  return _M_nodes;
1092 
1093  _Base_ptr __node = _M_nodes;
1094  _M_nodes = _M_nodes->_M_parent;
1095  if (_M_nodes)
1096  {
1097  if (_M_nodes->_M_right == __node)
1098  {
1099  _M_nodes->_M_right = _Base_ptr();
1100 
1101  if (_M_nodes->_M_left)
1102  {
1103  _M_nodes = _M_nodes->_M_left;
1104 
1105  while (_M_nodes->_M_right)
1106  _M_nodes = _M_nodes->_M_right;
1107 
1108  if (_M_nodes->_M_left)
1109  _M_nodes = _M_nodes->_M_left;
1110  }
1111  }
1112  else // __node is on the left.
1113  _M_nodes->_M_left = _Base_ptr();
1114  }
1115  else
1116  _M_root = _Base_ptr();
1117 
1118  return __node;
1119  }
1120 
1121  _Base_ptr _M_root;
1122  _Base_ptr _M_nodes;
1123  _Rb_tree& _M_t;
1124  };
1125 
1126  // Functor similar to the previous one but without any pool of nodes to
1127  // recycle.
1128  struct _Alloc_node
1129  {
1130  _Alloc_node(_Rb_tree& __t)
1131  : _M_t(__t) { }
1132 
1133  template<typename _Arg>
1134  _Node_ptr
1135  operator()(_GLIBCXX_FWDREF(_Arg) __arg) const
1136  { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
1137 
1138  private:
1139  _Rb_tree& _M_t;
1140  };
1141 
1142  public:
1143  typedef _Key key_type;
1144  typedef _Val value_type;
1145  typedef value_type* pointer;
1146  typedef const value_type* const_pointer;
1147  typedef value_type& reference;
1148  typedef const value_type& const_reference;
1149  typedef size_t size_type;
1150  typedef ptrdiff_t difference_type;
1151  typedef _Alloc allocator_type;
1152 
1153  _Node_allocator&
1154  _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
1155  { return this->_M_impl; }
1156 
1157  const _Node_allocator&
1158  _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
1159  { return this->_M_impl; }
1160 
1161  allocator_type
1162  get_allocator() const _GLIBCXX_NOEXCEPT
1163  { return allocator_type(_M_get_Node_allocator()); }
1164 
1165  protected:
1166  _Node_ptr
1167  _M_get_node()
1168  {
1169 #if __cplusplus < 201102L || _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
1170  return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
1171 #else
1172 #pragma GCC diagnostic push
1173 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1174  using __alloc_pointer = typename _Node_alloc_traits::pointer;
1175  if constexpr (is_same<_Node_ptr, __alloc_pointer>::value)
1176  return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
1177  else
1178  {
1179  auto __ptr =
1180  _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
1181  return std::__to_address(__ptr);
1182  }
1183 #pragma GCC diagnostic pop
1184 #endif
1185  }
1186 
1187  void
1188  _M_put_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT
1189  {
1190 #if __cplusplus < 201102L || _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
1191  _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1);
1192 #else
1193 #pragma GCC diagnostic push
1194 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1195  using __alloc_pointer = typename _Node_alloc_traits::pointer;
1196  if constexpr (is_same<_Node_ptr, __alloc_pointer>::value)
1197  _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1);
1198  else
1199  {
1200  // When not using the allocator's pointer type internally we must
1201  // convert __p to __alloc_pointer so it can be deallocated.
1202  auto __ap = pointer_traits<__alloc_pointer>::pointer_to(*__p);
1203  _Node_alloc_traits::deallocate(_M_get_Node_allocator(), __ap, 1);
1204  }
1205 #pragma GCC diagnostic pop
1206 #endif
1207  }
1208 
1209 #if __cplusplus < 201103L
1210  void
1211  _M_construct_node(_Node_ptr __node, const value_type& __x)
1212  {
1213  __try
1214  { get_allocator().construct(__node->_M_valptr(), __x); }
1215  __catch(...)
1216  {
1217  _M_put_node(__node);
1218  __throw_exception_again;
1219  }
1220  }
1221 
1222  _Node_ptr
1223  _M_create_node(const value_type& __x)
1224  {
1225  _Node_ptr __tmp = _M_get_node();
1226  _M_construct_node(__tmp, __x);
1227  return __tmp;
1228  }
1229 #else
1230  template<typename... _Args>
1231  void
1232  _M_construct_node(_Node_ptr __node, _Args&&... __args)
1233  {
1234  __try
1235  {
1236  ::new(std::addressof(*__node)) _Node;
1237  _Node_alloc_traits::construct(_M_get_Node_allocator(),
1238  __node->_M_valptr(),
1239  std::forward<_Args>(__args)...);
1240  }
1241  __catch(...)
1242  {
1243  __node->~_Node();
1244  _M_put_node(__node);
1245  __throw_exception_again;
1246  }
1247  }
1248 
1249  template<typename... _Args>
1250  _Node_ptr
1251  _M_create_node(_Args&&... __args)
1252  {
1253  _Node_ptr __tmp = _M_get_node();
1254  _M_construct_node(__tmp, std::forward<_Args>(__args)...);
1255  return __tmp;
1256  }
1257 #endif
1258 
1259  void
1260  _M_destroy_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT
1261  {
1262 #if __cplusplus < 201103L
1263  get_allocator().destroy(__p->_M_valptr());
1264 #else
1265  _Node_alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
1266  __p->~_Node();
1267 #endif
1268  }
1269 
1270  void
1271  _M_drop_node(_Node_ptr __p) _GLIBCXX_NOEXCEPT
1272  {
1273  _M_destroy_node(__p);
1274  _M_put_node(__p);
1275  }
1276 
1277  template<bool _MoveValue, typename _NodeGen>
1278  _Node_ptr
1279  _M_clone_node(_Node_ptr __x, _NodeGen& __node_gen)
1280  {
1281 #if __cplusplus >= 201103L
1282  using _Vp = __conditional_t<_MoveValue,
1283  value_type&&,
1284  const value_type&>;
1285 #endif
1286  _Node_ptr __tmp
1287  = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr()));
1288  __tmp->_M_color = __x->_M_color;
1289  __tmp->_M_left = __tmp->_M_right = _Base_ptr();
1290  return __tmp;
1291  }
1292 
1293  protected:
1294  typedef typename _Node_traits::_Header_t _Header_t;
1295 
1296 #if _GLIBCXX_INLINE_VERSION
1297  template<typename _Key_compare>
1298 #else
1299  // Unused _Is_pod_comparator is kept as it is part of mangled name.
1300  template<typename _Key_compare,
1301  bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
1302 #endif
1303  struct _Rb_tree_impl
1304  : public _Node_allocator
1305  , public _Rb_tree_key_compare<_Key_compare>
1306  , public _Header_t
1307  {
1308  typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
1309 
1310  _Rb_tree_impl()
1311  _GLIBCXX_NOEXCEPT_IF(
1312  is_nothrow_default_constructible<_Node_allocator>::value
1313  && is_nothrow_default_constructible<_Base_key_compare>::value )
1314  : _Node_allocator()
1315  { }
1316 
1317  _Rb_tree_impl(const _Rb_tree_impl& __x)
1318  : _Node_allocator(_Node_alloc_traits::_S_select_on_copy(__x))
1319  , _Base_key_compare(__x._M_key_compare)
1320  , _Header_t()
1321  { }
1322 
1323 #if __cplusplus < 201103L
1324  _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
1325  : _Node_allocator(__a), _Base_key_compare(__comp)
1326  { }
1327 #else
1328  _Rb_tree_impl(_Rb_tree_impl&&)
1329  noexcept( is_nothrow_move_constructible<_Base_key_compare>::value )
1330  = default;
1331 
1332  explicit
1333  _Rb_tree_impl(_Node_allocator&& __a)
1334  : _Node_allocator(std::move(__a))
1335  { }
1336 
1337  _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
1338  : _Node_allocator(std::move(__a)),
1339  _Base_key_compare(std::move(__x)),
1340  _Header_t(std::move(__x))
1341  { }
1342 
1343  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
1344  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
1345  { }
1346 #endif
1347  };
1348 
1349  _Rb_tree_impl<_Compare> _M_impl;
1350 
1351  protected:
1352  _Base_ptr&
1353  _M_root() _GLIBCXX_NOEXCEPT
1354  { return this->_M_impl._M_header._M_parent; }
1355 
1356  _Base_ptr
1357  _M_root() const _GLIBCXX_NOEXCEPT
1358  { return this->_M_impl._M_header._M_parent; }
1359 
1360  _Base_ptr&
1361  _M_leftmost() _GLIBCXX_NOEXCEPT
1362  { return this->_M_impl._M_header._M_left; }
1363 
1364  _Base_ptr
1365  _M_leftmost() const _GLIBCXX_NOEXCEPT
1366  { return this->_M_impl._M_header._M_left; }
1367 
1368  _Base_ptr&
1369  _M_rightmost() _GLIBCXX_NOEXCEPT
1370  { return this->_M_impl._M_header._M_right; }
1371 
1372  _Base_ptr
1373  _M_rightmost() const _GLIBCXX_NOEXCEPT
1374  { return this->_M_impl._M_header._M_right; }
1375 
1376  _Base_ptr
1377  _M_begin() const _GLIBCXX_NOEXCEPT
1378  { return this->_M_impl._M_header._M_parent; }
1379 
1380  _Node_ptr
1381  _M_begin_node() const _GLIBCXX_NOEXCEPT
1382  {
1383  _Base_ptr __begin = this->_M_impl._M_header._M_parent;
1384  return __begin
1385  ? static_cast<_Node&>(*__begin)._M_node_ptr()
1386  : _Node_ptr();
1387  }
1388 
1389  _Base_ptr
1390  _M_end() const _GLIBCXX_NOEXCEPT
1391  { return this->_M_impl._M_header._M_base_ptr(); }
1392 
1393  static const _Key&
1394  _S_key(const _Node& __node)
1395  {
1396 #if __cplusplus >= 201103L
1397  // If we're asking for the key we're presumably using the comparison
1398  // object, and so this is a good place to sanity check it.
1399  static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
1400  "comparison object must be invocable "
1401  "with two arguments of key type");
1402 # if __cplusplus >= 201703L
1403  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1404  // 2542. Missing const requirements for associative containers
1405  if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{})
1406  static_assert(
1407  is_invocable_v<const _Compare&, const _Key&, const _Key&>,
1408  "comparison object must be invocable as const");
1409 # endif // C++17
1410 #endif // C++11
1411 
1412  return _KeyOfValue()(*__node._M_valptr());
1413  }
1414 
1415  static const _Key&
1416  _S_key(_Base_ptr __x)
1417  { return _S_key(static_cast<const _Node&>(*__x)); }
1418 
1419  static const _Key&
1420  _S_key(_Node_ptr __x)
1421  { return _S_key(*__x); }
1422 
1423  static _Base_ptr
1424  _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
1425  { return __x->_M_left; }
1426 
1427  static _Node_ptr
1428  _S_left(_Node_ptr __x)
1429  {
1430  return __x->_M_left
1431  ? static_cast<_Node&>(*__x->_M_left)._M_node_ptr()
1432  : _Node_ptr();
1433  }
1434 
1435  static _Base_ptr
1436  _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
1437  { return __x->_M_right; }
1438 
1439  static _Node_ptr
1440  _S_right(_Node_ptr __x) _GLIBCXX_NOEXCEPT
1441  {
1442  return __x->_M_right
1443  ? static_cast<_Node&>(*__x->_M_right)._M_node_ptr()
1444  : _Node_ptr();
1445  }
1446 
1447  public:
1448  typedef typename _Node_traits::_Iterator iterator;
1449  typedef typename _Node_traits::_Const_iterator const_iterator;
1450 
1451  typedef std::reverse_iterator<iterator> reverse_iterator;
1452  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1453 
1454 #ifdef __glibcxx_node_extract // >= C++17
1455  using node_type = _Node_handle<_Key, _Val, _Node_allocator>;
1456  using insert_return_type = _Node_insert_return<
1457  __conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>,
1458  node_type>;
1459 #endif
1460 
1461  pair<_Base_ptr, _Base_ptr>
1462  _M_get_insert_unique_pos(const key_type& __k);
1463 
1464  pair<_Base_ptr, _Base_ptr>
1465  _M_get_insert_equal_pos(const key_type& __k);
1466 
1467  pair<_Base_ptr, _Base_ptr>
1468  _M_get_insert_hint_unique_pos(const_iterator __pos,
1469  const key_type& __k);
1470 
1471  pair<_Base_ptr, _Base_ptr>
1472  _M_get_insert_hint_equal_pos(const_iterator __pos,
1473  const key_type& __k);
1474 
1475  private:
1476 #if __cplusplus >= 201103L
1477  template<typename _Arg, typename _NodeGen>
1478  iterator
1479  _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
1480 
1481  iterator
1482  _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Node_ptr __z);
1483 
1484  template<typename _Arg>
1485  iterator
1486  _M_insert_lower(_Base_ptr __y, _Arg&& __v);
1487 
1488  template<typename _Arg>
1489  iterator
1490  _M_insert_equal_lower(_Arg&& __x);
1491 
1492  iterator
1493  _M_insert_lower_node(_Base_ptr __p, _Node_ptr __z);
1494 
1495  iterator
1496  _M_insert_equal_lower_node(_Node_ptr __z);
1497 #else
1498  template<typename _NodeGen>
1499  iterator
1500  _M_insert_(_Base_ptr __x, _Base_ptr __y,
1501  const value_type& __v, _NodeGen&);
1502 
1503  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1504  // 233. Insertion hints in associative containers.
1505  iterator
1506  _M_insert_lower(_Base_ptr __y, const value_type& __v);
1507 
1508  iterator
1509  _M_insert_equal_lower(const value_type& __x);
1510 #endif
1511 
1512  enum { __as_lvalue, __as_rvalue };
1513 
1514  template<bool _MoveValues, typename _NodeGen>
1515  _Base_ptr
1516  _M_copy(_Node_ptr, _Base_ptr, _NodeGen&);
1517 
1518  template<bool _MoveValues, typename _NodeGen>
1519  _Base_ptr
1520  _M_copy(const _Rb_tree& __x, _NodeGen& __gen)
1521  {
1522  _Base_ptr __root =
1523  _M_copy<_MoveValues>(__x._M_begin_node(), _M_end(), __gen);
1524  _M_leftmost() = _Node_base::_S_minimum(__root);
1525  _M_rightmost() = _Node_base::_S_maximum(__root);
1526  _M_impl._M_node_count = __x._M_impl._M_node_count;
1527  return __root;
1528  }
1529 
1530  _Base_ptr
1531  _M_copy(const _Rb_tree& __x)
1532  {
1533  _Alloc_node __an(*this);
1534  return _M_copy<__as_lvalue>(__x, __an);
1535  }
1536 
1537  void
1538  _M_erase(_Node_ptr __x);
1539 
1540  _Base_ptr
1541  _M_lower_bound(_Base_ptr __x, _Base_ptr __y,
1542  const _Key& __k) const;
1543 
1544  _Base_ptr
1545  _M_upper_bound(_Base_ptr __x, _Base_ptr __y,
1546  const _Key& __k) const;
1547 
1548  public:
1549  // allocation/deallocation
1550 #if __cplusplus < 201103L
1551  _Rb_tree() { }
1552 #else
1553  _Rb_tree() = default;
1554 #endif
1555 
1556  _Rb_tree(const _Compare& __comp,
1557  const allocator_type& __a = allocator_type())
1558  : _M_impl(__comp, _Node_allocator(__a)) { }
1559 
1560  _Rb_tree(const _Rb_tree& __x)
1561  : _M_impl(__x._M_impl)
1562  {
1563  if (__x._M_root())
1564  _M_root() = _M_copy(__x);
1565  }
1566 
1567 #if __cplusplus >= 201103L
1568  _Rb_tree(const allocator_type& __a)
1569  : _M_impl(_Node_allocator(__a))
1570  { }
1571 
1572  _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
1573  : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
1574  {
1575  if (__x._M_root())
1576  _M_root() = _M_copy(__x);
1577  }
1578 
1579  _Rb_tree(_Rb_tree&&) = default;
1580 
1581  _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
1582  : _Rb_tree(std::move(__x), _Node_allocator(__a))
1583  { }
1584 
1585  private:
1586  _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
1587  noexcept(is_nothrow_default_constructible<_Compare>::value)
1588  : _M_impl(std::move(__x._M_impl), std::move(__a))
1589  { }
1590 
1591  _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
1592  : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
1593  {
1594  if (__x._M_root())
1595  _M_move_data(__x, false_type{});
1596  }
1597 
1598  public:
1599  _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1600  noexcept( noexcept(
1601  _Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(),
1602  std::declval<typename _Node_alloc_traits::is_always_equal>())) )
1603  : _Rb_tree(std::move(__x), std::move(__a),
1604  typename _Node_alloc_traits::is_always_equal{})
1605  { }
1606 #endif
1607 
1608  ~_Rb_tree() _GLIBCXX_NOEXCEPT
1609  { _M_erase(_M_begin_node()); }
1610 
1611  _Rb_tree&
1612  operator=(const _Rb_tree& __x);
1613 
1614  // Accessors.
1615  _Compare
1616  key_comp() const
1617  { return _M_impl._M_key_compare; }
1618 
1619  iterator
1620  begin() _GLIBCXX_NOEXCEPT
1621  { return iterator(this->_M_impl._M_header._M_left); }
1622 
1623  const_iterator
1624  begin() const _GLIBCXX_NOEXCEPT
1625  { return const_iterator(this->_M_impl._M_header._M_left); }
1626 
1627  iterator
1628  end() _GLIBCXX_NOEXCEPT
1629  { return iterator(_M_end()); }
1630 
1631  const_iterator
1632  end() const _GLIBCXX_NOEXCEPT
1633  { return const_iterator(_M_end()); }
1634 
1635  reverse_iterator
1636  rbegin() _GLIBCXX_NOEXCEPT
1637  { return reverse_iterator(end()); }
1638 
1639  const_reverse_iterator
1640  rbegin() const _GLIBCXX_NOEXCEPT
1641  { return const_reverse_iterator(end()); }
1642 
1643  reverse_iterator
1644  rend() _GLIBCXX_NOEXCEPT
1645  { return reverse_iterator(begin()); }
1646 
1647  const_reverse_iterator
1648  rend() const _GLIBCXX_NOEXCEPT
1649  { return const_reverse_iterator(begin()); }
1650 
1651  _GLIBCXX_NODISCARD bool
1652  empty() const _GLIBCXX_NOEXCEPT
1653  { return _M_impl._M_node_count == 0; }
1654 
1655  size_type
1656  size() const _GLIBCXX_NOEXCEPT
1657  { return _M_impl._M_node_count; }
1658 
1659  size_type
1660  max_size() const _GLIBCXX_NOEXCEPT
1661  { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); }
1662 
1663  void
1664  swap(_Rb_tree& __t)
1665  _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
1666 
1667  // Insert/erase.
1668 #if __cplusplus >= 201103L
1669  template<typename _Arg>
1670  pair<iterator, bool>
1671  _M_insert_unique(_Arg&& __x);
1672 
1673  template<typename _Arg>
1674  iterator
1675  _M_insert_equal(_Arg&& __x);
1676 
1677  template<typename _Arg, typename _NodeGen>
1678  iterator
1679  _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1680 
1681  template<typename _Arg>
1682  iterator
1683  _M_insert_unique_(const_iterator __pos, _Arg&& __x)
1684  {
1685  _Alloc_node __an(*this);
1686  return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
1687  }
1688 
1689  template<typename _Arg, typename _NodeGen>
1690  iterator
1691  _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
1692 
1693  template<typename _Arg>
1694  iterator
1695  _M_insert_equal_(const_iterator __pos, _Arg&& __x)
1696  {
1697  _Alloc_node __an(*this);
1698  return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
1699  }
1700 
1701  template<typename... _Args>
1702  pair<iterator, bool>
1703  _M_emplace_unique(_Args&&... __args);
1704 
1705  template<typename... _Args>
1706  iterator
1707  _M_emplace_equal(_Args&&... __args);
1708 
1709  template<typename... _Args>
1710  iterator
1711  _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
1712 
1713  template<typename... _Args>
1714  iterator
1715  _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
1716 
1717  template<typename _Iter>
1718  using __same_value_type
1719  = is_same<value_type, typename iterator_traits<_Iter>::value_type>;
1720 
1721  template<typename _InputIterator>
1722  __enable_if_t<__same_value_type<_InputIterator>::value>
1723  _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1724  {
1725  _Alloc_node __an(*this);
1726  for (; __first != __last; ++__first)
1727  _M_insert_unique_(end(), *__first, __an);
1728  }
1729 
1730  template<typename _InputIterator>
1731  __enable_if_t<!__same_value_type<_InputIterator>::value>
1732  _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1733  {
1734  for (; __first != __last; ++__first)
1735  _M_emplace_unique(*__first);
1736  }
1737 
1738  template<typename _InputIterator>
1739  __enable_if_t<__same_value_type<_InputIterator>::value>
1740  _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1741  {
1742  _Alloc_node __an(*this);
1743  for (; __first != __last; ++__first)
1744  _M_insert_equal_(end(), *__first, __an);
1745  }
1746 
1747  template<typename _InputIterator>
1748  __enable_if_t<!__same_value_type<_InputIterator>::value>
1749  _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1750  {
1751  for (; __first != __last; ++__first)
1752  _M_emplace_equal(*__first);
1753  }
1754 #else
1755  pair<iterator, bool>
1756  _M_insert_unique(const value_type& __x);
1757 
1758  iterator
1759  _M_insert_equal(const value_type& __x);
1760 
1761  template<typename _NodeGen>
1762  iterator
1763  _M_insert_unique_(const_iterator __pos, const value_type& __x,
1764  _NodeGen&);
1765 
1766  iterator
1767  _M_insert_unique_(const_iterator __pos, const value_type& __x)
1768  {
1769  _Alloc_node __an(*this);
1770  return _M_insert_unique_(__pos, __x, __an);
1771  }
1772 
1773  template<typename _NodeGen>
1774  iterator
1775  _M_insert_equal_(const_iterator __pos, const value_type& __x,
1776  _NodeGen&);
1777  iterator
1778  _M_insert_equal_(const_iterator __pos, const value_type& __x)
1779  {
1780  _Alloc_node __an(*this);
1781  return _M_insert_equal_(__pos, __x, __an);
1782  }
1783 
1784  template<typename _InputIterator>
1785  void
1786  _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
1787  {
1788  _Alloc_node __an(*this);
1789  for (; __first != __last; ++__first)
1790  _M_insert_unique_(end(), *__first, __an);
1791  }
1792 
1793  template<typename _InputIterator>
1794  void
1795  _M_insert_range_equal(_InputIterator __first, _InputIterator __last)
1796  {
1797  _Alloc_node __an(*this);
1798  for (; __first != __last; ++__first)
1799  _M_insert_equal_(end(), *__first, __an);
1800  }
1801 #endif
1802 
1803  private:
1804  void
1805  _M_erase_aux(const_iterator __position);
1806 
1807  void
1808  _M_erase_aux(const_iterator __first, const_iterator __last);
1809 
1810  public:
1811 #if __cplusplus >= 201103L
1812  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1813  // DR 130. Associative erase should return an iterator.
1814  _GLIBCXX_ABI_TAG_CXX11
1815  iterator
1816  erase(const_iterator __position)
1817  {
1818  __glibcxx_assert(__position != end());
1819  const_iterator __result = __position;
1820  ++__result;
1821  _M_erase_aux(__position);
1822  return iterator(__result._M_node);
1823  }
1824 
1825  // LWG 2059.
1826  _GLIBCXX_ABI_TAG_CXX11
1827  iterator
1828  erase(iterator __position)
1829  {
1830  __glibcxx_assert(__position != end());
1831  iterator __result = __position;
1832  ++__result;
1833  _M_erase_aux(__position);
1834  return __result;
1835  }
1836 #else
1837  void
1838  erase(iterator __position)
1839  {
1840  __glibcxx_assert(__position != end());
1841  _M_erase_aux(__position);
1842  }
1843 
1844  void
1845  erase(const_iterator __position)
1846  {
1847  __glibcxx_assert(__position != end());
1848  _M_erase_aux(__position);
1849  }
1850 #endif
1851 
1852  size_type
1853  erase(const key_type& __x);
1854 
1855 #if __cplusplus >= 201103L
1856  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1857  // DR 130. Associative erase should return an iterator.
1858  _GLIBCXX_ABI_TAG_CXX11
1859  iterator
1860  erase(const_iterator __first, const_iterator __last)
1861  {
1862  _M_erase_aux(__first, __last);
1863  return iterator(__last._M_node);
1864  }
1865 #else
1866  void
1867  erase(iterator __first, iterator __last)
1868  { _M_erase_aux(__first, __last); }
1869 
1870  void
1871  erase(const_iterator __first, const_iterator __last)
1872  { _M_erase_aux(__first, __last); }
1873 #endif
1874 
1875  void
1876  clear() _GLIBCXX_NOEXCEPT
1877  {
1878  _M_erase(_M_begin_node());
1879  _M_impl._M_reset();
1880  }
1881 
1882  // Set operations.
1883  iterator
1884  find(const key_type& __k);
1885 
1886  const_iterator
1887  find(const key_type& __k) const;
1888 
1889  size_type
1890  count(const key_type& __k) const;
1891 
1892  iterator
1893  lower_bound(const key_type& __k)
1894  { return iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); }
1895 
1896  const_iterator
1897  lower_bound(const key_type& __k) const
1898  {
1899  return const_iterator
1900  (_M_lower_bound(_M_begin(), _M_end(), __k));
1901  }
1902 
1903  iterator
1904  upper_bound(const key_type& __k)
1905  { return iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); }
1906 
1907  const_iterator
1908  upper_bound(const key_type& __k) const
1909  {
1910  return const_iterator
1911  (_M_upper_bound(_M_begin(), _M_end(), __k));
1912  }
1913 
1914  pair<iterator, iterator>
1915  equal_range(const key_type& __k);
1916 
1917  pair<const_iterator, const_iterator>
1918  equal_range(const key_type& __k) const;
1919 
1920 #if __cplusplus >= 201402L
1921  template<typename _Kt,
1922  typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1923  iterator
1924  _M_find_tr(const _Kt& __k)
1925  {
1926  const _Rb_tree* __const_this = this;
1927  return iterator(__const_this->_M_find_tr(__k)._M_node);
1928  }
1929 
1930  template<typename _Kt,
1931  typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1932  const_iterator
1933  _M_find_tr(const _Kt& __k) const
1934  {
1935  const_iterator __j(_M_lower_bound_tr(__k));
1936  if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
1937  __j = end();
1938  return __j;
1939  }
1940 
1941  template<typename _Kt,
1942  typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1943  size_type
1944  _M_count_tr(const _Kt& __k) const
1945  {
1946  auto __p = _M_equal_range_tr(__k);
1947  return std::distance(__p.first, __p.second);
1948  }
1949 
1950  template<typename _Kt,
1951  typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1952  _Base_ptr
1953  _M_lower_bound_tr(const _Kt& __k) const
1954  {
1955  auto __x = _M_begin();
1956  auto __y = _M_end();
1957  while (__x)
1958  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1959  {
1960  __y = __x;
1961  __x = _S_left(__x);
1962  }
1963  else
1964  __x = _S_right(__x);
1965  return __y;
1966  }
1967 
1968  template<typename _Kt,
1969  typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1970  _Base_ptr
1971  _M_upper_bound_tr(const _Kt& __k) const
1972  {
1973  auto __x = _M_begin();
1974  auto __y = _M_end();
1975  while (__x)
1976  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1977  {
1978  __y = __x;
1979  __x = _S_left(__x);
1980  }
1981  else
1982  __x = _S_right(__x);
1983  return __y;
1984  }
1985 
1986  template<typename _Kt,
1987  typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1988  pair<iterator, iterator>
1989  _M_equal_range_tr(const _Kt& __k)
1990  {
1991  const _Rb_tree* __const_this = this;
1992  auto __ret = __const_this->_M_equal_range_tr(__k);
1993  return
1994  { iterator(__ret.first._M_node), iterator(__ret.second._M_node) };
1995  }
1996 
1997  template<typename _Kt,
1998  typename _Req = __has_is_transparent_t<_Compare, _Kt>>
1999  pair<const_iterator, const_iterator>
2000  _M_equal_range_tr(const _Kt& __k) const
2001  {
2002  const_iterator __low(_M_lower_bound_tr(__k));
2003  auto __high = __low;
2004  auto& __cmp = _M_impl._M_key_compare;
2005  while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
2006  ++__high;
2007  return { __low, __high };
2008  }
2009 #endif
2010 
2011  // Debugging.
2012  bool
2013  __rb_verify() const;
2014 
2015 #if __cplusplus >= 201103L
2016  _Rb_tree&
2017  operator=(_Rb_tree&&)
2018  noexcept(_Node_alloc_traits::_S_nothrow_move()
2019  && is_nothrow_move_assignable<_Compare>::value);
2020 
2021  template<typename _Iterator>
2022  void
2023  _M_assign_unique(_Iterator, _Iterator);
2024 
2025  template<typename _Iterator>
2026  void
2027  _M_assign_equal(_Iterator, _Iterator);
2028 
2029  private:
2030  // Move elements from container with equal allocator.
2031  void
2032  _M_move_data(_Rb_tree& __x, true_type)
2033  { _M_impl._M_move_data(__x._M_impl); }
2034 
2035  // Move elements from container with possibly non-equal allocator,
2036  // which might result in a copy not a move.
2037  void
2038  _M_move_data(_Rb_tree&, false_type);
2039 
2040  // Move assignment from container with equal allocator.
2041  void
2042  _M_move_assign(_Rb_tree&, true_type);
2043 
2044  // Move assignment from container with possibly non-equal allocator,
2045  // which might result in a copy not a move.
2046  void
2047  _M_move_assign(_Rb_tree&, false_type);
2048 #endif
2049 
2050 #if __glibcxx_node_extract // >= C++17
2051  static _Node_ptr
2052  _S_adapt(typename _Node_alloc_traits::pointer __ptr)
2053  {
2054 #if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
2055  return __ptr;
2056 #else
2057 #pragma GCC diagnostic push
2058 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
2059  using __alloc_ptr = typename _Node_alloc_traits::pointer;
2060  if constexpr (is_same<_Node_ptr, __alloc_ptr>::value)
2061  return __ptr;
2062  else
2063  return std::__to_address(__ptr);
2064 #pragma GCC diagnostic pop
2065 #endif
2066  }
2067 
2068  public:
2069  /// Re-insert an extracted node.
2070  insert_return_type
2071  _M_reinsert_node_unique(node_type&& __nh)
2072  {
2073  insert_return_type __ret;
2074  if (__nh.empty())
2075  __ret.position = end();
2076  else
2077  {
2078  __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2079 
2080  auto __res = _M_get_insert_unique_pos(__nh._M_key());
2081  if (__res.second)
2082  {
2083  __ret.position
2084  = _M_insert_node(__res.first, __res.second,
2085  _S_adapt(__nh._M_ptr));
2086  __nh.release();
2087  __ret.inserted = true;
2088  }
2089  else
2090  {
2091  __ret.node = std::move(__nh);
2092  __ret.position = iterator(__res.first);
2093  __ret.inserted = false;
2094  }
2095  }
2096  return __ret;
2097  }
2098 
2099  /// Re-insert an extracted node.
2100  iterator
2101  _M_reinsert_node_equal(node_type&& __nh)
2102  {
2103  iterator __ret;
2104  if (__nh.empty())
2105  __ret = end();
2106  else
2107  {
2108  __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2109  auto __res = _M_get_insert_equal_pos(__nh._M_key());
2110  if (__res.second)
2111  __ret = _M_insert_node(__res.first, __res.second,
2112  _S_adapt(__nh._M_ptr));
2113  else
2114  __ret = _M_insert_equal_lower_node(_S_adapt(__nh._M_ptr));
2115  __nh.release();
2116  }
2117  return __ret;
2118  }
2119 
2120  /// Re-insert an extracted node.
2121  iterator
2122  _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
2123  {
2124  iterator __ret;
2125  if (__nh.empty())
2126  __ret = end();
2127  else
2128  {
2129  __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2130  auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
2131  if (__res.second)
2132  {
2133  __ret = _M_insert_node(__res.first, __res.second,
2134  _S_adapt(__nh._M_ptr));
2135  __nh.release();
2136  }
2137  else
2138  __ret = iterator(__res.first);
2139  }
2140  return __ret;
2141  }
2142 
2143  /// Re-insert an extracted node.
2144  iterator
2145  _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
2146  {
2147  iterator __ret;
2148  if (__nh.empty())
2149  __ret = end();
2150  else
2151  {
2152  __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
2153  auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
2154  if (__res.second)
2155  __ret = _M_insert_node(__res.first, __res.second,
2156  _S_adapt(__nh._M_ptr));
2157  else
2158  __ret = _M_insert_equal_lower_node(_S_adapt(__nh._M_ptr));
2159  __nh.release();
2160  }
2161  return __ret;
2162  }
2163 
2164  /// Extract a node.
2165  node_type
2166  extract(const_iterator __pos)
2167  {
2168  auto __ptr = _Node_traits::_S_rebalance_for_erase
2169  (__pos._M_node, _M_impl._M_header);
2170  --_M_impl._M_node_count;
2171  auto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr();
2172 #if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
2173  return { __node_ptr, _M_get_Node_allocator() };
2174 #else
2175 #pragma GCC diagnostic push
2176 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
2177  using __alloc_ptr = typename _Node_alloc_traits::pointer;
2178  if constexpr (is_same<_Node_ptr, __alloc_ptr>::value)
2179  return { __node_ptr, _M_get_Node_allocator() };
2180  else
2181  {
2182  auto __ap = pointer_traits<__alloc_ptr>::pointer_to(*__node_ptr);
2183  return { __ap, _M_get_Node_allocator() };
2184  }
2185 #pragma GCC diagnostic pop
2186 #endif
2187  }
2188 
2189  /// Extract a node.
2190  node_type
2191  extract(const key_type& __k)
2192  {
2193  node_type __nh;
2194  auto __pos = find(__k);
2195  if (__pos != end())
2196  __nh = extract(const_iterator(__pos));
2197  return __nh;
2198  }
2199 
2200  template<typename _Compare2>
2201  using _Compatible_tree
2202  = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
2203 
2204  template<typename, typename>
2205  friend struct _Rb_tree_merge_helper;
2206 
2207  /// Merge from a compatible container into one with unique keys.
2208  template<typename _Compare2>
2209  void
2210  _M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept
2211  {
2212  using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
2213  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
2214  {
2215  auto __pos = __i++;
2216  auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos));
2217  if (__res.second)
2218  {
2219  auto& __src_impl = _Merge_helper::_S_get_impl(__src);
2220  auto __ptr = _Node_traits::_S_rebalance_for_erase
2221  (__pos._M_node, __src_impl._M_header);
2222  --__src_impl._M_node_count;
2223  auto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr();
2224  _M_insert_node(__res.first, __res.second, __node_ptr);
2225  }
2226  }
2227  }
2228 
2229  /// Merge from a compatible container into one with equivalent keys.
2230  template<typename _Compare2>
2231  void
2232  _M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept
2233  {
2234  using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
2235  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
2236  {
2237  auto __pos = __i++;
2238  auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos));
2239  if (__res.second)
2240  {
2241  auto& __src_impl = _Merge_helper::_S_get_impl(__src);
2242  auto __ptr = _Node_traits::_S_rebalance_for_erase
2243  (__pos._M_node, __src_impl._M_header);
2244  --__src_impl._M_node_count;
2245  auto __node_ptr = static_cast<_Node&>(*__ptr)._M_node_ptr();
2246  _M_insert_node(__res.first, __res.second, __node_ptr);
2247  }
2248  }
2249  }
2250 #endif // C++17 node_extract
2251 
2252  friend bool
2253  operator==(const _Rb_tree& __x, const _Rb_tree& __y)
2254  {
2255  return __x.size() == __y.size()
2256  && std::equal(__x.begin(), __x.end(), __y.begin());
2257  }
2258 
2259 #if __cpp_lib_three_way_comparison
2260  friend auto
2261  operator<=>(const _Rb_tree& __x, const _Rb_tree& __y)
2262  {
2263  if constexpr (requires { typename __detail::__synth3way_t<_Val>; })
2264  return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
2265  __y.begin(), __y.end(),
2266  __detail::__synth3way);
2267  }
2268 #else
2269  friend bool
2270  operator<(const _Rb_tree& __x, const _Rb_tree& __y)
2271  {
2272  return std::lexicographical_compare(__x.begin(), __x.end(),
2273  __y.begin(), __y.end());
2274  }
2275 #endif
2276 
2277  private:
2278 #if __cplusplus >= 201103L
2279  // An RAII _Node handle
2280  struct _Auto_node
2281  {
2282  template<typename... _Args>
2283  _Auto_node(_Rb_tree& __t, _Args&&... __args)
2284  : _M_t(__t),
2285  _M_node(__t._M_create_node(std::forward<_Args>(__args)...))
2286  { }
2287 
2288  ~_Auto_node()
2289  {
2290  if (_M_node)
2291  _M_t._M_drop_node(_M_node);
2292  }
2293 
2294  _Auto_node(_Auto_node&& __n)
2295  : _M_t(__n._M_t), _M_node(__n._M_node)
2296  { __n._M_node = nullptr; }
2297 
2298  const _Key&
2299  _M_key() const
2300  { return _S_key(_M_node); }
2301 
2302  iterator
2303  _M_insert(pair<_Base_ptr, _Base_ptr> __p)
2304  {
2305  auto __it = _M_t._M_insert_node(__p.first, __p.second, _M_node);
2306  _M_node = nullptr;
2307  return __it;
2308  }
2309 
2310  iterator
2311  _M_insert_equal_lower()
2312  {
2313  auto __it = _M_t._M_insert_equal_lower_node(_M_node);
2314  _M_node = nullptr;
2315  return __it;
2316  }
2317 
2318  _Rb_tree& _M_t;
2319  _Node_ptr _M_node;
2320  };
2321 #endif // C++11
2322  };
2323 
2324  template<typename _Key, typename _Val, typename _KeyOfValue,
2325  typename _Compare, typename _Alloc>
2326  inline void
2327  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
2328  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
2329  { __x.swap(__y); }
2330 
2331 #if __cplusplus >= 201103L
2332  template<typename _Key, typename _Val, typename _KeyOfValue,
2333  typename _Compare, typename _Alloc>
2334  void
2335  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2336  _M_move_data(_Rb_tree& __x, false_type)
2337  {
2338  if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
2339  _M_move_data(__x, true_type());
2340  else
2341  {
2342  constexpr bool __move = !__move_if_noexcept_cond<value_type>::value;
2343  _Alloc_node __an(*this);
2344  _M_root() = _M_copy<__move>(__x, __an);
2345  if _GLIBCXX17_CONSTEXPR (__move)
2346  __x.clear();
2347  }
2348  }
2349 
2350  template<typename _Key, typename _Val, typename _KeyOfValue,
2351  typename _Compare, typename _Alloc>
2352  inline void
2353  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2354  _M_move_assign(_Rb_tree& __x, true_type)
2355  {
2356  clear();
2357  if (__x._M_root())
2358  _M_move_data(__x, true_type());
2359  std::__alloc_on_move(_M_get_Node_allocator(),
2360  __x._M_get_Node_allocator());
2361  }
2362 
2363  template<typename _Key, typename _Val, typename _KeyOfValue,
2364  typename _Compare, typename _Alloc>
2365  void
2366  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2367  _M_move_assign(_Rb_tree& __x, false_type)
2368  {
2369  if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
2370  return _M_move_assign(__x, true_type{});
2371 
2372  // Try to move each node reusing existing nodes and copying __x nodes
2373  // structure.
2374  _Reuse_or_alloc_node __roan(*this);
2375  _M_impl._M_reset();
2376  if (__x._M_root())
2377  {
2378  _M_root() = _M_copy<__as_rvalue>(__x, __roan);
2379  __x.clear();
2380  }
2381  }
2382 
2383  template<typename _Key, typename _Val, typename _KeyOfValue,
2384  typename _Compare, typename _Alloc>
2385  inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
2386  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2387  operator=(_Rb_tree&& __x)
2388  noexcept(_Node_alloc_traits::_S_nothrow_move()
2389  && is_nothrow_move_assignable<_Compare>::value)
2390  {
2391  _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
2392  _M_move_assign(__x,
2393  __bool_constant<_Node_alloc_traits::_S_nothrow_move()>());
2394  return *this;
2395  }
2396 
2397  template<typename _Key, typename _Val, typename _KeyOfValue,
2398  typename _Compare, typename _Alloc>
2399  template<typename _Iterator>
2400  void
2401  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2402  _M_assign_unique(_Iterator __first, _Iterator __last)
2403  {
2404  _Reuse_or_alloc_node __roan(*this);
2405  _M_impl._M_reset();
2406  for (; __first != __last; ++__first)
2407  _M_insert_unique_(end(), *__first, __roan);
2408  }
2409 
2410  template<typename _Key, typename _Val, typename _KeyOfValue,
2411  typename _Compare, typename _Alloc>
2412  template<typename _Iterator>
2413  void
2414  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2415  _M_assign_equal(_Iterator __first, _Iterator __last)
2416  {
2417  _Reuse_or_alloc_node __roan(*this);
2418  _M_impl._M_reset();
2419  for (; __first != __last; ++__first)
2420  _M_insert_equal_(end(), *__first, __roan);
2421  }
2422 #endif
2423 
2424  template<typename _Key, typename _Val, typename _KeyOfValue,
2425  typename _Compare, typename _Alloc>
2426  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
2427  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2428  operator=(const _Rb_tree& __x)
2429  {
2430  if (this != std::__addressof(__x))
2431  {
2432  // Note that _Key may be a constant type.
2433 #if __cplusplus >= 201103L
2434  if (_Node_alloc_traits::_S_propagate_on_copy_assign())
2435  {
2436  auto& __this_alloc = this->_M_get_Node_allocator();
2437  auto& __that_alloc = __x._M_get_Node_allocator();
2438  if (!_Node_alloc_traits::_S_always_equal()
2439  && __this_alloc != __that_alloc)
2440  {
2441  // Replacement allocator cannot free existing storage, we need
2442  // to erase nodes first.
2443  clear();
2444  std::__alloc_on_copy(__this_alloc, __that_alloc);
2445  }
2446  }
2447 #endif
2448 
2449  _Reuse_or_alloc_node __roan(*this);
2450  _M_impl._M_reset();
2451  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
2452  if (__x._M_root())
2453  _M_root() = _M_copy<__as_lvalue>(__x, __roan);
2454  }
2455 
2456  return *this;
2457  }
2458 
2459  template<typename _Key, typename _Val, typename _KeyOfValue,
2460  typename _Compare, typename _Alloc>
2461 #if __cplusplus >= 201103L
2462  template<typename _Arg, typename _NodeGen>
2463 #else
2464  template<typename _NodeGen>
2465 #endif
2466  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2467  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2468  _M_insert_(_Base_ptr __x, _Base_ptr __p,
2469 #if __cplusplus >= 201103L
2470  _Arg&& __v,
2471 #else
2472  const _Val& __v,
2473 #endif
2474  _NodeGen& __node_gen)
2475  {
2476  bool __insert_left = (__x || __p == _M_end()
2477  || _M_impl._M_key_compare(_KeyOfValue()(__v),
2478  _S_key(__p)));
2479 
2480  _Base_ptr __z =
2481  __node_gen(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr();
2482 
2483  _Node_traits::_S_insert_and_rebalance
2484  (__insert_left, __z, __p, this->_M_impl._M_header);
2485  ++_M_impl._M_node_count;
2486  return iterator(__z);
2487  }
2488 
2489  template<typename _Key, typename _Val, typename _KeyOfValue,
2490  typename _Compare, typename _Alloc>
2491 #if __cplusplus >= 201103L
2492  template<typename _Arg>
2493 #endif
2494  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2495  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2496 #if __cplusplus >= 201103L
2497  _M_insert_lower(_Base_ptr __p, _Arg&& __v)
2498 #else
2499  _M_insert_lower(_Base_ptr __p, const _Val& __v)
2500 #endif
2501  {
2502  bool __insert_left = (__p == _M_end()
2503  || !_M_impl._M_key_compare(_S_key(__p),
2504  _KeyOfValue()(__v)));
2505 
2506  _Base_ptr __z =
2507  _M_create_node(_GLIBCXX_FORWARD(_Arg, __v))->_M_base_ptr();
2508  _Node_traits::_S_insert_and_rebalance
2509  (__insert_left, __z, __p, this->_M_impl._M_header);
2510  ++_M_impl._M_node_count;
2511  return iterator(__z);
2512  }
2513 
2514  template<typename _Key, typename _Val, typename _KeyOfValue,
2515  typename _Compare, typename _Alloc>
2516 #if __cplusplus >= 201103L
2517  template<typename _Arg>
2518 #endif
2519  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2520  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2521 #if __cplusplus >= 201103L
2522  _M_insert_equal_lower(_Arg&& __v)
2523 #else
2524  _M_insert_equal_lower(const _Val& __v)
2525 #endif
2526  {
2527  _Base_ptr __x = _M_begin();
2528  _Base_ptr __y = _M_end();
2529  while (__x)
2530  {
2531  __y = __x;
2532  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
2533  _S_left(__x) : _S_right(__x);
2534  }
2535  return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
2536  }
2537 
2538  template<typename _Key, typename _Val, typename _KoV,
2539  typename _Compare, typename _Alloc>
2540  template<bool _MoveValues, typename _NodeGen>
2541  typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Base_ptr
2542  _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
2543  _M_copy(_Node_ptr __x, _Base_ptr __p, _NodeGen& __node_gen)
2544  {
2545  // Structural copy. __x and __p must be non-null.
2546  _Node_ptr __top = _M_clone_node<_MoveValues>(__x, __node_gen);
2547  _Base_ptr __top_base = __top->_M_base_ptr();
2548  __top->_M_parent = __p;
2549 
2550  __try
2551  {
2552  if (__x->_M_right)
2553  __top->_M_right =
2554  _M_copy<_MoveValues>(_S_right(__x), __top_base, __node_gen);
2555  __p = __top_base;
2556  __x = _S_left(__x);
2557 
2558  while (__x)
2559  {
2560  _Base_ptr __y =
2561  _M_clone_node<_MoveValues>(__x, __node_gen)->_M_base_ptr();
2562  __p->_M_left = __y;
2563  __y->_M_parent = __p;
2564  if (__x->_M_right)
2565  __y->_M_right = _M_copy<_MoveValues>(_S_right(__x),
2566  __y, __node_gen);
2567  __p = __y;
2568  __x = _S_left(__x);
2569  }
2570  }
2571  __catch(...)
2572  {
2573  _M_erase(__top);
2574  __throw_exception_again;
2575  }
2576  return __top_base;
2577  }
2578 
2579  template<typename _Key, typename _Val, typename _KeyOfValue,
2580  typename _Compare, typename _Alloc>
2581  void
2582  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2583  _M_erase(_Node_ptr __x)
2584  {
2585  // Erase without rebalancing.
2586  while (__x)
2587  {
2588  _M_erase(_S_right(__x));
2589  _Node_ptr __y = _S_left(__x);
2590  _M_drop_node(__x);
2591  __x = __y;
2592  }
2593  }
2594 
2595  template<typename _Key, typename _Val, typename _KeyOfValue,
2596  typename _Compare, typename _Alloc>
2597  typename _Rb_tree<_Key, _Val, _KeyOfValue,
2598  _Compare, _Alloc>::_Base_ptr
2599  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2600  _M_lower_bound(_Base_ptr __x, _Base_ptr __y,
2601  const _Key& __k) const
2602  {
2603  while (__x)
2604  if (!_M_impl._M_key_compare(_S_key(__x), __k))
2605  __y = __x, __x = _S_left(__x);
2606  else
2607  __x = _S_right(__x);
2608  return __y;
2609  }
2610 
2611  template<typename _Key, typename _Val, typename _KeyOfValue,
2612  typename _Compare, typename _Alloc>
2613  typename _Rb_tree<_Key, _Val, _KeyOfValue,
2614  _Compare, _Alloc>::_Base_ptr
2615  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2616  _M_upper_bound(_Base_ptr __x, _Base_ptr __y,
2617  const _Key& __k) const
2618  {
2619  while (__x)
2620  if (_M_impl._M_key_compare(__k, _S_key(__x)))
2621  __y = __x, __x = _S_left(__x);
2622  else
2623  __x = _S_right(__x);
2624  return __y;
2625  }
2626 
2627  template<typename _Key, typename _Val, typename _KeyOfValue,
2628  typename _Compare, typename _Alloc>
2629  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2630  _Compare, _Alloc>::iterator,
2631  typename _Rb_tree<_Key, _Val, _KeyOfValue,
2632  _Compare, _Alloc>::iterator>
2633  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2634  equal_range(const _Key& __k)
2635  {
2636  typedef pair<iterator, iterator> _Ret;
2637 
2638  _Base_ptr __x = _M_begin();
2639  _Base_ptr __y = _M_end();
2640  while (__x)
2641  {
2642  if (_M_impl._M_key_compare(_S_key(__x), __k))
2643  __x = _S_right(__x);
2644  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2645  __y = __x, __x = _S_left(__x);
2646  else
2647  {
2648  _Base_ptr __xu(__x);
2649  _Base_ptr __yu(__y);
2650  __y = __x, __x = _S_left(__x);
2651  __xu = _S_right(__xu);
2652  return _Ret(iterator(_M_lower_bound(__x, __y, __k)),
2653  iterator(_M_upper_bound(__xu, __yu, __k)));
2654  }
2655  }
2656  return _Ret(iterator(__y), iterator(__y));
2657  }
2658 
2659  template<typename _Key, typename _Val, typename _KeyOfValue,
2660  typename _Compare, typename _Alloc>
2661  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2662  _Compare, _Alloc>::const_iterator,
2663  typename _Rb_tree<_Key, _Val, _KeyOfValue,
2664  _Compare, _Alloc>::const_iterator>
2665  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2666  equal_range(const _Key& __k) const
2667  {
2668  typedef pair<const_iterator, const_iterator> _Ret;
2669 
2670  _Base_ptr __x = _M_begin();
2671  _Base_ptr __y = _M_end();
2672  while (__x)
2673  {
2674  if (_M_impl._M_key_compare(_S_key(__x), __k))
2675  __x = _S_right(__x);
2676  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
2677  __y = __x, __x = _S_left(__x);
2678  else
2679  {
2680  _Base_ptr __xu(__x);
2681  _Base_ptr __yu(__y);
2682  __y = __x, __x = _S_left(__x);
2683  __xu = _S_right(__xu);
2684  return _Ret(const_iterator(_M_lower_bound(__x, __y, __k)),
2685  const_iterator(_M_upper_bound(__xu, __yu, __k)));
2686  }
2687  }
2688  return _Ret(const_iterator(__y), const_iterator(__y));
2689  }
2690 
2691  template<typename _Key, typename _Val, typename _KeyOfValue,
2692  typename _Compare, typename _Alloc>
2693  void
2694  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2695  swap(_Rb_tree& __t)
2696  _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
2697  {
2698  if (!_M_root())
2699  {
2700  if (__t._M_root())
2701  _M_impl._M_move_data(__t._M_impl);
2702  }
2703  else if (!__t._M_root())
2704  __t._M_impl._M_move_data(_M_impl);
2705  else
2706  {
2707  std::swap(_M_root(),__t._M_root());
2708  std::swap(_M_leftmost(),__t._M_leftmost());
2709  std::swap(_M_rightmost(),__t._M_rightmost());
2710 
2711  _M_root()->_M_parent = _M_end();
2712  __t._M_root()->_M_parent = __t._M_end();
2713  std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
2714  }
2715  // No need to swap header's color as it does not change.
2716 
2717  using std::swap;
2718  swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
2719 
2720  _Node_alloc_traits::_S_on_swap(_M_get_Node_allocator(),
2721  __t._M_get_Node_allocator());
2722  }
2723 
2724  template<typename _Key, typename _Val, typename _KeyOfValue,
2725  typename _Compare, typename _Alloc>
2726  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2727  _Compare, _Alloc>::_Base_ptr,
2728  typename _Rb_tree<_Key, _Val, _KeyOfValue,
2729  _Compare, _Alloc>::_Base_ptr>
2730  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2731  _M_get_insert_unique_pos(const key_type& __k)
2732  {
2733  typedef pair<_Base_ptr, _Base_ptr> _Res;
2734  _Base_ptr __x = _M_begin();
2735  _Base_ptr __y = _M_end();
2736  bool __comp = true;
2737  while (__x)
2738  {
2739  __y = __x;
2740  __comp = _M_impl._M_key_compare(__k, _S_key(__x));
2741  __x = __comp ? _S_left(__x) : _S_right(__x);
2742  }
2743  iterator __j = iterator(__y);
2744  if (__comp)
2745  {
2746  if (__j == begin())
2747  return _Res(__x, __y);
2748  else
2749  --__j;
2750  }
2751  if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
2752  return _Res(__x, __y);
2753  return _Res(__j._M_node, _Base_ptr());
2754  }
2755 
2756  template<typename _Key, typename _Val, typename _KeyOfValue,
2757  typename _Compare, typename _Alloc>
2758  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2759  _Compare, _Alloc>::_Base_ptr,
2760  typename _Rb_tree<_Key, _Val, _KeyOfValue,
2761  _Compare, _Alloc>::_Base_ptr>
2762  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2763  _M_get_insert_equal_pos(const key_type& __k)
2764  {
2765  typedef pair<_Base_ptr, _Base_ptr> _Res;
2766  _Base_ptr __x = _M_begin();
2767  _Base_ptr __y = _M_end();
2768  while (__x)
2769  {
2770  __y = __x;
2771  __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
2772  _S_left(__x) : _S_right(__x);
2773  }
2774  return _Res(__x, __y);
2775  }
2776 
2777  template<typename _Key, typename _Val, typename _KeyOfValue,
2778  typename _Compare, typename _Alloc>
2779 #if __cplusplus >= 201103L
2780  template<typename _Arg>
2781 #endif
2782  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2783  _Compare, _Alloc>::iterator, bool>
2784  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2785 #if __cplusplus >= 201103L
2786  _M_insert_unique(_Arg&& __v)
2787 #else
2788  _M_insert_unique(const _Val& __v)
2789 #endif
2790  {
2791  typedef pair<iterator, bool> _Res;
2792  pair<_Base_ptr, _Base_ptr> __res
2793  = _M_get_insert_unique_pos(_KeyOfValue()(__v));
2794 
2795  if (__res.second)
2796  {
2797  _Alloc_node __an(*this);
2798  return _Res(_M_insert_(__res.first, __res.second,
2799  _GLIBCXX_FORWARD(_Arg, __v), __an),
2800  true);
2801  }
2802 
2803  return _Res(iterator(__res.first), false);
2804  }
2805 
2806  template<typename _Key, typename _Val, typename _KeyOfValue,
2807  typename _Compare, typename _Alloc>
2808 #if __cplusplus >= 201103L
2809  template<typename _Arg>
2810 #endif
2811  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2812  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2813 #if __cplusplus >= 201103L
2814  _M_insert_equal(_Arg&& __v)
2815 #else
2816  _M_insert_equal(const _Val& __v)
2817 #endif
2818  {
2819  pair<_Base_ptr, _Base_ptr> __res
2820  = _M_get_insert_equal_pos(_KeyOfValue()(__v));
2821  _Alloc_node __an(*this);
2822  return _M_insert_(__res.first, __res.second,
2823  _GLIBCXX_FORWARD(_Arg, __v), __an);
2824  }
2825 
2826  template<typename _Key, typename _Val, typename _KeyOfValue,
2827  typename _Compare, typename _Alloc>
2828  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2829  _Compare, _Alloc>::_Base_ptr,
2830  typename _Rb_tree<_Key, _Val, _KeyOfValue,
2831  _Compare, _Alloc>::_Base_ptr>
2832  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2833  _M_get_insert_hint_unique_pos(const_iterator __position,
2834  const key_type& __k)
2835  {
2836  typedef pair<_Base_ptr, _Base_ptr> _Res;
2837 
2838  // end()
2839  if (__position._M_node == _M_end())
2840  {
2841  if (size() > 0
2842  && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
2843  return _Res(_Base_ptr(), _M_rightmost());
2844  else
2845  return _M_get_insert_unique_pos(__k);
2846  }
2847  else if (_M_impl._M_key_compare(__k, _S_key(__position._M_node)))
2848  {
2849  // First, try before...
2850  iterator __before(__position._M_node);
2851  if (__position._M_node == _M_leftmost()) // begin()
2852  return _Res(_M_leftmost(), _M_leftmost());
2853  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
2854  {
2855  if (!_S_right(__before._M_node))
2856  return _Res(_Base_ptr(), __before._M_node);
2857  else
2858  return _Res(__position._M_node, __position._M_node);
2859  }
2860  else
2861  return _M_get_insert_unique_pos(__k);
2862  }
2863  else if (_M_impl._M_key_compare(_S_key(__position._M_node), __k))
2864  {
2865  // ... then try after.
2866  iterator __after(__position._M_node);
2867  if (__position._M_node == _M_rightmost())
2868  return _Res(_Base_ptr(), _M_rightmost());
2869  else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
2870  {
2871  if (!_S_right(__position._M_node))
2872  return _Res(_Base_ptr(), __position._M_node);
2873  else
2874  return _Res(__after._M_node, __after._M_node);
2875  }
2876  else
2877  return _M_get_insert_unique_pos(__k);
2878  }
2879  else
2880  // Equivalent keys.
2881  return _Res(__position._M_node, _Base_ptr());
2882  }
2883 
2884  template<typename _Key, typename _Val, typename _KeyOfValue,
2885  typename _Compare, typename _Alloc>
2886 #if __cplusplus >= 201103L
2887  template<typename _Arg, typename _NodeGen>
2888 #else
2889  template<typename _NodeGen>
2890 #endif
2891  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2892  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2893  _M_insert_unique_(const_iterator __position,
2894 #if __cplusplus >= 201103L
2895  _Arg&& __v,
2896 #else
2897  const _Val& __v,
2898 #endif
2899  _NodeGen& __node_gen)
2900  {
2901  pair<_Base_ptr, _Base_ptr> __res
2902  = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
2903 
2904  if (__res.second)
2905  return _M_insert_(__res.first, __res.second,
2906  _GLIBCXX_FORWARD(_Arg, __v),
2907  __node_gen);
2908  return iterator(__res.first);
2909  }
2910 
2911  template<typename _Key, typename _Val, typename _KeyOfValue,
2912  typename _Compare, typename _Alloc>
2913  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2914  _Compare, _Alloc>::_Base_ptr,
2915  typename _Rb_tree<_Key, _Val, _KeyOfValue,
2916  _Compare, _Alloc>::_Base_ptr>
2917  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2918  _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
2919  {
2920  typedef pair<_Base_ptr, _Base_ptr> _Res;
2921 
2922  // end()
2923  if (__position._M_node == _M_end())
2924  {
2925  if (size() > 0
2926  && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2927  return _Res(_Base_ptr(), _M_rightmost());
2928  else
2929  return _M_get_insert_equal_pos(__k);
2930  }
2931  else if (!_M_impl._M_key_compare(_S_key(__position._M_node), __k))
2932  {
2933  // First, try before...
2934  iterator __before(__position._M_node);
2935  if (__position._M_node == _M_leftmost()) // begin()
2936  return _Res(_M_leftmost(), _M_leftmost());
2937  else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2938  {
2939  if (!_S_right(__before._M_node))
2940  return _Res(_Base_ptr(), __before._M_node);
2941  else
2942  return _Res(__position._M_node, __position._M_node);
2943  }
2944  else
2945  return _M_get_insert_equal_pos(__k);
2946  }
2947  else
2948  {
2949  // ... then try after.
2950  iterator __after(__position._M_node);
2951  if (__position._M_node == _M_rightmost())
2952  return _Res(_Base_ptr(), _M_rightmost());
2953  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2954  {
2955  if (!_S_right(__position._M_node))
2956  return _Res(_Base_ptr(), __position._M_node);
2957  else
2958  return _Res(__after._M_node, __after._M_node);
2959  }
2960  else
2961  return _Res(_Base_ptr(), _Base_ptr());
2962  }
2963  }
2964 
2965  template<typename _Key, typename _Val, typename _KeyOfValue,
2966  typename _Compare, typename _Alloc>
2967 #if __cplusplus >= 201103L
2968  template<typename _Arg, typename _NodeGen>
2969 #else
2970  template<typename _NodeGen>
2971 #endif
2972  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2973  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2974  _M_insert_equal_(const_iterator __position,
2975 #if __cplusplus >= 201103L
2976  _Arg&& __v,
2977 #else
2978  const _Val& __v,
2979 #endif
2980  _NodeGen& __node_gen)
2981  {
2982  pair<_Base_ptr, _Base_ptr> __res
2983  = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2984 
2985  if (__res.second)
2986  return _M_insert_(__res.first, __res.second,
2987  _GLIBCXX_FORWARD(_Arg, __v),
2988  __node_gen);
2989 
2990  return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2991  }
2992 
2993 #if __cplusplus >= 201103L
2994  template<typename _Key, typename _Val, typename _KeyOfValue,
2995  typename _Compare, typename _Alloc>
2996  auto
2997  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2998  _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Node_ptr __z)
2999  -> iterator
3000  {
3001  bool __insert_left = (__x || __p == _M_end()
3002  || _M_impl._M_key_compare(_S_key(__z),
3003  _S_key(__p)));
3004 
3005  _Base_ptr __base_z = __z->_M_base_ptr();
3006  _Node_traits::_S_insert_and_rebalance
3007  (__insert_left, __base_z, __p, this->_M_impl._M_header);
3008  ++_M_impl._M_node_count;
3009  return iterator(__base_z);
3010  }
3011 
3012  template<typename _Key, typename _Val, typename _KeyOfValue,
3013  typename _Compare, typename _Alloc>
3014  auto
3015  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3016  _M_insert_lower_node(_Base_ptr __p, _Node_ptr __z)
3017  -> iterator
3018  {
3019  bool __insert_left = (__p == _M_end()
3020  || !_M_impl._M_key_compare(_S_key(__p),
3021  _S_key(__z)));
3022 
3023  _Base_ptr __base_z = __z->_M_base_ptr();
3024  _Node_traits::_S_insert_and_rebalance
3025  (__insert_left, __base_z, __p, this->_M_impl._M_header);
3026  ++_M_impl._M_node_count;
3027  return iterator(__base_z);
3028  }
3029 
3030  template<typename _Key, typename _Val, typename _KeyOfValue,
3031  typename _Compare, typename _Alloc>
3032  auto
3033  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3034  _M_insert_equal_lower_node(_Node_ptr __z)
3035  -> iterator
3036  {
3037  _Base_ptr __x = _M_begin();
3038  _Base_ptr __y = _M_end();
3039  while (__x)
3040  {
3041  __y = __x;
3042  __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
3043  _S_left(__x) : _S_right(__x);
3044  }
3045  return _M_insert_lower_node(__y, __z);
3046  }
3047 
3048  template<typename _Key, typename _Val, typename _KeyOfValue,
3049  typename _Compare, typename _Alloc>
3050  template<typename... _Args>
3051  auto
3052  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3053  _M_emplace_unique(_Args&&... __args)
3054  -> pair<iterator, bool>
3055  {
3056  _Auto_node __z(*this, std::forward<_Args>(__args)...);
3057  auto __res = _M_get_insert_unique_pos(__z._M_key());
3058  if (__res.second)
3059  return {__z._M_insert(__res), true};
3060  return {iterator(__res.first), false};
3061  }
3062 
3063  template<typename _Key, typename _Val, typename _KeyOfValue,
3064  typename _Compare, typename _Alloc>
3065  template<typename... _Args>
3066  auto
3067  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3068  _M_emplace_equal(_Args&&... __args)
3069  -> iterator
3070  {
3071  _Auto_node __z(*this, std::forward<_Args>(__args)...);
3072  auto __res = _M_get_insert_equal_pos(__z._M_key());
3073  return __z._M_insert(__res);
3074  }
3075 
3076  template<typename _Key, typename _Val, typename _KeyOfValue,
3077  typename _Compare, typename _Alloc>
3078  template<typename... _Args>
3079  auto
3080  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3081  _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
3082  -> iterator
3083  {
3084  _Auto_node __z(*this, std::forward<_Args>(__args)...);
3085  auto __res = _M_get_insert_hint_unique_pos(__pos, __z._M_key());
3086  if (__res.second)
3087  return __z._M_insert(__res);
3088  return iterator(__res.first);
3089  }
3090 
3091  template<typename _Key, typename _Val, typename _KeyOfValue,
3092  typename _Compare, typename _Alloc>
3093  template<typename... _Args>
3094  auto
3095  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3096  _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
3097  -> iterator
3098  {
3099  _Auto_node __z(*this, std::forward<_Args>(__args)...);
3100  auto __res = _M_get_insert_hint_equal_pos(__pos, __z._M_key());
3101  if (__res.second)
3102  return __z._M_insert(__res);
3103  return __z._M_insert_equal_lower();
3104  }
3105 #endif
3106 
3107 
3108  template<typename _Key, typename _Val, typename _KeyOfValue,
3109  typename _Compare, typename _Alloc>
3110  void
3111  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3112  _M_erase_aux(const_iterator __position)
3113  {
3114  _Base_ptr __y = _Node_traits::_S_rebalance_for_erase
3115  (__position._M_node, this->_M_impl._M_header);
3116  _M_drop_node(static_cast<_Node&>(*__y)._M_node_ptr());
3117  --_M_impl._M_node_count;
3118  }
3119 
3120  template<typename _Key, typename _Val, typename _KeyOfValue,
3121  typename _Compare, typename _Alloc>
3122  void
3123  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3124  _M_erase_aux(const_iterator __first, const_iterator __last)
3125  {
3126  if (__first == begin() && __last == end())
3127  clear();
3128  else
3129  while (__first != __last)
3130  _M_erase_aux(__first++);
3131  }
3132 
3133  template<typename _Key, typename _Val, typename _KeyOfValue,
3134  typename _Compare, typename _Alloc>
3135  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
3136  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3137  erase(const _Key& __x)
3138  {
3139  pair<iterator, iterator> __p = equal_range(__x);
3140  const size_type __old_size = size();
3141  _M_erase_aux(__p.first, __p.second);
3142  return __old_size - size();
3143  }
3144 
3145  template<typename _Key, typename _Val, typename _KeyOfValue,
3146  typename _Compare, typename _Alloc>
3147  typename _Rb_tree<_Key, _Val, _KeyOfValue,
3148  _Compare, _Alloc>::iterator
3149  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3150  find(const _Key& __k)
3151  {
3152  iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));
3153  return (__j == end()
3154  || _M_impl._M_key_compare(__k,
3155  _S_key(__j._M_node))) ? end() : __j;
3156  }
3157 
3158  template<typename _Key, typename _Val, typename _KeyOfValue,
3159  typename _Compare, typename _Alloc>
3160  typename _Rb_tree<_Key, _Val, _KeyOfValue,
3161  _Compare, _Alloc>::const_iterator
3162  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3163  find(const _Key& __k) const
3164  {
3165  const_iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k));
3166  return (__j == end()
3167  || _M_impl._M_key_compare(__k,
3168  _S_key(__j._M_node))) ? end() : __j;
3169  }
3170 
3171  template<typename _Key, typename _Val, typename _KeyOfValue,
3172  typename _Compare, typename _Alloc>
3173  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
3174  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
3175  count(const _Key& __k) const
3176  {
3177  pair<const_iterator, const_iterator> __p = equal_range(__k);
3178  const size_type __n = std::distance(__p.first, __p.second);
3179  return __n;
3180  }
3181 
3182  _GLIBCXX_PURE unsigned int
3183  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
3184  const _Rb_tree_node_base* __root) throw ();
3185 
3186  template<typename _Key, typename _Val, typename _KeyOfValue,
3187  typename _Compare, typename _Alloc>
3188  bool
3189  _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
3190  {
3191  if (_M_impl._M_node_count == 0 || begin() == end())
3192  return _M_impl._M_node_count == 0 && begin() == end()
3193  && this->_M_impl._M_header._M_left == _M_end()
3194  && this->_M_impl._M_header._M_right == _M_end();
3195 
3196  unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
3197  for (const_iterator __it = begin(); __it != end(); ++__it)
3198  {
3199  _Base_ptr __x = __it._M_node;
3200  _Base_ptr __L = _S_left(__x);
3201  _Base_ptr __R = _S_right(__x);
3202 
3203  if (__x->_M_color == _S_red)
3204  if ((__L && __L->_M_color == _S_red)
3205  || (__R && __R->_M_color == _S_red))
3206  return false;
3207 
3208  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
3209  return false;
3210  if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
3211  return false;
3212 
3213  if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
3214  return false;
3215  }
3216 
3217  if (_M_leftmost() != _Node_base::_S_minimum(_M_root()))
3218  return false;
3219  if (_M_rightmost() != _Node_base::_S_maximum(_M_root()))
3220  return false;
3221  return true;
3222  }
3223 
3224 #ifdef __glibcxx_node_extract // >= C++17
3225  // Allow access to internals of compatible _Rb_tree specializations.
3226  template<typename _Key, typename _Val, typename _Sel, typename _Cmp1,
3227  typename _Alloc, typename _Cmp2>
3228  struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
3229  _Cmp2>
3230  {
3231  private:
3232  friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;
3233 
3234  static auto&
3235  _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
3236  { return __tree._M_impl; }
3237  };
3238 #endif // C++17
3239 
3240 _GLIBCXX_END_NAMESPACE_VERSION
3241 } // namespace
3242 
3243 #endif
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:826
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:434
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:116
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:119
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:52
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition: move.h:72
constexpr _Tp * addressof(_Tp &__r) noexcept
Returns the actual address of the object or function referenced by r, even in the presence of an over...
Definition: move.h:176
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1251
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1229
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr auto rbegin(_Container &__cont) noexcept(noexcept(__cont.rbegin())) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
Definition: range_access.h:156
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:294
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:274
constexpr auto rend(_Container &__cont) noexcept(noexcept(__cont.rend())) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
Definition: range_access.h:180
constexpr _Iterator __base(_Iterator __it)
Uniform interface to C++98 and C++11 allocators.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static constexpr size_type max_size(const _Alloc &__a) noexcept
The maximum supported allocation size.