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