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