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 static_cast<_Link_type>(&this->_M_impl._M_header); }
514 
515  _Const_Link_type
516  _M_end() const
517  { return static_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  iterator
804  erase(const_iterator __position)
805  {
806  const_iterator __result = __position;
807  ++__result;
808  _M_erase_aux(__position);
809  return __result._M_const_cast();
810  }
811 
812  // LWG 2059.
813  iterator
814  erase(iterator __position)
815  {
816  iterator __result = __position;
817  ++__result;
818  _M_erase_aux(__position);
819  return __result;
820  }
821 #else
822  void
823  erase(iterator __position)
824  { _M_erase_aux(__position); }
825 
826  void
827  erase(const_iterator __position)
828  { _M_erase_aux(__position); }
829 #endif
830  size_type
831  erase(const key_type& __x);
832 
833 #if __cplusplus >= 201103L
834  // _GLIBCXX_RESOLVE_LIB_DEFECTS
835  // DR 130. Associative erase should return an iterator.
836  iterator
837  erase(const_iterator __first, const_iterator __last)
838  {
839  _M_erase_aux(__first, __last);
840  return __last._M_const_cast();
841  }
842 #else
843  void
844  erase(iterator __first, iterator __last)
845  { _M_erase_aux(__first, __last); }
846 
847  void
848  erase(const_iterator __first, const_iterator __last)
849  { _M_erase_aux(__first, __last); }
850 #endif
851  void
852  erase(const key_type* __first, const key_type* __last);
853 
854  void
855  clear() _GLIBCXX_NOEXCEPT
856  {
857  _M_erase(_M_begin());
858  _M_leftmost() = _M_end();
859  _M_root() = 0;
860  _M_rightmost() = _M_end();
861  _M_impl._M_node_count = 0;
862  }
863 
864  // Set operations.
865  iterator
866  find(const key_type& __k);
867 
868  const_iterator
869  find(const key_type& __k) const;
870 
871  size_type
872  count(const key_type& __k) const;
873 
874  iterator
875  lower_bound(const key_type& __k)
876  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
877 
878  const_iterator
879  lower_bound(const key_type& __k) const
880  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
881 
882  iterator
883  upper_bound(const key_type& __k)
884  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
885 
886  const_iterator
887  upper_bound(const key_type& __k) const
888  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
889 
890  pair<iterator, iterator>
891  equal_range(const key_type& __k);
892 
893  pair<const_iterator, const_iterator>
894  equal_range(const key_type& __k) const;
895 
896  // Debugging.
897  bool
898  __rb_verify() const;
899  };
900 
901  template<typename _Key, typename _Val, typename _KeyOfValue,
902  typename _Compare, typename _Alloc>
903  inline bool
904  operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
905  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
906  {
907  return __x.size() == __y.size()
908  && std::equal(__x.begin(), __x.end(), __y.begin());
909  }
910 
911  template<typename _Key, typename _Val, typename _KeyOfValue,
912  typename _Compare, typename _Alloc>
913  inline bool
914  operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
915  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
916  {
917  return std::lexicographical_compare(__x.begin(), __x.end(),
918  __y.begin(), __y.end());
919  }
920 
921  template<typename _Key, typename _Val, typename _KeyOfValue,
922  typename _Compare, typename _Alloc>
923  inline bool
924  operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
925  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
926  { return !(__x == __y); }
927 
928  template<typename _Key, typename _Val, typename _KeyOfValue,
929  typename _Compare, typename _Alloc>
930  inline bool
931  operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
932  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
933  { return __y < __x; }
934 
935  template<typename _Key, typename _Val, typename _KeyOfValue,
936  typename _Compare, typename _Alloc>
937  inline bool
938  operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
939  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
940  { return !(__y < __x); }
941 
942  template<typename _Key, typename _Val, typename _KeyOfValue,
943  typename _Compare, typename _Alloc>
944  inline bool
945  operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
946  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
947  { return !(__x < __y); }
948 
949  template<typename _Key, typename _Val, typename _KeyOfValue,
950  typename _Compare, typename _Alloc>
951  inline void
952  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
953  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
954  { __x.swap(__y); }
955 
956 #if __cplusplus >= 201103L
957  template<typename _Key, typename _Val, typename _KeyOfValue,
958  typename _Compare, typename _Alloc>
959  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
960  _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
961  : _M_impl(__x._M_impl._M_key_compare,
962  std::move(__x._M_get_Node_allocator()))
963  {
964  if (__x._M_root() != 0)
965  {
966  _M_root() = __x._M_root();
967  _M_leftmost() = __x._M_leftmost();
968  _M_rightmost() = __x._M_rightmost();
969  _M_root()->_M_parent = _M_end();
970 
971  __x._M_root() = 0;
972  __x._M_leftmost() = __x._M_end();
973  __x._M_rightmost() = __x._M_end();
974 
975  this->_M_impl._M_node_count = __x._M_impl._M_node_count;
976  __x._M_impl._M_node_count = 0;
977  }
978  }
979 #endif
980 
981  template<typename _Key, typename _Val, typename _KeyOfValue,
982  typename _Compare, typename _Alloc>
983  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
984  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
985  operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
986  {
987  if (this != &__x)
988  {
989  // Note that _Key may be a constant type.
990  clear();
991  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
992  if (__x._M_root() != 0)
993  {
994  _M_root() = _M_copy(__x._M_begin(), _M_end());
995  _M_leftmost() = _S_minimum(_M_root());
996  _M_rightmost() = _S_maximum(_M_root());
997  _M_impl._M_node_count = __x._M_impl._M_node_count;
998  }
999  }
1000  return *this;
1001  }
1002 
1003  template<typename _Key, typename _Val, typename _KeyOfValue,
1004  typename _Compare, typename _Alloc>
1005 #if __cplusplus >= 201103L
1006  template<typename _Arg>
1007 #endif
1008  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1009  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1010 #if __cplusplus >= 201103L
1011  _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
1012 #else
1013  _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
1014 #endif
1015  {
1016  bool __insert_left = (__x != 0 || __p == _M_end()
1017  || _M_impl._M_key_compare(_KeyOfValue()(__v),
1018  _S_key(__p)));
1019 
1020  _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1021 
1022  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1023  this->_M_impl._M_header);
1024  ++_M_impl._M_node_count;
1025  return iterator(__z);
1026  }
1027 
1028  template<typename _Key, typename _Val, typename _KeyOfValue,
1029  typename _Compare, typename _Alloc>
1030 #if __cplusplus >= 201103L
1031  template<typename _Arg>
1032 #endif
1033  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1034  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1035 #if __cplusplus >= 201103L
1036  _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1037 #else
1038  _M_insert_lower(_Base_ptr __p, const _Val& __v)
1039 #endif
1040  {
1041  bool __insert_left = (__p == _M_end()
1042  || !_M_impl._M_key_compare(_S_key(__p),
1043  _KeyOfValue()(__v)));
1044 
1045  _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1046 
1047  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1048  this->_M_impl._M_header);
1049  ++_M_impl._M_node_count;
1050  return iterator(__z);
1051  }
1052 
1053  template<typename _Key, typename _Val, typename _KeyOfValue,
1054  typename _Compare, typename _Alloc>
1055 #if __cplusplus >= 201103L
1056  template<typename _Arg>
1057 #endif
1058  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1059  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1060 #if __cplusplus >= 201103L
1061  _M_insert_equal_lower(_Arg&& __v)
1062 #else
1063  _M_insert_equal_lower(const _Val& __v)
1064 #endif
1065  {
1066  _Link_type __x = _M_begin();
1067  _Link_type __y = _M_end();
1068  while (__x != 0)
1069  {
1070  __y = __x;
1071  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1072  _S_left(__x) : _S_right(__x);
1073  }
1074  return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1075  }
1076 
1077  template<typename _Key, typename _Val, typename _KoV,
1078  typename _Compare, typename _Alloc>
1079  typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1080  _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1081  _M_copy(_Const_Link_type __x, _Link_type __p)
1082  {
1083  // Structural copy. __x and __p must be non-null.
1084  _Link_type __top = _M_clone_node(__x);
1085  __top->_M_parent = __p;
1086 
1087  __try
1088  {
1089  if (__x->_M_right)
1090  __top->_M_right = _M_copy(_S_right(__x), __top);
1091  __p = __top;
1092  __x = _S_left(__x);
1093 
1094  while (__x != 0)
1095  {
1096  _Link_type __y = _M_clone_node(__x);
1097  __p->_M_left = __y;
1098  __y->_M_parent = __p;
1099  if (__x->_M_right)
1100  __y->_M_right = _M_copy(_S_right(__x), __y);
1101  __p = __y;
1102  __x = _S_left(__x);
1103  }
1104  }
1105  __catch(...)
1106  {
1107  _M_erase(__top);
1108  __throw_exception_again;
1109  }
1110  return __top;
1111  }
1112 
1113  template<typename _Key, typename _Val, typename _KeyOfValue,
1114  typename _Compare, typename _Alloc>
1115  void
1116  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1117  _M_erase(_Link_type __x)
1118  {
1119  // Erase without rebalancing.
1120  while (__x != 0)
1121  {
1122  _M_erase(_S_right(__x));
1123  _Link_type __y = _S_left(__x);
1124  _M_destroy_node(__x);
1125  __x = __y;
1126  }
1127  }
1128 
1129  template<typename _Key, typename _Val, typename _KeyOfValue,
1130  typename _Compare, typename _Alloc>
1131  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1132  _Compare, _Alloc>::iterator
1133  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1134  _M_lower_bound(_Link_type __x, _Link_type __y,
1135  const _Key& __k)
1136  {
1137  while (__x != 0)
1138  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1139  __y = __x, __x = _S_left(__x);
1140  else
1141  __x = _S_right(__x);
1142  return iterator(__y);
1143  }
1144 
1145  template<typename _Key, typename _Val, typename _KeyOfValue,
1146  typename _Compare, typename _Alloc>
1147  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1148  _Compare, _Alloc>::const_iterator
1149  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1150  _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1151  const _Key& __k) const
1152  {
1153  while (__x != 0)
1154  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1155  __y = __x, __x = _S_left(__x);
1156  else
1157  __x = _S_right(__x);
1158  return const_iterator(__y);
1159  }
1160 
1161  template<typename _Key, typename _Val, typename _KeyOfValue,
1162  typename _Compare, typename _Alloc>
1163  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1164  _Compare, _Alloc>::iterator
1165  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1166  _M_upper_bound(_Link_type __x, _Link_type __y,
1167  const _Key& __k)
1168  {
1169  while (__x != 0)
1170  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1171  __y = __x, __x = _S_left(__x);
1172  else
1173  __x = _S_right(__x);
1174  return iterator(__y);
1175  }
1176 
1177  template<typename _Key, typename _Val, typename _KeyOfValue,
1178  typename _Compare, typename _Alloc>
1179  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1180  _Compare, _Alloc>::const_iterator
1181  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1182  _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1183  const _Key& __k) const
1184  {
1185  while (__x != 0)
1186  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1187  __y = __x, __x = _S_left(__x);
1188  else
1189  __x = _S_right(__x);
1190  return const_iterator(__y);
1191  }
1192 
1193  template<typename _Key, typename _Val, typename _KeyOfValue,
1194  typename _Compare, typename _Alloc>
1195  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1196  _Compare, _Alloc>::iterator,
1197  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1198  _Compare, _Alloc>::iterator>
1199  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1200  equal_range(const _Key& __k)
1201  {
1202  _Link_type __x = _M_begin();
1203  _Link_type __y = _M_end();
1204  while (__x != 0)
1205  {
1206  if (_M_impl._M_key_compare(_S_key(__x), __k))
1207  __x = _S_right(__x);
1208  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1209  __y = __x, __x = _S_left(__x);
1210  else
1211  {
1212  _Link_type __xu(__x), __yu(__y);
1213  __y = __x, __x = _S_left(__x);
1214  __xu = _S_right(__xu);
1215  return pair<iterator,
1216  iterator>(_M_lower_bound(__x, __y, __k),
1217  _M_upper_bound(__xu, __yu, __k));
1218  }
1219  }
1220  return pair<iterator, iterator>(iterator(__y),
1221  iterator(__y));
1222  }
1223 
1224  template<typename _Key, typename _Val, typename _KeyOfValue,
1225  typename _Compare, typename _Alloc>
1226  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1227  _Compare, _Alloc>::const_iterator,
1228  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1229  _Compare, _Alloc>::const_iterator>
1230  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1231  equal_range(const _Key& __k) const
1232  {
1233  _Const_Link_type __x = _M_begin();
1234  _Const_Link_type __y = _M_end();
1235  while (__x != 0)
1236  {
1237  if (_M_impl._M_key_compare(_S_key(__x), __k))
1238  __x = _S_right(__x);
1239  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1240  __y = __x, __x = _S_left(__x);
1241  else
1242  {
1243  _Const_Link_type __xu(__x), __yu(__y);
1244  __y = __x, __x = _S_left(__x);
1245  __xu = _S_right(__xu);
1246  return pair<const_iterator,
1247  const_iterator>(_M_lower_bound(__x, __y, __k),
1248  _M_upper_bound(__xu, __yu, __k));
1249  }
1250  }
1251  return pair<const_iterator, const_iterator>(const_iterator(__y),
1252  const_iterator(__y));
1253  }
1254 
1255  template<typename _Key, typename _Val, typename _KeyOfValue,
1256  typename _Compare, typename _Alloc>
1257  void
1258  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1259  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1260  {
1261  if (_M_root() == 0)
1262  {
1263  if (__t._M_root() != 0)
1264  {
1265  _M_root() = __t._M_root();
1266  _M_leftmost() = __t._M_leftmost();
1267  _M_rightmost() = __t._M_rightmost();
1268  _M_root()->_M_parent = _M_end();
1269 
1270  __t._M_root() = 0;
1271  __t._M_leftmost() = __t._M_end();
1272  __t._M_rightmost() = __t._M_end();
1273  }
1274  }
1275  else if (__t._M_root() == 0)
1276  {
1277  __t._M_root() = _M_root();
1278  __t._M_leftmost() = _M_leftmost();
1279  __t._M_rightmost() = _M_rightmost();
1280  __t._M_root()->_M_parent = __t._M_end();
1281 
1282  _M_root() = 0;
1283  _M_leftmost() = _M_end();
1284  _M_rightmost() = _M_end();
1285  }
1286  else
1287  {
1288  std::swap(_M_root(),__t._M_root());
1289  std::swap(_M_leftmost(),__t._M_leftmost());
1290  std::swap(_M_rightmost(),__t._M_rightmost());
1291 
1292  _M_root()->_M_parent = _M_end();
1293  __t._M_root()->_M_parent = __t._M_end();
1294  }
1295  // No need to swap header's color as it does not change.
1296  std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1297  std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1298 
1299  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1300  // 431. Swapping containers with unequal allocators.
1301  std::__alloc_swap<_Node_allocator>::
1302  _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
1303  }
1304 
1305  template<typename _Key, typename _Val, typename _KeyOfValue,
1306  typename _Compare, typename _Alloc>
1307  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1308  _Compare, _Alloc>::_Base_ptr,
1309  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1310  _Compare, _Alloc>::_Base_ptr>
1311  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1312  _M_get_insert_unique_pos(const key_type& __k)
1313  {
1314  typedef pair<_Base_ptr, _Base_ptr> _Res;
1315  _Link_type __x = _M_begin();
1316  _Link_type __y = _M_end();
1317  bool __comp = true;
1318  while (__x != 0)
1319  {
1320  __y = __x;
1321  __comp = _M_impl._M_key_compare(__k, _S_key(__x));
1322  __x = __comp ? _S_left(__x) : _S_right(__x);
1323  }
1324  iterator __j = iterator(__y);
1325  if (__comp)
1326  {
1327  if (__j == begin())
1328  return _Res(__x, __y);
1329  else
1330  --__j;
1331  }
1332  if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
1333  return _Res(__x, __y);
1334  return _Res(__j._M_node, 0);
1335  }
1336 
1337  template<typename _Key, typename _Val, typename _KeyOfValue,
1338  typename _Compare, typename _Alloc>
1339  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1340  _Compare, _Alloc>::_Base_ptr,
1341  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1342  _Compare, _Alloc>::_Base_ptr>
1343  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1344  _M_get_insert_equal_pos(const key_type& __k)
1345  {
1346  typedef pair<_Base_ptr, _Base_ptr> _Res;
1347  _Link_type __x = _M_begin();
1348  _Link_type __y = _M_end();
1349  while (__x != 0)
1350  {
1351  __y = __x;
1352  __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
1353  _S_left(__x) : _S_right(__x);
1354  }
1355  return _Res(__x, __y);
1356  }
1357 
1358  template<typename _Key, typename _Val, typename _KeyOfValue,
1359  typename _Compare, typename _Alloc>
1360 #if __cplusplus >= 201103L
1361  template<typename _Arg>
1362 #endif
1363  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1364  _Compare, _Alloc>::iterator, bool>
1365  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1366 #if __cplusplus >= 201103L
1367  _M_insert_unique(_Arg&& __v)
1368 #else
1369  _M_insert_unique(const _Val& __v)
1370 #endif
1371  {
1372  typedef pair<iterator, bool> _Res;
1373  pair<_Base_ptr, _Base_ptr> __res
1374  = _M_get_insert_unique_pos(_KeyOfValue()(__v));
1375 
1376  if (__res.second)
1377  return _Res(_M_insert_(__res.first, __res.second,
1378  _GLIBCXX_FORWARD(_Arg, __v)),
1379  true);
1380 
1381  return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1382  }
1383 
1384  template<typename _Key, typename _Val, typename _KeyOfValue,
1385  typename _Compare, typename _Alloc>
1386 #if __cplusplus >= 201103L
1387  template<typename _Arg>
1388 #endif
1389  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1390  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1391 #if __cplusplus >= 201103L
1392  _M_insert_equal(_Arg&& __v)
1393 #else
1394  _M_insert_equal(const _Val& __v)
1395 #endif
1396  {
1397  pair<_Base_ptr, _Base_ptr> __res
1398  = _M_get_insert_equal_pos(_KeyOfValue()(__v));
1399  return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
1400  }
1401 
1402  template<typename _Key, typename _Val, typename _KeyOfValue,
1403  typename _Compare, typename _Alloc>
1404  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1405  _Compare, _Alloc>::_Base_ptr,
1406  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1407  _Compare, _Alloc>::_Base_ptr>
1408  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1409  _M_get_insert_hint_unique_pos(const_iterator __position,
1410  const key_type& __k)
1411  {
1412  iterator __pos = __position._M_const_cast();
1413  typedef pair<_Base_ptr, _Base_ptr> _Res;
1414 
1415  // end()
1416  if (__pos._M_node == _M_end())
1417  {
1418  if (size() > 0
1419  && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
1420  return _Res(0, _M_rightmost());
1421  else
1422  return _M_get_insert_unique_pos(__k);
1423  }
1424  else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
1425  {
1426  // First, try before...
1427  iterator __before = __pos;
1428  if (__pos._M_node == _M_leftmost()) // begin()
1429  return _Res(_M_leftmost(), _M_leftmost());
1430  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
1431  {
1432  if (_S_right(__before._M_node) == 0)
1433  return _Res(0, __before._M_node);
1434  else
1435  return _Res(__pos._M_node, __pos._M_node);
1436  }
1437  else
1438  return _M_get_insert_unique_pos(__k);
1439  }
1440  else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1441  {
1442  // ... then try after.
1443  iterator __after = __pos;
1444  if (__pos._M_node == _M_rightmost())
1445  return _Res(0, _M_rightmost());
1446  else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
1447  {
1448  if (_S_right(__pos._M_node) == 0)
1449  return _Res(0, __pos._M_node);
1450  else
1451  return _Res(__after._M_node, __after._M_node);
1452  }
1453  else
1454  return _M_get_insert_unique_pos(__k);
1455  }
1456  else
1457  // Equivalent keys.
1458  return _Res(__pos._M_node, 0);
1459  }
1460 
1461  template<typename _Key, typename _Val, typename _KeyOfValue,
1462  typename _Compare, typename _Alloc>
1463 #if __cplusplus >= 201103L
1464  template<typename _Arg>
1465 #endif
1466  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1467  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1468 #if __cplusplus >= 201103L
1469  _M_insert_unique_(const_iterator __position, _Arg&& __v)
1470 #else
1471  _M_insert_unique_(const_iterator __position, const _Val& __v)
1472 #endif
1473  {
1474  pair<_Base_ptr, _Base_ptr> __res
1475  = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
1476 
1477  if (__res.second)
1478  return _M_insert_(__res.first, __res.second,
1479  _GLIBCXX_FORWARD(_Arg, __v));
1480  return iterator(static_cast<_Link_type>(__res.first));
1481  }
1482 
1483  template<typename _Key, typename _Val, typename _KeyOfValue,
1484  typename _Compare, typename _Alloc>
1485  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1486  _Compare, _Alloc>::_Base_ptr,
1487  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1488  _Compare, _Alloc>::_Base_ptr>
1489  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1490  _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
1491  {
1492  iterator __pos = __position._M_const_cast();
1493  typedef pair<_Base_ptr, _Base_ptr> _Res;
1494 
1495  // end()
1496  if (__pos._M_node == _M_end())
1497  {
1498  if (size() > 0
1499  && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
1500  return _Res(0, _M_rightmost());
1501  else
1502  return _M_get_insert_equal_pos(__k);
1503  }
1504  else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1505  {
1506  // First, try before...
1507  iterator __before = __pos;
1508  if (__pos._M_node == _M_leftmost()) // begin()
1509  return _Res(_M_leftmost(), _M_leftmost());
1510  else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
1511  {
1512  if (_S_right(__before._M_node) == 0)
1513  return _Res(0, __before._M_node);
1514  else
1515  return _Res(__pos._M_node, __pos._M_node);
1516  }
1517  else
1518  return _M_get_insert_equal_pos(__k);
1519  }
1520  else
1521  {
1522  // ... then try after.
1523  iterator __after = __pos;
1524  if (__pos._M_node == _M_rightmost())
1525  return _Res(0, _M_rightmost());
1526  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
1527  {
1528  if (_S_right(__pos._M_node) == 0)
1529  return _Res(0, __pos._M_node);
1530  else
1531  return _Res(__after._M_node, __after._M_node);
1532  }
1533  else
1534  return _Res(0, 0);
1535  }
1536  }
1537 
1538  template<typename _Key, typename _Val, typename _KeyOfValue,
1539  typename _Compare, typename _Alloc>
1540 #if __cplusplus >= 201103L
1541  template<typename _Arg>
1542 #endif
1543  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1544  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1545 #if __cplusplus >= 201103L
1546  _M_insert_equal_(const_iterator __position, _Arg&& __v)
1547 #else
1548  _M_insert_equal_(const_iterator __position, const _Val& __v)
1549 #endif
1550  {
1551  pair<_Base_ptr, _Base_ptr> __res
1552  = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
1553 
1554  if (__res.second)
1555  return _M_insert_(__res.first, __res.second,
1556  _GLIBCXX_FORWARD(_Arg, __v));
1557 
1558  return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
1559  }
1560 
1561 #if __cplusplus >= 201103L
1562  template<typename _Key, typename _Val, typename _KeyOfValue,
1563  typename _Compare, typename _Alloc>
1564  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1565  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1566  _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
1567  {
1568  bool __insert_left = (__x != 0 || __p == _M_end()
1569  || _M_impl._M_key_compare(_S_key(__z),
1570  _S_key(__p)));
1571 
1572  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1573  this->_M_impl._M_header);
1574  ++_M_impl._M_node_count;
1575  return iterator(__z);
1576  }
1577 
1578  template<typename _Key, typename _Val, typename _KeyOfValue,
1579  typename _Compare, typename _Alloc>
1580  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1581  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1582  _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
1583  {
1584  bool __insert_left = (__p == _M_end()
1585  || !_M_impl._M_key_compare(_S_key(__p),
1586  _S_key(__z)));
1587 
1588  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1589  this->_M_impl._M_header);
1590  ++_M_impl._M_node_count;
1591  return iterator(__z);
1592  }
1593 
1594  template<typename _Key, typename _Val, typename _KeyOfValue,
1595  typename _Compare, typename _Alloc>
1596  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1597  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1598  _M_insert_equal_lower_node(_Link_type __z)
1599  {
1600  _Link_type __x = _M_begin();
1601  _Link_type __y = _M_end();
1602  while (__x != 0)
1603  {
1604  __y = __x;
1605  __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
1606  _S_left(__x) : _S_right(__x);
1607  }
1608  return _M_insert_lower_node(__y, __z);
1609  }
1610 
1611  template<typename _Key, typename _Val, typename _KeyOfValue,
1612  typename _Compare, typename _Alloc>
1613  template<typename... _Args>
1614  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1615  _Compare, _Alloc>::iterator, bool>
1616  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1617  _M_emplace_unique(_Args&&... __args)
1618  {
1619  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1620 
1621  __try
1622  {
1623  typedef pair<iterator, bool> _Res;
1624  auto __res = _M_get_insert_unique_pos(_S_key(__z));
1625  if (__res.second)
1626  return _Res(_M_insert_node(__res.first, __res.second, __z), true);
1627 
1628  _M_destroy_node(__z);
1629  return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1630  }
1631  __catch(...)
1632  {
1633  _M_destroy_node(__z);
1634  __throw_exception_again;
1635  }
1636  }
1637 
1638  template<typename _Key, typename _Val, typename _KeyOfValue,
1639  typename _Compare, typename _Alloc>
1640  template<typename... _Args>
1641  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1642  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1643  _M_emplace_equal(_Args&&... __args)
1644  {
1645  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1646 
1647  __try
1648  {
1649  auto __res = _M_get_insert_equal_pos(_S_key(__z));
1650  return _M_insert_node(__res.first, __res.second, __z);
1651  }
1652  __catch(...)
1653  {
1654  _M_destroy_node(__z);
1655  __throw_exception_again;
1656  }
1657  }
1658 
1659  template<typename _Key, typename _Val, typename _KeyOfValue,
1660  typename _Compare, typename _Alloc>
1661  template<typename... _Args>
1662  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1663  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1664  _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
1665  {
1666  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1667 
1668  __try
1669  {
1670  auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
1671 
1672  if (__res.second)
1673  return _M_insert_node(__res.first, __res.second, __z);
1674 
1675  _M_destroy_node(__z);
1676  return iterator(static_cast<_Link_type>(__res.first));
1677  }
1678  __catch(...)
1679  {
1680  _M_destroy_node(__z);
1681  __throw_exception_again;
1682  }
1683  }
1684 
1685  template<typename _Key, typename _Val, typename _KeyOfValue,
1686  typename _Compare, typename _Alloc>
1687  template<typename... _Args>
1688  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1689  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1690  _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
1691  {
1692  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1693 
1694  __try
1695  {
1696  auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
1697 
1698  if (__res.second)
1699  return _M_insert_node(__res.first, __res.second, __z);
1700 
1701  return _M_insert_equal_lower_node(__z);
1702  }
1703  __catch(...)
1704  {
1705  _M_destroy_node(__z);
1706  __throw_exception_again;
1707  }
1708  }
1709 #endif
1710 
1711  template<typename _Key, typename _Val, typename _KoV,
1712  typename _Cmp, typename _Alloc>
1713  template<class _II>
1714  void
1715  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1716  _M_insert_unique(_II __first, _II __last)
1717  {
1718  for (; __first != __last; ++__first)
1719  _M_insert_unique_(end(), *__first);
1720  }
1721 
1722  template<typename _Key, typename _Val, typename _KoV,
1723  typename _Cmp, typename _Alloc>
1724  template<class _II>
1725  void
1726  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1727  _M_insert_equal(_II __first, _II __last)
1728  {
1729  for (; __first != __last; ++__first)
1730  _M_insert_equal_(end(), *__first);
1731  }
1732 
1733  template<typename _Key, typename _Val, typename _KeyOfValue,
1734  typename _Compare, typename _Alloc>
1735  void
1736  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1737  _M_erase_aux(const_iterator __position)
1738  {
1739  _Link_type __y =
1740  static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1741  (const_cast<_Base_ptr>(__position._M_node),
1742  this->_M_impl._M_header));
1743  _M_destroy_node(__y);
1744  --_M_impl._M_node_count;
1745  }
1746 
1747  template<typename _Key, typename _Val, typename _KeyOfValue,
1748  typename _Compare, typename _Alloc>
1749  void
1750  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1751  _M_erase_aux(const_iterator __first, const_iterator __last)
1752  {
1753  if (__first == begin() && __last == end())
1754  clear();
1755  else
1756  while (__first != __last)
1757  erase(__first++);
1758  }
1759 
1760  template<typename _Key, typename _Val, typename _KeyOfValue,
1761  typename _Compare, typename _Alloc>
1762  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1763  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1764  erase(const _Key& __x)
1765  {
1766  pair<iterator, iterator> __p = equal_range(__x);
1767  const size_type __old_size = size();
1768  erase(__p.first, __p.second);
1769  return __old_size - size();
1770  }
1771 
1772  template<typename _Key, typename _Val, typename _KeyOfValue,
1773  typename _Compare, typename _Alloc>
1774  void
1775  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1776  erase(const _Key* __first, const _Key* __last)
1777  {
1778  while (__first != __last)
1779  erase(*__first++);
1780  }
1781 
1782  template<typename _Key, typename _Val, typename _KeyOfValue,
1783  typename _Compare, typename _Alloc>
1784  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1785  _Compare, _Alloc>::iterator
1786  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1787  find(const _Key& __k)
1788  {
1789  iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1790  return (__j == end()
1791  || _M_impl._M_key_compare(__k,
1792  _S_key(__j._M_node))) ? end() : __j;
1793  }
1794 
1795  template<typename _Key, typename _Val, typename _KeyOfValue,
1796  typename _Compare, typename _Alloc>
1797  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1798  _Compare, _Alloc>::const_iterator
1799  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1800  find(const _Key& __k) const
1801  {
1802  const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1803  return (__j == end()
1804  || _M_impl._M_key_compare(__k,
1805  _S_key(__j._M_node))) ? end() : __j;
1806  }
1807 
1808  template<typename _Key, typename _Val, typename _KeyOfValue,
1809  typename _Compare, typename _Alloc>
1810  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1811  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1812  count(const _Key& __k) const
1813  {
1814  pair<const_iterator, const_iterator> __p = equal_range(__k);
1815  const size_type __n = std::distance(__p.first, __p.second);
1816  return __n;
1817  }
1818 
1819  _GLIBCXX_PURE unsigned int
1820  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1821  const _Rb_tree_node_base* __root) throw ();
1822 
1823  template<typename _Key, typename _Val, typename _KeyOfValue,
1824  typename _Compare, typename _Alloc>
1825  bool
1826  _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1827  {
1828  if (_M_impl._M_node_count == 0 || begin() == end())
1829  return _M_impl._M_node_count == 0 && begin() == end()
1830  && this->_M_impl._M_header._M_left == _M_end()
1831  && this->_M_impl._M_header._M_right == _M_end();
1832 
1833  unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1834  for (const_iterator __it = begin(); __it != end(); ++__it)
1835  {
1836  _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1837  _Const_Link_type __L = _S_left(__x);
1838  _Const_Link_type __R = _S_right(__x);
1839 
1840  if (__x->_M_color == _S_red)
1841  if ((__L && __L->_M_color == _S_red)
1842  || (__R && __R->_M_color == _S_red))
1843  return false;
1844 
1845  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1846  return false;
1847  if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1848  return false;
1849 
1850  if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1851  return false;
1852  }
1853 
1854  if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1855  return false;
1856  if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1857  return false;
1858  return true;
1859  }
1860 
1861 _GLIBCXX_END_NAMESPACE_VERSION
1862 } // namespace
1863 
1864 #endif