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