1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
32 * Copyright (c) 1996,1997
33 * Silicon Graphics Computer Systems, Inc.
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Silicon Graphics makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
45 * Hewlett-Packard Company
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Hewlett-Packard Company makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
59 * This is an internal header file, included by other library headers.
60 * You should not attempt to use it directly.
68 Red-black tree class, designed for use in implementing STL
69 associative containers (set, multiset, map, and multimap). The
70 insertion and deletion algorithms are based on those in Cormen,
71 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
74 (1) the header cell is maintained with links not only to the root
75 but also to the leftmost node of the tree, to enable constant time
76 begin(), and to the rightmost node of the tree, to enable linear time
77 performance when used with the generic set algorithms (set_union,
80 (2) when a node being deleted has two children its successor node is
81 relinked into its place, rather than copied, so that the only
82 iterators invalidated are those referring to the deleted node.
86 #include <bits/stl_algobase.h>
87 #include <bits/allocator.h>
88 #include <bits/stl_construct.h>
89 #include <bits/stl_function.h>
93 enum _Rb_tree_color
{ _S_red
= false, _S_black
= true };
95 struct _Rb_tree_node_base
97 typedef _Rb_tree_node_base
* _Base_ptr
;
99 _Rb_tree_color _M_color
;
105 _S_minimum(_Base_ptr __x
)
107 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
112 _S_maximum(_Base_ptr __x
)
114 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
119 template<typename _Val
>
120 struct _Rb_tree_node
: public _Rb_tree_node_base
122 typedef _Rb_tree_node
<_Val
>* _Link_type
;
126 struct _Rb_tree_base_iterator
128 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
129 typedef bidirectional_iterator_tag iterator_category
;
130 typedef ptrdiff_t difference_type
;
137 if (_M_node
->_M_right
!= 0)
139 _M_node
= _M_node
->_M_right
;
140 while (_M_node
->_M_left
!= 0)
141 _M_node
= _M_node
->_M_left
;
145 _Base_ptr __y
= _M_node
->_M_parent
;
146 while (_M_node
== __y
->_M_right
)
149 __y
= __y
->_M_parent
;
151 if (_M_node
->_M_right
!= __y
)
159 if (_M_node
->_M_color
== _S_red
160 && _M_node
->_M_parent
->_M_parent
== _M_node
)
161 _M_node
= _M_node
->_M_right
;
162 else if (_M_node
->_M_left
!= 0)
164 _Base_ptr __y
= _M_node
->_M_left
;
165 while (__y
->_M_right
!= 0)
171 _Base_ptr __y
= _M_node
->_M_parent
;
172 while (_M_node
== __y
->_M_left
)
175 __y
= __y
->_M_parent
;
182 template<typename _Val
, typename _Ref
, typename _Ptr
>
183 struct _Rb_tree_iterator
: public _Rb_tree_base_iterator
185 typedef _Val value_type
;
186 typedef _Ref reference
;
187 typedef _Ptr pointer
;
188 typedef _Rb_tree_iterator
<_Val
, _Val
&, _Val
*> iterator
;
189 typedef _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>
191 typedef _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
> _Self
;
192 typedef _Rb_tree_node
<_Val
>* _Link_type
;
194 _Rb_tree_iterator() {}
195 _Rb_tree_iterator(_Rb_tree_node_base
* __x
) { _M_node
= __x
; }
196 _Rb_tree_iterator(const iterator
& __it
) { _M_node
= __it
._M_node
; }
199 operator*() const { return _Link_type(_M_node
)->_M_value_field
; }
202 operator->() const { return &(operator*()); }
220 operator--() { _M_decrement(); return *this; }
231 template<typename _Val
, typename _Ref
, typename _Ptr
>
233 operator==(const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __x
,
234 const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __y
)
235 { return __x
._M_node
== __y
._M_node
; }
237 template<typename _Val
>
239 operator==(const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __x
,
240 const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __y
)
241 { return __x
._M_node
== __y
._M_node
; }
243 template<typename _Val
>
245 operator==(const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __x
,
246 const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __y
)
247 { return __x
._M_node
== __y
._M_node
; }
249 template<typename _Val
, typename _Ref
, typename _Ptr
>
251 operator!=(const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __x
,
252 const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __y
)
253 { return __x
._M_node
!= __y
._M_node
; }
255 template<typename _Val
>
257 operator!=(const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __x
,
258 const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __y
)
259 { return __x
._M_node
!= __y
._M_node
; }
261 template<typename _Val
>
263 operator!=(const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __x
,
264 const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __y
)
265 { return __x
._M_node
!= __y
._M_node
; }
268 _Rb_tree_rotate_left(_Rb_tree_node_base
* __x
, _Rb_tree_node_base
*& __root
)
270 _Rb_tree_node_base
* __y
= __x
->_M_right
;
271 __x
->_M_right
= __y
->_M_left
;
272 if (__y
->_M_left
!=0)
273 __y
->_M_left
->_M_parent
= __x
;
274 __y
->_M_parent
= __x
->_M_parent
;
278 else if (__x
== __x
->_M_parent
->_M_left
)
279 __x
->_M_parent
->_M_left
= __y
;
281 __x
->_M_parent
->_M_right
= __y
;
283 __x
->_M_parent
= __y
;
287 _Rb_tree_rotate_right(_Rb_tree_node_base
* __x
, _Rb_tree_node_base
*& __root
)
289 _Rb_tree_node_base
* __y
= __x
->_M_left
;
290 __x
->_M_left
= __y
->_M_right
;
291 if (__y
->_M_right
!= 0)
292 __y
->_M_right
->_M_parent
= __x
;
293 __y
->_M_parent
= __x
->_M_parent
;
297 else if (__x
== __x
->_M_parent
->_M_right
)
298 __x
->_M_parent
->_M_right
= __y
;
300 __x
->_M_parent
->_M_left
= __y
;
302 __x
->_M_parent
= __y
;
306 _Rb_tree_rebalance(_Rb_tree_node_base
* __x
, _Rb_tree_node_base
*& __root
)
308 __x
->_M_color
= _S_red
;
310 && __x
->_M_parent
->_M_color
== _S_red
)
312 if (__x
->_M_parent
== __x
->_M_parent
->_M_parent
->_M_left
)
314 _Rb_tree_node_base
* __y
= __x
->_M_parent
->_M_parent
->_M_right
;
315 if (__y
&& __y
->_M_color
== _S_red
)
317 __x
->_M_parent
->_M_color
= _S_black
;
318 __y
->_M_color
= _S_black
;
319 __x
->_M_parent
->_M_parent
->_M_color
= _S_red
;
320 __x
= __x
->_M_parent
->_M_parent
;
324 if (__x
== __x
->_M_parent
->_M_right
)
326 __x
= __x
->_M_parent
;
327 _Rb_tree_rotate_left(__x
, __root
);
329 __x
->_M_parent
->_M_color
= _S_black
;
330 __x
->_M_parent
->_M_parent
->_M_color
= _S_red
;
331 _Rb_tree_rotate_right(__x
->_M_parent
->_M_parent
, __root
);
336 _Rb_tree_node_base
* __y
= __x
->_M_parent
->_M_parent
->_M_left
;
337 if (__y
&& __y
->_M_color
== _S_red
)
339 __x
->_M_parent
->_M_color
= _S_black
;
340 __y
->_M_color
= _S_black
;
341 __x
->_M_parent
->_M_parent
->_M_color
= _S_red
;
342 __x
= __x
->_M_parent
->_M_parent
;
346 if (__x
== __x
->_M_parent
->_M_left
)
348 __x
= __x
->_M_parent
;
349 _Rb_tree_rotate_right(__x
, __root
);
351 __x
->_M_parent
->_M_color
= _S_black
;
352 __x
->_M_parent
->_M_parent
->_M_color
= _S_red
;
353 _Rb_tree_rotate_left(__x
->_M_parent
->_M_parent
, __root
);
357 __root
->_M_color
= _S_black
;
360 inline _Rb_tree_node_base
*
361 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* __z
,
362 _Rb_tree_node_base
*& __root
,
363 _Rb_tree_node_base
*& __leftmost
,
364 _Rb_tree_node_base
*& __rightmost
)
366 _Rb_tree_node_base
* __y
= __z
;
367 _Rb_tree_node_base
* __x
= 0;
368 _Rb_tree_node_base
* __x_parent
= 0;
369 if (__y
->_M_left
== 0) // __z has at most one non-null child. y == z.
370 __x
= __y
->_M_right
; // __x might be null.
372 if (__y
->_M_right
== 0) // __z has exactly one non-null child. y == z.
373 __x
= __y
->_M_left
; // __x is not null.
376 // __z has two non-null children. Set __y to
377 __y
= __y
->_M_right
; // __z's successor. __x might be null.
378 while (__y
->_M_left
!= 0)
384 // relink y in place of z. y is z's successor
385 __z
->_M_left
->_M_parent
= __y
;
386 __y
->_M_left
= __z
->_M_left
;
387 if (__y
!= __z
->_M_right
)
389 __x_parent
= __y
->_M_parent
;
390 if (__x
) __x
->_M_parent
= __y
->_M_parent
;
391 __y
->_M_parent
->_M_left
= __x
; // __y must be a child of _M_left
392 __y
->_M_right
= __z
->_M_right
;
393 __z
->_M_right
->_M_parent
= __y
;
399 else if (__z
->_M_parent
->_M_left
== __z
)
400 __z
->_M_parent
->_M_left
= __y
;
402 __z
->_M_parent
->_M_right
= __y
;
403 __y
->_M_parent
= __z
->_M_parent
;
404 std::swap(__y
->_M_color
, __z
->_M_color
);
406 // __y now points to node to be actually deleted
410 __x_parent
= __y
->_M_parent
;
412 __x
->_M_parent
= __y
->_M_parent
;
416 if (__z
->_M_parent
->_M_left
== __z
)
417 __z
->_M_parent
->_M_left
= __x
;
419 __z
->_M_parent
->_M_right
= __x
;
420 if (__leftmost
== __z
)
421 if (__z
->_M_right
== 0) // __z->_M_left must be null also
422 __leftmost
= __z
->_M_parent
;
423 // makes __leftmost == _M_header if __z == __root
425 __leftmost
= _Rb_tree_node_base::_S_minimum(__x
);
426 if (__rightmost
== __z
)
427 if (__z
->_M_left
== 0) // __z->_M_right must be null also
428 __rightmost
= __z
->_M_parent
;
429 // makes __rightmost == _M_header if __z == __root
430 else // __x == __z->_M_left
431 __rightmost
= _Rb_tree_node_base::_S_maximum(__x
);
433 if (__y
->_M_color
!= _S_red
)
435 while (__x
!= __root
&& (__x
== 0 || __x
->_M_color
== _S_black
))
436 if (__x
== __x_parent
->_M_left
)
438 _Rb_tree_node_base
* __w
= __x_parent
->_M_right
;
439 if (__w
->_M_color
== _S_red
)
441 __w
->_M_color
= _S_black
;
442 __x_parent
->_M_color
= _S_red
;
443 _Rb_tree_rotate_left(__x_parent
, __root
);
444 __w
= __x_parent
->_M_right
;
446 if ((__w
->_M_left
== 0 ||
447 __w
->_M_left
->_M_color
== _S_black
) &&
448 (__w
->_M_right
== 0 ||
449 __w
->_M_right
->_M_color
== _S_black
))
451 __w
->_M_color
= _S_red
;
453 __x_parent
= __x_parent
->_M_parent
;
457 if (__w
->_M_right
== 0
458 || __w
->_M_right
->_M_color
== _S_black
)
460 __w
->_M_left
->_M_color
= _S_black
;
461 __w
->_M_color
= _S_red
;
462 _Rb_tree_rotate_right(__w
, __root
);
463 __w
= __x_parent
->_M_right
;
465 __w
->_M_color
= __x_parent
->_M_color
;
466 __x_parent
->_M_color
= _S_black
;
468 __w
->_M_right
->_M_color
= _S_black
;
469 _Rb_tree_rotate_left(__x_parent
, __root
);
475 // same as above, with _M_right <-> _M_left.
476 _Rb_tree_node_base
* __w
= __x_parent
->_M_left
;
477 if (__w
->_M_color
== _S_red
)
479 __w
->_M_color
= _S_black
;
480 __x_parent
->_M_color
= _S_red
;
481 _Rb_tree_rotate_right(__x_parent
, __root
);
482 __w
= __x_parent
->_M_left
;
484 if ((__w
->_M_right
== 0 ||
485 __w
->_M_right
->_M_color
== _S_black
) &&
486 (__w
->_M_left
== 0 ||
487 __w
->_M_left
->_M_color
== _S_black
))
489 __w
->_M_color
= _S_red
;
491 __x_parent
= __x_parent
->_M_parent
;
495 if (__w
->_M_left
== 0 || __w
->_M_left
->_M_color
== _S_black
)
497 __w
->_M_right
->_M_color
= _S_black
;
498 __w
->_M_color
= _S_red
;
499 _Rb_tree_rotate_left(__w
, __root
);
500 __w
= __x_parent
->_M_left
;
502 __w
->_M_color
= __x_parent
->_M_color
;
503 __x_parent
->_M_color
= _S_black
;
505 __w
->_M_left
->_M_color
= _S_black
;
506 _Rb_tree_rotate_right(__x_parent
, __root
);
510 if (__x
) __x
->_M_color
= _S_black
;
515 // Base class to encapsulate the differences between old SGI-style
516 // allocators and standard-conforming allocators. In order to avoid
517 // having an empty base class, we arbitrarily move one of rb_tree's
518 // data members into the base class.
520 // _Base for general standard-conforming allocators.
521 template<typename _Tp
, typename _Alloc
, bool _S_instanceless
>
522 class _Rb_tree_alloc_base
525 typedef typename _Alloc_traits
<_Tp
, _Alloc
>::allocator_type allocator_type
;
528 get_allocator() const { return _M_node_allocator
; }
530 _Rb_tree_alloc_base(const allocator_type
& __a
)
531 : _M_node_allocator(__a
) {}
534 typename _Alloc_traits
<_Rb_tree_node
<_Tp
>, _Alloc
>::allocator_type
537 _Rb_tree_node_base _M_header
;
540 _M_get_node() { return _M_node_allocator
.allocate(1); }
543 _M_put_node(_Rb_tree_node
<_Tp
>* __p
)
544 { _M_node_allocator
.deallocate(__p
, 1); }
547 // Specialization for instanceless allocators.
548 template<typename _Tp
, typename _Alloc
>
549 class _Rb_tree_alloc_base
<_Tp
, _Alloc
, true>
552 typedef typename _Alloc_traits
<_Tp
, _Alloc
>::allocator_type allocator_type
;
553 allocator_type
get_allocator() const { return allocator_type(); }
555 _Rb_tree_alloc_base(const allocator_type
&) {}
558 _Rb_tree_node_base _M_header
;
560 typedef typename _Alloc_traits
<_Rb_tree_node
<_Tp
>, _Alloc
>::_Alloc_type
564 _M_get_node() { return _Alloc_type::allocate(1); }
567 _M_put_node(_Rb_tree_node
<_Tp
>* __p
) { _Alloc_type::deallocate(__p
, 1); }
570 template<typename _Tp
, typename _Alloc
>
571 struct _Rb_tree_base
: public _Rb_tree_alloc_base
<_Tp
, _Alloc
,
572 _Alloc_traits
<_Tp
, _Alloc
>::_S_instanceless
>
574 typedef _Rb_tree_alloc_base
<_Tp
,
575 _Alloc
, _Alloc_traits
<_Tp
, _Alloc
>::_S_instanceless
> _Base
;
576 typedef typename
_Base::allocator_type allocator_type
;
578 _Rb_tree_base(const allocator_type
& __a
)
583 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
584 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
585 class _Rb_tree
: protected _Rb_tree_base
<_Val
, _Alloc
>
587 typedef _Rb_tree_base
<_Val
, _Alloc
> _Base
;
590 typedef _Rb_tree_node_base
* _Base_ptr
;
591 typedef _Rb_tree_node
<_Val
> _Rb_tree_node
;
594 typedef _Key key_type
;
595 typedef _Val value_type
;
596 typedef value_type
* pointer
;
597 typedef const value_type
* const_pointer
;
598 typedef value_type
& reference
;
599 typedef const value_type
& const_reference
;
600 typedef _Rb_tree_node
* _Link_type
;
601 typedef size_t size_type
;
602 typedef ptrdiff_t difference_type
;
604 typedef typename
_Base::allocator_type allocator_type
;
605 allocator_type
get_allocator() const { return _Base::get_allocator(); }
608 using _Base::_M_get_node
;
609 using _Base::_M_put_node
;
610 using _Base::_M_header
;
613 _M_create_node(const value_type
& __x
)
615 _Link_type __tmp
= _M_get_node();
617 { std::_Construct(&__tmp
->_M_value_field
, __x
); }
621 __throw_exception_again
;
627 _M_clone_node(_Link_type __x
)
629 _Link_type __tmp
= _M_create_node(__x
->_M_value_field
);
630 __tmp
->_M_color
= __x
->_M_color
;
637 destroy_node(_Link_type __p
)
639 std::_Destroy(&__p
->_M_value_field
);
643 size_type _M_node_count
; // keeps track of size of tree
644 _Compare _M_key_compare
;
647 _M_root() const { return (_Link_type
&) this->_M_header
._M_parent
; }
650 _M_leftmost() const { return (_Link_type
&) this->_M_header
._M_left
; }
653 _M_rightmost() const { return (_Link_type
&) this->_M_header
._M_right
; }
656 _M_end() const { return (_Link_type
) &this->_M_header
; }
659 _S_left(_Link_type __x
) { return (_Link_type
&)(__x
->_M_left
); }
662 _S_right(_Link_type __x
) { return (_Link_type
&)(__x
->_M_right
); }
665 _S_parent(_Link_type __x
) { return (_Link_type
&)(__x
->_M_parent
); }
668 _S_value(_Link_type __x
) { return __x
->_M_value_field
; }
671 _S_key(_Link_type __x
) { return _KeyOfValue()(_S_value(__x
)); }
674 _S_left(_Base_ptr __x
) { return (_Link_type
&)(__x
->_M_left
); }
677 _S_right(_Base_ptr __x
) { return (_Link_type
&)(__x
->_M_right
); }
680 _S_parent(_Base_ptr __x
) { return (_Link_type
&)(__x
->_M_parent
); }
683 _S_value(_Base_ptr __x
) { return ((_Link_type
)__x
)->_M_value_field
; }
686 _S_key(_Base_ptr __x
) { return _KeyOfValue()(_S_value(_Link_type(__x
)));}
688 static _Rb_tree_color
&
689 _S_color(_Base_ptr __x
) { return __x
->_M_color
; }
692 _S_minimum(_Link_type __x
)
693 { return (_Link_type
) _Rb_tree_node_base::_S_minimum(__x
); }
696 _S_maximum(_Link_type __x
)
697 { return (_Link_type
) _Rb_tree_node_base::_S_maximum(__x
); }
700 typedef _Rb_tree_iterator
<value_type
, reference
, pointer
> iterator
;
701 typedef _Rb_tree_iterator
<value_type
, const_reference
, const_pointer
>
704 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
705 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
709 _M_insert(_Base_ptr __x
, _Base_ptr __y
, const value_type
& __v
);
712 _M_copy(_Link_type __x
, _Link_type __p
);
715 _M_erase(_Link_type __x
);
718 // allocation/deallocation
720 : _Base(allocator_type()), _M_node_count(0), _M_key_compare()
721 { _M_empty_initialize(); }
723 _Rb_tree(const _Compare
& __comp
)
724 : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp
)
725 { _M_empty_initialize(); }
727 _Rb_tree(const _Compare
& __comp
, const allocator_type
& __a
)
728 : _Base(__a
), _M_node_count(0), _M_key_compare(__comp
)
729 { _M_empty_initialize(); }
731 _Rb_tree(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
)
732 : _Base(__x
.get_allocator()), _M_node_count(0),
733 _M_key_compare(__x
._M_key_compare
)
735 if (__x
._M_root() == 0)
736 _M_empty_initialize();
739 _S_color(&this->_M_header
) = _S_red
;
740 _M_root() = _M_copy(__x
._M_root(), _M_end());
741 _M_leftmost() = _S_minimum(_M_root());
742 _M_rightmost() = _S_maximum(_M_root());
744 _M_node_count
= __x
._M_node_count
;
747 ~_Rb_tree() { clear(); }
749 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>&
750 operator=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
);
753 void _M_empty_initialize()
755 // Used to distinguish header from __root, in iterator.operator++.
756 _S_color(&this->_M_header
) = _S_red
;
758 _M_leftmost() = _M_end();
759 _M_rightmost() = _M_end();
765 key_comp() const { return _M_key_compare
; }
768 begin() { return _M_leftmost(); }
771 begin() const { return _M_leftmost(); }
774 end() { return &this->_M_header
; }
777 end() const { return const_cast<_Base_ptr
>(&this->_M_header
); }
780 rbegin() { return reverse_iterator(end()); }
782 const_reverse_iterator
783 rbegin() const { return const_reverse_iterator(end()); }
786 rend() { return reverse_iterator(begin()); }
788 const_reverse_iterator
789 rend() const { return const_reverse_iterator(begin()); }
792 empty() const { return _M_node_count
== 0; }
795 size() const { return _M_node_count
; }
798 max_size() const { return size_type(-1); }
801 swap(_Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __t
);
805 insert_unique(const value_type
& __x
);
808 insert_equal(const value_type
& __x
);
811 insert_unique(iterator __position
, const value_type
& __x
);
814 insert_equal(iterator __position
, const value_type
& __x
);
816 template<typename _InputIterator
>
818 insert_unique(_InputIterator __first
, _InputIterator __last
);
820 template<typename _InputIterator
>
822 insert_equal(_InputIterator __first
, _InputIterator __last
);
825 erase(iterator __position
);
828 erase(const key_type
& __x
);
831 erase(iterator __first
, iterator __last
);
834 erase(const key_type
* __first
, const key_type
* __last
);
839 if (_M_node_count
!= 0)
842 _M_leftmost() = _M_end();
844 _M_rightmost() = _M_end();
851 find(const key_type
& __x
);
854 find(const key_type
& __x
) const;
857 count(const key_type
& __x
) const;
860 lower_bound(const key_type
& __x
);
863 lower_bound(const key_type
& __x
) const;
866 upper_bound(const key_type
& __x
);
869 upper_bound(const key_type
& __x
) const;
871 pair
<iterator
,iterator
>
872 equal_range(const key_type
& __x
);
874 pair
<const_iterator
, const_iterator
>
875 equal_range(const key_type
& __x
) const;
882 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
883 typename _Compare
, typename _Alloc
>
885 operator==(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
886 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
888 return __x
.size() == __y
.size() &&
889 equal(__x
.begin(), __x
.end(), __y
.begin());
892 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
893 typename _Compare
, typename _Alloc
>
895 operator<(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
896 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
898 return lexicographical_compare(__x
.begin(), __x
.end(),
899 __y
.begin(), __y
.end());
902 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
903 typename _Compare
, typename _Alloc
>
905 operator!=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
906 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
907 { return !(__x
== __y
); }
909 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
910 typename _Compare
, typename _Alloc
>
912 operator>(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
913 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
914 { return __y
< __x
; }
916 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
917 typename _Compare
, typename _Alloc
>
919 operator<=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
920 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
921 { return !(__y
< __x
); }
923 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
924 typename _Compare
, typename _Alloc
>
926 operator>=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
927 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
928 { return !(__x
< __y
); }
930 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
931 typename _Compare
, typename _Alloc
>
933 swap(_Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
934 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
937 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
938 typename _Compare
, typename _Alloc
>
939 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>&
940 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
941 operator=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
)
945 // Note that _Key may be a constant type.
948 _M_key_compare
= __x
._M_key_compare
;
949 if (__x
._M_root() == 0)
952 _M_leftmost() = _M_end();
953 _M_rightmost() = _M_end();
957 _M_root() = _M_copy(__x
._M_root(), _M_end());
958 _M_leftmost() = _S_minimum(_M_root());
959 _M_rightmost() = _S_maximum(_M_root());
960 _M_node_count
= __x
._M_node_count
;
966 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
967 typename _Compare
, typename _Alloc
>
968 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
969 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
970 _M_insert(_Base_ptr __x_
, _Base_ptr __y_
, const _Val
& __v
)
972 _Link_type __x
= (_Link_type
) __x_
;
973 _Link_type __y
= (_Link_type
) __y_
;
976 if (__y
== &this->_M_header
|| __x
!= 0 ||
977 _M_key_compare(_KeyOfValue()(__v
), _S_key(__y
)))
979 __z
= _M_create_node(__v
);
980 _S_left(__y
) = __z
; // also makes _M_leftmost() = __z
981 // when __y == &_M_header
982 if (__y
== &this->_M_header
)
985 _M_rightmost() = __z
;
987 else if (__y
== _M_leftmost())
988 _M_leftmost() = __z
; // maintain _M_leftmost() pointing to min node
992 __z
= _M_create_node(__v
);
994 // Maintain _M_rightmost() pointing to max node.
995 if (__y
== _M_rightmost())
996 _M_rightmost() = __z
;
998 _S_parent(__z
) = __y
;
1001 _Rb_tree_rebalance(__z
, this->_M_header
._M_parent
);
1003 return iterator(__z
);
1006 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1007 typename _Compare
, typename _Alloc
>
1008 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1009 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1010 insert_equal(const _Val
& __v
)
1012 _Link_type __y
= _M_end();
1013 _Link_type __x
= _M_root();
1017 __x
= _M_key_compare(_KeyOfValue()(__v
), _S_key(__x
)) ?
1018 _S_left(__x
) : _S_right(__x
);
1020 return _M_insert(__x
, __y
, __v
);
1023 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1024 typename _Compare
, typename _Alloc
>
1026 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1027 swap(_Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __t
)
1031 if (__t
._M_root() != 0)
1033 _M_root() = __t
._M_root();
1034 _M_leftmost() = __t
._M_leftmost();
1035 _M_rightmost() = __t
._M_rightmost();
1036 _M_root()->_M_parent
= _M_end();
1039 __t
._M_leftmost() = __t
._M_end();
1040 __t
._M_rightmost() = __t
._M_end();
1043 else if (__t
._M_root() == 0)
1045 __t
._M_root() = _M_root();
1046 __t
._M_leftmost() = _M_leftmost();
1047 __t
._M_rightmost() = _M_rightmost();
1048 __t
._M_root()->_M_parent
= __t
._M_end();
1051 _M_leftmost() = _M_end();
1052 _M_rightmost() = _M_end();
1056 std::swap(_M_root(),__t
._M_root());
1057 std::swap(_M_leftmost(),__t
._M_leftmost());
1058 std::swap(_M_rightmost(),__t
._M_rightmost());
1060 _M_root()->_M_parent
= _M_end();
1061 __t
._M_root()->_M_parent
= __t
._M_end();
1063 // No need to swap header's color as it does not change.
1064 std::swap(this->_M_node_count
, __t
._M_node_count
);
1065 std::swap(this->_M_key_compare
, __t
._M_key_compare
);
1068 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1069 typename _Compare
, typename _Alloc
>
1070 pair
<typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
,
1072 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1073 insert_unique(const _Val
& __v
)
1075 _Link_type __y
= _M_end();
1076 _Link_type __x
= _M_root();
1081 __comp
= _M_key_compare(_KeyOfValue()(__v
), _S_key(__x
));
1082 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
1084 iterator __j
= iterator(__y
);
1087 return pair
<iterator
,bool>(_M_insert(__x
, __y
, __v
), true);
1090 if (_M_key_compare(_S_key(__j
._M_node
), _KeyOfValue()(__v
)))
1091 return pair
<iterator
,bool>(_M_insert(__x
, __y
, __v
), true);
1092 return pair
<iterator
,bool>(__j
, false);
1096 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1097 typename _Compare
, typename _Alloc
>
1098 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1099 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1100 insert_unique(iterator __position
, const _Val
& __v
)
1102 if (__position
._M_node
== this->_M_header
._M_left
)
1106 _M_key_compare(_KeyOfValue()(__v
), _S_key(__position
._M_node
)))
1107 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
1108 // first argument just needs to be non-null
1110 return insert_unique(__v
).first
;
1112 else if (__position
._M_node
== &this->_M_header
)
1115 if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v
)))
1116 return _M_insert(0, _M_rightmost(), __v
);
1118 return insert_unique(__v
).first
;
1122 iterator __before
= __position
;
1124 if (_M_key_compare(_S_key(__before
._M_node
), _KeyOfValue()(__v
))
1125 && _M_key_compare(_KeyOfValue()(__v
),_S_key(__position
._M_node
)))
1127 if (_S_right(__before
._M_node
) == 0)
1128 return _M_insert(0, __before
._M_node
, __v
);
1130 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
1131 // first argument just needs to be non-null
1134 return insert_unique(__v
).first
;
1138 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1139 typename _Compare
, typename _Alloc
>
1140 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1141 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1142 insert_equal(iterator __position
, const _Val
& __v
)
1144 if (__position
._M_node
== this->_M_header
._M_left
)
1148 !_M_key_compare(_S_key(__position
._M_node
), _KeyOfValue()(__v
)))
1149 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
1150 // first argument just needs to be non-null
1152 return insert_equal(__v
);
1154 else if (__position
._M_node
== &this->_M_header
)
1157 if (!_M_key_compare(_KeyOfValue()(__v
), _S_key(_M_rightmost())))
1158 return _M_insert(0, _M_rightmost(), __v
);
1160 return insert_equal(__v
);
1164 iterator __before
= __position
;
1166 if (!_M_key_compare(_KeyOfValue()(__v
), _S_key(__before
._M_node
))
1167 && !_M_key_compare(_S_key(__position
._M_node
),
1168 _KeyOfValue()(__v
)))
1170 if (_S_right(__before
._M_node
) == 0)
1171 return _M_insert(0, __before
._M_node
, __v
);
1173 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
1174 // first argument just needs to be non-null
1177 return insert_equal(__v
);
1181 template<typename _Key
, typename _Val
, typename _KoV
,
1182 typename _Cmp
, typename _Alloc
>
1185 _Rb_tree
<_Key
,_Val
,_KoV
,_Cmp
,_Alloc
>::
1186 insert_equal(_II __first
, _II __last
)
1188 for ( ; __first
!= __last
; ++__first
)
1189 insert_equal(*__first
);
1192 template<typename _Key
, typename _Val
, typename _KoV
,
1193 typename _Cmp
, typename _Alloc
>
1196 _Rb_tree
<_Key
,_Val
,_KoV
,_Cmp
,_Alloc
>::
1197 insert_unique(_II __first
, _II __last
)
1199 for ( ; __first
!= __last
; ++__first
)
1200 insert_unique(*__first
);
1203 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1204 typename _Compare
, typename _Alloc
>
1206 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::erase(iterator __position
)
1209 (_Link_type
) _Rb_tree_rebalance_for_erase(__position
._M_node
,
1210 this->_M_header
._M_parent
,
1211 this->_M_header
._M_left
,
1212 this->_M_header
._M_right
);
1217 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1218 typename _Compare
, typename _Alloc
>
1219 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::size_type
1220 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::erase(const _Key
& __x
)
1222 pair
<iterator
,iterator
> __p
= equal_range(__x
);
1223 size_type __n
= std::distance(__p
.first
, __p
.second
);
1224 erase(__p
.first
, __p
.second
);
1228 template<typename _Key
, typename _Val
, typename _KoV
,
1229 typename _Compare
, typename _Alloc
>
1230 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1231 _Rb_tree
<_Key
,_Val
,_KoV
,_Compare
,_Alloc
>::
1232 _M_copy(_Link_type __x
, _Link_type __p
)
1234 // Structural copy. __x and __p must be non-null.
1235 _Link_type __top
= _M_clone_node(__x
);
1236 __top
->_M_parent
= __p
;
1241 __top
->_M_right
= _M_copy(_S_right(__x
), __top
);
1247 _Link_type __y
= _M_clone_node(__x
);
1249 __y
->_M_parent
= __p
;
1251 __y
->_M_right
= _M_copy(_S_right(__x
), __y
);
1259 __throw_exception_again
;
1264 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1265 typename _Compare
, typename _Alloc
>
1267 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::_M_erase(_Link_type __x
)
1269 // Erase without rebalancing.
1272 _M_erase(_S_right(__x
));
1273 _Link_type __y
= _S_left(__x
);
1279 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1280 typename _Compare
, typename _Alloc
>
1282 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1283 erase(iterator __first
, iterator __last
)
1285 if (__first
== begin() && __last
== end())
1288 while (__first
!= __last
) erase(__first
++);
1291 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1292 typename _Compare
, typename _Alloc
>
1294 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1295 erase(const _Key
* __first
, const _Key
* __last
)
1297 while (__first
!= __last
)
1301 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1302 typename _Compare
, typename _Alloc
>
1303 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1304 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::find(const _Key
& __k
)
1306 _Link_type __y
= _M_end(); // Last node which is not less than __k.
1307 _Link_type __x
= _M_root(); // Current node.
1310 if (!_M_key_compare(_S_key(__x
), __k
))
1311 __y
= __x
, __x
= _S_left(__x
);
1313 __x
= _S_right(__x
);
1315 iterator __j
= iterator(__y
);
1316 return (__j
== end() || _M_key_compare(__k
, _S_key(__j
._M_node
))) ?
1320 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1321 typename _Compare
, typename _Alloc
>
1322 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1323 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1324 find(const _Key
& __k
) const
1326 _Link_type __y
= _M_end(); // Last node which is not less than __k.
1327 _Link_type __x
= _M_root(); // Current node.
1331 if (!_M_key_compare(_S_key(__x
), __k
))
1332 __y
= __x
, __x
= _S_left(__x
);
1334 __x
= _S_right(__x
);
1336 const_iterator __j
= const_iterator(__y
);
1337 return (__j
== end() || _M_key_compare(__k
, _S_key(__j
._M_node
))) ?
1341 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1342 typename _Compare
, typename _Alloc
>
1343 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::size_type
1344 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1345 count(const _Key
& __k
) const
1347 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
1348 size_type __n
= std::distance(__p
.first
, __p
.second
);
1352 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1353 typename _Compare
, typename _Alloc
>
1354 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1355 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1356 lower_bound(const _Key
& __k
)
1358 _Link_type __y
= _M_end(); // Last node which is not less than __k
1359 _Link_type __x
= _M_root(); // Current node.
1362 if (!_M_key_compare(_S_key(__x
), __k
))
1363 __y
= __x
, __x
= _S_left(__x
);
1365 __x
= _S_right(__x
);
1367 return iterator(__y
);
1370 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1371 typename _Compare
, typename _Alloc
>
1372 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1373 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1374 lower_bound(const _Key
& __k
) const
1376 _Link_type __y
= _M_end(); // Last node which is not less than __k.
1377 _Link_type __x
= _M_root(); // Current node.
1380 if (!_M_key_compare(_S_key(__x
), __k
))
1381 __y
= __x
, __x
= _S_left(__x
);
1383 __x
= _S_right(__x
);
1385 return const_iterator(__y
);
1388 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1389 typename _Compare
, typename _Alloc
>
1390 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1391 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1392 upper_bound(const _Key
& __k
)
1394 _Link_type __y
= _M_end(); // Last node which is greater than __k.
1395 _Link_type __x
= _M_root(); // Current node.
1398 if (_M_key_compare(__k
, _S_key(__x
)))
1399 __y
= __x
, __x
= _S_left(__x
);
1401 __x
= _S_right(__x
);
1403 return iterator(__y
);
1406 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1407 typename _Compare
, typename _Alloc
>
1408 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1409 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1410 upper_bound(const _Key
& __k
) const
1412 _Link_type __y
= _M_end(); // Last node which is greater than __k.
1413 _Link_type __x
= _M_root(); // Current node.
1416 if (_M_key_compare(__k
, _S_key(__x
)))
1417 __y
= __x
, __x
= _S_left(__x
);
1419 __x
= _S_right(__x
);
1421 return const_iterator(__y
);
1424 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1425 typename _Compare
, typename _Alloc
>
1427 pair
<typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
,
1428 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
>
1429 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1430 equal_range(const _Key
& __k
)
1431 { return pair
<iterator
, iterator
>(lower_bound(__k
), upper_bound(__k
)); }
1433 template<typename _Key
, typename _Val
, typename _KoV
,
1434 typename _Compare
, typename _Alloc
>
1436 pair
<typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::const_iterator
,
1437 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::const_iterator
>
1438 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>
1439 ::equal_range(const _Key
& __k
) const
1441 return pair
<const_iterator
,const_iterator
>(lower_bound(__k
),
1446 __black_count(_Rb_tree_node_base
* __node
, _Rb_tree_node_base
* __root
)
1453 if (__node
->_M_color
== _S_black
)
1455 if (__node
== __root
)
1457 __node
= __node
->_M_parent
;
1463 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1464 typename _Compare
, typename _Alloc
>
1466 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
1468 if (_M_node_count
== 0 || begin() == end())
1469 return _M_node_count
== 0 && begin() == end() &&
1470 this->_M_header
._M_left
== &this->_M_header
&&
1471 this->_M_header
._M_right
== &this->_M_header
;
1473 int __len
= __black_count(_M_leftmost(), _M_root());
1474 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
1476 _Link_type __x
= (_Link_type
) __it
._M_node
;
1477 _Link_type __L
= _S_left(__x
);
1478 _Link_type __R
= _S_right(__x
);
1480 if (__x
->_M_color
== _S_red
)
1481 if ((__L
&& __L
->_M_color
== _S_red
)
1482 || (__R
&& __R
->_M_color
== _S_red
))
1485 if (__L
&& _M_key_compare(_S_key(__x
), _S_key(__L
)))
1487 if (__R
&& _M_key_compare(_S_key(__R
), _S_key(__x
)))
1490 if (!__L
&& !__R
&& __black_count(__x
, _M_root()) != __len
)
1494 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1496 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))