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  {
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,
845  std::move(__x._M_get_Node_allocator()))
846  {
847  if (__x._M_root() != 0)
848  _M_move_data(__x, std::true_type());
849  }
850 
851  _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
852  : _Rb_tree(std::move(__x), _Node_allocator(__a))
853  { }
854 
855  _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
856 #endif
857 
858  ~_Rb_tree() _GLIBCXX_NOEXCEPT
859  { _M_erase(_M_begin()); }
860 
861  _Rb_tree&
862  operator=(const _Rb_tree& __x);
863 
864  // Accessors.
865  _Compare
866  key_comp() const
867  { return _M_impl._M_key_compare; }
868 
869  iterator
870  begin() _GLIBCXX_NOEXCEPT
871  { return iterator(this->_M_impl._M_header._M_left); }
872 
873  const_iterator
874  begin() const _GLIBCXX_NOEXCEPT
875  { return const_iterator(this->_M_impl._M_header._M_left); }
876 
877  iterator
878  end() _GLIBCXX_NOEXCEPT
879  { return iterator(&this->_M_impl._M_header); }
880 
881  const_iterator
882  end() const _GLIBCXX_NOEXCEPT
883  { return const_iterator(&this->_M_impl._M_header); }
884 
885  reverse_iterator
886  rbegin() _GLIBCXX_NOEXCEPT
887  { return reverse_iterator(end()); }
888 
889  const_reverse_iterator
890  rbegin() const _GLIBCXX_NOEXCEPT
891  { return const_reverse_iterator(end()); }
892 
893  reverse_iterator
894  rend() _GLIBCXX_NOEXCEPT
895  { return reverse_iterator(begin()); }
896 
897  const_reverse_iterator
898  rend() const _GLIBCXX_NOEXCEPT
899  { return const_reverse_iterator(begin()); }
900 
901  bool
902  empty() const _GLIBCXX_NOEXCEPT
903  { return _M_impl._M_node_count == 0; }
904 
905  size_type
906  size() const _GLIBCXX_NOEXCEPT
907  { return _M_impl._M_node_count; }
908 
909  size_type
910  max_size() const _GLIBCXX_NOEXCEPT
911  { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
912 
913  void
914 #if __cplusplus >= 201103L
915  swap(_Rb_tree& __t) noexcept(_Alloc_traits::_S_nothrow_swap());
916 #else
917  swap(_Rb_tree& __t);
918 #endif
919 
920  // Insert/erase.
921 #if __cplusplus >= 201103L
922  template<typename _Arg>
923  pair<iterator, bool>
924  _M_insert_unique(_Arg&& __x);
925 
926  template<typename _Arg>
927  iterator
928  _M_insert_equal(_Arg&& __x);
929 
930  template<typename _Arg, typename _NodeGen>
931  iterator
932  _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
933 
934  template<typename _Arg>
935  iterator
936  _M_insert_unique_(const_iterator __pos, _Arg&& __x)
937  {
938  _Alloc_node __an(*this);
939  return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
940  }
941 
942  template<typename _Arg, typename _NodeGen>
943  iterator
944  _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
945 
946  template<typename _Arg>
947  iterator
948  _M_insert_equal_(const_iterator __pos, _Arg&& __x)
949  {
950  _Alloc_node __an(*this);
951  return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
952  }
953 
954  template<typename... _Args>
955  pair<iterator, bool>
956  _M_emplace_unique(_Args&&... __args);
957 
958  template<typename... _Args>
959  iterator
960  _M_emplace_equal(_Args&&... __args);
961 
962  template<typename... _Args>
963  iterator
964  _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
965 
966  template<typename... _Args>
967  iterator
968  _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
969 #else
970  pair<iterator, bool>
971  _M_insert_unique(const value_type& __x);
972 
973  iterator
974  _M_insert_equal(const value_type& __x);
975 
976  template<typename _NodeGen>
977  iterator
978  _M_insert_unique_(const_iterator __pos, const value_type& __x,
979  _NodeGen&);
980 
981  iterator
982  _M_insert_unique_(const_iterator __pos, const value_type& __x)
983  {
984  _Alloc_node __an(*this);
985  return _M_insert_unique_(__pos, __x, __an);
986  }
987 
988  template<typename _NodeGen>
989  iterator
990  _M_insert_equal_(const_iterator __pos, const value_type& __x,
991  _NodeGen&);
992  iterator
993  _M_insert_equal_(const_iterator __pos, const value_type& __x)
994  {
995  _Alloc_node __an(*this);
996  return _M_insert_equal_(__pos, __x, __an);
997  }
998 #endif
999 
1000  template<typename _InputIterator>
1001  void
1002  _M_insert_unique(_InputIterator __first, _InputIterator __last);
1003 
1004  template<typename _InputIterator>
1005  void
1006  _M_insert_equal(_InputIterator __first, _InputIterator __last);
1007 
1008  private:
1009  void
1010  _M_erase_aux(const_iterator __position);
1011 
1012  void
1013  _M_erase_aux(const_iterator __first, const_iterator __last);
1014 
1015  public:
1016 #if __cplusplus >= 201103L
1017  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1018  // DR 130. Associative erase should return an iterator.
1019  _GLIBCXX_ABI_TAG_CXX11
1020  iterator
1021  erase(const_iterator __position)
1022  {
1023  const_iterator __result = __position;
1024  ++__result;
1025  _M_erase_aux(__position);
1026  return __result._M_const_cast();
1027  }
1028 
1029  // LWG 2059.
1030  _GLIBCXX_ABI_TAG_CXX11
1031  iterator
1032  erase(iterator __position)
1033  {
1034  iterator __result = __position;
1035  ++__result;
1036  _M_erase_aux(__position);
1037  return __result;
1038  }
1039 #else
1040  void
1041  erase(iterator __position)
1042  { _M_erase_aux(__position); }
1043 
1044  void
1045  erase(const_iterator __position)
1046  { _M_erase_aux(__position); }
1047 #endif
1048  size_type
1049  erase(const key_type& __x);
1050 
1051 #if __cplusplus >= 201103L
1052  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1053  // DR 130. Associative erase should return an iterator.
1054  _GLIBCXX_ABI_TAG_CXX11
1055  iterator
1056  erase(const_iterator __first, const_iterator __last)
1057  {
1058  _M_erase_aux(__first, __last);
1059  return __last._M_const_cast();
1060  }
1061 #else
1062  void
1063  erase(iterator __first, iterator __last)
1064  { _M_erase_aux(__first, __last); }
1065 
1066  void
1067  erase(const_iterator __first, const_iterator __last)
1068  { _M_erase_aux(__first, __last); }
1069 #endif
1070  void
1071  erase(const key_type* __first, const key_type* __last);
1072 
1073  void
1074  clear() _GLIBCXX_NOEXCEPT
1075  {
1076  _M_erase(_M_begin());
1077  _M_impl._M_reset();
1078  }
1079 
1080  // Set operations.
1081  iterator
1082  find(const key_type& __k);
1083 
1084  const_iterator
1085  find(const key_type& __k) const;
1086 
1087  size_type
1088  count(const key_type& __k) const;
1089 
1090  iterator
1091  lower_bound(const key_type& __k)
1092  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1093 
1094  const_iterator
1095  lower_bound(const key_type& __k) const
1096  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1097 
1098  iterator
1099  upper_bound(const key_type& __k)
1100  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1101 
1102  const_iterator
1103  upper_bound(const key_type& __k) const
1104  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1105 
1106  pair<iterator, iterator>
1107  equal_range(const key_type& __k);
1108 
1109  pair<const_iterator, const_iterator>
1110  equal_range(const key_type& __k) const;
1111 
1112 #if __cplusplus > 201103L
1113  template<typename _Cmp, typename _Kt, typename = __void_t<>>
1114  struct __is_transparent { };
1115 
1116  template<typename _Cmp, typename _Kt>
1117  struct
1118  __is_transparent<_Cmp, _Kt, __void_t<typename _Cmp::is_transparent>>
1119  { typedef void type; };
1120 
1121  static auto _S_iter(_Link_type __x) { return iterator(__x); }
1122 
1123  static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); }
1124 
1125  template<typename _Cmp, typename _Link, typename _Kt>
1126  static auto
1127  _S_lower_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
1128  {
1129  while (__x != 0)
1130  if (!__cmp(_S_key(__x), __k))
1131  __y = __x, __x = _S_left(__x);
1132  else
1133  __x = _S_right(__x);
1134  return _S_iter(__y);
1135  }
1136 
1137  template<typename _Cmp, typename _Link, typename _Kt>
1138  static auto
1139  _S_upper_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
1140  {
1141  while (__x != 0)
1142  if (__cmp(__k, _S_key(__x)))
1143  __y = __x, __x = _S_left(__x);
1144  else
1145  __x = _S_right(__x);
1146  return _S_iter(__y);
1147  }
1148 
1149  template<typename _Kt,
1150  typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1151  iterator
1152  _M_find_tr(const _Kt& __k)
1153  {
1154  auto& __cmp = _M_impl._M_key_compare;
1155  auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1156  return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
1157  ? end() : __j;
1158  }
1159 
1160  template<typename _Kt,
1161  typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1162  const_iterator
1163  _M_find_tr(const _Kt& __k) const
1164  {
1165  auto& __cmp = _M_impl._M_key_compare;
1166  auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1167  return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
1168  ? end() : __j;
1169  }
1170 
1171  template<typename _Kt,
1172  typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1173  size_type
1174  _M_count_tr(const _Kt& __k) const
1175  {
1176  auto __p = _M_equal_range_tr(__k);
1177  return std::distance(__p.first, __p.second);
1178  }
1179 
1180  template<typename _Kt,
1181  typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1182  iterator
1183  _M_lower_bound_tr(const _Kt& __k)
1184  {
1185  auto& __cmp = _M_impl._M_key_compare;
1186  return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1187  }
1188 
1189  template<typename _Kt,
1190  typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1191  const_iterator
1192  _M_lower_bound_tr(const _Kt& __k) const
1193  {
1194  auto& __cmp = _M_impl._M_key_compare;
1195  return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1196  }
1197 
1198  template<typename _Kt,
1199  typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1200  iterator
1201  _M_upper_bound_tr(const _Kt& __k)
1202  {
1203  auto& __cmp = _M_impl._M_key_compare;
1204  return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1205  }
1206 
1207  template<typename _Kt,
1208  typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1209  const_iterator
1210  _M_upper_bound_tr(const _Kt& __k) const
1211  {
1212  auto& __cmp = _M_impl._M_key_compare;
1213  return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1214  }
1215 
1216  template<typename _Kt,
1217  typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1218  pair<iterator, iterator>
1219  _M_equal_range_tr(const _Kt& __k)
1220  {
1221  auto __low = _M_lower_bound_tr(__k);
1222  auto __high = __low;
1223  auto& __cmp = _M_impl._M_key_compare;
1224  while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1225  ++__high;
1226  return { __low, __high };
1227  }
1228 
1229  template<typename _Kt,
1230  typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1231  pair<const_iterator, const_iterator>
1232  _M_equal_range_tr(const _Kt& __k) const
1233  {
1234  auto __low = _M_lower_bound_tr(__k);
1235  auto __high = __low;
1236  auto& __cmp = _M_impl._M_key_compare;
1237  while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1238  ++__high;
1239  return { __low, __high };
1240  }
1241 #endif
1242 
1243  // Debugging.
1244  bool
1245  __rb_verify() const;
1246 
1247 #if __cplusplus >= 201103L
1248  _Rb_tree&
1249  operator=(_Rb_tree&&)
1250  noexcept(_Alloc_traits::_S_nothrow_move()
1251  && is_nothrow_move_assignable<_Compare>::value);
1252 
1253  template<typename _Iterator>
1254  void
1255  _M_assign_unique(_Iterator, _Iterator);
1256 
1257  template<typename _Iterator>
1258  void
1259  _M_assign_equal(_Iterator, _Iterator);
1260 
1261  private:
1262  // Move elements from container with equal allocator.
1263  void
1264  _M_move_data(_Rb_tree&, std::true_type);
1265 
1266  // Move elements from container with possibly non-equal allocator,
1267  // which might result in a copy not a move.
1268  void
1269  _M_move_data(_Rb_tree&, std::false_type);
1270 
1271  // Move assignment from container with equal allocator.
1272  void
1273  _M_move_assign(_Rb_tree&, std::true_type);
1274 
1275  // Move assignment from container with possibly non-equal allocator,
1276  // which might result in a copy not a move.
1277  void
1278  _M_move_assign(_Rb_tree&, std::false_type);
1279 #endif
1280  };
1281 
1282  template<typename _Key, typename _Val, typename _KeyOfValue,
1283  typename _Compare, typename _Alloc>
1284  inline bool
1285  operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1286  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1287  {
1288  return __x.size() == __y.size()
1289  && std::equal(__x.begin(), __x.end(), __y.begin());
1290  }
1291 
1292  template<typename _Key, typename _Val, typename _KeyOfValue,
1293  typename _Compare, typename _Alloc>
1294  inline bool
1295  operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1296  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1297  {
1298  return std::lexicographical_compare(__x.begin(), __x.end(),
1299  __y.begin(), __y.end());
1300  }
1301 
1302  template<typename _Key, typename _Val, typename _KeyOfValue,
1303  typename _Compare, typename _Alloc>
1304  inline bool
1305  operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1306  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1307  { return !(__x == __y); }
1308 
1309  template<typename _Key, typename _Val, typename _KeyOfValue,
1310  typename _Compare, typename _Alloc>
1311  inline bool
1312  operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1313  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1314  { return __y < __x; }
1315 
1316  template<typename _Key, typename _Val, typename _KeyOfValue,
1317  typename _Compare, typename _Alloc>
1318  inline bool
1319  operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1320  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1321  { return !(__y < __x); }
1322 
1323  template<typename _Key, typename _Val, typename _KeyOfValue,
1324  typename _Compare, typename _Alloc>
1325  inline bool
1326  operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1327  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1328  { return !(__x < __y); }
1329 
1330  template<typename _Key, typename _Val, typename _KeyOfValue,
1331  typename _Compare, typename _Alloc>
1332  inline void
1333  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1334  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1335  { __x.swap(__y); }
1336 
1337 #if __cplusplus >= 201103L
1338  template<typename _Key, typename _Val, typename _KeyOfValue,
1339  typename _Compare, typename _Alloc>
1340  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1341  _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1342  : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
1343  {
1344  using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>;
1345  if (__x._M_root() != nullptr)
1346  _M_move_data(__x, __eq());
1347  }
1348 
1349  template<typename _Key, typename _Val, typename _KeyOfValue,
1350  typename _Compare, typename _Alloc>
1351  void
1352  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1353  _M_move_data(_Rb_tree& __x, std::true_type)
1354  {
1355  _M_root() = __x._M_root();
1356  _M_leftmost() = __x._M_leftmost();
1357  _M_rightmost() = __x._M_rightmost();
1358  _M_root()->_M_parent = _M_end();
1359 
1360  __x._M_root() = 0;
1361  __x._M_leftmost() = __x._M_end();
1362  __x._M_rightmost() = __x._M_end();
1363 
1364  this->_M_impl._M_node_count = __x._M_impl._M_node_count;
1365  __x._M_impl._M_node_count = 0;
1366  }
1367 
1368  template<typename _Key, typename _Val, typename _KeyOfValue,
1369  typename _Compare, typename _Alloc>
1370  void
1371  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1372  _M_move_data(_Rb_tree& __x, std::false_type)
1373  {
1374  if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1375  _M_move_data(__x, std::true_type());
1376  else
1377  {
1378  _Alloc_node __an(*this);
1379  auto __lbd =
1380  [&__an](const value_type& __cval)
1381  {
1382  auto& __val = const_cast<value_type&>(__cval);
1383  return __an(std::move_if_noexcept(__val));
1384  };
1385  _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1386  _M_leftmost() = _S_minimum(_M_root());
1387  _M_rightmost() = _S_maximum(_M_root());
1388  _M_impl._M_node_count = __x._M_impl._M_node_count;
1389  }
1390  }
1391 
1392  template<typename _Key, typename _Val, typename _KeyOfValue,
1393  typename _Compare, typename _Alloc>
1394  inline void
1395  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1396  _M_move_assign(_Rb_tree& __x, true_type)
1397  {
1398  clear();
1399  if (__x._M_root() != nullptr)
1400  _M_move_data(__x, std::true_type());
1401  std::__alloc_on_move(_M_get_Node_allocator(),
1402  __x._M_get_Node_allocator());
1403  }
1404 
1405  template<typename _Key, typename _Val, typename _KeyOfValue,
1406  typename _Compare, typename _Alloc>
1407  void
1408  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1409  _M_move_assign(_Rb_tree& __x, false_type)
1410  {
1411  if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1412  return _M_move_assign(__x, true_type{});
1413 
1414  // Try to move each node reusing existing nodes and copying __x nodes
1415  // structure.
1416  _Reuse_or_alloc_node __roan(*this);
1417  _M_impl._M_reset();
1418  if (__x._M_root() != nullptr)
1419  {
1420  auto __lbd =
1421  [&__roan](const value_type& __cval)
1422  {
1423  auto& __val = const_cast<value_type&>(__cval);
1424  return __roan(std::move_if_noexcept(__val));
1425  };
1426  _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1427  _M_leftmost() = _S_minimum(_M_root());
1428  _M_rightmost() = _S_maximum(_M_root());
1429  _M_impl._M_node_count = __x._M_impl._M_node_count;
1430  __x.clear();
1431  }
1432  }
1433 
1434  template<typename _Key, typename _Val, typename _KeyOfValue,
1435  typename _Compare, typename _Alloc>
1436  inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1437  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1438  operator=(_Rb_tree&& __x)
1439  noexcept(_Alloc_traits::_S_nothrow_move()
1440  && is_nothrow_move_assignable<_Compare>::value)
1441  {
1442  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1443  constexpr bool __move_storage =
1444  _Alloc_traits::_S_propagate_on_move_assign()
1445  || _Alloc_traits::_S_always_equal();
1446  _M_move_assign(__x, __bool_constant<__move_storage>());
1447  return *this;
1448  }
1449 
1450  template<typename _Key, typename _Val, typename _KeyOfValue,
1451  typename _Compare, typename _Alloc>
1452  template<typename _Iterator>
1453  void
1454  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1455  _M_assign_unique(_Iterator __first, _Iterator __last)
1456  {
1457  _Reuse_or_alloc_node __roan(*this);
1458  _M_impl._M_reset();
1459  for (; __first != __last; ++__first)
1460  _M_insert_unique_(end(), *__first, __roan);
1461  }
1462 
1463  template<typename _Key, typename _Val, typename _KeyOfValue,
1464  typename _Compare, typename _Alloc>
1465  template<typename _Iterator>
1466  void
1467  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1468  _M_assign_equal(_Iterator __first, _Iterator __last)
1469  {
1470  _Reuse_or_alloc_node __roan(*this);
1471  _M_impl._M_reset();
1472  for (; __first != __last; ++__first)
1473  _M_insert_equal_(end(), *__first, __roan);
1474  }
1475 #endif
1476 
1477  template<typename _Key, typename _Val, typename _KeyOfValue,
1478  typename _Compare, typename _Alloc>
1479  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1480  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1481  operator=(const _Rb_tree& __x)
1482  {
1483  if (this != &__x)
1484  {
1485  // Note that _Key may be a constant type.
1486 #if __cplusplus >= 201103L
1487  if (_Alloc_traits::_S_propagate_on_copy_assign())
1488  {
1489  auto& __this_alloc = this->_M_get_Node_allocator();
1490  auto& __that_alloc = __x._M_get_Node_allocator();
1491  if (!_Alloc_traits::_S_always_equal()
1492  && __this_alloc != __that_alloc)
1493  {
1494  // Replacement allocator cannot free existing storage, we need
1495  // to erase nodes first.
1496  clear();
1497  std::__alloc_on_copy(__this_alloc, __that_alloc);
1498  }
1499  }
1500 #endif
1501 
1502  _Reuse_or_alloc_node __roan(*this);
1503  _M_impl._M_reset();
1504  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1505  if (__x._M_root() != 0)
1506  {
1507  _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
1508  _M_leftmost() = _S_minimum(_M_root());
1509  _M_rightmost() = _S_maximum(_M_root());
1510  _M_impl._M_node_count = __x._M_impl._M_node_count;
1511  }
1512  }
1513 
1514  return *this;
1515  }
1516 
1517  template<typename _Key, typename _Val, typename _KeyOfValue,
1518  typename _Compare, typename _Alloc>
1519 #if __cplusplus >= 201103L
1520  template<typename _Arg, typename _NodeGen>
1521 #else
1522  template<typename _NodeGen>
1523 #endif
1524  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1525  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1526  _M_insert_(_Base_ptr __x, _Base_ptr __p,
1527 #if __cplusplus >= 201103L
1528  _Arg&& __v,
1529 #else
1530  const _Val& __v,
1531 #endif
1532  _NodeGen& __node_gen)
1533  {
1534  bool __insert_left = (__x != 0 || __p == _M_end()
1535  || _M_impl._M_key_compare(_KeyOfValue()(__v),
1536  _S_key(__p)));
1537 
1538  _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1539 
1540  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1541  this->_M_impl._M_header);
1542  ++_M_impl._M_node_count;
1543  return iterator(__z);
1544  }
1545 
1546  template<typename _Key, typename _Val, typename _KeyOfValue,
1547  typename _Compare, typename _Alloc>
1548 #if __cplusplus >= 201103L
1549  template<typename _Arg>
1550 #endif
1551  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1552  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1553 #if __cplusplus >= 201103L
1554  _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1555 #else
1556  _M_insert_lower(_Base_ptr __p, const _Val& __v)
1557 #endif
1558  {
1559  bool __insert_left = (__p == _M_end()
1560  || !_M_impl._M_key_compare(_S_key(__p),
1561  _KeyOfValue()(__v)));
1562 
1563  _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1564 
1565  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1566  this->_M_impl._M_header);
1567  ++_M_impl._M_node_count;
1568  return iterator(__z);
1569  }
1570 
1571  template<typename _Key, typename _Val, typename _KeyOfValue,
1572  typename _Compare, typename _Alloc>
1573 #if __cplusplus >= 201103L
1574  template<typename _Arg>
1575 #endif
1576  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1577  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1578 #if __cplusplus >= 201103L
1579  _M_insert_equal_lower(_Arg&& __v)
1580 #else
1581  _M_insert_equal_lower(const _Val& __v)
1582 #endif
1583  {
1584  _Link_type __x = _M_begin();
1585  _Link_type __y = _M_end();
1586  while (__x != 0)
1587  {
1588  __y = __x;
1589  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1590  _S_left(__x) : _S_right(__x);
1591  }
1592  return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1593  }
1594 
1595  template<typename _Key, typename _Val, typename _KoV,
1596  typename _Compare, typename _Alloc>
1597  template<typename _NodeGen>
1598  typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1599  _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1600  _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen& __node_gen)
1601  {
1602  // Structural copy. __x and __p must be non-null.
1603  _Link_type __top = _M_clone_node(__x, __node_gen);
1604  __top->_M_parent = __p;
1605 
1606  __try
1607  {
1608  if (__x->_M_right)
1609  __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1610  __p = __top;
1611  __x = _S_left(__x);
1612 
1613  while (__x != 0)
1614  {
1615  _Link_type __y = _M_clone_node(__x, __node_gen);
1616  __p->_M_left = __y;
1617  __y->_M_parent = __p;
1618  if (__x->_M_right)
1619  __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1620  __p = __y;
1621  __x = _S_left(__x);
1622  }
1623  }
1624  __catch(...)
1625  {
1626  _M_erase(__top);
1627  __throw_exception_again;
1628  }
1629  return __top;
1630  }
1631 
1632  template<typename _Key, typename _Val, typename _KeyOfValue,
1633  typename _Compare, typename _Alloc>
1634  void
1635  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1636  _M_erase(_Link_type __x)
1637  {
1638  // Erase without rebalancing.
1639  while (__x != 0)
1640  {
1641  _M_erase(_S_right(__x));
1642  _Link_type __y = _S_left(__x);
1643  _M_drop_node(__x);
1644  __x = __y;
1645  }
1646  }
1647 
1648  template<typename _Key, typename _Val, typename _KeyOfValue,
1649  typename _Compare, typename _Alloc>
1650  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1651  _Compare, _Alloc>::iterator
1652  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1653  _M_lower_bound(_Link_type __x, _Link_type __y,
1654  const _Key& __k)
1655  {
1656  while (__x != 0)
1657  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1658  __y = __x, __x = _S_left(__x);
1659  else
1660  __x = _S_right(__x);
1661  return iterator(__y);
1662  }
1663 
1664  template<typename _Key, typename _Val, typename _KeyOfValue,
1665  typename _Compare, typename _Alloc>
1666  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1667  _Compare, _Alloc>::const_iterator
1668  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1669  _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1670  const _Key& __k) const
1671  {
1672  while (__x != 0)
1673  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1674  __y = __x, __x = _S_left(__x);
1675  else
1676  __x = _S_right(__x);
1677  return const_iterator(__y);
1678  }
1679 
1680  template<typename _Key, typename _Val, typename _KeyOfValue,
1681  typename _Compare, typename _Alloc>
1682  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1683  _Compare, _Alloc>::iterator
1684  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1685  _M_upper_bound(_Link_type __x, _Link_type __y,
1686  const _Key& __k)
1687  {
1688  while (__x != 0)
1689  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1690  __y = __x, __x = _S_left(__x);
1691  else
1692  __x = _S_right(__x);
1693  return iterator(__y);
1694  }
1695 
1696  template<typename _Key, typename _Val, typename _KeyOfValue,
1697  typename _Compare, typename _Alloc>
1698  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1699  _Compare, _Alloc>::const_iterator
1700  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1701  _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1702  const _Key& __k) const
1703  {
1704  while (__x != 0)
1705  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1706  __y = __x, __x = _S_left(__x);
1707  else
1708  __x = _S_right(__x);
1709  return const_iterator(__y);
1710  }
1711 
1712  template<typename _Key, typename _Val, typename _KeyOfValue,
1713  typename _Compare, typename _Alloc>
1714  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1715  _Compare, _Alloc>::iterator,
1716  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1717  _Compare, _Alloc>::iterator>
1718  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1719  equal_range(const _Key& __k)
1720  {
1721  _Link_type __x = _M_begin();
1722  _Link_type __y = _M_end();
1723  while (__x != 0)
1724  {
1725  if (_M_impl._M_key_compare(_S_key(__x), __k))
1726  __x = _S_right(__x);
1727  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1728  __y = __x, __x = _S_left(__x);
1729  else
1730  {
1731  _Link_type __xu(__x), __yu(__y);
1732  __y = __x, __x = _S_left(__x);
1733  __xu = _S_right(__xu);
1734  return pair<iterator,
1735  iterator>(_M_lower_bound(__x, __y, __k),
1736  _M_upper_bound(__xu, __yu, __k));
1737  }
1738  }
1739  return pair<iterator, iterator>(iterator(__y),
1740  iterator(__y));
1741  }
1742 
1743  template<typename _Key, typename _Val, typename _KeyOfValue,
1744  typename _Compare, typename _Alloc>
1745  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1746  _Compare, _Alloc>::const_iterator,
1747  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1748  _Compare, _Alloc>::const_iterator>
1749  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1750  equal_range(const _Key& __k) const
1751  {
1752  _Const_Link_type __x = _M_begin();
1753  _Const_Link_type __y = _M_end();
1754  while (__x != 0)
1755  {
1756  if (_M_impl._M_key_compare(_S_key(__x), __k))
1757  __x = _S_right(__x);
1758  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1759  __y = __x, __x = _S_left(__x);
1760  else
1761  {
1762  _Const_Link_type __xu(__x), __yu(__y);
1763  __y = __x, __x = _S_left(__x);
1764  __xu = _S_right(__xu);
1765  return pair<const_iterator,
1766  const_iterator>(_M_lower_bound(__x, __y, __k),
1767  _M_upper_bound(__xu, __yu, __k));
1768  }
1769  }
1770  return pair<const_iterator, const_iterator>(const_iterator(__y),
1771  const_iterator(__y));
1772  }
1773 
1774  template<typename _Key, typename _Val, typename _KeyOfValue,
1775  typename _Compare, typename _Alloc>
1776  void
1777  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1778  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1779 #if __cplusplus >= 201103L
1780  noexcept(_Alloc_traits::_S_nothrow_swap())
1781 #endif
1782  {
1783  if (_M_root() == 0)
1784  {
1785  if (__t._M_root() != 0)
1786  {
1787  _M_root() = __t._M_root();
1788  _M_leftmost() = __t._M_leftmost();
1789  _M_rightmost() = __t._M_rightmost();
1790  _M_root()->_M_parent = _M_end();
1791  _M_impl._M_node_count = __t._M_impl._M_node_count;
1792 
1793  __t._M_impl._M_reset();
1794  }
1795  }
1796  else if (__t._M_root() == 0)
1797  {
1798  __t._M_root() = _M_root();
1799  __t._M_leftmost() = _M_leftmost();
1800  __t._M_rightmost() = _M_rightmost();
1801  __t._M_root()->_M_parent = __t._M_end();
1802  __t._M_impl._M_node_count = _M_impl._M_node_count;
1803 
1804  _M_impl._M_reset();
1805  }
1806  else
1807  {
1808  std::swap(_M_root(),__t._M_root());
1809  std::swap(_M_leftmost(),__t._M_leftmost());
1810  std::swap(_M_rightmost(),__t._M_rightmost());
1811 
1812  _M_root()->_M_parent = _M_end();
1813  __t._M_root()->_M_parent = __t._M_end();
1814  std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1815  }
1816  // No need to swap header's color as it does not change.
1817  std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1818 
1819  _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
1820  __t._M_get_Node_allocator());
1821  }
1822 
1823  template<typename _Key, typename _Val, typename _KeyOfValue,
1824  typename _Compare, typename _Alloc>
1825  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1826  _Compare, _Alloc>::_Base_ptr,
1827  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1828  _Compare, _Alloc>::_Base_ptr>
1829  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1830  _M_get_insert_unique_pos(const key_type& __k)
1831  {
1832  typedef pair<_Base_ptr, _Base_ptr> _Res;
1833  _Link_type __x = _M_begin();
1834  _Link_type __y = _M_end();
1835  bool __comp = true;
1836  while (__x != 0)
1837  {
1838  __y = __x;
1839  __comp = _M_impl._M_key_compare(__k, _S_key(__x));
1840  __x = __comp ? _S_left(__x) : _S_right(__x);
1841  }
1842  iterator __j = iterator(__y);
1843  if (__comp)
1844  {
1845  if (__j == begin())
1846  return _Res(__x, __y);
1847  else
1848  --__j;
1849  }
1850  if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
1851  return _Res(__x, __y);
1852  return _Res(__j._M_node, 0);
1853  }
1854 
1855  template<typename _Key, typename _Val, typename _KeyOfValue,
1856  typename _Compare, typename _Alloc>
1857  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1858  _Compare, _Alloc>::_Base_ptr,
1859  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1860  _Compare, _Alloc>::_Base_ptr>
1861  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1862  _M_get_insert_equal_pos(const key_type& __k)
1863  {
1864  typedef pair<_Base_ptr, _Base_ptr> _Res;
1865  _Link_type __x = _M_begin();
1866  _Link_type __y = _M_end();
1867  while (__x != 0)
1868  {
1869  __y = __x;
1870  __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
1871  _S_left(__x) : _S_right(__x);
1872  }
1873  return _Res(__x, __y);
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  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1882  _Compare, _Alloc>::iterator, bool>
1883  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1884 #if __cplusplus >= 201103L
1885  _M_insert_unique(_Arg&& __v)
1886 #else
1887  _M_insert_unique(const _Val& __v)
1888 #endif
1889  {
1890  typedef pair<iterator, bool> _Res;
1891  pair<_Base_ptr, _Base_ptr> __res
1892  = _M_get_insert_unique_pos(_KeyOfValue()(__v));
1893 
1894  if (__res.second)
1895  {
1896  _Alloc_node __an(*this);
1897  return _Res(_M_insert_(__res.first, __res.second,
1898  _GLIBCXX_FORWARD(_Arg, __v), __an),
1899  true);
1900  }
1901 
1902  return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1903  }
1904 
1905  template<typename _Key, typename _Val, typename _KeyOfValue,
1906  typename _Compare, typename _Alloc>
1907 #if __cplusplus >= 201103L
1908  template<typename _Arg>
1909 #endif
1910  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1911  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1912 #if __cplusplus >= 201103L
1913  _M_insert_equal(_Arg&& __v)
1914 #else
1915  _M_insert_equal(const _Val& __v)
1916 #endif
1917  {
1918  pair<_Base_ptr, _Base_ptr> __res
1919  = _M_get_insert_equal_pos(_KeyOfValue()(__v));
1920  _Alloc_node __an(*this);
1921  return _M_insert_(__res.first, __res.second,
1922  _GLIBCXX_FORWARD(_Arg, __v), __an);
1923  }
1924 
1925  template<typename _Key, typename _Val, typename _KeyOfValue,
1926  typename _Compare, typename _Alloc>
1927  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1928  _Compare, _Alloc>::_Base_ptr,
1929  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1930  _Compare, _Alloc>::_Base_ptr>
1931  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1932  _M_get_insert_hint_unique_pos(const_iterator __position,
1933  const key_type& __k)
1934  {
1935  iterator __pos = __position._M_const_cast();
1936  typedef pair<_Base_ptr, _Base_ptr> _Res;
1937 
1938  // end()
1939  if (__pos._M_node == _M_end())
1940  {
1941  if (size() > 0
1942  && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
1943  return _Res(0, _M_rightmost());
1944  else
1945  return _M_get_insert_unique_pos(__k);
1946  }
1947  else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
1948  {
1949  // First, try before...
1950  iterator __before = __pos;
1951  if (__pos._M_node == _M_leftmost()) // begin()
1952  return _Res(_M_leftmost(), _M_leftmost());
1953  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
1954  {
1955  if (_S_right(__before._M_node) == 0)
1956  return _Res(0, __before._M_node);
1957  else
1958  return _Res(__pos._M_node, __pos._M_node);
1959  }
1960  else
1961  return _M_get_insert_unique_pos(__k);
1962  }
1963  else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1964  {
1965  // ... then try after.
1966  iterator __after = __pos;
1967  if (__pos._M_node == _M_rightmost())
1968  return _Res(0, _M_rightmost());
1969  else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
1970  {
1971  if (_S_right(__pos._M_node) == 0)
1972  return _Res(0, __pos._M_node);
1973  else
1974  return _Res(__after._M_node, __after._M_node);
1975  }
1976  else
1977  return _M_get_insert_unique_pos(__k);
1978  }
1979  else
1980  // Equivalent keys.
1981  return _Res(__pos._M_node, 0);
1982  }
1983 
1984  template<typename _Key, typename _Val, typename _KeyOfValue,
1985  typename _Compare, typename _Alloc>
1986 #if __cplusplus >= 201103L
1987  template<typename _Arg, typename _NodeGen>
1988 #else
1989  template<typename _NodeGen>
1990 #endif
1991  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1992  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1993  _M_insert_unique_(const_iterator __position,
1994 #if __cplusplus >= 201103L
1995  _Arg&& __v,
1996 #else
1997  const _Val& __v,
1998 #endif
1999  _NodeGen& __node_gen)
2000  {
2001  pair<_Base_ptr, _Base_ptr> __res
2002  = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
2003 
2004  if (__res.second)
2005  return _M_insert_(__res.first, __res.second,
2006  _GLIBCXX_FORWARD(_Arg, __v),
2007  __node_gen);
2008  return iterator(static_cast<_Link_type>(__res.first));
2009  }
2010 
2011  template<typename _Key, typename _Val, typename _KeyOfValue,
2012  typename _Compare, typename _Alloc>
2013  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2014  _Compare, _Alloc>::_Base_ptr,
2015  typename _Rb_tree<_Key, _Val, _KeyOfValue,
2016  _Compare, _Alloc>::_Base_ptr>
2017  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2018  _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
2019  {
2020  iterator __pos = __position._M_const_cast();
2021  typedef pair<_Base_ptr, _Base_ptr> _Res;
2022 
2023  // end()
2024  if (__pos._M_node == _M_end())
2025  {
2026  if (size() > 0
2027  && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
2028  return _Res(0, _M_rightmost());
2029  else
2030  return _M_get_insert_equal_pos(__k);
2031  }
2032  else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2033  {
2034  // First, try before...
2035  iterator __before = __pos;
2036  if (__pos._M_node == _M_leftmost()) // begin()
2037  return _Res(_M_leftmost(), _M_leftmost());
2038  else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2039  {
2040  if (_S_right(__before._M_node) == 0)
2041  return _Res(0, __before._M_node);
2042  else
2043  return _Res(__pos._M_node, __pos._M_node);
2044  }
2045  else
2046  return _M_get_insert_equal_pos(__k);
2047  }
2048  else
2049  {
2050  // ... then try after.
2051  iterator __after = __pos;
2052  if (__pos._M_node == _M_rightmost())
2053  return _Res(0, _M_rightmost());
2054  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2055  {
2056  if (_S_right(__pos._M_node) == 0)
2057  return _Res(0, __pos._M_node);
2058  else
2059  return _Res(__after._M_node, __after._M_node);
2060  }
2061  else
2062  return _Res(0, 0);
2063  }
2064  }
2065 
2066  template<typename _Key, typename _Val, typename _KeyOfValue,
2067  typename _Compare, typename _Alloc>
2068 #if __cplusplus >= 201103L
2069  template<typename _Arg, typename _NodeGen>
2070 #else
2071  template<typename _NodeGen>
2072 #endif
2073  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2074  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2075  _M_insert_equal_(const_iterator __position,
2076 #if __cplusplus >= 201103L
2077  _Arg&& __v,
2078 #else
2079  const _Val& __v,
2080 #endif
2081  _NodeGen& __node_gen)
2082  {
2083  pair<_Base_ptr, _Base_ptr> __res
2084  = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2085 
2086  if (__res.second)
2087  return _M_insert_(__res.first, __res.second,
2088  _GLIBCXX_FORWARD(_Arg, __v),
2089  __node_gen);
2090 
2091  return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2092  }
2093 
2094 #if __cplusplus >= 201103L
2095  template<typename _Key, typename _Val, typename _KeyOfValue,
2096  typename _Compare, typename _Alloc>
2097  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2098  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2099  _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2100  {
2101  bool __insert_left = (__x != 0 || __p == _M_end()
2102  || _M_impl._M_key_compare(_S_key(__z),
2103  _S_key(__p)));
2104 
2105  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2106  this->_M_impl._M_header);
2107  ++_M_impl._M_node_count;
2108  return iterator(__z);
2109  }
2110 
2111  template<typename _Key, typename _Val, typename _KeyOfValue,
2112  typename _Compare, typename _Alloc>
2113  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2114  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2115  _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2116  {
2117  bool __insert_left = (__p == _M_end()
2118  || !_M_impl._M_key_compare(_S_key(__p),
2119  _S_key(__z)));
2120 
2121  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2122  this->_M_impl._M_header);
2123  ++_M_impl._M_node_count;
2124  return iterator(__z);
2125  }
2126 
2127  template<typename _Key, typename _Val, typename _KeyOfValue,
2128  typename _Compare, typename _Alloc>
2129  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2130  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2131  _M_insert_equal_lower_node(_Link_type __z)
2132  {
2133  _Link_type __x = _M_begin();
2134  _Link_type __y = _M_end();
2135  while (__x != 0)
2136  {
2137  __y = __x;
2138  __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2139  _S_left(__x) : _S_right(__x);
2140  }
2141  return _M_insert_lower_node(__y, __z);
2142  }
2143 
2144  template<typename _Key, typename _Val, typename _KeyOfValue,
2145  typename _Compare, typename _Alloc>
2146  template<typename... _Args>
2147  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2148  _Compare, _Alloc>::iterator, bool>
2149  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2150  _M_emplace_unique(_Args&&... __args)
2151  {
2152  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2153 
2154  __try
2155  {
2156  typedef pair<iterator, bool> _Res;
2157  auto __res = _M_get_insert_unique_pos(_S_key(__z));
2158  if (__res.second)
2159  return _Res(_M_insert_node(__res.first, __res.second, __z), true);
2160 
2161  _M_drop_node(__z);
2162  return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
2163  }
2164  __catch(...)
2165  {
2166  _M_drop_node(__z);
2167  __throw_exception_again;
2168  }
2169  }
2170 
2171  template<typename _Key, typename _Val, typename _KeyOfValue,
2172  typename _Compare, typename _Alloc>
2173  template<typename... _Args>
2174  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2175  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2176  _M_emplace_equal(_Args&&... __args)
2177  {
2178  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2179 
2180  __try
2181  {
2182  auto __res = _M_get_insert_equal_pos(_S_key(__z));
2183  return _M_insert_node(__res.first, __res.second, __z);
2184  }
2185  __catch(...)
2186  {
2187  _M_drop_node(__z);
2188  __throw_exception_again;
2189  }
2190  }
2191 
2192  template<typename _Key, typename _Val, typename _KeyOfValue,
2193  typename _Compare, typename _Alloc>
2194  template<typename... _Args>
2195  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2196  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2197  _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2198  {
2199  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2200 
2201  __try
2202  {
2203  auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2204 
2205  if (__res.second)
2206  return _M_insert_node(__res.first, __res.second, __z);
2207 
2208  _M_drop_node(__z);
2209  return iterator(static_cast<_Link_type>(__res.first));
2210  }
2211  __catch(...)
2212  {
2213  _M_drop_node(__z);
2214  __throw_exception_again;
2215  }
2216  }
2217 
2218  template<typename _Key, typename _Val, typename _KeyOfValue,
2219  typename _Compare, typename _Alloc>
2220  template<typename... _Args>
2221  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2222  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2223  _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2224  {
2225  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2226 
2227  __try
2228  {
2229  auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2230 
2231  if (__res.second)
2232  return _M_insert_node(__res.first, __res.second, __z);
2233 
2234  return _M_insert_equal_lower_node(__z);
2235  }
2236  __catch(...)
2237  {
2238  _M_drop_node(__z);
2239  __throw_exception_again;
2240  }
2241  }
2242 #endif
2243 
2244  template<typename _Key, typename _Val, typename _KoV,
2245  typename _Cmp, typename _Alloc>
2246  template<class _II>
2247  void
2248  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2249  _M_insert_unique(_II __first, _II __last)
2250  {
2251  _Alloc_node __an(*this);
2252  for (; __first != __last; ++__first)
2253  _M_insert_unique_(end(), *__first, __an);
2254  }
2255 
2256  template<typename _Key, typename _Val, typename _KoV,
2257  typename _Cmp, typename _Alloc>
2258  template<class _II>
2259  void
2260  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2261  _M_insert_equal(_II __first, _II __last)
2262  {
2263  _Alloc_node __an(*this);
2264  for (; __first != __last; ++__first)
2265  _M_insert_equal_(end(), *__first, __an);
2266  }
2267 
2268  template<typename _Key, typename _Val, typename _KeyOfValue,
2269  typename _Compare, typename _Alloc>
2270  void
2271  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2272  _M_erase_aux(const_iterator __position)
2273  {
2274  _Link_type __y =
2275  static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
2276  (const_cast<_Base_ptr>(__position._M_node),
2277  this->_M_impl._M_header));
2278  _M_drop_node(__y);
2279  --_M_impl._M_node_count;
2280  }
2281 
2282  template<typename _Key, typename _Val, typename _KeyOfValue,
2283  typename _Compare, typename _Alloc>
2284  void
2285  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2286  _M_erase_aux(const_iterator __first, const_iterator __last)
2287  {
2288  if (__first == begin() && __last == end())
2289  clear();
2290  else
2291  while (__first != __last)
2292  erase(__first++);
2293  }
2294 
2295  template<typename _Key, typename _Val, typename _KeyOfValue,
2296  typename _Compare, typename _Alloc>
2297  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2298  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2299  erase(const _Key& __x)
2300  {
2301  pair<iterator, iterator> __p = equal_range(__x);
2302  const size_type __old_size = size();
2303  erase(__p.first, __p.second);
2304  return __old_size - size();
2305  }
2306 
2307  template<typename _Key, typename _Val, typename _KeyOfValue,
2308  typename _Compare, typename _Alloc>
2309  void
2310  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2311  erase(const _Key* __first, const _Key* __last)
2312  {
2313  while (__first != __last)
2314  erase(*__first++);
2315  }
2316 
2317  template<typename _Key, typename _Val, typename _KeyOfValue,
2318  typename _Compare, typename _Alloc>
2319  typename _Rb_tree<_Key, _Val, _KeyOfValue,
2320  _Compare, _Alloc>::iterator
2321  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2322  find(const _Key& __k)
2323  {
2324  iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2325  return (__j == end()
2326  || _M_impl._M_key_compare(__k,
2327  _S_key(__j._M_node))) ? end() : __j;
2328  }
2329 
2330  template<typename _Key, typename _Val, typename _KeyOfValue,
2331  typename _Compare, typename _Alloc>
2332  typename _Rb_tree<_Key, _Val, _KeyOfValue,
2333  _Compare, _Alloc>::const_iterator
2334  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2335  find(const _Key& __k) const
2336  {
2337  const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2338  return (__j == end()
2339  || _M_impl._M_key_compare(__k,
2340  _S_key(__j._M_node))) ? end() : __j;
2341  }
2342 
2343  template<typename _Key, typename _Val, typename _KeyOfValue,
2344  typename _Compare, typename _Alloc>
2345  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2346  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2347  count(const _Key& __k) const
2348  {
2349  pair<const_iterator, const_iterator> __p = equal_range(__k);
2350  const size_type __n = std::distance(__p.first, __p.second);
2351  return __n;
2352  }
2353 
2354  _GLIBCXX_PURE unsigned int
2355  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
2356  const _Rb_tree_node_base* __root) throw ();
2357 
2358  template<typename _Key, typename _Val, typename _KeyOfValue,
2359  typename _Compare, typename _Alloc>
2360  bool
2361  _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
2362  {
2363  if (_M_impl._M_node_count == 0 || begin() == end())
2364  return _M_impl._M_node_count == 0 && begin() == end()
2365  && this->_M_impl._M_header._M_left == _M_end()
2366  && this->_M_impl._M_header._M_right == _M_end();
2367 
2368  unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2369  for (const_iterator __it = begin(); __it != end(); ++__it)
2370  {
2371  _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
2372  _Const_Link_type __L = _S_left(__x);
2373  _Const_Link_type __R = _S_right(__x);
2374 
2375  if (__x->_M_color == _S_red)
2376  if ((__L && __L->_M_color == _S_red)
2377  || (__R && __R->_M_color == _S_red))
2378  return false;
2379 
2380  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2381  return false;
2382  if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2383  return false;
2384 
2385  if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2386  return false;
2387  }
2388 
2389  if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2390  return false;
2391  if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2392  return false;
2393  return true;
2394  }
2395 
2396 _GLIBCXX_END_NAMESPACE_VERSION
2397 } // namespace
2398 
2399 #endif
integral_constant
Definition: type_traits:69
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:386
iterator begin()
As per Table mumble.
Definition: stl_tempbuf.h:151
Uniform interface to C++98 and C++0x allocators.
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
size_type size() const
As per Table mumble.
Definition: stl_tempbuf.h:141
ISO C++ entities toplevel namespace is std.
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
bool equal(_IIter1 __first1, _IIter1 __last1, _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
Tests a range for element-wise equality.
iterator end()
As per Table mumble.
Definition: stl_tempbuf.h:156
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:90
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
auto rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
Definition: range_access.h:138
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:87
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