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