libstdc++
stl_tree.h
Go to the documentation of this file.
1 // RB tree implementation -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
4 // 2009, 2010, 2011
5 // Free Software Foundation, Inc.
6 //
7 // This file is part of the GNU ISO C++ Library. This library is free
8 // software; you can redistribute it and/or modify it under the
9 // terms of the GNU General Public License as published by the
10 // Free Software Foundation; either version 3, or (at your option)
11 // any later version.
12 
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 // GNU General Public License for more details.
17 
18 // Under Section 7 of GPL version 3, you are granted additional
19 // permissions described in the GCC Runtime Library Exception, version
20 // 3.1, as published by the Free Software Foundation.
21 
22 // You should have received a copy of the GNU General Public License and
23 // a copy of the GCC Runtime Library Exception along with this program;
24 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
25 // <http://www.gnu.org/licenses/>.
26 
27 /*
28  *
29  * Copyright (c) 1996,1997
30  * Silicon Graphics Computer Systems, Inc.
31  *
32  * Permission to use, copy, modify, distribute and sell this software
33  * and its documentation for any purpose is hereby granted without fee,
34  * provided that the above copyright notice appear in all copies and
35  * that both that copyright notice and this permission notice appear
36  * in supporting documentation. Silicon Graphics makes no
37  * representations about the suitability of this software for any
38  * purpose. It is provided "as is" without express or implied warranty.
39  *
40  *
41  * Copyright (c) 1994
42  * Hewlett-Packard Company
43  *
44  * Permission to use, copy, modify, distribute and sell this software
45  * and its documentation for any purpose is hereby granted without fee,
46  * provided that the above copyright notice appear in all copies and
47  * that both that copyright notice and this permission notice appear
48  * in supporting documentation. Hewlett-Packard Company makes no
49  * representations about the suitability of this software for any
50  * purpose. It is provided "as is" without express or implied warranty.
51  *
52  *
53  */
54 
55 /** @file bits/stl_tree.h
56  * This is an internal header file, included by other library headers.
57  * Do not attempt to use it directly. @headername{map or set}
58  */
59 
60 #ifndef _STL_TREE_H
61 #define _STL_TREE_H 1
62 
63 #include <bits/stl_algobase.h>
64 #include <bits/allocator.h>
65 #include <bits/stl_function.h>
66 #include <bits/cpp_type_traits.h>
67 
68 namespace std _GLIBCXX_VISIBILITY(default)
69 {
70 _GLIBCXX_BEGIN_NAMESPACE_VERSION
71 
72  // Red-black tree class, designed for use in implementing STL
73  // associative containers (set, multiset, map, and multimap). The
74  // insertion and deletion algorithms are based on those in Cormen,
75  // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
76  // 1990), except that
77  //
78  // (1) the header cell is maintained with links not only to the root
79  // but also to the leftmost node of the tree, to enable constant
80  // time begin(), and to the rightmost node of the tree, to enable
81  // linear time performance when used with the generic set algorithms
82  // (set_union, etc.)
83  //
84  // (2) when a node being deleted has two children its successor node
85  // is relinked into its place, rather than copied, so that the only
86  // iterators invalidated are those referring to the deleted node.
87 
88  enum _Rb_tree_color { _S_red = false, _S_black = true };
89 
90  struct _Rb_tree_node_base
91  {
92  typedef _Rb_tree_node_base* _Base_ptr;
93  typedef const _Rb_tree_node_base* _Const_Base_ptr;
94 
95  _Rb_tree_color _M_color;
96  _Base_ptr _M_parent;
97  _Base_ptr _M_left;
98  _Base_ptr _M_right;
99 
100  static _Base_ptr
101  _S_minimum(_Base_ptr __x)
102  {
103  while (__x->_M_left != 0) __x = __x->_M_left;
104  return __x;
105  }
106 
107  static _Const_Base_ptr
108  _S_minimum(_Const_Base_ptr __x)
109  {
110  while (__x->_M_left != 0) __x = __x->_M_left;
111  return __x;
112  }
113 
114  static _Base_ptr
115  _S_maximum(_Base_ptr __x)
116  {
117  while (__x->_M_right != 0) __x = __x->_M_right;
118  return __x;
119  }
120 
121  static _Const_Base_ptr
122  _S_maximum(_Const_Base_ptr __x)
123  {
124  while (__x->_M_right != 0) __x = __x->_M_right;
125  return __x;
126  }
127  };
128 
129  template<typename _Val>
130  struct _Rb_tree_node : public _Rb_tree_node_base
131  {
132  typedef _Rb_tree_node<_Val>* _Link_type;
133  _Val _M_value_field;
134 
135 #ifdef __GXX_EXPERIMENTAL_CXX0X__
136  template<typename... _Args>
137  _Rb_tree_node(_Args&&... __args)
138  : _Rb_tree_node_base(),
139  _M_value_field(std::forward<_Args>(__args)...) { }
140 #endif
141  };
142 
143  _GLIBCXX_PURE _Rb_tree_node_base*
144  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
145 
146  _GLIBCXX_PURE const _Rb_tree_node_base*
147  _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
148 
149  _GLIBCXX_PURE _Rb_tree_node_base*
150  _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
151 
152  _GLIBCXX_PURE const _Rb_tree_node_base*
153  _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
154 
155  template<typename _Tp>
156  struct _Rb_tree_iterator
157  {
158  typedef _Tp value_type;
159  typedef _Tp& reference;
160  typedef _Tp* pointer;
161 
162  typedef bidirectional_iterator_tag iterator_category;
163  typedef ptrdiff_t difference_type;
164 
165  typedef _Rb_tree_iterator<_Tp> _Self;
166  typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
167  typedef _Rb_tree_node<_Tp>* _Link_type;
168 
169  _Rb_tree_iterator()
170  : _M_node() { }
171 
172  explicit
173  _Rb_tree_iterator(_Link_type __x)
174  : _M_node(__x) { }
175 
176  reference
177  operator*() const
178  { return static_cast<_Link_type>(_M_node)->_M_value_field; }
179 
180  pointer
181  operator->() const
182  { return std::__addressof(static_cast<_Link_type>
183  (_M_node)->_M_value_field); }
184 
185  _Self&
186  operator++()
187  {
188  _M_node = _Rb_tree_increment(_M_node);
189  return *this;
190  }
191 
192  _Self
193  operator++(int)
194  {
195  _Self __tmp = *this;
196  _M_node = _Rb_tree_increment(_M_node);
197  return __tmp;
198  }
199 
200  _Self&
201  operator--()
202  {
203  _M_node = _Rb_tree_decrement(_M_node);
204  return *this;
205  }
206 
207  _Self
208  operator--(int)
209  {
210  _Self __tmp = *this;
211  _M_node = _Rb_tree_decrement(_M_node);
212  return __tmp;
213  }
214 
215  bool
216  operator==(const _Self& __x) const
217  { return _M_node == __x._M_node; }
218 
219  bool
220  operator!=(const _Self& __x) const
221  { return _M_node != __x._M_node; }
222 
223  _Base_ptr _M_node;
224  };
225 
226  template<typename _Tp>
227  struct _Rb_tree_const_iterator
228  {
229  typedef _Tp value_type;
230  typedef const _Tp& reference;
231  typedef const _Tp* pointer;
232 
233  typedef _Rb_tree_iterator<_Tp> iterator;
234 
235  typedef bidirectional_iterator_tag iterator_category;
236  typedef ptrdiff_t difference_type;
237 
238  typedef _Rb_tree_const_iterator<_Tp> _Self;
239  typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
240  typedef const _Rb_tree_node<_Tp>* _Link_type;
241 
242  _Rb_tree_const_iterator()
243  : _M_node() { }
244 
245  explicit
246  _Rb_tree_const_iterator(_Link_type __x)
247  : _M_node(__x) { }
248 
249  _Rb_tree_const_iterator(const iterator& __it)
250  : _M_node(__it._M_node) { }
251 
252  iterator
253  _M_const_cast() const
254  { return iterator(static_cast<typename iterator::_Link_type>
255  (const_cast<typename iterator::_Base_ptr>(_M_node))); }
256 
257  reference
258  operator*() const
259  { return static_cast<_Link_type>(_M_node)->_M_value_field; }
260 
261  pointer
262  operator->() const
263  { return std::__addressof(static_cast<_Link_type>
264  (_M_node)->_M_value_field); }
265 
266  _Self&
267  operator++()
268  {
269  _M_node = _Rb_tree_increment(_M_node);
270  return *this;
271  }
272 
273  _Self
274  operator++(int)
275  {
276  _Self __tmp = *this;
277  _M_node = _Rb_tree_increment(_M_node);
278  return __tmp;
279  }
280 
281  _Self&
282  operator--()
283  {
284  _M_node = _Rb_tree_decrement(_M_node);
285  return *this;
286  }
287 
288  _Self
289  operator--(int)
290  {
291  _Self __tmp = *this;
292  _M_node = _Rb_tree_decrement(_M_node);
293  return __tmp;
294  }
295 
296  bool
297  operator==(const _Self& __x) const
298  { return _M_node == __x._M_node; }
299 
300  bool
301  operator!=(const _Self& __x) const
302  { return _M_node != __x._M_node; }
303 
304  _Base_ptr _M_node;
305  };
306 
307  template<typename _Val>
308  inline bool
309  operator==(const _Rb_tree_iterator<_Val>& __x,
310  const _Rb_tree_const_iterator<_Val>& __y)
311  { return __x._M_node == __y._M_node; }
312 
313  template<typename _Val>
314  inline bool
315  operator!=(const _Rb_tree_iterator<_Val>& __x,
316  const _Rb_tree_const_iterator<_Val>& __y)
317  { return __x._M_node != __y._M_node; }
318 
319  void
320  _Rb_tree_insert_and_rebalance(const bool __insert_left,
321  _Rb_tree_node_base* __x,
322  _Rb_tree_node_base* __p,
323  _Rb_tree_node_base& __header) throw ();
324 
325  _Rb_tree_node_base*
326  _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
327  _Rb_tree_node_base& __header) throw ();
328 
329 
330  template<typename _Key, typename _Val, typename _KeyOfValue,
331  typename _Compare, typename _Alloc = allocator<_Val> >
332  class _Rb_tree
333  {
334  typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
335  _Node_allocator;
336 
337  protected:
338  typedef _Rb_tree_node_base* _Base_ptr;
339  typedef const _Rb_tree_node_base* _Const_Base_ptr;
340 
341  public:
342  typedef _Key key_type;
343  typedef _Val value_type;
344  typedef value_type* pointer;
345  typedef const value_type* const_pointer;
346  typedef value_type& reference;
347  typedef const value_type& const_reference;
348  typedef _Rb_tree_node<_Val>* _Link_type;
349  typedef const _Rb_tree_node<_Val>* _Const_Link_type;
350  typedef size_t size_type;
351  typedef ptrdiff_t difference_type;
352  typedef _Alloc allocator_type;
353 
354  _Node_allocator&
355  _M_get_Node_allocator()
356  { return *static_cast<_Node_allocator*>(&this->_M_impl); }
357 
358  const _Node_allocator&
359  _M_get_Node_allocator() const
360  { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
361 
362  allocator_type
363  get_allocator() const
364  { return allocator_type(_M_get_Node_allocator()); }
365 
366  protected:
367  _Link_type
368  _M_get_node()
369  { return _M_impl._Node_allocator::allocate(1); }
370 
371  void
372  _M_put_node(_Link_type __p)
373  { _M_impl._Node_allocator::deallocate(__p, 1); }
374 
375 #ifndef __GXX_EXPERIMENTAL_CXX0X__
376  _Link_type
377  _M_create_node(const value_type& __x)
378  {
379  _Link_type __tmp = _M_get_node();
380  __try
381  { get_allocator().construct
382  (std::__addressof(__tmp->_M_value_field), __x); }
383  __catch(...)
384  {
385  _M_put_node(__tmp);
386  __throw_exception_again;
387  }
388  return __tmp;
389  }
390 
391  void
392  _M_destroy_node(_Link_type __p)
393  {
394  get_allocator().destroy(std::__addressof(__p->_M_value_field));
395  _M_put_node(__p);
396  }
397 #else
398  template<typename... _Args>
399  _Link_type
400  _M_create_node(_Args&&... __args)
401  {
402  _Link_type __tmp = _M_get_node();
403  __try
404  {
405  _M_get_Node_allocator().construct(__tmp,
406  std::forward<_Args>(__args)...);
407  }
408  __catch(...)
409  {
410  _M_put_node(__tmp);
411  __throw_exception_again;
412  }
413  return __tmp;
414  }
415 
416  void
417  _M_destroy_node(_Link_type __p)
418  {
419  _M_get_Node_allocator().destroy(__p);
420  _M_put_node(__p);
421  }
422 #endif
423 
424  _Link_type
425  _M_clone_node(_Const_Link_type __x)
426  {
427  _Link_type __tmp = _M_create_node(__x->_M_value_field);
428  __tmp->_M_color = __x->_M_color;
429  __tmp->_M_left = 0;
430  __tmp->_M_right = 0;
431  return __tmp;
432  }
433 
434  protected:
435  template<typename _Key_compare,
436  bool _Is_pod_comparator = __is_pod(_Key_compare)>
437  struct _Rb_tree_impl : public _Node_allocator
438  {
439  _Key_compare _M_key_compare;
440  _Rb_tree_node_base _M_header;
441  size_type _M_node_count; // Keeps track of size of tree.
442 
443  _Rb_tree_impl()
444  : _Node_allocator(), _M_key_compare(), _M_header(),
445  _M_node_count(0)
446  { _M_initialize(); }
447 
448  _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
449  : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
450  _M_node_count(0)
451  { _M_initialize(); }
452 
453  private:
454  void
455  _M_initialize()
456  {
457  this->_M_header._M_color = _S_red;
458  this->_M_header._M_parent = 0;
459  this->_M_header._M_left = &this->_M_header;
460  this->_M_header._M_right = &this->_M_header;
461  }
462  };
463 
464  _Rb_tree_impl<_Compare> _M_impl;
465 
466  protected:
467  _Base_ptr&
468  _M_root()
469  { return this->_M_impl._M_header._M_parent; }
470 
471  _Const_Base_ptr
472  _M_root() const
473  { return this->_M_impl._M_header._M_parent; }
474 
475  _Base_ptr&
476  _M_leftmost()
477  { return this->_M_impl._M_header._M_left; }
478 
479  _Const_Base_ptr
480  _M_leftmost() const
481  { return this->_M_impl._M_header._M_left; }
482 
483  _Base_ptr&
484  _M_rightmost()
485  { return this->_M_impl._M_header._M_right; }
486 
487  _Const_Base_ptr
488  _M_rightmost() const
489  { return this->_M_impl._M_header._M_right; }
490 
491  _Link_type
492  _M_begin()
493  { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
494 
495  _Const_Link_type
496  _M_begin() const
497  {
498  return static_cast<_Const_Link_type>
499  (this->_M_impl._M_header._M_parent);
500  }
501 
502  _Link_type
503  _M_end()
504  { return static_cast<_Link_type>(&this->_M_impl._M_header); }
505 
506  _Const_Link_type
507  _M_end() const
508  { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
509 
510  static const_reference
511  _S_value(_Const_Link_type __x)
512  { return __x->_M_value_field; }
513 
514  static const _Key&
515  _S_key(_Const_Link_type __x)
516  { return _KeyOfValue()(_S_value(__x)); }
517 
518  static _Link_type
519  _S_left(_Base_ptr __x)
520  { return static_cast<_Link_type>(__x->_M_left); }
521 
522  static _Const_Link_type
523  _S_left(_Const_Base_ptr __x)
524  { return static_cast<_Const_Link_type>(__x->_M_left); }
525 
526  static _Link_type
527  _S_right(_Base_ptr __x)
528  { return static_cast<_Link_type>(__x->_M_right); }
529 
530  static _Const_Link_type
531  _S_right(_Const_Base_ptr __x)
532  { return static_cast<_Const_Link_type>(__x->_M_right); }
533 
534  static const_reference
535  _S_value(_Const_Base_ptr __x)
536  { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
537 
538  static const _Key&
539  _S_key(_Const_Base_ptr __x)
540  { return _KeyOfValue()(_S_value(__x)); }
541 
542  static _Base_ptr
543  _S_minimum(_Base_ptr __x)
544  { return _Rb_tree_node_base::_S_minimum(__x); }
545 
546  static _Const_Base_ptr
547  _S_minimum(_Const_Base_ptr __x)
548  { return _Rb_tree_node_base::_S_minimum(__x); }
549 
550  static _Base_ptr
551  _S_maximum(_Base_ptr __x)
552  { return _Rb_tree_node_base::_S_maximum(__x); }
553 
554  static _Const_Base_ptr
555  _S_maximum(_Const_Base_ptr __x)
556  { return _Rb_tree_node_base::_S_maximum(__x); }
557 
558  public:
559  typedef _Rb_tree_iterator<value_type> iterator;
560  typedef _Rb_tree_const_iterator<value_type> const_iterator;
561 
562  typedef std::reverse_iterator<iterator> reverse_iterator;
563  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
564 
565  private:
566 #ifdef __GXX_EXPERIMENTAL_CXX0X__
567  template<typename _Arg>
568  iterator
569  _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, _Arg&& __v);
570 
571  template<typename _Arg>
572  iterator
573  _M_insert_lower(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
574 
575  template<typename _Arg>
576  iterator
577  _M_insert_equal_lower(_Arg&& __x);
578 #else
579  iterator
580  _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
581  const value_type& __v);
582 
583  // _GLIBCXX_RESOLVE_LIB_DEFECTS
584  // 233. Insertion hints in associative containers.
585  iterator
586  _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
587 
588  iterator
589  _M_insert_equal_lower(const value_type& __x);
590 #endif
591 
592  _Link_type
593  _M_copy(_Const_Link_type __x, _Link_type __p);
594 
595  void
596  _M_erase(_Link_type __x);
597 
598  iterator
599  _M_lower_bound(_Link_type __x, _Link_type __y,
600  const _Key& __k);
601 
602  const_iterator
603  _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
604  const _Key& __k) const;
605 
606  iterator
607  _M_upper_bound(_Link_type __x, _Link_type __y,
608  const _Key& __k);
609 
610  const_iterator
611  _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
612  const _Key& __k) const;
613 
614  public:
615  // allocation/deallocation
616  _Rb_tree() { }
617 
618  _Rb_tree(const _Compare& __comp,
619  const allocator_type& __a = allocator_type())
620  : _M_impl(__comp, __a) { }
621 
622  _Rb_tree(const _Rb_tree& __x)
623  : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
624  {
625  if (__x._M_root() != 0)
626  {
627  _M_root() = _M_copy(__x._M_begin(), _M_end());
628  _M_leftmost() = _S_minimum(_M_root());
629  _M_rightmost() = _S_maximum(_M_root());
630  _M_impl._M_node_count = __x._M_impl._M_node_count;
631  }
632  }
633 
634 #ifdef __GXX_EXPERIMENTAL_CXX0X__
635  _Rb_tree(_Rb_tree&& __x);
636 #endif
637 
638  ~_Rb_tree()
639  { _M_erase(_M_begin()); }
640 
641  _Rb_tree&
642  operator=(const _Rb_tree& __x);
643 
644  // Accessors.
645  _Compare
646  key_comp() const
647  { return _M_impl._M_key_compare; }
648 
649  iterator
650  begin()
651  {
652  return iterator(static_cast<_Link_type>
653  (this->_M_impl._M_header._M_left));
654  }
655 
656  const_iterator
657  begin() const
658  {
659  return const_iterator(static_cast<_Const_Link_type>
660  (this->_M_impl._M_header._M_left));
661  }
662 
663  iterator
664  end()
665  { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
666 
667  const_iterator
668  end() const
669  {
670  return const_iterator(static_cast<_Const_Link_type>
671  (&this->_M_impl._M_header));
672  }
673 
674  reverse_iterator
675  rbegin()
676  { return reverse_iterator(end()); }
677 
678  const_reverse_iterator
679  rbegin() const
680  { return const_reverse_iterator(end()); }
681 
682  reverse_iterator
683  rend()
684  { return reverse_iterator(begin()); }
685 
686  const_reverse_iterator
687  rend() const
688  { return const_reverse_iterator(begin()); }
689 
690  bool
691  empty() const
692  { return _M_impl._M_node_count == 0; }
693 
694  size_type
695  size() const
696  { return _M_impl._M_node_count; }
697 
698  size_type
699  max_size() const
700  { return _M_get_Node_allocator().max_size(); }
701 
702  void
703  swap(_Rb_tree& __t);
704 
705  // Insert/erase.
706 #ifdef __GXX_EXPERIMENTAL_CXX0X__
707  template<typename _Arg>
708  pair<iterator, bool>
709  _M_insert_unique(_Arg&& __x);
710 
711  template<typename _Arg>
712  iterator
713  _M_insert_equal(_Arg&& __x);
714 
715  template<typename _Arg>
716  iterator
717  _M_insert_unique_(const_iterator __position, _Arg&& __x);
718 
719  template<typename _Arg>
720  iterator
721  _M_insert_equal_(const_iterator __position, _Arg&& __x);
722 #else
723  pair<iterator, bool>
724  _M_insert_unique(const value_type& __x);
725 
726  iterator
727  _M_insert_equal(const value_type& __x);
728 
729  iterator
730  _M_insert_unique_(const_iterator __position, const value_type& __x);
731 
732  iterator
733  _M_insert_equal_(const_iterator __position, const value_type& __x);
734 #endif
735 
736  template<typename _InputIterator>
737  void
738  _M_insert_unique(_InputIterator __first, _InputIterator __last);
739 
740  template<typename _InputIterator>
741  void
742  _M_insert_equal(_InputIterator __first, _InputIterator __last);
743 
744  private:
745  void
746  _M_erase_aux(const_iterator __position);
747 
748  void
749  _M_erase_aux(const_iterator __first, const_iterator __last);
750 
751  public:
752 #ifdef __GXX_EXPERIMENTAL_CXX0X__
753  // _GLIBCXX_RESOLVE_LIB_DEFECTS
754  // DR 130. Associative erase should return an iterator.
755  iterator
756  erase(const_iterator __position)
757  {
758  const_iterator __result = __position;
759  ++__result;
760  _M_erase_aux(__position);
761  return __result._M_const_cast();
762  }
763 
764  // LWG 2059.
765  iterator
766  erase(iterator __position)
767  {
768  iterator __result = __position;
769  ++__result;
770  _M_erase_aux(__position);
771  return __result;
772  }
773 #else
774  void
775  erase(iterator __position)
776  { _M_erase_aux(__position); }
777 
778  void
779  erase(const_iterator __position)
780  { _M_erase_aux(__position); }
781 #endif
782  size_type
783  erase(const key_type& __x);
784 
785 #ifdef __GXX_EXPERIMENTAL_CXX0X__
786  // _GLIBCXX_RESOLVE_LIB_DEFECTS
787  // DR 130. Associative erase should return an iterator.
788  iterator
789  erase(const_iterator __first, const_iterator __last)
790  {
791  _M_erase_aux(__first, __last);
792  return __last._M_const_cast();
793  }
794 #else
795  void
796  erase(iterator __first, iterator __last)
797  { _M_erase_aux(__first, __last); }
798 
799  void
800  erase(const_iterator __first, const_iterator __last)
801  { _M_erase_aux(__first, __last); }
802 #endif
803  void
804  erase(const key_type* __first, const key_type* __last);
805 
806  void
807  clear()
808  {
809  _M_erase(_M_begin());
810  _M_leftmost() = _M_end();
811  _M_root() = 0;
812  _M_rightmost() = _M_end();
813  _M_impl._M_node_count = 0;
814  }
815 
816  // Set operations.
817  iterator
818  find(const key_type& __k);
819 
820  const_iterator
821  find(const key_type& __k) const;
822 
823  size_type
824  count(const key_type& __k) const;
825 
826  iterator
827  lower_bound(const key_type& __k)
828  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
829 
830  const_iterator
831  lower_bound(const key_type& __k) const
832  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
833 
834  iterator
835  upper_bound(const key_type& __k)
836  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
837 
838  const_iterator
839  upper_bound(const key_type& __k) const
840  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
841 
842  pair<iterator, iterator>
843  equal_range(const key_type& __k);
844 
845  pair<const_iterator, const_iterator>
846  equal_range(const key_type& __k) const;
847 
848  // Debugging.
849  bool
850  __rb_verify() const;
851  };
852 
853  template<typename _Key, typename _Val, typename _KeyOfValue,
854  typename _Compare, typename _Alloc>
855  inline bool
856  operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
857  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
858  {
859  return __x.size() == __y.size()
860  && std::equal(__x.begin(), __x.end(), __y.begin());
861  }
862 
863  template<typename _Key, typename _Val, typename _KeyOfValue,
864  typename _Compare, typename _Alloc>
865  inline bool
866  operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
867  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
868  {
869  return std::lexicographical_compare(__x.begin(), __x.end(),
870  __y.begin(), __y.end());
871  }
872 
873  template<typename _Key, typename _Val, typename _KeyOfValue,
874  typename _Compare, typename _Alloc>
875  inline bool
876  operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
877  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
878  { return !(__x == __y); }
879 
880  template<typename _Key, typename _Val, typename _KeyOfValue,
881  typename _Compare, typename _Alloc>
882  inline bool
883  operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
884  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
885  { return __y < __x; }
886 
887  template<typename _Key, typename _Val, typename _KeyOfValue,
888  typename _Compare, typename _Alloc>
889  inline bool
890  operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
891  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
892  { return !(__y < __x); }
893 
894  template<typename _Key, typename _Val, typename _KeyOfValue,
895  typename _Compare, typename _Alloc>
896  inline bool
897  operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
898  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
899  { return !(__x < __y); }
900 
901  template<typename _Key, typename _Val, typename _KeyOfValue,
902  typename _Compare, typename _Alloc>
903  inline void
904  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
905  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
906  { __x.swap(__y); }
907 
908 #ifdef __GXX_EXPERIMENTAL_CXX0X__
909  template<typename _Key, typename _Val, typename _KeyOfValue,
910  typename _Compare, typename _Alloc>
911  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
912  _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
913  : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
914  {
915  if (__x._M_root() != 0)
916  {
917  _M_root() = __x._M_root();
918  _M_leftmost() = __x._M_leftmost();
919  _M_rightmost() = __x._M_rightmost();
920  _M_root()->_M_parent = _M_end();
921 
922  __x._M_root() = 0;
923  __x._M_leftmost() = __x._M_end();
924  __x._M_rightmost() = __x._M_end();
925 
926  this->_M_impl._M_node_count = __x._M_impl._M_node_count;
927  __x._M_impl._M_node_count = 0;
928  }
929  }
930 #endif
931 
932  template<typename _Key, typename _Val, typename _KeyOfValue,
933  typename _Compare, typename _Alloc>
934  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
935  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
936  operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
937  {
938  if (this != &__x)
939  {
940  // Note that _Key may be a constant type.
941  clear();
942  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
943  if (__x._M_root() != 0)
944  {
945  _M_root() = _M_copy(__x._M_begin(), _M_end());
946  _M_leftmost() = _S_minimum(_M_root());
947  _M_rightmost() = _S_maximum(_M_root());
948  _M_impl._M_node_count = __x._M_impl._M_node_count;
949  }
950  }
951  return *this;
952  }
953 
954  template<typename _Key, typename _Val, typename _KeyOfValue,
955  typename _Compare, typename _Alloc>
956 #ifdef __GXX_EXPERIMENTAL_CXX0X__
957  template<typename _Arg>
958 #endif
959  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
960  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
961 #ifdef __GXX_EXPERIMENTAL_CXX0X__
962  _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v)
963 #else
964  _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
965 #endif
966  {
967  bool __insert_left = (__x != 0 || __p == _M_end()
968  || _M_impl._M_key_compare(_KeyOfValue()(__v),
969  _S_key(__p)));
970 
971  _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
972 
973  _Rb_tree_insert_and_rebalance(__insert_left, __z,
974  const_cast<_Base_ptr>(__p),
975  this->_M_impl._M_header);
976  ++_M_impl._M_node_count;
977  return iterator(__z);
978  }
979 
980  template<typename _Key, typename _Val, typename _KeyOfValue,
981  typename _Compare, typename _Alloc>
982 #ifdef __GXX_EXPERIMENTAL_CXX0X__
983  template<typename _Arg>
984 #endif
985  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
986  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
987 #ifdef __GXX_EXPERIMENTAL_CXX0X__
988  _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
989 #else
990  _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
991 #endif
992  {
993  bool __insert_left = (__x != 0 || __p == _M_end()
994  || !_M_impl._M_key_compare(_S_key(__p),
995  _KeyOfValue()(__v)));
996 
997  _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
998 
999  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1000  this->_M_impl._M_header);
1001  ++_M_impl._M_node_count;
1002  return iterator(__z);
1003  }
1004 
1005  template<typename _Key, typename _Val, typename _KeyOfValue,
1006  typename _Compare, typename _Alloc>
1007 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1008  template<typename _Arg>
1009 #endif
1010  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1011  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1012 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1013  _M_insert_equal_lower(_Arg&& __v)
1014 #else
1015  _M_insert_equal_lower(const _Val& __v)
1016 #endif
1017  {
1018  _Link_type __x = _M_begin();
1019  _Link_type __y = _M_end();
1020  while (__x != 0)
1021  {
1022  __y = __x;
1023  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1024  _S_left(__x) : _S_right(__x);
1025  }
1026  return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
1027  }
1028 
1029  template<typename _Key, typename _Val, typename _KoV,
1030  typename _Compare, typename _Alloc>
1031  typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1032  _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1033  _M_copy(_Const_Link_type __x, _Link_type __p)
1034  {
1035  // Structural copy. __x and __p must be non-null.
1036  _Link_type __top = _M_clone_node(__x);
1037  __top->_M_parent = __p;
1038 
1039  __try
1040  {
1041  if (__x->_M_right)
1042  __top->_M_right = _M_copy(_S_right(__x), __top);
1043  __p = __top;
1044  __x = _S_left(__x);
1045 
1046  while (__x != 0)
1047  {
1048  _Link_type __y = _M_clone_node(__x);
1049  __p->_M_left = __y;
1050  __y->_M_parent = __p;
1051  if (__x->_M_right)
1052  __y->_M_right = _M_copy(_S_right(__x), __y);
1053  __p = __y;
1054  __x = _S_left(__x);
1055  }
1056  }
1057  __catch(...)
1058  {
1059  _M_erase(__top);
1060  __throw_exception_again;
1061  }
1062  return __top;
1063  }
1064 
1065  template<typename _Key, typename _Val, typename _KeyOfValue,
1066  typename _Compare, typename _Alloc>
1067  void
1068  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1069  _M_erase(_Link_type __x)
1070  {
1071  // Erase without rebalancing.
1072  while (__x != 0)
1073  {
1074  _M_erase(_S_right(__x));
1075  _Link_type __y = _S_left(__x);
1076  _M_destroy_node(__x);
1077  __x = __y;
1078  }
1079  }
1080 
1081  template<typename _Key, typename _Val, typename _KeyOfValue,
1082  typename _Compare, typename _Alloc>
1083  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1084  _Compare, _Alloc>::iterator
1085  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1086  _M_lower_bound(_Link_type __x, _Link_type __y,
1087  const _Key& __k)
1088  {
1089  while (__x != 0)
1090  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1091  __y = __x, __x = _S_left(__x);
1092  else
1093  __x = _S_right(__x);
1094  return iterator(__y);
1095  }
1096 
1097  template<typename _Key, typename _Val, typename _KeyOfValue,
1098  typename _Compare, typename _Alloc>
1099  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1100  _Compare, _Alloc>::const_iterator
1101  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1102  _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1103  const _Key& __k) const
1104  {
1105  while (__x != 0)
1106  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1107  __y = __x, __x = _S_left(__x);
1108  else
1109  __x = _S_right(__x);
1110  return const_iterator(__y);
1111  }
1112 
1113  template<typename _Key, typename _Val, typename _KeyOfValue,
1114  typename _Compare, typename _Alloc>
1115  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1116  _Compare, _Alloc>::iterator
1117  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1118  _M_upper_bound(_Link_type __x, _Link_type __y,
1119  const _Key& __k)
1120  {
1121  while (__x != 0)
1122  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1123  __y = __x, __x = _S_left(__x);
1124  else
1125  __x = _S_right(__x);
1126  return iterator(__y);
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>::const_iterator
1133  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1134  _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1135  const _Key& __k) const
1136  {
1137  while (__x != 0)
1138  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1139  __y = __x, __x = _S_left(__x);
1140  else
1141  __x = _S_right(__x);
1142  return const_iterator(__y);
1143  }
1144 
1145  template<typename _Key, typename _Val, typename _KeyOfValue,
1146  typename _Compare, typename _Alloc>
1147  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1148  _Compare, _Alloc>::iterator,
1149  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1150  _Compare, _Alloc>::iterator>
1151  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1152  equal_range(const _Key& __k)
1153  {
1154  _Link_type __x = _M_begin();
1155  _Link_type __y = _M_end();
1156  while (__x != 0)
1157  {
1158  if (_M_impl._M_key_compare(_S_key(__x), __k))
1159  __x = _S_right(__x);
1160  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1161  __y = __x, __x = _S_left(__x);
1162  else
1163  {
1164  _Link_type __xu(__x), __yu(__y);
1165  __y = __x, __x = _S_left(__x);
1166  __xu = _S_right(__xu);
1167  return pair<iterator,
1168  iterator>(_M_lower_bound(__x, __y, __k),
1169  _M_upper_bound(__xu, __yu, __k));
1170  }
1171  }
1172  return pair<iterator, iterator>(iterator(__y),
1173  iterator(__y));
1174  }
1175 
1176  template<typename _Key, typename _Val, typename _KeyOfValue,
1177  typename _Compare, typename _Alloc>
1178  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1179  _Compare, _Alloc>::const_iterator,
1180  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1181  _Compare, _Alloc>::const_iterator>
1182  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1183  equal_range(const _Key& __k) const
1184  {
1185  _Const_Link_type __x = _M_begin();
1186  _Const_Link_type __y = _M_end();
1187  while (__x != 0)
1188  {
1189  if (_M_impl._M_key_compare(_S_key(__x), __k))
1190  __x = _S_right(__x);
1191  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1192  __y = __x, __x = _S_left(__x);
1193  else
1194  {
1195  _Const_Link_type __xu(__x), __yu(__y);
1196  __y = __x, __x = _S_left(__x);
1197  __xu = _S_right(__xu);
1198  return pair<const_iterator,
1199  const_iterator>(_M_lower_bound(__x, __y, __k),
1200  _M_upper_bound(__xu, __yu, __k));
1201  }
1202  }
1203  return pair<const_iterator, const_iterator>(const_iterator(__y),
1204  const_iterator(__y));
1205  }
1206 
1207  template<typename _Key, typename _Val, typename _KeyOfValue,
1208  typename _Compare, typename _Alloc>
1209  void
1210  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1211  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1212  {
1213  if (_M_root() == 0)
1214  {
1215  if (__t._M_root() != 0)
1216  {
1217  _M_root() = __t._M_root();
1218  _M_leftmost() = __t._M_leftmost();
1219  _M_rightmost() = __t._M_rightmost();
1220  _M_root()->_M_parent = _M_end();
1221 
1222  __t._M_root() = 0;
1223  __t._M_leftmost() = __t._M_end();
1224  __t._M_rightmost() = __t._M_end();
1225  }
1226  }
1227  else if (__t._M_root() == 0)
1228  {
1229  __t._M_root() = _M_root();
1230  __t._M_leftmost() = _M_leftmost();
1231  __t._M_rightmost() = _M_rightmost();
1232  __t._M_root()->_M_parent = __t._M_end();
1233 
1234  _M_root() = 0;
1235  _M_leftmost() = _M_end();
1236  _M_rightmost() = _M_end();
1237  }
1238  else
1239  {
1240  std::swap(_M_root(),__t._M_root());
1241  std::swap(_M_leftmost(),__t._M_leftmost());
1242  std::swap(_M_rightmost(),__t._M_rightmost());
1243 
1244  _M_root()->_M_parent = _M_end();
1245  __t._M_root()->_M_parent = __t._M_end();
1246  }
1247  // No need to swap header's color as it does not change.
1248  std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1249  std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1250 
1251  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1252  // 431. Swapping containers with unequal allocators.
1253  std::__alloc_swap<_Node_allocator>::
1254  _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
1255  }
1256 
1257  template<typename _Key, typename _Val, typename _KeyOfValue,
1258  typename _Compare, typename _Alloc>
1259 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1260  template<typename _Arg>
1261 #endif
1262  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1263  _Compare, _Alloc>::iterator, bool>
1264  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1265 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1266  _M_insert_unique(_Arg&& __v)
1267 #else
1268  _M_insert_unique(const _Val& __v)
1269 #endif
1270  {
1271  _Link_type __x = _M_begin();
1272  _Link_type __y = _M_end();
1273  bool __comp = true;
1274  while (__x != 0)
1275  {
1276  __y = __x;
1277  __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1278  __x = __comp ? _S_left(__x) : _S_right(__x);
1279  }
1280  iterator __j = iterator(__y);
1281  if (__comp)
1282  {
1283  if (__j == begin())
1284  return pair<iterator, bool>
1285  (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
1286  else
1287  --__j;
1288  }
1289  if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
1290  return pair<iterator, bool>
1291  (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
1292  return pair<iterator, bool>(__j, false);
1293  }
1294 
1295  template<typename _Key, typename _Val, typename _KeyOfValue,
1296  typename _Compare, typename _Alloc>
1297 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1298  template<typename _Arg>
1299 #endif
1300  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1301  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1302 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1303  _M_insert_equal(_Arg&& __v)
1304 #else
1305  _M_insert_equal(const _Val& __v)
1306 #endif
1307  {
1308  _Link_type __x = _M_begin();
1309  _Link_type __y = _M_end();
1310  while (__x != 0)
1311  {
1312  __y = __x;
1313  __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1314  _S_left(__x) : _S_right(__x);
1315  }
1316  return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
1317  }
1318 
1319  template<typename _Key, typename _Val, typename _KeyOfValue,
1320  typename _Compare, typename _Alloc>
1321 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1322  template<typename _Arg>
1323 #endif
1324  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1325  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1326 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1327  _M_insert_unique_(const_iterator __position, _Arg&& __v)
1328 #else
1329  _M_insert_unique_(const_iterator __position, const _Val& __v)
1330 #endif
1331  {
1332  // end()
1333  if (__position._M_node == _M_end())
1334  {
1335  if (size() > 0
1336  && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1337  _KeyOfValue()(__v)))
1338  return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v));
1339  else
1340  return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1341  }
1342  else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1343  _S_key(__position._M_node)))
1344  {
1345  // First, try before...
1346  const_iterator __before = __position;
1347  if (__position._M_node == _M_leftmost()) // begin()
1348  return _M_insert_(_M_leftmost(), _M_leftmost(),
1349  _GLIBCXX_FORWARD(_Arg, __v));
1350  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1351  _KeyOfValue()(__v)))
1352  {
1353  if (_S_right(__before._M_node) == 0)
1354  return _M_insert_(0, __before._M_node,
1355  _GLIBCXX_FORWARD(_Arg, __v));
1356  else
1357  return _M_insert_(__position._M_node,
1358  __position._M_node,
1359  _GLIBCXX_FORWARD(_Arg, __v));
1360  }
1361  else
1362  return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1363  }
1364  else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1365  _KeyOfValue()(__v)))
1366  {
1367  // ... then try after.
1368  const_iterator __after = __position;
1369  if (__position._M_node == _M_rightmost())
1370  return _M_insert_(0, _M_rightmost(),
1371  _GLIBCXX_FORWARD(_Arg, __v));
1372  else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1373  _S_key((++__after)._M_node)))
1374  {
1375  if (_S_right(__position._M_node) == 0)
1376  return _M_insert_(0, __position._M_node,
1377  _GLIBCXX_FORWARD(_Arg, __v));
1378  else
1379  return _M_insert_(__after._M_node, __after._M_node,
1380  _GLIBCXX_FORWARD(_Arg, __v));
1381  }
1382  else
1383  return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1384  }
1385  else
1386  // Equivalent keys.
1387  return __position._M_const_cast();
1388  }
1389 
1390  template<typename _Key, typename _Val, typename _KeyOfValue,
1391  typename _Compare, typename _Alloc>
1392 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1393  template<typename _Arg>
1394 #endif
1395  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1396  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1397 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1398  _M_insert_equal_(const_iterator __position, _Arg&& __v)
1399 #else
1400  _M_insert_equal_(const_iterator __position, const _Val& __v)
1401 #endif
1402  {
1403  // end()
1404  if (__position._M_node == _M_end())
1405  {
1406  if (size() > 0
1407  && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1408  _S_key(_M_rightmost())))
1409  return _M_insert_(0, _M_rightmost(),
1410  _GLIBCXX_FORWARD(_Arg, __v));
1411  else
1412  return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
1413  }
1414  else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1415  _KeyOfValue()(__v)))
1416  {
1417  // First, try before...
1418  const_iterator __before = __position;
1419  if (__position._M_node == _M_leftmost()) // begin()
1420  return _M_insert_(_M_leftmost(), _M_leftmost(),
1421  _GLIBCXX_FORWARD(_Arg, __v));
1422  else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1423  _S_key((--__before)._M_node)))
1424  {
1425  if (_S_right(__before._M_node) == 0)
1426  return _M_insert_(0, __before._M_node,
1427  _GLIBCXX_FORWARD(_Arg, __v));
1428  else
1429  return _M_insert_(__position._M_node,
1430  __position._M_node,
1431  _GLIBCXX_FORWARD(_Arg, __v));
1432  }
1433  else
1434  return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
1435  }
1436  else
1437  {
1438  // ... then try after.
1439  const_iterator __after = __position;
1440  if (__position._M_node == _M_rightmost())
1441  return _M_insert_(0, _M_rightmost(),
1442  _GLIBCXX_FORWARD(_Arg, __v));
1443  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1444  _KeyOfValue()(__v)))
1445  {
1446  if (_S_right(__position._M_node) == 0)
1447  return _M_insert_(0, __position._M_node,
1448  _GLIBCXX_FORWARD(_Arg, __v));
1449  else
1450  return _M_insert_(__after._M_node, __after._M_node,
1451  _GLIBCXX_FORWARD(_Arg, __v));
1452  }
1453  else
1454  return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
1455  }
1456  }
1457 
1458  template<typename _Key, typename _Val, typename _KoV,
1459  typename _Cmp, typename _Alloc>
1460  template<class _II>
1461  void
1462  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1463  _M_insert_unique(_II __first, _II __last)
1464  {
1465  for (; __first != __last; ++__first)
1466  _M_insert_unique_(end(), *__first);
1467  }
1468 
1469  template<typename _Key, typename _Val, typename _KoV,
1470  typename _Cmp, typename _Alloc>
1471  template<class _II>
1472  void
1473  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1474  _M_insert_equal(_II __first, _II __last)
1475  {
1476  for (; __first != __last; ++__first)
1477  _M_insert_equal_(end(), *__first);
1478  }
1479 
1480  template<typename _Key, typename _Val, typename _KeyOfValue,
1481  typename _Compare, typename _Alloc>
1482  void
1483  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1484  _M_erase_aux(const_iterator __position)
1485  {
1486  _Link_type __y =
1487  static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1488  (const_cast<_Base_ptr>(__position._M_node),
1489  this->_M_impl._M_header));
1490  _M_destroy_node(__y);
1491  --_M_impl._M_node_count;
1492  }
1493 
1494  template<typename _Key, typename _Val, typename _KeyOfValue,
1495  typename _Compare, typename _Alloc>
1496  void
1497  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1498  _M_erase_aux(const_iterator __first, const_iterator __last)
1499  {
1500  if (__first == begin() && __last == end())
1501  clear();
1502  else
1503  while (__first != __last)
1504  erase(__first++);
1505  }
1506 
1507  template<typename _Key, typename _Val, typename _KeyOfValue,
1508  typename _Compare, typename _Alloc>
1509  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1510  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1511  erase(const _Key& __x)
1512  {
1513  pair<iterator, iterator> __p = equal_range(__x);
1514  const size_type __old_size = size();
1515  erase(__p.first, __p.second);
1516  return __old_size - size();
1517  }
1518 
1519  template<typename _Key, typename _Val, typename _KeyOfValue,
1520  typename _Compare, typename _Alloc>
1521  void
1522  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1523  erase(const _Key* __first, const _Key* __last)
1524  {
1525  while (__first != __last)
1526  erase(*__first++);
1527  }
1528 
1529  template<typename _Key, typename _Val, typename _KeyOfValue,
1530  typename _Compare, typename _Alloc>
1531  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1532  _Compare, _Alloc>::iterator
1533  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1534  find(const _Key& __k)
1535  {
1536  iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1537  return (__j == end()
1538  || _M_impl._M_key_compare(__k,
1539  _S_key(__j._M_node))) ? end() : __j;
1540  }
1541 
1542  template<typename _Key, typename _Val, typename _KeyOfValue,
1543  typename _Compare, typename _Alloc>
1544  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1545  _Compare, _Alloc>::const_iterator
1546  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1547  find(const _Key& __k) const
1548  {
1549  const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1550  return (__j == end()
1551  || _M_impl._M_key_compare(__k,
1552  _S_key(__j._M_node))) ? end() : __j;
1553  }
1554 
1555  template<typename _Key, typename _Val, typename _KeyOfValue,
1556  typename _Compare, typename _Alloc>
1557  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1558  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1559  count(const _Key& __k) const
1560  {
1561  pair<const_iterator, const_iterator> __p = equal_range(__k);
1562  const size_type __n = std::distance(__p.first, __p.second);
1563  return __n;
1564  }
1565 
1566  _GLIBCXX_PURE unsigned int
1567  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1568  const _Rb_tree_node_base* __root) throw ();
1569 
1570  template<typename _Key, typename _Val, typename _KeyOfValue,
1571  typename _Compare, typename _Alloc>
1572  bool
1573  _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1574  {
1575  if (_M_impl._M_node_count == 0 || begin() == end())
1576  return _M_impl._M_node_count == 0 && begin() == end()
1577  && this->_M_impl._M_header._M_left == _M_end()
1578  && this->_M_impl._M_header._M_right == _M_end();
1579 
1580  unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1581  for (const_iterator __it = begin(); __it != end(); ++__it)
1582  {
1583  _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1584  _Const_Link_type __L = _S_left(__x);
1585  _Const_Link_type __R = _S_right(__x);
1586 
1587  if (__x->_M_color == _S_red)
1588  if ((__L && __L->_M_color == _S_red)
1589  || (__R && __R->_M_color == _S_red))
1590  return false;
1591 
1592  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1593  return false;
1594  if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1595  return false;
1596 
1597  if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1598  return false;
1599  }
1600 
1601  if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1602  return false;
1603  if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1604  return false;
1605  return true;
1606  }
1607 
1608 _GLIBCXX_END_NAMESPACE_VERSION
1609 } // namespace
1610 
1611 #endif