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