OSDN Git Service

2009-08-14 Edward Smith-Rowland <3dw4rd@verizon.net>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / stl_tree.h
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   _GLIBCXX_PURE _Rb_tree_node_base*
141   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
142
143   _GLIBCXX_PURE const _Rb_tree_node_base*
144   _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
145
146   _GLIBCXX_PURE _Rb_tree_node_base*
147   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
148
149   _GLIBCXX_PURE const _Rb_tree_node_base*
150   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
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) throw ();
314
315   _Rb_tree_node_base*
316   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
317                                _Rb_tree_node_base& __header) throw ();
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       swap(_Rb_tree& __t);      
679
680       // Insert/erase.
681       pair<iterator, bool>
682       _M_insert_unique(const value_type& __x);
683
684       iterator
685       _M_insert_equal(const value_type& __x);
686
687       iterator
688       _M_insert_unique_(const_iterator __position, const value_type& __x);
689
690       iterator
691       _M_insert_equal_(const_iterator __position, const value_type& __x);
692
693       template<typename _InputIterator>
694         void
695         _M_insert_unique(_InputIterator __first, _InputIterator __last);
696
697       template<typename _InputIterator>
698         void
699         _M_insert_equal(_InputIterator __first, _InputIterator __last);
700
701 #ifdef __GXX_EXPERIMENTAL_CXX0X__
702       // _GLIBCXX_RESOLVE_LIB_DEFECTS
703       // DR 130. Associative erase should return an iterator.
704       iterator
705       erase(iterator __position);
706
707       // _GLIBCXX_RESOLVE_LIB_DEFECTS
708       // DR 130. Associative erase should return an iterator.
709       const_iterator
710       erase(const_iterator __position);
711 #else
712       void
713       erase(iterator __position);
714
715       void
716       erase(const_iterator __position);
717 #endif
718       size_type
719       erase(const key_type& __x);
720
721 #ifdef __GXX_EXPERIMENTAL_CXX0X__
722       // _GLIBCXX_RESOLVE_LIB_DEFECTS
723       // DR 130. Associative erase should return an iterator.
724       iterator
725       erase(iterator __first, iterator __last);
726
727       // _GLIBCXX_RESOLVE_LIB_DEFECTS
728       // DR 130. Associative erase should return an iterator.
729       const_iterator
730       erase(const_iterator __first, const_iterator __last);
731 #else
732       void
733       erase(iterator __first, iterator __last);
734
735       void
736       erase(const_iterator __first, const_iterator __last);
737 #endif
738       void
739       erase(const key_type* __first, const key_type* __last);
740
741       void
742       clear()
743       {
744         _M_erase(_M_begin());
745         _M_leftmost() = _M_end();
746         _M_root() = 0;
747         _M_rightmost() = _M_end();
748         _M_impl._M_node_count = 0;
749       }
750
751       // Set operations.
752       iterator
753       find(const key_type& __k);
754
755       const_iterator
756       find(const key_type& __k) const;
757
758       size_type
759       count(const key_type& __k) const;
760
761       iterator
762       lower_bound(const key_type& __k)
763       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
764
765       const_iterator
766       lower_bound(const key_type& __k) const
767       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
768
769       iterator
770       upper_bound(const key_type& __k)
771       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
772
773       const_iterator
774       upper_bound(const key_type& __k) const
775       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
776
777       pair<iterator, iterator>
778       equal_range(const key_type& __k);
779
780       pair<const_iterator, const_iterator>
781       equal_range(const key_type& __k) const;
782
783       // Debugging.
784       bool
785       __rb_verify() const;
786     };
787
788   template<typename _Key, typename _Val, typename _KeyOfValue,
789            typename _Compare, typename _Alloc>
790     inline bool
791     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
792                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
793     {
794       return __x.size() == __y.size()
795              && std::equal(__x.begin(), __x.end(), __y.begin());
796     }
797
798   template<typename _Key, typename _Val, typename _KeyOfValue,
799            typename _Compare, typename _Alloc>
800     inline bool
801     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
802               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
803     {
804       return std::lexicographical_compare(__x.begin(), __x.end(), 
805                                           __y.begin(), __y.end());
806     }
807
808   template<typename _Key, typename _Val, typename _KeyOfValue,
809            typename _Compare, typename _Alloc>
810     inline bool
811     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
812                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
813     { return !(__x == __y); }
814
815   template<typename _Key, typename _Val, typename _KeyOfValue,
816            typename _Compare, typename _Alloc>
817     inline bool
818     operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
819               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
820     { return __y < __x; }
821
822   template<typename _Key, typename _Val, typename _KeyOfValue,
823            typename _Compare, typename _Alloc>
824     inline bool
825     operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
826                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
827     { return !(__y < __x); }
828
829   template<typename _Key, typename _Val, typename _KeyOfValue,
830            typename _Compare, typename _Alloc>
831     inline bool
832     operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
833                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
834     { return !(__x < __y); }
835
836   template<typename _Key, typename _Val, typename _KeyOfValue,
837            typename _Compare, typename _Alloc>
838     inline void
839     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
840          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
841     { __x.swap(__y); }
842
843 #ifdef __GXX_EXPERIMENTAL_CXX0X__
844   template<typename _Key, typename _Val, typename _KeyOfValue,
845            typename _Compare, typename _Alloc>
846     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
847     _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
848     : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
849     {
850       if (__x._M_root() != 0)
851         {
852           _M_root() = __x._M_root();
853           _M_leftmost() = __x._M_leftmost();
854           _M_rightmost() = __x._M_rightmost();
855           _M_root()->_M_parent = _M_end();
856
857           __x._M_root() = 0;
858           __x._M_leftmost() = __x._M_end();
859           __x._M_rightmost() = __x._M_end();
860
861           this->_M_impl._M_node_count = __x._M_impl._M_node_count;
862           __x._M_impl._M_node_count = 0;
863         }
864     }
865 #endif
866
867   template<typename _Key, typename _Val, typename _KeyOfValue,
868            typename _Compare, typename _Alloc>
869     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
870     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
871     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
872     {
873       if (this != &__x)
874         {
875           // Note that _Key may be a constant type.
876           clear();
877           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
878           if (__x._M_root() != 0)
879             {
880               _M_root() = _M_copy(__x._M_begin(), _M_end());
881               _M_leftmost() = _S_minimum(_M_root());
882               _M_rightmost() = _S_maximum(_M_root());
883               _M_impl._M_node_count = __x._M_impl._M_node_count;
884             }
885         }
886       return *this;
887     }
888
889   template<typename _Key, typename _Val, typename _KeyOfValue,
890            typename _Compare, typename _Alloc>
891     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
892     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
893     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
894     {
895       bool __insert_left = (__x != 0 || __p == _M_end()
896                             || _M_impl._M_key_compare(_KeyOfValue()(__v), 
897                                                       _S_key(__p)));
898
899       _Link_type __z = _M_create_node(__v);
900
901       _Rb_tree_insert_and_rebalance(__insert_left, __z,
902                                     const_cast<_Base_ptr>(__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_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
913     {
914       bool __insert_left = (__x != 0 || __p == _M_end()
915                             || !_M_impl._M_key_compare(_S_key(__p),
916                                                        _KeyOfValue()(__v)));
917
918       _Link_type __z = _M_create_node(__v);
919
920       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
921                                     this->_M_impl._M_header);
922       ++_M_impl._M_node_count;
923       return iterator(__z);
924     }
925
926   template<typename _Key, typename _Val, typename _KeyOfValue,
927            typename _Compare, typename _Alloc>
928     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
929     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
930     _M_insert_equal_lower(const _Val& __v)
931     {
932       _Link_type __x = _M_begin();
933       _Link_type __y = _M_end();
934       while (__x != 0)
935         {
936           __y = __x;
937           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
938                 _S_left(__x) : _S_right(__x);
939         }
940       return _M_insert_lower(__x, __y, __v);
941     }
942
943   template<typename _Key, typename _Val, typename _KoV,
944            typename _Compare, typename _Alloc>
945     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
946     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
947     _M_copy(_Const_Link_type __x, _Link_type __p)
948     {
949       // Structural copy.  __x and __p must be non-null.
950       _Link_type __top = _M_clone_node(__x);
951       __top->_M_parent = __p;
952
953       __try
954         {
955           if (__x->_M_right)
956             __top->_M_right = _M_copy(_S_right(__x), __top);
957           __p = __top;
958           __x = _S_left(__x);
959
960           while (__x != 0)
961             {
962               _Link_type __y = _M_clone_node(__x);
963               __p->_M_left = __y;
964               __y->_M_parent = __p;
965               if (__x->_M_right)
966                 __y->_M_right = _M_copy(_S_right(__x), __y);
967               __p = __y;
968               __x = _S_left(__x);
969             }
970         }
971       __catch(...)
972         {
973           _M_erase(__top);
974           __throw_exception_again;
975         }
976       return __top;
977     }
978
979   template<typename _Key, typename _Val, typename _KeyOfValue,
980            typename _Compare, typename _Alloc>
981     void
982     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
983     _M_erase(_Link_type __x)
984     {
985       // Erase without rebalancing.
986       while (__x != 0)
987         {
988           _M_erase(_S_right(__x));
989           _Link_type __y = _S_left(__x);
990           _M_destroy_node(__x);
991           __x = __y;
992         }
993     }
994
995   template<typename _Key, typename _Val, typename _KeyOfValue,
996            typename _Compare, typename _Alloc>
997     typename _Rb_tree<_Key, _Val, _KeyOfValue,
998                       _Compare, _Alloc>::iterator
999     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1000     _M_lower_bound(_Link_type __x, _Link_type __y,
1001                    const _Key& __k)
1002     {
1003       while (__x != 0)
1004         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1005           __y = __x, __x = _S_left(__x);
1006         else
1007           __x = _S_right(__x);
1008       return iterator(__y);
1009     }
1010
1011   template<typename _Key, typename _Val, typename _KeyOfValue,
1012            typename _Compare, typename _Alloc>
1013     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1014                       _Compare, _Alloc>::const_iterator
1015     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1016     _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1017                    const _Key& __k) const
1018     {
1019       while (__x != 0)
1020         if (!_M_impl._M_key_compare(_S_key(__x), __k))
1021           __y = __x, __x = _S_left(__x);
1022         else
1023           __x = _S_right(__x);
1024       return const_iterator(__y);
1025     }
1026
1027   template<typename _Key, typename _Val, typename _KeyOfValue,
1028            typename _Compare, typename _Alloc>
1029     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1030                       _Compare, _Alloc>::iterator
1031     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1032     _M_upper_bound(_Link_type __x, _Link_type __y,
1033                    const _Key& __k)
1034     {
1035       while (__x != 0)
1036         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1037           __y = __x, __x = _S_left(__x);
1038         else
1039           __x = _S_right(__x);
1040       return iterator(__y);
1041     }
1042
1043   template<typename _Key, typename _Val, typename _KeyOfValue,
1044            typename _Compare, typename _Alloc>
1045     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1046                       _Compare, _Alloc>::const_iterator
1047     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1048     _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1049                    const _Key& __k) const
1050     {
1051       while (__x != 0)
1052         if (_M_impl._M_key_compare(__k, _S_key(__x)))
1053           __y = __x, __x = _S_left(__x);
1054         else
1055           __x = _S_right(__x);
1056       return const_iterator(__y);
1057     }
1058
1059   template<typename _Key, typename _Val, typename _KeyOfValue,
1060            typename _Compare, typename _Alloc>
1061     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1062                            _Compare, _Alloc>::iterator,
1063          typename _Rb_tree<_Key, _Val, _KeyOfValue,
1064                            _Compare, _Alloc>::iterator>
1065     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1066     equal_range(const _Key& __k)
1067     {
1068       _Link_type __x = _M_begin();
1069       _Link_type __y = _M_end();
1070       while (__x != 0)
1071         {
1072           if (_M_impl._M_key_compare(_S_key(__x), __k))
1073             __x = _S_right(__x);
1074           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1075             __y = __x, __x = _S_left(__x);
1076           else
1077             {
1078               _Link_type __xu(__x), __yu(__y);
1079               __y = __x, __x = _S_left(__x);
1080               __xu = _S_right(__xu);
1081               return pair<iterator,
1082                           iterator>(_M_lower_bound(__x, __y, __k),
1083                                     _M_upper_bound(__xu, __yu, __k));
1084             }
1085         }
1086       return pair<iterator, iterator>(iterator(__y),
1087                                       iterator(__y));
1088     }
1089
1090   template<typename _Key, typename _Val, typename _KeyOfValue,
1091            typename _Compare, typename _Alloc>
1092     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1093                            _Compare, _Alloc>::const_iterator,
1094          typename _Rb_tree<_Key, _Val, _KeyOfValue,
1095                            _Compare, _Alloc>::const_iterator>
1096     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1097     equal_range(const _Key& __k) const
1098     {
1099       _Const_Link_type __x = _M_begin();
1100       _Const_Link_type __y = _M_end();
1101       while (__x != 0)
1102         {
1103           if (_M_impl._M_key_compare(_S_key(__x), __k))
1104             __x = _S_right(__x);
1105           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1106             __y = __x, __x = _S_left(__x);
1107           else
1108             {
1109               _Const_Link_type __xu(__x), __yu(__y);
1110               __y = __x, __x = _S_left(__x);
1111               __xu = _S_right(__xu);
1112               return pair<const_iterator,
1113                           const_iterator>(_M_lower_bound(__x, __y, __k),
1114                                           _M_upper_bound(__xu, __yu, __k));
1115             }
1116         }
1117       return pair<const_iterator, const_iterator>(const_iterator(__y),
1118                                                   const_iterator(__y));
1119     }
1120
1121   template<typename _Key, typename _Val, typename _KeyOfValue,
1122            typename _Compare, typename _Alloc>
1123     void
1124     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1125     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1126     {
1127       if (_M_root() == 0)
1128         {
1129           if (__t._M_root() != 0)
1130             {
1131               _M_root() = __t._M_root();
1132               _M_leftmost() = __t._M_leftmost();
1133               _M_rightmost() = __t._M_rightmost();
1134               _M_root()->_M_parent = _M_end();
1135               
1136               __t._M_root() = 0;
1137               __t._M_leftmost() = __t._M_end();
1138               __t._M_rightmost() = __t._M_end();
1139             }
1140         }
1141       else if (__t._M_root() == 0)
1142         {
1143           __t._M_root() = _M_root();
1144           __t._M_leftmost() = _M_leftmost();
1145           __t._M_rightmost() = _M_rightmost();
1146           __t._M_root()->_M_parent = __t._M_end();
1147           
1148           _M_root() = 0;
1149           _M_leftmost() = _M_end();
1150           _M_rightmost() = _M_end();
1151         }
1152       else
1153         {
1154           std::swap(_M_root(),__t._M_root());
1155           std::swap(_M_leftmost(),__t._M_leftmost());
1156           std::swap(_M_rightmost(),__t._M_rightmost());
1157           
1158           _M_root()->_M_parent = _M_end();
1159           __t._M_root()->_M_parent = __t._M_end();
1160         }
1161       // No need to swap header's color as it does not change.
1162       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1163       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1164       
1165       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1166       // 431. Swapping containers with unequal allocators.
1167       std::__alloc_swap<_Node_allocator>::
1168         _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
1169     }
1170
1171   template<typename _Key, typename _Val, typename _KeyOfValue,
1172            typename _Compare, typename _Alloc>
1173     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1174                            _Compare, _Alloc>::iterator, bool>
1175     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1176     _M_insert_unique(const _Val& __v)
1177     {
1178       _Link_type __x = _M_begin();
1179       _Link_type __y = _M_end();
1180       bool __comp = true;
1181       while (__x != 0)
1182         {
1183           __y = __x;
1184           __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1185           __x = __comp ? _S_left(__x) : _S_right(__x);
1186         }
1187       iterator __j = iterator(__y);
1188       if (__comp)
1189         {
1190           if (__j == begin())
1191             return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
1192           else
1193             --__j;
1194         }
1195       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
1196         return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
1197       return pair<iterator, bool>(__j, false);
1198     }
1199
1200   template<typename _Key, typename _Val, typename _KeyOfValue,
1201            typename _Compare, typename _Alloc>
1202     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1203     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1204     _M_insert_equal(const _Val& __v)
1205     {
1206       _Link_type __x = _M_begin();
1207       _Link_type __y = _M_end();
1208       while (__x != 0)
1209         {
1210           __y = __x;
1211           __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1212                 _S_left(__x) : _S_right(__x);
1213         }
1214       return _M_insert_(__x, __y, __v);
1215     }
1216
1217   template<typename _Key, typename _Val, typename _KeyOfValue,
1218            typename _Compare, typename _Alloc>
1219     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1220     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1221     _M_insert_unique_(const_iterator __position, const _Val& __v)
1222     {
1223       // end()
1224       if (__position._M_node == _M_end())
1225         {
1226           if (size() > 0
1227               && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
1228                                         _KeyOfValue()(__v)))
1229             return _M_insert_(0, _M_rightmost(), __v);
1230           else
1231             return _M_insert_unique(__v).first;
1232         }
1233       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1234                                       _S_key(__position._M_node)))
1235         {
1236           // First, try before...
1237           const_iterator __before = __position;
1238           if (__position._M_node == _M_leftmost()) // begin()
1239             return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
1240           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 
1241                                           _KeyOfValue()(__v)))
1242             {
1243               if (_S_right(__before._M_node) == 0)
1244                 return _M_insert_(0, __before._M_node, __v);
1245               else
1246                 return _M_insert_(__position._M_node,
1247                                   __position._M_node, __v);
1248             }
1249           else
1250             return _M_insert_unique(__v).first;
1251         }
1252       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
1253                                       _KeyOfValue()(__v)))
1254         {
1255           // ... then try after.
1256           const_iterator __after = __position;
1257           if (__position._M_node == _M_rightmost())
1258             return _M_insert_(0, _M_rightmost(), __v);
1259           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
1260                                           _S_key((++__after)._M_node)))
1261             {
1262               if (_S_right(__position._M_node) == 0)
1263                 return _M_insert_(0, __position._M_node, __v);
1264               else
1265                 return _M_insert_(__after._M_node, __after._M_node, __v);
1266             }
1267           else
1268             return _M_insert_unique(__v).first;
1269         }
1270       else
1271         // Equivalent keys.
1272         return iterator(static_cast<_Link_type>
1273                         (const_cast<_Base_ptr>(__position._M_node)));
1274     }
1275
1276   template<typename _Key, typename _Val, typename _KeyOfValue,
1277            typename _Compare, typename _Alloc>
1278     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1279     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1280     _M_insert_equal_(const_iterator __position, const _Val& __v)
1281     {
1282       // end()
1283       if (__position._M_node == _M_end())
1284         {
1285           if (size() > 0
1286               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1287                                          _S_key(_M_rightmost())))
1288             return _M_insert_(0, _M_rightmost(), __v);
1289           else
1290             return _M_insert_equal(__v);
1291         }
1292       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1293                                        _KeyOfValue()(__v)))
1294         {
1295           // First, try before...
1296           const_iterator __before = __position;
1297           if (__position._M_node == _M_leftmost()) // begin()
1298             return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
1299           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1300                                            _S_key((--__before)._M_node)))
1301             {
1302               if (_S_right(__before._M_node) == 0)
1303                 return _M_insert_(0, __before._M_node, __v);
1304               else
1305                 return _M_insert_(__position._M_node,
1306                                   __position._M_node, __v);
1307             }
1308           else
1309             return _M_insert_equal(__v);
1310         }
1311       else
1312         {
1313           // ... then try after.  
1314           const_iterator __after = __position;
1315           if (__position._M_node == _M_rightmost())
1316             return _M_insert_(0, _M_rightmost(), __v);
1317           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1318                                            _KeyOfValue()(__v)))
1319             {
1320               if (_S_right(__position._M_node) == 0)
1321                 return _M_insert_(0, __position._M_node, __v);
1322               else
1323                 return _M_insert_(__after._M_node, __after._M_node, __v);
1324             }
1325           else
1326             return _M_insert_equal_lower(__v);
1327         }
1328     }
1329
1330   template<typename _Key, typename _Val, typename _KoV,
1331            typename _Cmp, typename _Alloc>
1332     template<class _II>
1333       void
1334       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1335       _M_insert_unique(_II __first, _II __last)
1336       {
1337         for (; __first != __last; ++__first)
1338           _M_insert_unique_(end(), *__first);
1339       }
1340
1341   template<typename _Key, typename _Val, typename _KoV,
1342            typename _Cmp, typename _Alloc>
1343     template<class _II>
1344       void
1345       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1346       _M_insert_equal(_II __first, _II __last)
1347       {
1348         for (; __first != __last; ++__first)
1349           _M_insert_equal_(end(), *__first);
1350       }
1351
1352 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1353   // _GLIBCXX_RESOLVE_LIB_DEFECTS
1354   // DR 130. Associative erase should return an iterator.
1355   template<typename _Key, typename _Val, typename _KeyOfValue,
1356            typename _Compare, typename _Alloc>
1357     inline typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1358     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1359     erase(iterator __position)
1360     {
1361       iterator __result = __position;
1362       ++__result;
1363       _Link_type __y =
1364         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1365                                 (__position._M_node,
1366                                  this->_M_impl._M_header));
1367       _M_destroy_node(__y);
1368       --_M_impl._M_node_count;
1369       return __result;
1370     }
1371
1372   // _GLIBCXX_RESOLVE_LIB_DEFECTS
1373   // DR 130. Associative erase should return an iterator.
1374   template<typename _Key, typename _Val, typename _KeyOfValue,
1375            typename _Compare, typename _Alloc>
1376     inline typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1377     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1378     erase(const_iterator __position)
1379     {
1380       const_iterator __result = __position;
1381       ++__result;
1382       _Link_type __y =
1383         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1384                                 (const_cast<_Base_ptr>(__position._M_node),
1385                                  this->_M_impl._M_header));
1386       _M_destroy_node(__y);
1387       --_M_impl._M_node_count;
1388       return __result;
1389     }
1390 #else
1391   template<typename _Key, typename _Val, typename _KeyOfValue,
1392            typename _Compare, typename _Alloc>
1393     inline void
1394     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1395     erase(iterator __position)
1396     {
1397       _Link_type __y =
1398         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1399                                 (__position._M_node,
1400                                  this->_M_impl._M_header));
1401       _M_destroy_node(__y);
1402       --_M_impl._M_node_count;
1403     }
1404
1405   template<typename _Key, typename _Val, typename _KeyOfValue,
1406            typename _Compare, typename _Alloc>
1407     inline void
1408     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1409     erase(const_iterator __position)
1410     {
1411       _Link_type __y =
1412         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1413                                 (const_cast<_Base_ptr>(__position._M_node),
1414                                  this->_M_impl._M_header));
1415       _M_destroy_node(__y);
1416       --_M_impl._M_node_count;
1417     }
1418 #endif
1419
1420   template<typename _Key, typename _Val, typename _KeyOfValue,
1421            typename _Compare, typename _Alloc>
1422     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1423     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1424     erase(const _Key& __x)
1425     {
1426       pair<iterator, iterator> __p = equal_range(__x);
1427       const size_type __old_size = size();
1428       erase(__p.first, __p.second);
1429       return __old_size - size();
1430     }
1431
1432 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1433   // _GLIBCXX_RESOLVE_LIB_DEFECTS
1434   // DR 130. Associative erase should return an iterator.
1435   template<typename _Key, typename _Val, typename _KeyOfValue,
1436            typename _Compare, typename _Alloc>
1437     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1438     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1439     erase(iterator __first, iterator __last)
1440     {
1441       if (__first == begin() && __last == end())
1442         {
1443           clear();
1444           return end();
1445         }
1446       else
1447         {
1448           while (__first != __last)
1449             erase(__first++);
1450           return __last;
1451         }
1452     }
1453
1454   // _GLIBCXX_RESOLVE_LIB_DEFECTS
1455   // DR 130. Associative erase should return an iterator.
1456   template<typename _Key, typename _Val, typename _KeyOfValue,
1457            typename _Compare, typename _Alloc>
1458     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
1459     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1460     erase(const_iterator __first, const_iterator __last)
1461     {
1462       if (__first == begin() && __last == end())
1463         {
1464           clear();
1465           return end();
1466         }
1467       else
1468         {
1469           while (__first != __last)
1470             erase(__first++);
1471           return __last;
1472         }
1473     }
1474 #else
1475   template<typename _Key, typename _Val, typename _KeyOfValue,
1476            typename _Compare, typename _Alloc>
1477     void
1478     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1479     erase(iterator __first, iterator __last)
1480     {
1481       if (__first == begin() && __last == end())
1482         clear();
1483       else
1484         while (__first != __last)
1485           erase(__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     erase(const_iterator __first, const_iterator __last)
1493     {
1494       if (__first == begin() && __last == end())
1495         clear();
1496       else
1497         while (__first != __last)
1498           erase(__first++);
1499     }
1500 #endif
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     erase(const _Key* __first, const _Key* __last)
1507     {
1508       while (__first != __last)
1509         erase(*__first++);
1510     }
1511
1512   template<typename _Key, typename _Val, typename _KeyOfValue,
1513            typename _Compare, typename _Alloc>
1514     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1515                       _Compare, _Alloc>::iterator
1516     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1517     find(const _Key& __k)
1518     {
1519       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1520       return (__j == end()
1521               || _M_impl._M_key_compare(__k,
1522                                         _S_key(__j._M_node))) ? end() : __j;
1523     }
1524
1525   template<typename _Key, typename _Val, typename _KeyOfValue,
1526            typename _Compare, typename _Alloc>
1527     typename _Rb_tree<_Key, _Val, _KeyOfValue,
1528                       _Compare, _Alloc>::const_iterator
1529     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1530     find(const _Key& __k) const
1531     {
1532       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1533       return (__j == end()
1534               || _M_impl._M_key_compare(__k, 
1535                                         _S_key(__j._M_node))) ? end() : __j;
1536     }
1537
1538   template<typename _Key, typename _Val, typename _KeyOfValue,
1539            typename _Compare, typename _Alloc>
1540     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1541     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1542     count(const _Key& __k) const
1543     {
1544       pair<const_iterator, const_iterator> __p = equal_range(__k);
1545       const size_type __n = std::distance(__p.first, __p.second);
1546       return __n;
1547     }
1548
1549   _GLIBCXX_PURE unsigned int
1550   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1551                        const _Rb_tree_node_base* __root) throw ();
1552
1553   template<typename _Key, typename _Val, typename _KeyOfValue,
1554            typename _Compare, typename _Alloc>
1555     bool
1556     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1557     {
1558       if (_M_impl._M_node_count == 0 || begin() == end())
1559         return _M_impl._M_node_count == 0 && begin() == end()
1560                && this->_M_impl._M_header._M_left == _M_end()
1561                && this->_M_impl._M_header._M_right == _M_end();
1562
1563       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1564       for (const_iterator __it = begin(); __it != end(); ++__it)
1565         {
1566           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1567           _Const_Link_type __L = _S_left(__x);
1568           _Const_Link_type __R = _S_right(__x);
1569
1570           if (__x->_M_color == _S_red)
1571             if ((__L && __L->_M_color == _S_red)
1572                 || (__R && __R->_M_color == _S_red))
1573               return false;
1574
1575           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1576             return false;
1577           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1578             return false;
1579
1580           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1581             return false;
1582         }
1583
1584       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1585         return false;
1586       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1587         return false;
1588       return true;
1589     }
1590
1591 _GLIBCXX_END_NAMESPACE
1592
1593 #endif