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