OSDN Git Service

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