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