OSDN Git Service

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