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