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