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