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