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