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() _GLIBCXX_NOEXCEPT
356  { return *static_cast<_Node_allocator*>(&this->_M_impl); }
357 
358  const _Node_allocator&
359  _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
360  { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
361 
362  allocator_type
363  get_allocator() const _GLIBCXX_NOEXCEPT
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 #ifdef __GXX_EXPERIMENTAL_CXX0X__
454  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
455  : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
456  _M_header(), _M_node_count(0)
457  { _M_initialize(); }
458 #endif
459 
460  private:
461  void
462  _M_initialize()
463  {
464  this->_M_header._M_color = _S_red;
465  this->_M_header._M_parent = 0;
466  this->_M_header._M_left = &this->_M_header;
467  this->_M_header._M_right = &this->_M_header;
468  }
469  };
470 
471  _Rb_tree_impl<_Compare> _M_impl;
472 
473  protected:
474  _Base_ptr&
475  _M_root()
476  { return this->_M_impl._M_header._M_parent; }
477 
478  _Const_Base_ptr
479  _M_root() const
480  { return this->_M_impl._M_header._M_parent; }
481 
482  _Base_ptr&
483  _M_leftmost()
484  { return this->_M_impl._M_header._M_left; }
485 
486  _Const_Base_ptr
487  _M_leftmost() const
488  { return this->_M_impl._M_header._M_left; }
489 
490  _Base_ptr&
491  _M_rightmost()
492  { return this->_M_impl._M_header._M_right; }
493 
494  _Const_Base_ptr
495  _M_rightmost() const
496  { return this->_M_impl._M_header._M_right; }
497 
498  _Link_type
499  _M_begin()
500  { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
501 
502  _Const_Link_type
503  _M_begin() const
504  {
505  return static_cast<_Const_Link_type>
506  (this->_M_impl._M_header._M_parent);
507  }
508 
509  _Link_type
510  _M_end()
511  { return static_cast<_Link_type>(&this->_M_impl._M_header); }
512 
513  _Const_Link_type
514  _M_end() const
515  { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
516 
517  static const_reference
518  _S_value(_Const_Link_type __x)
519  { return __x->_M_value_field; }
520 
521  static const _Key&
522  _S_key(_Const_Link_type __x)
523  { return _KeyOfValue()(_S_value(__x)); }
524 
525  static _Link_type
526  _S_left(_Base_ptr __x)
527  { return static_cast<_Link_type>(__x->_M_left); }
528 
529  static _Const_Link_type
530  _S_left(_Const_Base_ptr __x)
531  { return static_cast<_Const_Link_type>(__x->_M_left); }
532 
533  static _Link_type
534  _S_right(_Base_ptr __x)
535  { return static_cast<_Link_type>(__x->_M_right); }
536 
537  static _Const_Link_type
538  _S_right(_Const_Base_ptr __x)
539  { return static_cast<_Const_Link_type>(__x->_M_right); }
540 
541  static const_reference
542  _S_value(_Const_Base_ptr __x)
543  { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
544 
545  static const _Key&
546  _S_key(_Const_Base_ptr __x)
547  { return _KeyOfValue()(_S_value(__x)); }
548 
549  static _Base_ptr
550  _S_minimum(_Base_ptr __x)
551  { return _Rb_tree_node_base::_S_minimum(__x); }
552 
553  static _Const_Base_ptr
554  _S_minimum(_Const_Base_ptr __x)
555  { return _Rb_tree_node_base::_S_minimum(__x); }
556 
557  static _Base_ptr
558  _S_maximum(_Base_ptr __x)
559  { return _Rb_tree_node_base::_S_maximum(__x); }
560 
561  static _Const_Base_ptr
562  _S_maximum(_Const_Base_ptr __x)
563  { return _Rb_tree_node_base::_S_maximum(__x); }
564 
565  public:
566  typedef _Rb_tree_iterator<value_type> iterator;
567  typedef _Rb_tree_const_iterator<value_type> const_iterator;
568 
569  typedef std::reverse_iterator<iterator> reverse_iterator;
570  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
571 
572  private:
573 #ifdef __GXX_EXPERIMENTAL_CXX0X__
574  template<typename _Arg>
575  iterator
576  _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, _Arg&& __v);
577 
578  template<typename _Arg>
579  iterator
580  _M_insert_lower(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
581 
582  template<typename _Arg>
583  iterator
584  _M_insert_equal_lower(_Arg&& __x);
585 #else
586  iterator
587  _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
588  const value_type& __v);
589 
590  // _GLIBCXX_RESOLVE_LIB_DEFECTS
591  // 233. Insertion hints in associative containers.
592  iterator
593  _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
594 
595  iterator
596  _M_insert_equal_lower(const value_type& __x);
597 #endif
598 
599  _Link_type
600  _M_copy(_Const_Link_type __x, _Link_type __p);
601 
602  void
603  _M_erase(_Link_type __x);
604 
605  iterator
606  _M_lower_bound(_Link_type __x, _Link_type __y,
607  const _Key& __k);
608 
609  const_iterator
610  _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
611  const _Key& __k) const;
612 
613  iterator
614  _M_upper_bound(_Link_type __x, _Link_type __y,
615  const _Key& __k);
616 
617  const_iterator
618  _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
619  const _Key& __k) const;
620 
621  public:
622  // allocation/deallocation
623  _Rb_tree() { }
624 
625  _Rb_tree(const _Compare& __comp,
626  const allocator_type& __a = allocator_type())
627  : _M_impl(__comp, _Node_allocator(__a)) { }
628 
629  _Rb_tree(const _Rb_tree& __x)
630  : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
631  {
632  if (__x._M_root() != 0)
633  {
634  _M_root() = _M_copy(__x._M_begin(), _M_end());
635  _M_leftmost() = _S_minimum(_M_root());
636  _M_rightmost() = _S_maximum(_M_root());
637  _M_impl._M_node_count = __x._M_impl._M_node_count;
638  }
639  }
640 
641 #ifdef __GXX_EXPERIMENTAL_CXX0X__
642  _Rb_tree(_Rb_tree&& __x);
643 #endif
644 
645  ~_Rb_tree() _GLIBCXX_NOEXCEPT
646  { _M_erase(_M_begin()); }
647 
648  _Rb_tree&
649  operator=(const _Rb_tree& __x);
650 
651  // Accessors.
652  _Compare
653  key_comp() const
654  { return _M_impl._M_key_compare; }
655 
656  iterator
657  begin() _GLIBCXX_NOEXCEPT
658  {
659  return iterator(static_cast<_Link_type>
660  (this->_M_impl._M_header._M_left));
661  }
662 
663  const_iterator
664  begin() const _GLIBCXX_NOEXCEPT
665  {
666  return const_iterator(static_cast<_Const_Link_type>
667  (this->_M_impl._M_header._M_left));
668  }
669 
670  iterator
671  end() _GLIBCXX_NOEXCEPT
672  { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
673 
674  const_iterator
675  end() const _GLIBCXX_NOEXCEPT
676  {
677  return const_iterator(static_cast<_Const_Link_type>
678  (&this->_M_impl._M_header));
679  }
680 
681  reverse_iterator
682  rbegin() _GLIBCXX_NOEXCEPT
683  { return reverse_iterator(end()); }
684 
685  const_reverse_iterator
686  rbegin() const _GLIBCXX_NOEXCEPT
687  { return const_reverse_iterator(end()); }
688 
689  reverse_iterator
690  rend() _GLIBCXX_NOEXCEPT
691  { return reverse_iterator(begin()); }
692 
693  const_reverse_iterator
694  rend() const _GLIBCXX_NOEXCEPT
695  { return const_reverse_iterator(begin()); }
696 
697  bool
698  empty() const _GLIBCXX_NOEXCEPT
699  { return _M_impl._M_node_count == 0; }
700 
701  size_type
702  size() const _GLIBCXX_NOEXCEPT
703  { return _M_impl._M_node_count; }
704 
705  size_type
706  max_size() const _GLIBCXX_NOEXCEPT
707  { return _M_get_Node_allocator().max_size(); }
708 
709  void
710  swap(_Rb_tree& __t);
711 
712  // Insert/erase.
713 #ifdef __GXX_EXPERIMENTAL_CXX0X__
714  template<typename _Arg>
715  pair<iterator, bool>
716  _M_insert_unique(_Arg&& __x);
717 
718  template<typename _Arg>
719  iterator
720  _M_insert_equal(_Arg&& __x);
721 
722  template<typename _Arg>
723  iterator
724  _M_insert_unique_(const_iterator __position, _Arg&& __x);
725 
726  template<typename _Arg>
727  iterator
728  _M_insert_equal_(const_iterator __position, _Arg&& __x);
729 #else
730  pair<iterator, bool>
731  _M_insert_unique(const value_type& __x);
732 
733  iterator
734  _M_insert_equal(const value_type& __x);
735 
736  iterator
737  _M_insert_unique_(const_iterator __position, const value_type& __x);
738 
739  iterator
740  _M_insert_equal_(const_iterator __position, const value_type& __x);
741 #endif
742 
743  template<typename _InputIterator>
744  void
745  _M_insert_unique(_InputIterator __first, _InputIterator __last);
746 
747  template<typename _InputIterator>
748  void
749  _M_insert_equal(_InputIterator __first, _InputIterator __last);
750 
751  private:
752  void
753  _M_erase_aux(const_iterator __position);
754 
755  void
756  _M_erase_aux(const_iterator __first, const_iterator __last);
757 
758  public:
759 #ifdef __GXX_EXPERIMENTAL_CXX0X__
760  // _GLIBCXX_RESOLVE_LIB_DEFECTS
761  // DR 130. Associative erase should return an iterator.
762  iterator
763  erase(const_iterator __position)
764  {
765  const_iterator __result = __position;
766  ++__result;
767  _M_erase_aux(__position);
768  return __result._M_const_cast();
769  }
770 
771  // LWG 2059.
772  iterator
773  erase(iterator __position)
774  {
775  iterator __result = __position;
776  ++__result;
777  _M_erase_aux(__position);
778  return __result;
779  }
780 #else
781  void
782  erase(iterator __position)
783  { _M_erase_aux(__position); }
784 
785  void
786  erase(const_iterator __position)
787  { _M_erase_aux(__position); }
788 #endif
789  size_type
790  erase(const key_type& __x);
791 
792 #ifdef __GXX_EXPERIMENTAL_CXX0X__
793  // _GLIBCXX_RESOLVE_LIB_DEFECTS
794  // DR 130. Associative erase should return an iterator.
795  iterator
796  erase(const_iterator __first, const_iterator __last)
797  {
798  _M_erase_aux(__first, __last);
799  return __last._M_const_cast();
800  }
801 #else
802  void
803  erase(iterator __first, iterator __last)
804  { _M_erase_aux(__first, __last); }
805 
806  void
807  erase(const_iterator __first, const_iterator __last)
808  { _M_erase_aux(__first, __last); }
809 #endif
810  void
811  erase(const key_type* __first, const key_type* __last);
812 
813  void
814  clear() _GLIBCXX_NOEXCEPT
815  {
816  _M_erase(_M_begin());
817  _M_leftmost() = _M_end();
818  _M_root() = 0;
819  _M_rightmost() = _M_end();
820  _M_impl._M_node_count = 0;
821  }
822 
823  // Set operations.
824  iterator
825  find(const key_type& __k);
826 
827  const_iterator
828  find(const key_type& __k) const;
829 
830  size_type
831  count(const key_type& __k) const;
832 
833  iterator
834  lower_bound(const key_type& __k)
835  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
836 
837  const_iterator
838  lower_bound(const key_type& __k) const
839  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
840 
841  iterator
842  upper_bound(const key_type& __k)
843  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
844 
845  const_iterator
846  upper_bound(const key_type& __k) const
847  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
848 
849  pair<iterator, iterator>
850  equal_range(const key_type& __k);
851 
852  pair<const_iterator, const_iterator>
853  equal_range(const key_type& __k) const;
854 
855  // Debugging.
856  bool
857  __rb_verify() const;
858  };
859 
860  template<typename _Key, typename _Val, typename _KeyOfValue,
861  typename _Compare, typename _Alloc>
862  inline bool
863  operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
864  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
865  {
866  return __x.size() == __y.size()
867  && std::equal(__x.begin(), __x.end(), __y.begin());
868  }
869 
870  template<typename _Key, typename _Val, typename _KeyOfValue,
871  typename _Compare, typename _Alloc>
872  inline bool
873  operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
874  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
875  {
876  return std::lexicographical_compare(__x.begin(), __x.end(),
877  __y.begin(), __y.end());
878  }
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 !(__x == __y); }
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 !(__y < __x); }
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  { return !(__x < __y); }
907 
908  template<typename _Key, typename _Val, typename _KeyOfValue,
909  typename _Compare, typename _Alloc>
910  inline void
911  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
912  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
913  { __x.swap(__y); }
914 
915 #ifdef __GXX_EXPERIMENTAL_CXX0X__
916  template<typename _Key, typename _Val, typename _KeyOfValue,
917  typename _Compare, typename _Alloc>
918  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
919  _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
920  : _M_impl(__x._M_impl._M_key_compare,
921  std::move(__x._M_get_Node_allocator()))
922  {
923  if (__x._M_root() != 0)
924  {
925  _M_root() = __x._M_root();
926  _M_leftmost() = __x._M_leftmost();
927  _M_rightmost() = __x._M_rightmost();
928  _M_root()->_M_parent = _M_end();
929 
930  __x._M_root() = 0;
931  __x._M_leftmost() = __x._M_end();
932  __x._M_rightmost() = __x._M_end();
933 
934  this->_M_impl._M_node_count = __x._M_impl._M_node_count;
935  __x._M_impl._M_node_count = 0;
936  }
937  }
938 #endif
939 
940  template<typename _Key, typename _Val, typename _KeyOfValue,
941  typename _Compare, typename _Alloc>
942  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
943  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
944  operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
945  {
946  if (this != &__x)
947  {
948  // Note that _Key may be a constant type.
949  clear();
950  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
951  if (__x._M_root() != 0)
952  {
953  _M_root() = _M_copy(__x._M_begin(), _M_end());
954  _M_leftmost() = _S_minimum(_M_root());
955  _M_rightmost() = _S_maximum(_M_root());
956  _M_impl._M_node_count = __x._M_impl._M_node_count;
957  }
958  }
959  return *this;
960  }
961 
962  template<typename _Key, typename _Val, typename _KeyOfValue,
963  typename _Compare, typename _Alloc>
964 #ifdef __GXX_EXPERIMENTAL_CXX0X__
965  template<typename _Arg>
966 #endif
967  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
968  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
969 #ifdef __GXX_EXPERIMENTAL_CXX0X__
970  _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v)
971 #else
972  _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
973 #endif
974  {
975  bool __insert_left = (__x != 0 || __p == _M_end()
976  || _M_impl._M_key_compare(_KeyOfValue()(__v),
977  _S_key(__p)));
978 
979  _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
980 
981  _Rb_tree_insert_and_rebalance(__insert_left, __z,
982  const_cast<_Base_ptr>(__p),
983  this->_M_impl._M_header);
984  ++_M_impl._M_node_count;
985  return iterator(__z);
986  }
987 
988  template<typename _Key, typename _Val, typename _KeyOfValue,
989  typename _Compare, typename _Alloc>
990 #ifdef __GXX_EXPERIMENTAL_CXX0X__
991  template<typename _Arg>
992 #endif
993  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
994  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
995 #ifdef __GXX_EXPERIMENTAL_CXX0X__
996  _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
997 #else
998  _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
999 #endif
1000  {
1001  bool __insert_left = (__x != 0 || __p == _M_end()
1002  || !_M_impl._M_key_compare(_S_key(__p),
1003  _KeyOfValue()(__v)));
1004 
1005  _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1006 
1007  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1008  this->_M_impl._M_header);
1009  ++_M_impl._M_node_count;
1010  return iterator(__z);
1011  }
1012 
1013  template<typename _Key, typename _Val, typename _KeyOfValue,
1014  typename _Compare, typename _Alloc>
1015 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1016  template<typename _Arg>
1017 #endif
1018  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1019  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1020 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1021  _M_insert_equal_lower(_Arg&& __v)
1022 #else
1023  _M_insert_equal_lower(const _Val& __v)
1024 #endif
1025  {
1026  _Link_type __x = _M_begin();
1027  _Link_type __y = _M_end();
1028  while (__x != 0)
1029  {
1030  __y = __x;
1031  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1032  _S_left(__x) : _S_right(__x);
1033  }
1034  return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
1035  }
1036 
1037  template<typename _Key, typename _Val, typename _KoV,
1038  typename _Compare, typename _Alloc>
1039  typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1040  _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1041  _M_copy(_Const_Link_type __x, _Link_type __p)
1042  {
1043  // Structural copy. __x and __p must be non-null.
1044  _Link_type __top = _M_clone_node(__x);
1045  __top->_M_parent = __p;
1046 
1047  __try
1048  {
1049  if (__x->_M_right)
1050  __top->_M_right = _M_copy(_S_right(__x), __top);
1051  __p = __top;
1052  __x = _S_left(__x);
1053 
1054  while (__x != 0)
1055  {
1056  _Link_type __y = _M_clone_node(__x);
1057  __p->_M_left = __y;
1058  __y->_M_parent = __p;
1059  if (__x->_M_right)
1060  __y->_M_right = _M_copy(_S_right(__x), __y);
1061  __p = __y;
1062  __x = _S_left(__x);
1063  }
1064  }
1065  __catch(...)
1066  {
1067  _M_erase(__top);
1068  __throw_exception_again;
1069  }
1070  return __top;
1071  }
1072 
1073  template<typename _Key, typename _Val, typename _KeyOfValue,
1074  typename _Compare, typename _Alloc>
1075  void
1076  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1077  _M_erase(_Link_type __x)
1078  {
1079  // Erase without rebalancing.
1080  while (__x != 0)
1081  {
1082  _M_erase(_S_right(__x));
1083  _Link_type __y = _S_left(__x);
1084  _M_destroy_node(__x);
1085  __x = __y;
1086  }
1087  }
1088 
1089  template<typename _Key, typename _Val, typename _KeyOfValue,
1090  typename _Compare, typename _Alloc>
1091  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1092  _Compare, _Alloc>::iterator
1093  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1094  _M_lower_bound(_Link_type __x, _Link_type __y,
1095  const _Key& __k)
1096  {
1097  while (__x != 0)
1098  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1099  __y = __x, __x = _S_left(__x);
1100  else
1101  __x = _S_right(__x);
1102  return iterator(__y);
1103  }
1104 
1105  template<typename _Key, typename _Val, typename _KeyOfValue,
1106  typename _Compare, typename _Alloc>
1107  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1108  _Compare, _Alloc>::const_iterator
1109  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1110  _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1111  const _Key& __k) const
1112  {
1113  while (__x != 0)
1114  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1115  __y = __x, __x = _S_left(__x);
1116  else
1117  __x = _S_right(__x);
1118  return const_iterator(__y);
1119  }
1120 
1121  template<typename _Key, typename _Val, typename _KeyOfValue,
1122  typename _Compare, typename _Alloc>
1123  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1124  _Compare, _Alloc>::iterator
1125  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1126  _M_upper_bound(_Link_type __x, _Link_type __y,
1127  const _Key& __k)
1128  {
1129  while (__x != 0)
1130  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1131  __y = __x, __x = _S_left(__x);
1132  else
1133  __x = _S_right(__x);
1134  return iterator(__y);
1135  }
1136 
1137  template<typename _Key, typename _Val, typename _KeyOfValue,
1138  typename _Compare, typename _Alloc>
1139  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1140  _Compare, _Alloc>::const_iterator
1141  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1142  _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1143  const _Key& __k) const
1144  {
1145  while (__x != 0)
1146  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1147  __y = __x, __x = _S_left(__x);
1148  else
1149  __x = _S_right(__x);
1150  return const_iterator(__y);
1151  }
1152 
1153  template<typename _Key, typename _Val, typename _KeyOfValue,
1154  typename _Compare, typename _Alloc>
1155  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1156  _Compare, _Alloc>::iterator,
1157  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1158  _Compare, _Alloc>::iterator>
1159  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1160  equal_range(const _Key& __k)
1161  {
1162  _Link_type __x = _M_begin();
1163  _Link_type __y = _M_end();
1164  while (__x != 0)
1165  {
1166  if (_M_impl._M_key_compare(_S_key(__x), __k))
1167  __x = _S_right(__x);
1168  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1169  __y = __x, __x = _S_left(__x);
1170  else
1171  {
1172  _Link_type __xu(__x), __yu(__y);
1173  __y = __x, __x = _S_left(__x);
1174  __xu = _S_right(__xu);
1175  return pair<iterator,
1176  iterator>(_M_lower_bound(__x, __y, __k),
1177  _M_upper_bound(__xu, __yu, __k));
1178  }
1179  }
1180  return pair<iterator, iterator>(iterator(__y),
1181  iterator(__y));
1182  }
1183 
1184  template<typename _Key, typename _Val, typename _KeyOfValue,
1185  typename _Compare, typename _Alloc>
1186  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1187  _Compare, _Alloc>::const_iterator,
1188  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1189  _Compare, _Alloc>::const_iterator>
1190  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1191  equal_range(const _Key& __k) const
1192  {
1193  _Const_Link_type __x = _M_begin();
1194  _Const_Link_type __y = _M_end();
1195  while (__x != 0)
1196  {
1197  if (_M_impl._M_key_compare(_S_key(__x), __k))
1198  __x = _S_right(__x);
1199  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1200  __y = __x, __x = _S_left(__x);
1201  else
1202  {
1203  _Const_Link_type __xu(__x), __yu(__y);
1204  __y = __x, __x = _S_left(__x);
1205  __xu = _S_right(__xu);
1206  return pair<const_iterator,
1207  const_iterator>(_M_lower_bound(__x, __y, __k),
1208  _M_upper_bound(__xu, __yu, __k));
1209  }
1210  }
1211  return pair<const_iterator, const_iterator>(const_iterator(__y),
1212  const_iterator(__y));
1213  }
1214 
1215  template<typename _Key, typename _Val, typename _KeyOfValue,
1216  typename _Compare, typename _Alloc>
1217  void
1218  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1219  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1220  {
1221  if (_M_root() == 0)
1222  {
1223  if (__t._M_root() != 0)
1224  {
1225  _M_root() = __t._M_root();
1226  _M_leftmost() = __t._M_leftmost();
1227  _M_rightmost() = __t._M_rightmost();
1228  _M_root()->_M_parent = _M_end();
1229 
1230  __t._M_root() = 0;
1231  __t._M_leftmost() = __t._M_end();
1232  __t._M_rightmost() = __t._M_end();
1233  }
1234  }
1235  else if (__t._M_root() == 0)
1236  {
1237  __t._M_root() = _M_root();
1238  __t._M_leftmost() = _M_leftmost();
1239  __t._M_rightmost() = _M_rightmost();
1240  __t._M_root()->_M_parent = __t._M_end();
1241 
1242  _M_root() = 0;
1243  _M_leftmost() = _M_end();
1244  _M_rightmost() = _M_end();
1245  }
1246  else
1247  {
1248  std::swap(_M_root(),__t._M_root());
1249  std::swap(_M_leftmost(),__t._M_leftmost());
1250  std::swap(_M_rightmost(),__t._M_rightmost());
1251 
1252  _M_root()->_M_parent = _M_end();
1253  __t._M_root()->_M_parent = __t._M_end();
1254  }
1255  // No need to swap header's color as it does not change.
1256  std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1257  std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1258 
1259  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1260  // 431. Swapping containers with unequal allocators.
1261  std::__alloc_swap<_Node_allocator>::
1262  _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
1263  }
1264 
1265  template<typename _Key, typename _Val, typename _KeyOfValue,
1266  typename _Compare, typename _Alloc>
1267 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1268  template<typename _Arg>
1269 #endif
1270  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1271  _Compare, _Alloc>::iterator, bool>
1272  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1273 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1274  _M_insert_unique(_Arg&& __v)
1275 #else
1276  _M_insert_unique(const _Val& __v)
1277 #endif
1278  {
1279  _Link_type __x = _M_begin();
1280  _Link_type __y = _M_end();
1281  bool __comp = true;
1282  while (__x != 0)
1283  {
1284  __y = __x;
1285  __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1286  __x = __comp ? _S_left(__x) : _S_right(__x);
1287  }
1288  iterator __j = iterator(__y);
1289  if (__comp)
1290  {
1291  if (__j == begin())
1292  return pair<iterator, bool>
1293  (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
1294  else
1295  --__j;
1296  }
1297  if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
1298  return pair<iterator, bool>
1299  (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
1300  return pair<iterator, bool>(__j, false);
1301  }
1302 
1303  template<typename _Key, typename _Val, typename _KeyOfValue,
1304  typename _Compare, typename _Alloc>
1305 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1306  template<typename _Arg>
1307 #endif
1308  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1309  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1310 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1311  _M_insert_equal(_Arg&& __v)
1312 #else
1313  _M_insert_equal(const _Val& __v)
1314 #endif
1315  {
1316  _Link_type __x = _M_begin();
1317  _Link_type __y = _M_end();
1318  while (__x != 0)
1319  {
1320  __y = __x;
1321  __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1322  _S_left(__x) : _S_right(__x);
1323  }
1324  return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
1325  }
1326 
1327  template<typename _Key, typename _Val, typename _KeyOfValue,
1328  typename _Compare, typename _Alloc>
1329 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1330  template<typename _Arg>
1331 #endif
1332  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1333  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1334 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1335  _M_insert_unique_(const_iterator __position, _Arg&& __v)
1336 #else
1337  _M_insert_unique_(const_iterator __position, const _Val& __v)
1338 #endif
1339  {
1340  // end()
1341  if (__position._M_node == _M_end())
1342  {
1343  if (size() > 0
1344  && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1345  _KeyOfValue()(__v)))
1346  return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v));
1347  else
1348  return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1349  }
1350  else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1351  _S_key(__position._M_node)))
1352  {
1353  // First, try before...
1354  const_iterator __before = __position;
1355  if (__position._M_node == _M_leftmost()) // begin()
1356  return _M_insert_(_M_leftmost(), _M_leftmost(),
1357  _GLIBCXX_FORWARD(_Arg, __v));
1358  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
1359  _KeyOfValue()(__v)))
1360  {
1361  if (_S_right(__before._M_node) == 0)
1362  return _M_insert_(0, __before._M_node,
1363  _GLIBCXX_FORWARD(_Arg, __v));
1364  else
1365  return _M_insert_(__position._M_node,
1366  __position._M_node,
1367  _GLIBCXX_FORWARD(_Arg, __v));
1368  }
1369  else
1370  return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1371  }
1372  else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1373  _KeyOfValue()(__v)))
1374  {
1375  // ... then try after.
1376  const_iterator __after = __position;
1377  if (__position._M_node == _M_rightmost())
1378  return _M_insert_(0, _M_rightmost(),
1379  _GLIBCXX_FORWARD(_Arg, __v));
1380  else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1381  _S_key((++__after)._M_node)))
1382  {
1383  if (_S_right(__position._M_node) == 0)
1384  return _M_insert_(0, __position._M_node,
1385  _GLIBCXX_FORWARD(_Arg, __v));
1386  else
1387  return _M_insert_(__after._M_node, __after._M_node,
1388  _GLIBCXX_FORWARD(_Arg, __v));
1389  }
1390  else
1391  return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
1392  }
1393  else
1394  // Equivalent keys.
1395  return __position._M_const_cast();
1396  }
1397 
1398  template<typename _Key, typename _Val, typename _KeyOfValue,
1399  typename _Compare, typename _Alloc>
1400 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1401  template<typename _Arg>
1402 #endif
1403  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1404  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1405 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1406  _M_insert_equal_(const_iterator __position, _Arg&& __v)
1407 #else
1408  _M_insert_equal_(const_iterator __position, const _Val& __v)
1409 #endif
1410  {
1411  // end()
1412  if (__position._M_node == _M_end())
1413  {
1414  if (size() > 0
1415  && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1416  _S_key(_M_rightmost())))
1417  return _M_insert_(0, _M_rightmost(),
1418  _GLIBCXX_FORWARD(_Arg, __v));
1419  else
1420  return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
1421  }
1422  else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1423  _KeyOfValue()(__v)))
1424  {
1425  // First, try before...
1426  const_iterator __before = __position;
1427  if (__position._M_node == _M_leftmost()) // begin()
1428  return _M_insert_(_M_leftmost(), _M_leftmost(),
1429  _GLIBCXX_FORWARD(_Arg, __v));
1430  else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1431  _S_key((--__before)._M_node)))
1432  {
1433  if (_S_right(__before._M_node) == 0)
1434  return _M_insert_(0, __before._M_node,
1435  _GLIBCXX_FORWARD(_Arg, __v));
1436  else
1437  return _M_insert_(__position._M_node,
1438  __position._M_node,
1439  _GLIBCXX_FORWARD(_Arg, __v));
1440  }
1441  else
1442  return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
1443  }
1444  else
1445  {
1446  // ... then try after.
1447  const_iterator __after = __position;
1448  if (__position._M_node == _M_rightmost())
1449  return _M_insert_(0, _M_rightmost(),
1450  _GLIBCXX_FORWARD(_Arg, __v));
1451  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1452  _KeyOfValue()(__v)))
1453  {
1454  if (_S_right(__position._M_node) == 0)
1455  return _M_insert_(0, __position._M_node,
1456  _GLIBCXX_FORWARD(_Arg, __v));
1457  else
1458  return _M_insert_(__after._M_node, __after._M_node,
1459  _GLIBCXX_FORWARD(_Arg, __v));
1460  }
1461  else
1462  return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
1463  }
1464  }
1465 
1466  template<typename _Key, typename _Val, typename _KoV,
1467  typename _Cmp, typename _Alloc>
1468  template<class _II>
1469  void
1470  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1471  _M_insert_unique(_II __first, _II __last)
1472  {
1473  for (; __first != __last; ++__first)
1474  _M_insert_unique_(end(), *__first);
1475  }
1476 
1477  template<typename _Key, typename _Val, typename _KoV,
1478  typename _Cmp, typename _Alloc>
1479  template<class _II>
1480  void
1481  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1482  _M_insert_equal(_II __first, _II __last)
1483  {
1484  for (; __first != __last; ++__first)
1485  _M_insert_equal_(end(), *__first);
1486  }
1487 
1488  template<typename _Key, typename _Val, typename _KeyOfValue,
1489  typename _Compare, typename _Alloc>
1490  void
1491  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1492  _M_erase_aux(const_iterator __position)
1493  {
1494  _Link_type __y =
1495  static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1496  (const_cast<_Base_ptr>(__position._M_node),
1497  this->_M_impl._M_header));
1498  _M_destroy_node(__y);
1499  --_M_impl._M_node_count;
1500  }
1501 
1502  template<typename _Key, typename _Val, typename _KeyOfValue,
1503  typename _Compare, typename _Alloc>
1504  void
1505  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1506  _M_erase_aux(const_iterator __first, const_iterator __last)
1507  {
1508  if (__first == begin() && __last == end())
1509  clear();
1510  else
1511  while (__first != __last)
1512  erase(__first++);
1513  }
1514 
1515  template<typename _Key, typename _Val, typename _KeyOfValue,
1516  typename _Compare, typename _Alloc>
1517  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1518  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1519  erase(const _Key& __x)
1520  {
1521  pair<iterator, iterator> __p = equal_range(__x);
1522  const size_type __old_size = size();
1523  erase(__p.first, __p.second);
1524  return __old_size - size();
1525  }
1526 
1527  template<typename _Key, typename _Val, typename _KeyOfValue,
1528  typename _Compare, typename _Alloc>
1529  void
1530  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1531  erase(const _Key* __first, const _Key* __last)
1532  {
1533  while (__first != __last)
1534  erase(*__first++);
1535  }
1536 
1537  template<typename _Key, typename _Val, typename _KeyOfValue,
1538  typename _Compare, typename _Alloc>
1539  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1540  _Compare, _Alloc>::iterator
1541  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1542  find(const _Key& __k)
1543  {
1544  iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1545  return (__j == end()
1546  || _M_impl._M_key_compare(__k,
1547  _S_key(__j._M_node))) ? end() : __j;
1548  }
1549 
1550  template<typename _Key, typename _Val, typename _KeyOfValue,
1551  typename _Compare, typename _Alloc>
1552  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1553  _Compare, _Alloc>::const_iterator
1554  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1555  find(const _Key& __k) const
1556  {
1557  const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1558  return (__j == end()
1559  || _M_impl._M_key_compare(__k,
1560  _S_key(__j._M_node))) ? end() : __j;
1561  }
1562 
1563  template<typename _Key, typename _Val, typename _KeyOfValue,
1564  typename _Compare, typename _Alloc>
1565  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1566  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1567  count(const _Key& __k) const
1568  {
1569  pair<const_iterator, const_iterator> __p = equal_range(__k);
1570  const size_type __n = std::distance(__p.first, __p.second);
1571  return __n;
1572  }
1573 
1574  _GLIBCXX_PURE unsigned int
1575  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1576  const _Rb_tree_node_base* __root) throw ();
1577 
1578  template<typename _Key, typename _Val, typename _KeyOfValue,
1579  typename _Compare, typename _Alloc>
1580  bool
1581  _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1582  {
1583  if (_M_impl._M_node_count == 0 || begin() == end())
1584  return _M_impl._M_node_count == 0 && begin() == end()
1585  && this->_M_impl._M_header._M_left == _M_end()
1586  && this->_M_impl._M_header._M_right == _M_end();
1587 
1588  unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1589  for (const_iterator __it = begin(); __it != end(); ++__it)
1590  {
1591  _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1592  _Const_Link_type __L = _S_left(__x);
1593  _Const_Link_type __R = _S_right(__x);
1594 
1595  if (__x->_M_color == _S_red)
1596  if ((__L && __L->_M_color == _S_red)
1597  || (__R && __R->_M_color == _S_red))
1598  return false;
1599 
1600  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1601  return false;
1602  if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1603  return false;
1604 
1605  if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1606  return false;
1607  }
1608 
1609  if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1610  return false;
1611  if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1612  return false;
1613  return true;
1614  }
1615 
1616 _GLIBCXX_END_NAMESPACE_VERSION
1617 } // namespace
1618 
1619 #endif