libstdc++
stl_tree.h
Go to the documentation of this file.
1 // RB tree implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2013 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 #include <bits/stl_algobase.h>
62 #include <bits/allocator.h>
63 #include <bits/stl_function.h>
64 #include <bits/cpp_type_traits.h>
65 #if __cplusplus >= 201103L
66 #include <bits/alloc_traits.h>
67 #endif
68 
69 namespace std _GLIBCXX_VISIBILITY(default)
70 {
71 _GLIBCXX_BEGIN_NAMESPACE_VERSION
72 
73  // Red-black tree class, designed for use in implementing STL
74  // associative containers (set, multiset, map, and multimap). The
75  // insertion and deletion algorithms are based on those in Cormen,
76  // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
77  // 1990), except that
78  //
79  // (1) the header cell is maintained with links not only to the root
80  // but also to the leftmost node of the tree, to enable constant
81  // time begin(), and to the rightmost node of the tree, to enable
82  // linear time performance when used with the generic set algorithms
83  // (set_union, etc.)
84  //
85  // (2) when a node being deleted has two children its successor node
86  // is relinked into its place, rather than copied, so that the only
87  // iterators invalidated are those referring to the deleted node.
88 
89  enum _Rb_tree_color { _S_red = false, _S_black = true };
90 
91  struct _Rb_tree_node_base
92  {
93  typedef _Rb_tree_node_base* _Base_ptr;
94  typedef const _Rb_tree_node_base* _Const_Base_ptr;
95 
96  _Rb_tree_color _M_color;
97  _Base_ptr _M_parent;
98  _Base_ptr _M_left;
99  _Base_ptr _M_right;
100 
101  static _Base_ptr
102  _S_minimum(_Base_ptr __x)
103  {
104  while (__x->_M_left != 0) __x = __x->_M_left;
105  return __x;
106  }
107 
108  static _Const_Base_ptr
109  _S_minimum(_Const_Base_ptr __x)
110  {
111  while (__x->_M_left != 0) __x = __x->_M_left;
112  return __x;
113  }
114 
115  static _Base_ptr
116  _S_maximum(_Base_ptr __x)
117  {
118  while (__x->_M_right != 0) __x = __x->_M_right;
119  return __x;
120  }
121 
122  static _Const_Base_ptr
123  _S_maximum(_Const_Base_ptr __x)
124  {
125  while (__x->_M_right != 0) __x = __x->_M_right;
126  return __x;
127  }
128  };
129 
130  template<typename _Val>
131  struct _Rb_tree_node : public _Rb_tree_node_base
132  {
133  typedef _Rb_tree_node<_Val>* _Link_type;
134  _Val _M_value_field;
135 
136 #if __cplusplus >= 201103L
137  template<typename... _Args>
138  _Rb_tree_node(_Args&&... __args)
139  : _Rb_tree_node_base(),
140  _M_value_field(std::forward<_Args>(__args)...) { }
141 #endif
142  };
143 
144  _GLIBCXX_PURE _Rb_tree_node_base*
145  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
146 
147  _GLIBCXX_PURE const _Rb_tree_node_base*
148  _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
149 
150  _GLIBCXX_PURE _Rb_tree_node_base*
151  _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
152 
153  _GLIBCXX_PURE const _Rb_tree_node_base*
154  _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
155 
156  template<typename _Tp>
157  struct _Rb_tree_iterator
158  {
159  typedef _Tp value_type;
160  typedef _Tp& reference;
161  typedef _Tp* pointer;
162 
163  typedef bidirectional_iterator_tag iterator_category;
164  typedef ptrdiff_t difference_type;
165 
166  typedef _Rb_tree_iterator<_Tp> _Self;
167  typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
168  typedef _Rb_tree_node<_Tp>* _Link_type;
169 
170  _Rb_tree_iterator()
171  : _M_node() { }
172 
173  explicit
174  _Rb_tree_iterator(_Link_type __x)
175  : _M_node(__x) { }
176 
177  reference
178  operator*() const
179  { return static_cast<_Link_type>(_M_node)->_M_value_field; }
180 
181  pointer
182  operator->() const
183  { return std::__addressof(static_cast<_Link_type>
184  (_M_node)->_M_value_field); }
185 
186  _Self&
187  operator++()
188  {
189  _M_node = _Rb_tree_increment(_M_node);
190  return *this;
191  }
192 
193  _Self
194  operator++(int)
195  {
196  _Self __tmp = *this;
197  _M_node = _Rb_tree_increment(_M_node);
198  return __tmp;
199  }
200 
201  _Self&
202  operator--()
203  {
204  _M_node = _Rb_tree_decrement(_M_node);
205  return *this;
206  }
207 
208  _Self
209  operator--(int)
210  {
211  _Self __tmp = *this;
212  _M_node = _Rb_tree_decrement(_M_node);
213  return __tmp;
214  }
215 
216  bool
217  operator==(const _Self& __x) const
218  { return _M_node == __x._M_node; }
219 
220  bool
221  operator!=(const _Self& __x) const
222  { return _M_node != __x._M_node; }
223 
224  _Base_ptr _M_node;
225  };
226 
227  template<typename _Tp>
228  struct _Rb_tree_const_iterator
229  {
230  typedef _Tp value_type;
231  typedef const _Tp& reference;
232  typedef const _Tp* pointer;
233 
234  typedef _Rb_tree_iterator<_Tp> iterator;
235 
236  typedef bidirectional_iterator_tag iterator_category;
237  typedef ptrdiff_t difference_type;
238 
239  typedef _Rb_tree_const_iterator<_Tp> _Self;
240  typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
241  typedef const _Rb_tree_node<_Tp>* _Link_type;
242 
243  _Rb_tree_const_iterator()
244  : _M_node() { }
245 
246  explicit
247  _Rb_tree_const_iterator(_Link_type __x)
248  : _M_node(__x) { }
249 
250  _Rb_tree_const_iterator(const iterator& __it)
251  : _M_node(__it._M_node) { }
252 
253  iterator
254  _M_const_cast() const
255  { return iterator(static_cast<typename iterator::_Link_type>
256  (const_cast<typename iterator::_Base_ptr>(_M_node))); }
257 
258  reference
259  operator*() const
260  { return static_cast<_Link_type>(_M_node)->_M_value_field; }
261 
262  pointer
263  operator->() const
264  { return std::__addressof(static_cast<_Link_type>
265  (_M_node)->_M_value_field); }
266 
267  _Self&
268  operator++()
269  {
270  _M_node = _Rb_tree_increment(_M_node);
271  return *this;
272  }
273 
274  _Self
275  operator++(int)
276  {
277  _Self __tmp = *this;
278  _M_node = _Rb_tree_increment(_M_node);
279  return __tmp;
280  }
281 
282  _Self&
283  operator--()
284  {
285  _M_node = _Rb_tree_decrement(_M_node);
286  return *this;
287  }
288 
289  _Self
290  operator--(int)
291  {
292  _Self __tmp = *this;
293  _M_node = _Rb_tree_decrement(_M_node);
294  return __tmp;
295  }
296 
297  bool
298  operator==(const _Self& __x) const
299  { return _M_node == __x._M_node; }
300 
301  bool
302  operator!=(const _Self& __x) const
303  { return _M_node != __x._M_node; }
304 
305  _Base_ptr _M_node;
306  };
307 
308  template<typename _Val>
309  inline bool
310  operator==(const _Rb_tree_iterator<_Val>& __x,
311  const _Rb_tree_const_iterator<_Val>& __y)
312  { return __x._M_node == __y._M_node; }
313 
314  template<typename _Val>
315  inline bool
316  operator!=(const _Rb_tree_iterator<_Val>& __x,
317  const _Rb_tree_const_iterator<_Val>& __y)
318  { return __x._M_node != __y._M_node; }
319 
320  void
321  _Rb_tree_insert_and_rebalance(const bool __insert_left,
322  _Rb_tree_node_base* __x,
323  _Rb_tree_node_base* __p,
324  _Rb_tree_node_base& __header) throw ();
325 
326  _Rb_tree_node_base*
327  _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
328  _Rb_tree_node_base& __header) throw ();
329 
330 
331  template<typename _Key, typename _Val, typename _KeyOfValue,
332  typename _Compare, typename _Alloc = allocator<_Val> >
333  class _Rb_tree
334  {
335  typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
336  _Node_allocator;
337 
338  protected:
339  typedef _Rb_tree_node_base* _Base_ptr;
340  typedef const _Rb_tree_node_base* _Const_Base_ptr;
341 
342  public:
343  typedef _Key key_type;
344  typedef _Val value_type;
345  typedef value_type* pointer;
346  typedef const value_type* const_pointer;
347  typedef value_type& reference;
348  typedef const value_type& const_reference;
349  typedef _Rb_tree_node<_Val>* _Link_type;
350  typedef const _Rb_tree_node<_Val>* _Const_Link_type;
351  typedef size_t size_type;
352  typedef ptrdiff_t difference_type;
353  typedef _Alloc allocator_type;
354 
355  _Node_allocator&
356  _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
357  { return *static_cast<_Node_allocator*>(&this->_M_impl); }
358 
359  const _Node_allocator&
360  _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
361  { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
362 
363  allocator_type
364  get_allocator() const _GLIBCXX_NOEXCEPT
365  { return allocator_type(_M_get_Node_allocator()); }
366 
367  protected:
368  _Link_type
369  _M_get_node()
370  { return _M_impl._Node_allocator::allocate(1); }
371 
372  void
373  _M_put_node(_Link_type __p)
374  { _M_impl._Node_allocator::deallocate(__p, 1); }
375 
376 #if __cplusplus < 201103L
377  _Link_type
378  _M_create_node(const value_type& __x)
379  {
380  _Link_type __tmp = _M_get_node();
381  __try
382  { get_allocator().construct
383  (std::__addressof(__tmp->_M_value_field), __x); }
384  __catch(...)
385  {
386  _M_put_node(__tmp);
387  __throw_exception_again;
388  }
389  return __tmp;
390  }
391 
392  void
393  _M_destroy_node(_Link_type __p)
394  {
395  get_allocator().destroy(std::__addressof(__p->_M_value_field));
396  _M_put_node(__p);
397  }
398 #else
399  template<typename... _Args>
400  _Link_type
401  _M_create_node(_Args&&... __args)
402  {
403  _Link_type __tmp = _M_get_node();
404  __try
405  {
406  allocator_traits<_Node_allocator>::
407  construct(_M_get_Node_allocator(), __tmp,
408  std::forward<_Args>(__args)...);
409  }
410  __catch(...)
411  {
412  _M_put_node(__tmp);
413  __throw_exception_again;
414  }
415  return __tmp;
416  }
417 
418  void
419  _M_destroy_node(_Link_type __p)
420  {
421  _M_get_Node_allocator().destroy(__p);
422  _M_put_node(__p);
423  }
424 #endif
425 
426  _Link_type
427  _M_clone_node(_Const_Link_type __x)
428  {
429  _Link_type __tmp = _M_create_node(__x->_M_value_field);
430  __tmp->_M_color = __x->_M_color;
431  __tmp->_M_left = 0;
432  __tmp->_M_right = 0;
433  return __tmp;
434  }
435 
436  protected:
437  template<typename _Key_compare,
438  bool _Is_pod_comparator = __is_pod(_Key_compare)>
439  struct _Rb_tree_impl : public _Node_allocator
440  {
441  _Key_compare _M_key_compare;
442  _Rb_tree_node_base _M_header;
443  size_type _M_node_count; // Keeps track of size of tree.
444 
445  _Rb_tree_impl()
446  : _Node_allocator(), _M_key_compare(), _M_header(),
447  _M_node_count(0)
448  { _M_initialize(); }
449 
450  _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
451  : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
452  _M_node_count(0)
453  { _M_initialize(); }
454 
455 #if __cplusplus >= 201103L
456  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
457  : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
458  _M_header(), _M_node_count(0)
459  { _M_initialize(); }
460 #endif
461 
462  private:
463  void
464  _M_initialize()
465  {
466  this->_M_header._M_color = _S_red;
467  this->_M_header._M_parent = 0;
468  this->_M_header._M_left = &this->_M_header;
469  this->_M_header._M_right = &this->_M_header;
470  }
471  };
472 
473  _Rb_tree_impl<_Compare> _M_impl;
474 
475  protected:
476  _Base_ptr&
477  _M_root()
478  { return this->_M_impl._M_header._M_parent; }
479 
480  _Const_Base_ptr
481  _M_root() const
482  { return this->_M_impl._M_header._M_parent; }
483 
484  _Base_ptr&
485  _M_leftmost()
486  { return this->_M_impl._M_header._M_left; }
487 
488  _Const_Base_ptr
489  _M_leftmost() const
490  { return this->_M_impl._M_header._M_left; }
491 
492  _Base_ptr&
493  _M_rightmost()
494  { return this->_M_impl._M_header._M_right; }
495 
496  _Const_Base_ptr
497  _M_rightmost() const
498  { return this->_M_impl._M_header._M_right; }
499 
500  _Link_type
501  _M_begin()
502  { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
503 
504  _Const_Link_type
505  _M_begin() const
506  {
507  return static_cast<_Const_Link_type>
508  (this->_M_impl._M_header._M_parent);
509  }
510 
511  _Link_type
512  _M_end()
513  { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }
514 
515  _Const_Link_type
516  _M_end() const
517  { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }
518 
519  static const_reference
520  _S_value(_Const_Link_type __x)
521  { return __x->_M_value_field; }
522 
523  static const _Key&
524  _S_key(_Const_Link_type __x)
525  { return _KeyOfValue()(_S_value(__x)); }
526 
527  static _Link_type
528  _S_left(_Base_ptr __x)
529  { return static_cast<_Link_type>(__x->_M_left); }
530 
531  static _Const_Link_type
532  _S_left(_Const_Base_ptr __x)
533  { return static_cast<_Const_Link_type>(__x->_M_left); }
534 
535  static _Link_type
536  _S_right(_Base_ptr __x)
537  { return static_cast<_Link_type>(__x->_M_right); }
538 
539  static _Const_Link_type
540  _S_right(_Const_Base_ptr __x)
541  { return static_cast<_Const_Link_type>(__x->_M_right); }
542 
543  static const_reference
544  _S_value(_Const_Base_ptr __x)
545  { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
546 
547  static const _Key&
548  _S_key(_Const_Base_ptr __x)
549  { return _KeyOfValue()(_S_value(__x)); }
550 
551  static _Base_ptr
552  _S_minimum(_Base_ptr __x)
553  { return _Rb_tree_node_base::_S_minimum(__x); }
554 
555  static _Const_Base_ptr
556  _S_minimum(_Const_Base_ptr __x)
557  { return _Rb_tree_node_base::_S_minimum(__x); }
558 
559  static _Base_ptr
560  _S_maximum(_Base_ptr __x)
561  { return _Rb_tree_node_base::_S_maximum(__x); }
562 
563  static _Const_Base_ptr
564  _S_maximum(_Const_Base_ptr __x)
565  { return _Rb_tree_node_base::_S_maximum(__x); }
566 
567  public:
568  typedef _Rb_tree_iterator<value_type> iterator;
569  typedef _Rb_tree_const_iterator<value_type> const_iterator;
570 
571  typedef std::reverse_iterator<iterator> reverse_iterator;
572  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
573 
574  private:
575  pair<_Base_ptr, _Base_ptr>
576  _M_get_insert_unique_pos(const key_type& __k);
577 
578  pair<_Base_ptr, _Base_ptr>
579  _M_get_insert_equal_pos(const key_type& __k);
580 
581  pair<_Base_ptr, _Base_ptr>
582  _M_get_insert_hint_unique_pos(const_iterator __pos,
583  const key_type& __k);
584 
585  pair<_Base_ptr, _Base_ptr>
586  _M_get_insert_hint_equal_pos(const_iterator __pos,
587  const key_type& __k);
588 
589 #if __cplusplus >= 201103L
590  template<typename _Arg>
591  iterator
592  _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
593 
594  iterator
595  _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
596 
597  template<typename _Arg>
598  iterator
599  _M_insert_lower(_Base_ptr __y, _Arg&& __v);
600 
601  template<typename _Arg>
602  iterator
603  _M_insert_equal_lower(_Arg&& __x);
604 
605  iterator
606  _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
607 
608  iterator
609  _M_insert_equal_lower_node(_Link_type __z);
610 #else
611  iterator
612  _M_insert_(_Base_ptr __x, _Base_ptr __y,
613  const value_type& __v);
614 
615  // _GLIBCXX_RESOLVE_LIB_DEFECTS
616  // 233. Insertion hints in associative containers.
617  iterator
618  _M_insert_lower(_Base_ptr __y, const value_type& __v);
619 
620  iterator
621  _M_insert_equal_lower(const value_type& __x);
622 #endif
623 
624  _Link_type
625  _M_copy(_Const_Link_type __x, _Link_type __p);
626 
627  void
628  _M_erase(_Link_type __x);
629 
630  iterator
631  _M_lower_bound(_Link_type __x, _Link_type __y,
632  const _Key& __k);
633 
634  const_iterator
635  _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
636  const _Key& __k) const;
637 
638  iterator
639  _M_upper_bound(_Link_type __x, _Link_type __y,
640  const _Key& __k);
641 
642  const_iterator
643  _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
644  const _Key& __k) const;
645 
646  public:
647  // allocation/deallocation
648  _Rb_tree() { }
649 
650  _Rb_tree(const _Compare& __comp,
651  const allocator_type& __a = allocator_type())
652  : _M_impl(__comp, _Node_allocator(__a)) { }
653 
654  _Rb_tree(const _Rb_tree& __x)
655  : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
656  {
657  if (__x._M_root() != 0)
658  {
659  _M_root() = _M_copy(__x._M_begin(), _M_end());
660  _M_leftmost() = _S_minimum(_M_root());
661  _M_rightmost() = _S_maximum(_M_root());
662  _M_impl._M_node_count = __x._M_impl._M_node_count;
663  }
664  }
665 
666 #if __cplusplus >= 201103L
667  _Rb_tree(_Rb_tree&& __x);
668 #endif
669 
670  ~_Rb_tree() _GLIBCXX_NOEXCEPT
671  { _M_erase(_M_begin()); }
672 
673  _Rb_tree&
674  operator=(const _Rb_tree& __x);
675 
676  // Accessors.
677  _Compare
678  key_comp() const
679  { return _M_impl._M_key_compare; }
680 
681  iterator
682  begin() _GLIBCXX_NOEXCEPT
683  {
684  return iterator(static_cast<_Link_type>
685  (this->_M_impl._M_header._M_left));
686  }
687 
688  const_iterator
689  begin() const _GLIBCXX_NOEXCEPT
690  {
691  return const_iterator(static_cast<_Const_Link_type>
692  (this->_M_impl._M_header._M_left));
693  }
694 
695  iterator
696  end() _GLIBCXX_NOEXCEPT
697  { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
698 
699  const_iterator
700  end() const _GLIBCXX_NOEXCEPT
701  {
702  return const_iterator(static_cast<_Const_Link_type>
703  (&this->_M_impl._M_header));
704  }
705 
706  reverse_iterator
707  rbegin() _GLIBCXX_NOEXCEPT
708  { return reverse_iterator(end()); }
709 
710  const_reverse_iterator
711  rbegin() const _GLIBCXX_NOEXCEPT
712  { return const_reverse_iterator(end()); }
713 
714  reverse_iterator
715  rend() _GLIBCXX_NOEXCEPT
716  { return reverse_iterator(begin()); }
717 
718  const_reverse_iterator
719  rend() const _GLIBCXX_NOEXCEPT
720  { return const_reverse_iterator(begin()); }
721 
722  bool
723  empty() const _GLIBCXX_NOEXCEPT
724  { return _M_impl._M_node_count == 0; }
725 
726  size_type
727  size() const _GLIBCXX_NOEXCEPT
728  { return _M_impl._M_node_count; }
729 
730  size_type
731  max_size() const _GLIBCXX_NOEXCEPT
732  { return _M_get_Node_allocator().max_size(); }
733 
734  void
735  swap(_Rb_tree& __t);
736 
737  // Insert/erase.
738 #if __cplusplus >= 201103L
739  template<typename _Arg>
740  pair<iterator, bool>
741  _M_insert_unique(_Arg&& __x);
742 
743  template<typename _Arg>
744  iterator
745  _M_insert_equal(_Arg&& __x);
746 
747  template<typename _Arg>
748  iterator
749  _M_insert_unique_(const_iterator __position, _Arg&& __x);
750 
751  template<typename _Arg>
752  iterator
753  _M_insert_equal_(const_iterator __position, _Arg&& __x);
754 
755  template<typename... _Args>
756  pair<iterator, bool>
757  _M_emplace_unique(_Args&&... __args);
758 
759  template<typename... _Args>
760  iterator
761  _M_emplace_equal(_Args&&... __args);
762 
763  template<typename... _Args>
764  iterator
765  _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
766 
767  template<typename... _Args>
768  iterator
769  _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
770 #else
771  pair<iterator, bool>
772  _M_insert_unique(const value_type& __x);
773 
774  iterator
775  _M_insert_equal(const value_type& __x);
776 
777  iterator
778  _M_insert_unique_(const_iterator __position, const value_type& __x);
779 
780  iterator
781  _M_insert_equal_(const_iterator __position, const value_type& __x);
782 #endif
783 
784  template<typename _InputIterator>
785  void
786  _M_insert_unique(_InputIterator __first, _InputIterator __last);
787 
788  template<typename _InputIterator>
789  void
790  _M_insert_equal(_InputIterator __first, _InputIterator __last);
791 
792  private:
793  void
794  _M_erase_aux(const_iterator __position);
795 
796  void
797  _M_erase_aux(const_iterator __first, const_iterator __last);
798 
799  public:
800 #if __cplusplus >= 201103L
801  // _GLIBCXX_RESOLVE_LIB_DEFECTS
802  // DR 130. Associative erase should return an iterator.
803  _GLIBCXX_ABI_TAG_CXX11
804  iterator
805  erase(const_iterator __position)
806  {
807  const_iterator __result = __position;
808  ++__result;
809  _M_erase_aux(__position);
810  return __result._M_const_cast();
811  }
812 
813  // LWG 2059.
814  _GLIBCXX_ABI_TAG_CXX11
815  iterator
816  erase(iterator __position)
817  {
818  iterator __result = __position;
819  ++__result;
820  _M_erase_aux(__position);
821  return __result;
822  }
823 #else
824  void
825  erase(iterator __position)
826  { _M_erase_aux(__position); }
827 
828  void
829  erase(const_iterator __position)
830  { _M_erase_aux(__position); }
831 #endif
832  size_type
833  erase(const key_type& __x);
834 
835 #if __cplusplus >= 201103L
836  // _GLIBCXX_RESOLVE_LIB_DEFECTS
837  // DR 130. Associative erase should return an iterator.
838  _GLIBCXX_ABI_TAG_CXX11
839  iterator
840  erase(const_iterator __first, const_iterator __last)
841  {
842  _M_erase_aux(__first, __last);
843  return __last._M_const_cast();
844  }
845 #else
846  void
847  erase(iterator __first, iterator __last)
848  { _M_erase_aux(__first, __last); }
849 
850  void
851  erase(const_iterator __first, const_iterator __last)
852  { _M_erase_aux(__first, __last); }
853 #endif
854  void
855  erase(const key_type* __first, const key_type* __last);
856 
857  void
858  clear() _GLIBCXX_NOEXCEPT
859  {
860  _M_erase(_M_begin());
861  _M_leftmost() = _M_end();
862  _M_root() = 0;
863  _M_rightmost() = _M_end();
864  _M_impl._M_node_count = 0;
865  }
866 
867  // Set operations.
868  iterator
869  find(const key_type& __k);
870 
871  const_iterator
872  find(const key_type& __k) const;
873 
874  size_type
875  count(const key_type& __k) const;
876 
877  iterator
878  lower_bound(const key_type& __k)
879  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
880 
881  const_iterator
882  lower_bound(const key_type& __k) const
883  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
884 
885  iterator
886  upper_bound(const key_type& __k)
887  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
888 
889  const_iterator
890  upper_bound(const key_type& __k) const
891  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
892 
893  pair<iterator, iterator>
894  equal_range(const key_type& __k);
895 
896  pair<const_iterator, const_iterator>
897  equal_range(const key_type& __k) const;
898 
899  // Debugging.
900  bool
901  __rb_verify() const;
902  };
903 
904  template<typename _Key, typename _Val, typename _KeyOfValue,
905  typename _Compare, typename _Alloc>
906  inline bool
907  operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
908  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
909  {
910  return __x.size() == __y.size()
911  && std::equal(__x.begin(), __x.end(), __y.begin());
912  }
913 
914  template<typename _Key, typename _Val, typename _KeyOfValue,
915  typename _Compare, typename _Alloc>
916  inline bool
917  operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
918  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
919  {
920  return std::lexicographical_compare(__x.begin(), __x.end(),
921  __y.begin(), __y.end());
922  }
923 
924  template<typename _Key, typename _Val, typename _KeyOfValue,
925  typename _Compare, typename _Alloc>
926  inline bool
927  operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
928  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
929  { return !(__x == __y); }
930 
931  template<typename _Key, typename _Val, typename _KeyOfValue,
932  typename _Compare, typename _Alloc>
933  inline bool
934  operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
935  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
936  { return __y < __x; }
937 
938  template<typename _Key, typename _Val, typename _KeyOfValue,
939  typename _Compare, typename _Alloc>
940  inline bool
941  operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
942  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
943  { return !(__y < __x); }
944 
945  template<typename _Key, typename _Val, typename _KeyOfValue,
946  typename _Compare, typename _Alloc>
947  inline bool
948  operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
949  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
950  { return !(__x < __y); }
951 
952  template<typename _Key, typename _Val, typename _KeyOfValue,
953  typename _Compare, typename _Alloc>
954  inline void
955  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
956  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
957  { __x.swap(__y); }
958 
959 #if __cplusplus >= 201103L
960  template<typename _Key, typename _Val, typename _KeyOfValue,
961  typename _Compare, typename _Alloc>
962  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
963  _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
964  : _M_impl(__x._M_impl._M_key_compare,
965  std::move(__x._M_get_Node_allocator()))
966  {
967  if (__x._M_root() != 0)
968  {
969  _M_root() = __x._M_root();
970  _M_leftmost() = __x._M_leftmost();
971  _M_rightmost() = __x._M_rightmost();
972  _M_root()->_M_parent = _M_end();
973 
974  __x._M_root() = 0;
975  __x._M_leftmost() = __x._M_end();
976  __x._M_rightmost() = __x._M_end();
977 
978  this->_M_impl._M_node_count = __x._M_impl._M_node_count;
979  __x._M_impl._M_node_count = 0;
980  }
981  }
982 #endif
983 
984  template<typename _Key, typename _Val, typename _KeyOfValue,
985  typename _Compare, typename _Alloc>
986  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
987  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
988  operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
989  {
990  if (this != &__x)
991  {
992  // Note that _Key may be a constant type.
993  clear();
994  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
995  if (__x._M_root() != 0)
996  {
997  _M_root() = _M_copy(__x._M_begin(), _M_end());
998  _M_leftmost() = _S_minimum(_M_root());
999  _M_rightmost() = _S_maximum(_M_root());
1000  _M_impl._M_node_count = __x._M_impl._M_node_count;
1001  }
1002  }
1003  return *this;
1004  }
1005 
1006  template<typename _Key, typename _Val, typename _KeyOfValue,
1007  typename _Compare, typename _Alloc>
1008 #if __cplusplus >= 201103L
1009  template<typename _Arg>
1010 #endif
1011  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1012  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1013 #if __cplusplus >= 201103L
1014  _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
1015 #else
1016  _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
1017 #endif
1018  {
1019  bool __insert_left = (__x != 0 || __p == _M_end()
1020  || _M_impl._M_key_compare(_KeyOfValue()(__v),
1021  _S_key(__p)));
1022 
1023  _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1024 
1025  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1026  this->_M_impl._M_header);
1027  ++_M_impl._M_node_count;
1028  return iterator(__z);
1029  }
1030 
1031  template<typename _Key, typename _Val, typename _KeyOfValue,
1032  typename _Compare, typename _Alloc>
1033 #if __cplusplus >= 201103L
1034  template<typename _Arg>
1035 #endif
1036  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1037  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1038 #if __cplusplus >= 201103L
1039  _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1040 #else
1041  _M_insert_lower(_Base_ptr __p, const _Val& __v)
1042 #endif
1043  {
1044  bool __insert_left = (__p == _M_end()
1045  || !_M_impl._M_key_compare(_S_key(__p),
1046  _KeyOfValue()(__v)));
1047 
1048  _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1049 
1050  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1051  this->_M_impl._M_header);
1052  ++_M_impl._M_node_count;
1053  return iterator(__z);
1054  }
1055 
1056  template<typename _Key, typename _Val, typename _KeyOfValue,
1057  typename _Compare, typename _Alloc>
1058 #if __cplusplus >= 201103L
1059  template<typename _Arg>
1060 #endif
1061  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1062  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1063 #if __cplusplus >= 201103L
1064  _M_insert_equal_lower(_Arg&& __v)
1065 #else
1066  _M_insert_equal_lower(const _Val& __v)
1067 #endif
1068  {
1069  _Link_type __x = _M_begin();
1070  _Link_type __y = _M_end();
1071  while (__x != 0)
1072  {
1073  __y = __x;
1074  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1075  _S_left(__x) : _S_right(__x);
1076  }
1077  return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1078  }
1079 
1080  template<typename _Key, typename _Val, typename _KoV,
1081  typename _Compare, typename _Alloc>
1082  typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1083  _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1084  _M_copy(_Const_Link_type __x, _Link_type __p)
1085  {
1086  // Structural copy. __x and __p must be non-null.
1087  _Link_type __top = _M_clone_node(__x);
1088  __top->_M_parent = __p;
1089 
1090  __try
1091  {
1092  if (__x->_M_right)
1093  __top->_M_right = _M_copy(_S_right(__x), __top);
1094  __p = __top;
1095  __x = _S_left(__x);
1096 
1097  while (__x != 0)
1098  {
1099  _Link_type __y = _M_clone_node(__x);
1100  __p->_M_left = __y;
1101  __y->_M_parent = __p;
1102  if (__x->_M_right)
1103  __y->_M_right = _M_copy(_S_right(__x), __y);
1104  __p = __y;
1105  __x = _S_left(__x);
1106  }
1107  }
1108  __catch(...)
1109  {
1110  _M_erase(__top);
1111  __throw_exception_again;
1112  }
1113  return __top;
1114  }
1115 
1116  template<typename _Key, typename _Val, typename _KeyOfValue,
1117  typename _Compare, typename _Alloc>
1118  void
1119  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1120  _M_erase(_Link_type __x)
1121  {
1122  // Erase without rebalancing.
1123  while (__x != 0)
1124  {
1125  _M_erase(_S_right(__x));
1126  _Link_type __y = _S_left(__x);
1127  _M_destroy_node(__x);
1128  __x = __y;
1129  }
1130  }
1131 
1132  template<typename _Key, typename _Val, typename _KeyOfValue,
1133  typename _Compare, typename _Alloc>
1134  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1135  _Compare, _Alloc>::iterator
1136  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1137  _M_lower_bound(_Link_type __x, _Link_type __y,
1138  const _Key& __k)
1139  {
1140  while (__x != 0)
1141  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1142  __y = __x, __x = _S_left(__x);
1143  else
1144  __x = _S_right(__x);
1145  return iterator(__y);
1146  }
1147 
1148  template<typename _Key, typename _Val, typename _KeyOfValue,
1149  typename _Compare, typename _Alloc>
1150  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1151  _Compare, _Alloc>::const_iterator
1152  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1153  _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1154  const _Key& __k) const
1155  {
1156  while (__x != 0)
1157  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1158  __y = __x, __x = _S_left(__x);
1159  else
1160  __x = _S_right(__x);
1161  return const_iterator(__y);
1162  }
1163 
1164  template<typename _Key, typename _Val, typename _KeyOfValue,
1165  typename _Compare, typename _Alloc>
1166  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1167  _Compare, _Alloc>::iterator
1168  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1169  _M_upper_bound(_Link_type __x, _Link_type __y,
1170  const _Key& __k)
1171  {
1172  while (__x != 0)
1173  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1174  __y = __x, __x = _S_left(__x);
1175  else
1176  __x = _S_right(__x);
1177  return iterator(__y);
1178  }
1179 
1180  template<typename _Key, typename _Val, typename _KeyOfValue,
1181  typename _Compare, typename _Alloc>
1182  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1183  _Compare, _Alloc>::const_iterator
1184  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1185  _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1186  const _Key& __k) const
1187  {
1188  while (__x != 0)
1189  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1190  __y = __x, __x = _S_left(__x);
1191  else
1192  __x = _S_right(__x);
1193  return const_iterator(__y);
1194  }
1195 
1196  template<typename _Key, typename _Val, typename _KeyOfValue,
1197  typename _Compare, typename _Alloc>
1198  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1199  _Compare, _Alloc>::iterator,
1200  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1201  _Compare, _Alloc>::iterator>
1202  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1203  equal_range(const _Key& __k)
1204  {
1205  _Link_type __x = _M_begin();
1206  _Link_type __y = _M_end();
1207  while (__x != 0)
1208  {
1209  if (_M_impl._M_key_compare(_S_key(__x), __k))
1210  __x = _S_right(__x);
1211  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1212  __y = __x, __x = _S_left(__x);
1213  else
1214  {
1215  _Link_type __xu(__x), __yu(__y);
1216  __y = __x, __x = _S_left(__x);
1217  __xu = _S_right(__xu);
1218  return pair<iterator,
1219  iterator>(_M_lower_bound(__x, __y, __k),
1220  _M_upper_bound(__xu, __yu, __k));
1221  }
1222  }
1223  return pair<iterator, iterator>(iterator(__y),
1224  iterator(__y));
1225  }
1226 
1227  template<typename _Key, typename _Val, typename _KeyOfValue,
1228  typename _Compare, typename _Alloc>
1229  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1230  _Compare, _Alloc>::const_iterator,
1231  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1232  _Compare, _Alloc>::const_iterator>
1233  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1234  equal_range(const _Key& __k) const
1235  {
1236  _Const_Link_type __x = _M_begin();
1237  _Const_Link_type __y = _M_end();
1238  while (__x != 0)
1239  {
1240  if (_M_impl._M_key_compare(_S_key(__x), __k))
1241  __x = _S_right(__x);
1242  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1243  __y = __x, __x = _S_left(__x);
1244  else
1245  {
1246  _Const_Link_type __xu(__x), __yu(__y);
1247  __y = __x, __x = _S_left(__x);
1248  __xu = _S_right(__xu);
1249  return pair<const_iterator,
1250  const_iterator>(_M_lower_bound(__x, __y, __k),
1251  _M_upper_bound(__xu, __yu, __k));
1252  }
1253  }
1254  return pair<const_iterator, const_iterator>(const_iterator(__y),
1255  const_iterator(__y));
1256  }
1257 
1258  template<typename _Key, typename _Val, typename _KeyOfValue,
1259  typename _Compare, typename _Alloc>
1260  void
1261  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1262  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1263  {
1264  if (_M_root() == 0)
1265  {
1266  if (__t._M_root() != 0)
1267  {
1268  _M_root() = __t._M_root();
1269  _M_leftmost() = __t._M_leftmost();
1270  _M_rightmost() = __t._M_rightmost();
1271  _M_root()->_M_parent = _M_end();
1272 
1273  __t._M_root() = 0;
1274  __t._M_leftmost() = __t._M_end();
1275  __t._M_rightmost() = __t._M_end();
1276  }
1277  }
1278  else if (__t._M_root() == 0)
1279  {
1280  __t._M_root() = _M_root();
1281  __t._M_leftmost() = _M_leftmost();
1282  __t._M_rightmost() = _M_rightmost();
1283  __t._M_root()->_M_parent = __t._M_end();
1284 
1285  _M_root() = 0;
1286  _M_leftmost() = _M_end();
1287  _M_rightmost() = _M_end();
1288  }
1289  else
1290  {
1291  std::swap(_M_root(),__t._M_root());
1292  std::swap(_M_leftmost(),__t._M_leftmost());
1293  std::swap(_M_rightmost(),__t._M_rightmost());
1294 
1295  _M_root()->_M_parent = _M_end();
1296  __t._M_root()->_M_parent = __t._M_end();
1297  }
1298  // No need to swap header's color as it does not change.
1299  std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1300  std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1301 
1302  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1303  // 431. Swapping containers with unequal allocators.
1304  std::__alloc_swap<_Node_allocator>::
1305  _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
1306  }
1307 
1308  template<typename _Key, typename _Val, typename _KeyOfValue,
1309  typename _Compare, typename _Alloc>
1310  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1311  _Compare, _Alloc>::_Base_ptr,
1312  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1313  _Compare, _Alloc>::_Base_ptr>
1314  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1315  _M_get_insert_unique_pos(const key_type& __k)
1316  {
1317  typedef pair<_Base_ptr, _Base_ptr> _Res;
1318  _Link_type __x = _M_begin();
1319  _Link_type __y = _M_end();
1320  bool __comp = true;
1321  while (__x != 0)
1322  {
1323  __y = __x;
1324  __comp = _M_impl._M_key_compare(__k, _S_key(__x));
1325  __x = __comp ? _S_left(__x) : _S_right(__x);
1326  }
1327  iterator __j = iterator(__y);
1328  if (__comp)
1329  {
1330  if (__j == begin())
1331  return _Res(__x, __y);
1332  else
1333  --__j;
1334  }
1335  if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
1336  return _Res(__x, __y);
1337  return _Res(__j._M_node, 0);
1338  }
1339 
1340  template<typename _Key, typename _Val, typename _KeyOfValue,
1341  typename _Compare, typename _Alloc>
1342  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1343  _Compare, _Alloc>::_Base_ptr,
1344  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1345  _Compare, _Alloc>::_Base_ptr>
1346  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1347  _M_get_insert_equal_pos(const key_type& __k)
1348  {
1349  typedef pair<_Base_ptr, _Base_ptr> _Res;
1350  _Link_type __x = _M_begin();
1351  _Link_type __y = _M_end();
1352  while (__x != 0)
1353  {
1354  __y = __x;
1355  __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
1356  _S_left(__x) : _S_right(__x);
1357  }
1358  return _Res(__x, __y);
1359  }
1360 
1361  template<typename _Key, typename _Val, typename _KeyOfValue,
1362  typename _Compare, typename _Alloc>
1363 #if __cplusplus >= 201103L
1364  template<typename _Arg>
1365 #endif
1366  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1367  _Compare, _Alloc>::iterator, bool>
1368  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1369 #if __cplusplus >= 201103L
1370  _M_insert_unique(_Arg&& __v)
1371 #else
1372  _M_insert_unique(const _Val& __v)
1373 #endif
1374  {
1375  typedef pair<iterator, bool> _Res;
1376  pair<_Base_ptr, _Base_ptr> __res
1377  = _M_get_insert_unique_pos(_KeyOfValue()(__v));
1378 
1379  if (__res.second)
1380  return _Res(_M_insert_(__res.first, __res.second,
1381  _GLIBCXX_FORWARD(_Arg, __v)),
1382  true);
1383 
1384  return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1385  }
1386 
1387  template<typename _Key, typename _Val, typename _KeyOfValue,
1388  typename _Compare, typename _Alloc>
1389 #if __cplusplus >= 201103L
1390  template<typename _Arg>
1391 #endif
1392  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1393  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1394 #if __cplusplus >= 201103L
1395  _M_insert_equal(_Arg&& __v)
1396 #else
1397  _M_insert_equal(const _Val& __v)
1398 #endif
1399  {
1400  pair<_Base_ptr, _Base_ptr> __res
1401  = _M_get_insert_equal_pos(_KeyOfValue()(__v));
1402  return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
1403  }
1404 
1405  template<typename _Key, typename _Val, typename _KeyOfValue,
1406  typename _Compare, typename _Alloc>
1407  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1408  _Compare, _Alloc>::_Base_ptr,
1409  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1410  _Compare, _Alloc>::_Base_ptr>
1411  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1412  _M_get_insert_hint_unique_pos(const_iterator __position,
1413  const key_type& __k)
1414  {
1415  iterator __pos = __position._M_const_cast();
1416  typedef pair<_Base_ptr, _Base_ptr> _Res;
1417 
1418  // end()
1419  if (__pos._M_node == _M_end())
1420  {
1421  if (size() > 0
1422  && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
1423  return _Res(0, _M_rightmost());
1424  else
1425  return _M_get_insert_unique_pos(__k);
1426  }
1427  else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
1428  {
1429  // First, try before...
1430  iterator __before = __pos;
1431  if (__pos._M_node == _M_leftmost()) // begin()
1432  return _Res(_M_leftmost(), _M_leftmost());
1433  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
1434  {
1435  if (_S_right(__before._M_node) == 0)
1436  return _Res(0, __before._M_node);
1437  else
1438  return _Res(__pos._M_node, __pos._M_node);
1439  }
1440  else
1441  return _M_get_insert_unique_pos(__k);
1442  }
1443  else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1444  {
1445  // ... then try after.
1446  iterator __after = __pos;
1447  if (__pos._M_node == _M_rightmost())
1448  return _Res(0, _M_rightmost());
1449  else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
1450  {
1451  if (_S_right(__pos._M_node) == 0)
1452  return _Res(0, __pos._M_node);
1453  else
1454  return _Res(__after._M_node, __after._M_node);
1455  }
1456  else
1457  return _M_get_insert_unique_pos(__k);
1458  }
1459  else
1460  // Equivalent keys.
1461  return _Res(__pos._M_node, 0);
1462  }
1463 
1464  template<typename _Key, typename _Val, typename _KeyOfValue,
1465  typename _Compare, typename _Alloc>
1466 #if __cplusplus >= 201103L
1467  template<typename _Arg>
1468 #endif
1469  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1470  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1471 #if __cplusplus >= 201103L
1472  _M_insert_unique_(const_iterator __position, _Arg&& __v)
1473 #else
1474  _M_insert_unique_(const_iterator __position, const _Val& __v)
1475 #endif
1476  {
1477  pair<_Base_ptr, _Base_ptr> __res
1478  = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
1479 
1480  if (__res.second)
1481  return _M_insert_(__res.first, __res.second,
1482  _GLIBCXX_FORWARD(_Arg, __v));
1483  return iterator(static_cast<_Link_type>(__res.first));
1484  }
1485 
1486  template<typename _Key, typename _Val, typename _KeyOfValue,
1487  typename _Compare, typename _Alloc>
1488  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1489  _Compare, _Alloc>::_Base_ptr,
1490  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1491  _Compare, _Alloc>::_Base_ptr>
1492  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1493  _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
1494  {
1495  iterator __pos = __position._M_const_cast();
1496  typedef pair<_Base_ptr, _Base_ptr> _Res;
1497 
1498  // end()
1499  if (__pos._M_node == _M_end())
1500  {
1501  if (size() > 0
1502  && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
1503  return _Res(0, _M_rightmost());
1504  else
1505  return _M_get_insert_equal_pos(__k);
1506  }
1507  else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1508  {
1509  // First, try before...
1510  iterator __before = __pos;
1511  if (__pos._M_node == _M_leftmost()) // begin()
1512  return _Res(_M_leftmost(), _M_leftmost());
1513  else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
1514  {
1515  if (_S_right(__before._M_node) == 0)
1516  return _Res(0, __before._M_node);
1517  else
1518  return _Res(__pos._M_node, __pos._M_node);
1519  }
1520  else
1521  return _M_get_insert_equal_pos(__k);
1522  }
1523  else
1524  {
1525  // ... then try after.
1526  iterator __after = __pos;
1527  if (__pos._M_node == _M_rightmost())
1528  return _Res(0, _M_rightmost());
1529  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
1530  {
1531  if (_S_right(__pos._M_node) == 0)
1532  return _Res(0, __pos._M_node);
1533  else
1534  return _Res(__after._M_node, __after._M_node);
1535  }
1536  else
1537  return _Res(0, 0);
1538  }
1539  }
1540 
1541  template<typename _Key, typename _Val, typename _KeyOfValue,
1542  typename _Compare, typename _Alloc>
1543 #if __cplusplus >= 201103L
1544  template<typename _Arg>
1545 #endif
1546  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1547  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1548 #if __cplusplus >= 201103L
1549  _M_insert_equal_(const_iterator __position, _Arg&& __v)
1550 #else
1551  _M_insert_equal_(const_iterator __position, const _Val& __v)
1552 #endif
1553  {
1554  pair<_Base_ptr, _Base_ptr> __res
1555  = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
1556 
1557  if (__res.second)
1558  return _M_insert_(__res.first, __res.second,
1559  _GLIBCXX_FORWARD(_Arg, __v));
1560 
1561  return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
1562  }
1563 
1564 #if __cplusplus >= 201103L
1565  template<typename _Key, typename _Val, typename _KeyOfValue,
1566  typename _Compare, typename _Alloc>
1567  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1568  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1569  _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
1570  {
1571  bool __insert_left = (__x != 0 || __p == _M_end()
1572  || _M_impl._M_key_compare(_S_key(__z),
1573  _S_key(__p)));
1574 
1575  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1576  this->_M_impl._M_header);
1577  ++_M_impl._M_node_count;
1578  return iterator(__z);
1579  }
1580 
1581  template<typename _Key, typename _Val, typename _KeyOfValue,
1582  typename _Compare, typename _Alloc>
1583  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1584  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1585  _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
1586  {
1587  bool __insert_left = (__p == _M_end()
1588  || !_M_impl._M_key_compare(_S_key(__p),
1589  _S_key(__z)));
1590 
1591  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1592  this->_M_impl._M_header);
1593  ++_M_impl._M_node_count;
1594  return iterator(__z);
1595  }
1596 
1597  template<typename _Key, typename _Val, typename _KeyOfValue,
1598  typename _Compare, typename _Alloc>
1599  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1600  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1601  _M_insert_equal_lower_node(_Link_type __z)
1602  {
1603  _Link_type __x = _M_begin();
1604  _Link_type __y = _M_end();
1605  while (__x != 0)
1606  {
1607  __y = __x;
1608  __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
1609  _S_left(__x) : _S_right(__x);
1610  }
1611  return _M_insert_lower_node(__y, __z);
1612  }
1613 
1614  template<typename _Key, typename _Val, typename _KeyOfValue,
1615  typename _Compare, typename _Alloc>
1616  template<typename... _Args>
1617  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1618  _Compare, _Alloc>::iterator, bool>
1619  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1620  _M_emplace_unique(_Args&&... __args)
1621  {
1622  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1623 
1624  __try
1625  {
1626  typedef pair<iterator, bool> _Res;
1627  auto __res = _M_get_insert_unique_pos(_S_key(__z));
1628  if (__res.second)
1629  return _Res(_M_insert_node(__res.first, __res.second, __z), true);
1630 
1631  _M_destroy_node(__z);
1632  return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1633  }
1634  __catch(...)
1635  {
1636  _M_destroy_node(__z);
1637  __throw_exception_again;
1638  }
1639  }
1640 
1641  template<typename _Key, typename _Val, typename _KeyOfValue,
1642  typename _Compare, typename _Alloc>
1643  template<typename... _Args>
1644  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1645  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1646  _M_emplace_equal(_Args&&... __args)
1647  {
1648  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1649 
1650  __try
1651  {
1652  auto __res = _M_get_insert_equal_pos(_S_key(__z));
1653  return _M_insert_node(__res.first, __res.second, __z);
1654  }
1655  __catch(...)
1656  {
1657  _M_destroy_node(__z);
1658  __throw_exception_again;
1659  }
1660  }
1661 
1662  template<typename _Key, typename _Val, typename _KeyOfValue,
1663  typename _Compare, typename _Alloc>
1664  template<typename... _Args>
1665  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1666  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1667  _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
1668  {
1669  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1670 
1671  __try
1672  {
1673  auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
1674 
1675  if (__res.second)
1676  return _M_insert_node(__res.first, __res.second, __z);
1677 
1678  _M_destroy_node(__z);
1679  return iterator(static_cast<_Link_type>(__res.first));
1680  }
1681  __catch(...)
1682  {
1683  _M_destroy_node(__z);
1684  __throw_exception_again;
1685  }
1686  }
1687 
1688  template<typename _Key, typename _Val, typename _KeyOfValue,
1689  typename _Compare, typename _Alloc>
1690  template<typename... _Args>
1691  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1692  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1693  _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
1694  {
1695  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1696 
1697  __try
1698  {
1699  auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
1700 
1701  if (__res.second)
1702  return _M_insert_node(__res.first, __res.second, __z);
1703 
1704  return _M_insert_equal_lower_node(__z);
1705  }
1706  __catch(...)
1707  {
1708  _M_destroy_node(__z);
1709  __throw_exception_again;
1710  }
1711  }
1712 #endif
1713 
1714  template<typename _Key, typename _Val, typename _KoV,
1715  typename _Cmp, typename _Alloc>
1716  template<class _II>
1717  void
1718  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1719  _M_insert_unique(_II __first, _II __last)
1720  {
1721  for (; __first != __last; ++__first)
1722  _M_insert_unique_(end(), *__first);
1723  }
1724 
1725  template<typename _Key, typename _Val, typename _KoV,
1726  typename _Cmp, typename _Alloc>
1727  template<class _II>
1728  void
1729  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1730  _M_insert_equal(_II __first, _II __last)
1731  {
1732  for (; __first != __last; ++__first)
1733  _M_insert_equal_(end(), *__first);
1734  }
1735 
1736  template<typename _Key, typename _Val, typename _KeyOfValue,
1737  typename _Compare, typename _Alloc>
1738  void
1739  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1740  _M_erase_aux(const_iterator __position)
1741  {
1742  _Link_type __y =
1743  static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1744  (const_cast<_Base_ptr>(__position._M_node),
1745  this->_M_impl._M_header));
1746  _M_destroy_node(__y);
1747  --_M_impl._M_node_count;
1748  }
1749 
1750  template<typename _Key, typename _Val, typename _KeyOfValue,
1751  typename _Compare, typename _Alloc>
1752  void
1753  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1754  _M_erase_aux(const_iterator __first, const_iterator __last)
1755  {
1756  if (__first == begin() && __last == end())
1757  clear();
1758  else
1759  while (__first != __last)
1760  erase(__first++);
1761  }
1762 
1763  template<typename _Key, typename _Val, typename _KeyOfValue,
1764  typename _Compare, typename _Alloc>
1765  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1766  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1767  erase(const _Key& __x)
1768  {
1769  pair<iterator, iterator> __p = equal_range(__x);
1770  const size_type __old_size = size();
1771  erase(__p.first, __p.second);
1772  return __old_size - size();
1773  }
1774 
1775  template<typename _Key, typename _Val, typename _KeyOfValue,
1776  typename _Compare, typename _Alloc>
1777  void
1778  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1779  erase(const _Key* __first, const _Key* __last)
1780  {
1781  while (__first != __last)
1782  erase(*__first++);
1783  }
1784 
1785  template<typename _Key, typename _Val, typename _KeyOfValue,
1786  typename _Compare, typename _Alloc>
1787  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1788  _Compare, _Alloc>::iterator
1789  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1790  find(const _Key& __k)
1791  {
1792  iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1793  return (__j == end()
1794  || _M_impl._M_key_compare(__k,
1795  _S_key(__j._M_node))) ? end() : __j;
1796  }
1797 
1798  template<typename _Key, typename _Val, typename _KeyOfValue,
1799  typename _Compare, typename _Alloc>
1800  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1801  _Compare, _Alloc>::const_iterator
1802  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1803  find(const _Key& __k) const
1804  {
1805  const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1806  return (__j == end()
1807  || _M_impl._M_key_compare(__k,
1808  _S_key(__j._M_node))) ? end() : __j;
1809  }
1810 
1811  template<typename _Key, typename _Val, typename _KeyOfValue,
1812  typename _Compare, typename _Alloc>
1813  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1814  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1815  count(const _Key& __k) const
1816  {
1817  pair<const_iterator, const_iterator> __p = equal_range(__k);
1818  const size_type __n = std::distance(__p.first, __p.second);
1819  return __n;
1820  }
1821 
1822  _GLIBCXX_PURE unsigned int
1823  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1824  const _Rb_tree_node_base* __root) throw ();
1825 
1826  template<typename _Key, typename _Val, typename _KeyOfValue,
1827  typename _Compare, typename _Alloc>
1828  bool
1829  _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1830  {
1831  if (_M_impl._M_node_count == 0 || begin() == end())
1832  return _M_impl._M_node_count == 0 && begin() == end()
1833  && this->_M_impl._M_header._M_left == _M_end()
1834  && this->_M_impl._M_header._M_right == _M_end();
1835 
1836  unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1837  for (const_iterator __it = begin(); __it != end(); ++__it)
1838  {
1839  _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1840  _Const_Link_type __L = _S_left(__x);
1841  _Const_Link_type __R = _S_right(__x);
1842 
1843  if (__x->_M_color == _S_red)
1844  if ((__L && __L->_M_color == _S_red)
1845  || (__R && __R->_M_color == _S_red))
1846  return false;
1847 
1848  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1849  return false;
1850  if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1851  return false;
1852 
1853  if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1854  return false;
1855  }
1856 
1857  if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1858  return false;
1859  if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1860  return false;
1861  return true;
1862  }
1863 
1864 _GLIBCXX_END_NAMESPACE_VERSION
1865 } // namespace
1866 
1867 #endif
std::equal
bool equal(_II1 __first1, _II1 __last1, _II2 __first2)
Tests a range for element-wise equality.
Definition: stl_algobase.h:1021
std::end
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
std::distance
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:114
std::forward
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition: move.h:76
std::__addressof
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
std::operator>=
bool operator>=(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string doesn't precede string.
Definition: basic_string.h:2680
std
ISO C++ entities toplevel namespace is std.
std::lexicographical_compare
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.
Definition: stl_algobase.h:1120
std::begin
auto begin(_Container &__cont) -> decltype(__cont.begin())
Return an iterator pointing to the first element of the container.
Definition: range_access.h:48
std::swap
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:166
std::allocator_traits::construct
static auto construct(_Alloc &__a, _Tp *__p, _Args &&...__args) -> decltype(_S_construct(__a, __p, std::forward< _Args >(__args)...))
Construct an object of type _Tp.
Definition: bits/alloc_traits.h:391
std::operator>
bool operator>(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string follows string.
Definition: basic_string.h:2606