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