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