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