1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001 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.
63 #ifndef __GLIBCPP_INTERNAL_TREE_H
64 #define __GLIBCPP_INTERNAL_TREE_H
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/stl_alloc.h>
88 #include <bits/stl_construct.h>
89 #include <bits/stl_function.h>
94 typedef bool _Rb_tree_Color_type
;
95 const _Rb_tree_Color_type _S_rb_tree_red
= false;
96 const _Rb_tree_Color_type _S_rb_tree_black
= true;
98 struct _Rb_tree_node_base
100 typedef _Rb_tree_Color_type _Color_type
;
101 typedef _Rb_tree_node_base
* _Base_ptr
;
103 _Color_type _M_color
;
108 static _Base_ptr
_S_minimum(_Base_ptr __x
)
110 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
114 static _Base_ptr
_S_maximum(_Base_ptr __x
)
116 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
121 template <class _Value
>
122 struct _Rb_tree_node
: public _Rb_tree_node_base
124 typedef _Rb_tree_node
<_Value
>* _Link_type
;
125 _Value _M_value_field
;
129 struct _Rb_tree_base_iterator
131 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
132 typedef bidirectional_iterator_tag iterator_category
;
133 typedef ptrdiff_t difference_type
;
138 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
;
144 _Base_ptr __y
= _M_node
->_M_parent
;
145 while (_M_node
== __y
->_M_right
) {
147 __y
= __y
->_M_parent
;
149 if (_M_node
->_M_right
!= __y
)
156 if (_M_node
->_M_color
== _S_rb_tree_red
&&
157 _M_node
->_M_parent
->_M_parent
== _M_node
)
158 _M_node
= _M_node
->_M_right
;
159 else if (_M_node
->_M_left
!= 0) {
160 _Base_ptr __y
= _M_node
->_M_left
;
161 while (__y
->_M_right
!= 0)
166 _Base_ptr __y
= _M_node
->_M_parent
;
167 while (_M_node
== __y
->_M_left
) {
169 __y
= __y
->_M_parent
;
176 template <class _Value
, class _Ref
, class _Ptr
>
177 struct _Rb_tree_iterator
: public _Rb_tree_base_iterator
179 typedef _Value value_type
;
180 typedef _Ref reference
;
181 typedef _Ptr pointer
;
182 typedef _Rb_tree_iterator
<_Value
, _Value
&, _Value
*>
184 typedef _Rb_tree_iterator
<_Value
, const _Value
&, const _Value
*>
186 typedef _Rb_tree_iterator
<_Value
, _Ref
, _Ptr
>
188 typedef _Rb_tree_node
<_Value
>* _Link_type
;
190 _Rb_tree_iterator() {}
191 _Rb_tree_iterator(_Link_type __x
) { _M_node
= __x
; }
192 _Rb_tree_iterator(const iterator
& __it
) { _M_node
= __it
._M_node
; }
194 reference
operator*() const { return _Link_type(_M_node
)->_M_value_field
; }
195 pointer
operator->() const { return &(operator*()); }
197 _Self
& operator++() { _M_increment(); return *this; }
198 _Self
operator++(int) {
204 _Self
& operator--() { _M_decrement(); return *this; }
205 _Self
operator--(int) {
212 template <class _Value
, class _Ref
, class _Ptr
>
213 inline bool operator==(const _Rb_tree_iterator
<_Value
, _Ref
, _Ptr
>& __x
,
214 const _Rb_tree_iterator
<_Value
, _Ref
, _Ptr
>& __y
) {
215 return __x
._M_node
== __y
._M_node
;
218 template <class _Value
>
219 inline bool operator==(const _Rb_tree_iterator
<_Value
, const _Value
&, const _Value
*>& __x
,
220 const _Rb_tree_iterator
<_Value
, _Value
&, _Value
*>& __y
) {
221 return __x
._M_node
== __y
._M_node
;
224 template <class _Value
>
225 inline bool operator==(const _Rb_tree_iterator
<_Value
, _Value
&, _Value
*>& __x
,
226 const _Rb_tree_iterator
<_Value
, const _Value
&, const _Value
*>& __y
) {
227 return __x
._M_node
== __y
._M_node
;
230 template <class _Value
, class _Ref
, class _Ptr
>
231 inline bool operator!=(const _Rb_tree_iterator
<_Value
, _Ref
, _Ptr
>& __x
,
232 const _Rb_tree_iterator
<_Value
, _Ref
, _Ptr
>& __y
) {
233 return __x
._M_node
!= __y
._M_node
;
236 template <class _Value
>
237 inline bool operator!=(const _Rb_tree_iterator
<_Value
, const _Value
&, const _Value
*>& __x
,
238 const _Rb_tree_iterator
<_Value
, _Value
&, _Value
*>& __y
) {
239 return __x
._M_node
!= __y
._M_node
;
242 template <class _Value
>
243 inline bool operator!=(const _Rb_tree_iterator
<_Value
, _Value
&, _Value
*>& __x
,
244 const _Rb_tree_iterator
<_Value
, const _Value
&, const _Value
*>& __y
) {
245 return __x
._M_node
!= __y
._M_node
;
249 _Rb_tree_rotate_left(_Rb_tree_node_base
* __x
, _Rb_tree_node_base
*& __root
)
251 _Rb_tree_node_base
* __y
= __x
->_M_right
;
252 __x
->_M_right
= __y
->_M_left
;
253 if (__y
->_M_left
!=0)
254 __y
->_M_left
->_M_parent
= __x
;
255 __y
->_M_parent
= __x
->_M_parent
;
259 else if (__x
== __x
->_M_parent
->_M_left
)
260 __x
->_M_parent
->_M_left
= __y
;
262 __x
->_M_parent
->_M_right
= __y
;
264 __x
->_M_parent
= __y
;
268 _Rb_tree_rotate_right(_Rb_tree_node_base
* __x
, _Rb_tree_node_base
*& __root
)
270 _Rb_tree_node_base
* __y
= __x
->_M_left
;
271 __x
->_M_left
= __y
->_M_right
;
272 if (__y
->_M_right
!= 0)
273 __y
->_M_right
->_M_parent
= __x
;
274 __y
->_M_parent
= __x
->_M_parent
;
278 else if (__x
== __x
->_M_parent
->_M_right
)
279 __x
->_M_parent
->_M_right
= __y
;
281 __x
->_M_parent
->_M_left
= __y
;
283 __x
->_M_parent
= __y
;
287 _Rb_tree_rebalance(_Rb_tree_node_base
* __x
, _Rb_tree_node_base
*& __root
)
289 __x
->_M_color
= _S_rb_tree_red
;
290 while (__x
!= __root
&& __x
->_M_parent
->_M_color
== _S_rb_tree_red
) {
291 if (__x
->_M_parent
== __x
->_M_parent
->_M_parent
->_M_left
) {
292 _Rb_tree_node_base
* __y
= __x
->_M_parent
->_M_parent
->_M_right
;
293 if (__y
&& __y
->_M_color
== _S_rb_tree_red
) {
294 __x
->_M_parent
->_M_color
= _S_rb_tree_black
;
295 __y
->_M_color
= _S_rb_tree_black
;
296 __x
->_M_parent
->_M_parent
->_M_color
= _S_rb_tree_red
;
297 __x
= __x
->_M_parent
->_M_parent
;
300 if (__x
== __x
->_M_parent
->_M_right
) {
301 __x
= __x
->_M_parent
;
302 _Rb_tree_rotate_left(__x
, __root
);
304 __x
->_M_parent
->_M_color
= _S_rb_tree_black
;
305 __x
->_M_parent
->_M_parent
->_M_color
= _S_rb_tree_red
;
306 _Rb_tree_rotate_right(__x
->_M_parent
->_M_parent
, __root
);
310 _Rb_tree_node_base
* __y
= __x
->_M_parent
->_M_parent
->_M_left
;
311 if (__y
&& __y
->_M_color
== _S_rb_tree_red
) {
312 __x
->_M_parent
->_M_color
= _S_rb_tree_black
;
313 __y
->_M_color
= _S_rb_tree_black
;
314 __x
->_M_parent
->_M_parent
->_M_color
= _S_rb_tree_red
;
315 __x
= __x
->_M_parent
->_M_parent
;
318 if (__x
== __x
->_M_parent
->_M_left
) {
319 __x
= __x
->_M_parent
;
320 _Rb_tree_rotate_right(__x
, __root
);
322 __x
->_M_parent
->_M_color
= _S_rb_tree_black
;
323 __x
->_M_parent
->_M_parent
->_M_color
= _S_rb_tree_red
;
324 _Rb_tree_rotate_left(__x
->_M_parent
->_M_parent
, __root
);
328 __root
->_M_color
= _S_rb_tree_black
;
331 inline _Rb_tree_node_base
*
332 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* __z
,
333 _Rb_tree_node_base
*& __root
,
334 _Rb_tree_node_base
*& __leftmost
,
335 _Rb_tree_node_base
*& __rightmost
)
337 _Rb_tree_node_base
* __y
= __z
;
338 _Rb_tree_node_base
* __x
= 0;
339 _Rb_tree_node_base
* __x_parent
= 0;
340 if (__y
->_M_left
== 0) // __z has at most one non-null child. y == z.
341 __x
= __y
->_M_right
; // __x might be null.
343 if (__y
->_M_right
== 0) // __z has exactly one non-null child. y == z.
344 __x
= __y
->_M_left
; // __x is not null.
345 else { // __z has two non-null children. Set __y to
346 __y
= __y
->_M_right
; // __z's successor. __x might be null.
347 while (__y
->_M_left
!= 0)
351 if (__y
!= __z
) { // relink y in place of z. y is z's successor
352 __z
->_M_left
->_M_parent
= __y
;
353 __y
->_M_left
= __z
->_M_left
;
354 if (__y
!= __z
->_M_right
) {
355 __x_parent
= __y
->_M_parent
;
356 if (__x
) __x
->_M_parent
= __y
->_M_parent
;
357 __y
->_M_parent
->_M_left
= __x
; // __y must be a child of _M_left
358 __y
->_M_right
= __z
->_M_right
;
359 __z
->_M_right
->_M_parent
= __y
;
365 else if (__z
->_M_parent
->_M_left
== __z
)
366 __z
->_M_parent
->_M_left
= __y
;
368 __z
->_M_parent
->_M_right
= __y
;
369 __y
->_M_parent
= __z
->_M_parent
;
370 std::swap(__y
->_M_color
, __z
->_M_color
);
372 // __y now points to node to be actually deleted
375 __x_parent
= __y
->_M_parent
;
376 if (__x
) __x
->_M_parent
= __y
->_M_parent
;
380 if (__z
->_M_parent
->_M_left
== __z
)
381 __z
->_M_parent
->_M_left
= __x
;
383 __z
->_M_parent
->_M_right
= __x
;
384 if (__leftmost
== __z
)
385 if (__z
->_M_right
== 0) // __z->_M_left must be null also
386 __leftmost
= __z
->_M_parent
;
387 // makes __leftmost == _M_header if __z == __root
389 __leftmost
= _Rb_tree_node_base::_S_minimum(__x
);
390 if (__rightmost
== __z
)
391 if (__z
->_M_left
== 0) // __z->_M_right must be null also
392 __rightmost
= __z
->_M_parent
;
393 // makes __rightmost == _M_header if __z == __root
394 else // __x == __z->_M_left
395 __rightmost
= _Rb_tree_node_base::_S_maximum(__x
);
397 if (__y
->_M_color
!= _S_rb_tree_red
) {
398 while (__x
!= __root
&& (__x
== 0 || __x
->_M_color
== _S_rb_tree_black
))
399 if (__x
== __x_parent
->_M_left
) {
400 _Rb_tree_node_base
* __w
= __x_parent
->_M_right
;
401 if (__w
->_M_color
== _S_rb_tree_red
) {
402 __w
->_M_color
= _S_rb_tree_black
;
403 __x_parent
->_M_color
= _S_rb_tree_red
;
404 _Rb_tree_rotate_left(__x_parent
, __root
);
405 __w
= __x_parent
->_M_right
;
407 if ((__w
->_M_left
== 0 ||
408 __w
->_M_left
->_M_color
== _S_rb_tree_black
) &&
409 (__w
->_M_right
== 0 ||
410 __w
->_M_right
->_M_color
== _S_rb_tree_black
)) {
411 __w
->_M_color
= _S_rb_tree_red
;
413 __x_parent
= __x_parent
->_M_parent
;
415 if (__w
->_M_right
== 0 ||
416 __w
->_M_right
->_M_color
== _S_rb_tree_black
) {
417 if (__w
->_M_left
) __w
->_M_left
->_M_color
= _S_rb_tree_black
;
418 __w
->_M_color
= _S_rb_tree_red
;
419 _Rb_tree_rotate_right(__w
, __root
);
420 __w
= __x_parent
->_M_right
;
422 __w
->_M_color
= __x_parent
->_M_color
;
423 __x_parent
->_M_color
= _S_rb_tree_black
;
424 if (__w
->_M_right
) __w
->_M_right
->_M_color
= _S_rb_tree_black
;
425 _Rb_tree_rotate_left(__x_parent
, __root
);
428 } else { // same as above, with _M_right <-> _M_left.
429 _Rb_tree_node_base
* __w
= __x_parent
->_M_left
;
430 if (__w
->_M_color
== _S_rb_tree_red
) {
431 __w
->_M_color
= _S_rb_tree_black
;
432 __x_parent
->_M_color
= _S_rb_tree_red
;
433 _Rb_tree_rotate_right(__x_parent
, __root
);
434 __w
= __x_parent
->_M_left
;
436 if ((__w
->_M_right
== 0 ||
437 __w
->_M_right
->_M_color
== _S_rb_tree_black
) &&
438 (__w
->_M_left
== 0 ||
439 __w
->_M_left
->_M_color
== _S_rb_tree_black
)) {
440 __w
->_M_color
= _S_rb_tree_red
;
442 __x_parent
= __x_parent
->_M_parent
;
444 if (__w
->_M_left
== 0 ||
445 __w
->_M_left
->_M_color
== _S_rb_tree_black
) {
446 if (__w
->_M_right
) __w
->_M_right
->_M_color
= _S_rb_tree_black
;
447 __w
->_M_color
= _S_rb_tree_red
;
448 _Rb_tree_rotate_left(__w
, __root
);
449 __w
= __x_parent
->_M_left
;
451 __w
->_M_color
= __x_parent
->_M_color
;
452 __x_parent
->_M_color
= _S_rb_tree_black
;
453 if (__w
->_M_left
) __w
->_M_left
->_M_color
= _S_rb_tree_black
;
454 _Rb_tree_rotate_right(__x_parent
, __root
);
458 if (__x
) __x
->_M_color
= _S_rb_tree_black
;
463 // Base class to encapsulate the differences between old SGI-style
464 // allocators and standard-conforming allocators. In order to avoid
465 // having an empty base class, we arbitrarily move one of rb_tree's
466 // data members into the base class.
468 // _Base for general standard-conforming allocators.
469 template <class _Tp
, class _Alloc
, bool _S_instanceless
>
470 class _Rb_tree_alloc_base
{
472 typedef typename _Alloc_traits
<_Tp
, _Alloc
>::allocator_type allocator_type
;
473 allocator_type
get_allocator() const { return _M_node_allocator
; }
475 _Rb_tree_alloc_base(const allocator_type
& __a
)
476 : _M_node_allocator(__a
), _M_header(0) {}
479 typename _Alloc_traits
<_Rb_tree_node
<_Tp
>, _Alloc
>::allocator_type
481 _Rb_tree_node
<_Tp
>* _M_header
;
483 _Rb_tree_node
<_Tp
>* _M_get_node()
484 { return _M_node_allocator
.allocate(1); }
485 void _M_put_node(_Rb_tree_node
<_Tp
>* __p
)
486 { _M_node_allocator
.deallocate(__p
, 1); }
489 // Specialization for instanceless allocators.
490 template <class _Tp
, class _Alloc
>
491 class _Rb_tree_alloc_base
<_Tp
, _Alloc
, true> {
493 typedef typename _Alloc_traits
<_Tp
, _Alloc
>::allocator_type allocator_type
;
494 allocator_type
get_allocator() const { return allocator_type(); }
496 _Rb_tree_alloc_base(const allocator_type
&) : _M_header(0) {}
499 _Rb_tree_node
<_Tp
>* _M_header
;
501 typedef typename _Alloc_traits
<_Rb_tree_node
<_Tp
>, _Alloc
>::_Alloc_type
504 _Rb_tree_node
<_Tp
>* _M_get_node()
505 { return _Alloc_type::allocate(1); }
506 void _M_put_node(_Rb_tree_node
<_Tp
>* __p
)
507 { _Alloc_type::deallocate(__p
, 1); }
510 template <class _Tp
, class _Alloc
>
512 : public _Rb_tree_alloc_base
<_Tp
, _Alloc
,
513 _Alloc_traits
<_Tp
, _Alloc
>::_S_instanceless
>
515 typedef _Rb_tree_alloc_base
<_Tp
, _Alloc
,
516 _Alloc_traits
<_Tp
, _Alloc
>::_S_instanceless
>
518 typedef typename
_Base::allocator_type allocator_type
;
520 _Rb_tree_base(const allocator_type
& __a
)
521 : _Base(__a
) { _M_header
= _M_get_node(); }
522 ~_Rb_tree_base() { _M_put_node(_M_header
); }
527 template <class _Key
, class _Value
, class _KeyOfValue
, class _Compare
,
528 class _Alloc
= allocator
<_Value
> >
529 class _Rb_tree
: protected _Rb_tree_base
<_Value
, _Alloc
> {
530 typedef _Rb_tree_base
<_Value
, _Alloc
> _Base
;
532 typedef _Rb_tree_node_base
* _Base_ptr
;
533 typedef _Rb_tree_node
<_Value
> _Rb_tree_node
;
534 typedef _Rb_tree_Color_type _Color_type
;
536 typedef _Key key_type
;
537 typedef _Value value_type
;
538 typedef value_type
* pointer
;
539 typedef const value_type
* const_pointer
;
540 typedef value_type
& reference
;
541 typedef const value_type
& const_reference
;
542 typedef _Rb_tree_node
* _Link_type
;
543 typedef size_t size_type
;
544 typedef ptrdiff_t difference_type
;
546 typedef typename
_Base::allocator_type allocator_type
;
547 allocator_type
get_allocator() const { return _Base::get_allocator(); }
550 using _Base::_M_get_node
;
551 using _Base::_M_put_node
;
552 using _Base::_M_header
;
557 _M_create_node(const value_type
& __x
)
559 _Link_type __tmp
= _M_get_node();
561 _Construct(&__tmp
->_M_value_field
, __x
);
566 __throw_exception_again
;
571 _Link_type
_M_clone_node(_Link_type __x
)
573 _Link_type __tmp
= _M_create_node(__x
->_M_value_field
);
574 __tmp
->_M_color
= __x
->_M_color
;
581 destroy_node(_Link_type __p
)
583 _Destroy(&__p
->_M_value_field
);
588 size_type _M_node_count
; // keeps track of size of tree
589 _Compare _M_key_compare
;
591 _Link_type
& _M_root() const
592 { return (_Link_type
&) _M_header
->_M_parent
; }
593 _Link_type
& _M_leftmost() const
594 { return (_Link_type
&) _M_header
->_M_left
; }
595 _Link_type
& _M_rightmost() const
596 { return (_Link_type
&) _M_header
->_M_right
; }
598 static _Link_type
& _S_left(_Link_type __x
)
599 { return (_Link_type
&)(__x
->_M_left
); }
600 static _Link_type
& _S_right(_Link_type __x
)
601 { return (_Link_type
&)(__x
->_M_right
); }
602 static _Link_type
& _S_parent(_Link_type __x
)
603 { return (_Link_type
&)(__x
->_M_parent
); }
604 static reference
_S_value(_Link_type __x
)
605 { return __x
->_M_value_field
; }
606 static const _Key
& _S_key(_Link_type __x
)
607 { return _KeyOfValue()(_S_value(__x
)); }
608 static _Color_type
& _S_color(_Link_type __x
)
609 { return (_Color_type
&)(__x
->_M_color
); }
611 static _Link_type
& _S_left(_Base_ptr __x
)
612 { return (_Link_type
&)(__x
->_M_left
); }
613 static _Link_type
& _S_right(_Base_ptr __x
)
614 { return (_Link_type
&)(__x
->_M_right
); }
615 static _Link_type
& _S_parent(_Base_ptr __x
)
616 { return (_Link_type
&)(__x
->_M_parent
); }
617 static reference
_S_value(_Base_ptr __x
)
618 { return ((_Link_type
)__x
)->_M_value_field
; }
619 static const _Key
& _S_key(_Base_ptr __x
)
620 { return _KeyOfValue()(_S_value(_Link_type(__x
)));}
621 static _Color_type
& _S_color(_Base_ptr __x
)
622 { return (_Color_type
&)(_Link_type(__x
)->_M_color
); }
624 static _Link_type
_S_minimum(_Link_type __x
)
625 { return (_Link_type
) _Rb_tree_node_base::_S_minimum(__x
); }
627 static _Link_type
_S_maximum(_Link_type __x
)
628 { return (_Link_type
) _Rb_tree_node_base::_S_maximum(__x
); }
631 typedef _Rb_tree_iterator
<value_type
, reference
, pointer
> iterator
;
632 typedef _Rb_tree_iterator
<value_type
, const_reference
, const_pointer
>
635 typedef reverse_iterator
<const_iterator
> const_reverse_iterator
;
636 typedef reverse_iterator
<iterator
> reverse_iterator
;
639 iterator
_M_insert(_Base_ptr __x
, _Base_ptr __y
, const value_type
& __v
);
640 _Link_type
_M_copy(_Link_type __x
, _Link_type __p
);
641 void _M_erase(_Link_type __x
);
644 // allocation/deallocation
646 : _Base(allocator_type()), _M_node_count(0), _M_key_compare()
647 { _M_empty_initialize(); }
649 _Rb_tree(const _Compare
& __comp
)
650 : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp
)
651 { _M_empty_initialize(); }
653 _Rb_tree(const _Compare
& __comp
, const allocator_type
& __a
)
654 : _Base(__a
), _M_node_count(0), _M_key_compare(__comp
)
655 { _M_empty_initialize(); }
657 _Rb_tree(const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __x
)
658 : _Base(__x
.get_allocator()),
659 _M_node_count(0), _M_key_compare(__x
._M_key_compare
)
661 if (__x
._M_root() == 0)
662 _M_empty_initialize();
664 _S_color(_M_header
) = _S_rb_tree_red
;
665 _M_root() = _M_copy(__x
._M_root(), _M_header
);
666 _M_leftmost() = _S_minimum(_M_root());
667 _M_rightmost() = _S_maximum(_M_root());
669 _M_node_count
= __x
._M_node_count
;
671 ~_Rb_tree() { clear(); }
672 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>&
673 operator=(const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __x
);
676 void _M_empty_initialize() {
677 _S_color(_M_header
) = _S_rb_tree_red
; // used to distinguish header from
678 // __root, in iterator.operator++
680 _M_leftmost() = _M_header
;
681 _M_rightmost() = _M_header
;
686 _Compare
key_comp() const { return _M_key_compare
; }
687 iterator
begin() { return _M_leftmost(); }
688 const_iterator
begin() const { return _M_leftmost(); }
689 iterator
end() { return _M_header
; }
690 const_iterator
end() const { return _M_header
; }
691 reverse_iterator
rbegin() { return reverse_iterator(end()); }
692 const_reverse_iterator
rbegin() const {
693 return const_reverse_iterator(end());
695 reverse_iterator
rend() { return reverse_iterator(begin()); }
696 const_reverse_iterator
rend() const {
697 return const_reverse_iterator(begin());
699 bool empty() const { return _M_node_count
== 0; }
700 size_type
size() const { return _M_node_count
; }
701 size_type
max_size() const { return size_type(-1); }
703 void swap(_Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __t
) {
704 std::swap(_M_header
, __t
._M_header
);
705 std::swap(_M_node_count
, __t
._M_node_count
);
706 std::swap(_M_key_compare
, __t
._M_key_compare
);
711 pair
<iterator
,bool> insert_unique(const value_type
& __x
);
712 iterator
insert_equal(const value_type
& __x
);
714 iterator
insert_unique(iterator __position
, const value_type
& __x
);
715 iterator
insert_equal(iterator __position
, const value_type
& __x
);
717 template <class _InputIterator
>
718 void insert_unique(_InputIterator __first
, _InputIterator __last
);
719 template <class _InputIterator
>
720 void insert_equal(_InputIterator __first
, _InputIterator __last
);
722 void erase(iterator __position
);
723 size_type
erase(const key_type
& __x
);
724 void erase(iterator __first
, iterator __last
);
725 void erase(const key_type
* __first
, const key_type
* __last
);
727 if (_M_node_count
!= 0) {
729 _M_leftmost() = _M_header
;
731 _M_rightmost() = _M_header
;
738 iterator
find(const key_type
& __x
);
739 const_iterator
find(const key_type
& __x
) const;
740 size_type
count(const key_type
& __x
) const;
741 iterator
lower_bound(const key_type
& __x
);
742 const_iterator
lower_bound(const key_type
& __x
) const;
743 iterator
upper_bound(const key_type
& __x
);
744 const_iterator
upper_bound(const key_type
& __x
) const;
745 pair
<iterator
,iterator
> equal_range(const key_type
& __x
);
746 pair
<const_iterator
, const_iterator
> equal_range(const key_type
& __x
) const;
750 bool __rb_verify() const;
753 template <class _Key
, class _Value
, class _KeyOfValue
,
754 class _Compare
, class _Alloc
>
756 operator==(const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
757 const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
759 return __x
.size() == __y
.size() &&
760 equal(__x
.begin(), __x
.end(), __y
.begin());
763 template <class _Key
, class _Value
, class _KeyOfValue
,
764 class _Compare
, class _Alloc
>
766 operator<(const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
767 const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
769 return lexicographical_compare(__x
.begin(), __x
.end(),
770 __y
.begin(), __y
.end());
773 template <class _Key
, class _Value
, class _KeyOfValue
,
774 class _Compare
, class _Alloc
>
776 operator!=(const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
777 const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __y
) {
778 return !(__x
== __y
);
781 template <class _Key
, class _Value
, class _KeyOfValue
,
782 class _Compare
, class _Alloc
>
784 operator>(const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
785 const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __y
) {
789 template <class _Key
, class _Value
, class _KeyOfValue
,
790 class _Compare
, class _Alloc
>
792 operator<=(const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
793 const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __y
) {
797 template <class _Key
, class _Value
, class _KeyOfValue
,
798 class _Compare
, class _Alloc
>
800 operator>=(const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
801 const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __y
) {
806 template <class _Key
, class _Value
, class _KeyOfValue
,
807 class _Compare
, class _Alloc
>
809 swap(_Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
810 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
816 template <class _Key
, class _Value
, class _KeyOfValue
,
817 class _Compare
, class _Alloc
>
818 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>&
819 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
820 ::operator=(const _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>& __x
)
823 // Note that _Key may be a constant type.
826 _M_key_compare
= __x
._M_key_compare
;
827 if (__x
._M_root() == 0) {
829 _M_leftmost() = _M_header
;
830 _M_rightmost() = _M_header
;
833 _M_root() = _M_copy(__x
._M_root(), _M_header
);
834 _M_leftmost() = _S_minimum(_M_root());
835 _M_rightmost() = _S_maximum(_M_root());
836 _M_node_count
= __x
._M_node_count
;
842 template <class _Key
, class _Value
, class _KeyOfValue
,
843 class _Compare
, class _Alloc
>
844 typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
845 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
846 ::_M_insert(_Base_ptr __x_
, _Base_ptr __y_
, const _Value
& __v
)
848 _Link_type __x
= (_Link_type
) __x_
;
849 _Link_type __y
= (_Link_type
) __y_
;
852 if (__y
== _M_header
|| __x
!= 0 ||
853 _M_key_compare(_KeyOfValue()(__v
), _S_key(__y
))) {
854 __z
= _M_create_node(__v
);
855 _S_left(__y
) = __z
; // also makes _M_leftmost() = __z
856 // when __y == _M_header
857 if (__y
== _M_header
) {
859 _M_rightmost() = __z
;
861 else if (__y
== _M_leftmost())
862 _M_leftmost() = __z
; // maintain _M_leftmost() pointing to min node
865 __z
= _M_create_node(__v
);
867 if (__y
== _M_rightmost())
868 _M_rightmost() = __z
; // maintain _M_rightmost() pointing to max node
870 _S_parent(__z
) = __y
;
873 _Rb_tree_rebalance(__z
, _M_header
->_M_parent
);
875 return iterator(__z
);
878 template <class _Key
, class _Value
, class _KeyOfValue
,
879 class _Compare
, class _Alloc
>
880 typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
881 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
882 ::insert_equal(const _Value
& __v
)
884 _Link_type __y
= _M_header
;
885 _Link_type __x
= _M_root();
888 __x
= _M_key_compare(_KeyOfValue()(__v
), _S_key(__x
)) ?
889 _S_left(__x
) : _S_right(__x
);
891 return _M_insert(__x
, __y
, __v
);
895 template <class _Key
, class _Value
, class _KeyOfValue
,
896 class _Compare
, class _Alloc
>
897 pair
<typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
,
899 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
900 ::insert_unique(const _Value
& __v
)
902 _Link_type __y
= _M_header
;
903 _Link_type __x
= _M_root();
907 __comp
= _M_key_compare(_KeyOfValue()(__v
), _S_key(__x
));
908 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
910 iterator __j
= iterator(__y
);
913 return pair
<iterator
,bool>(_M_insert(__x
, __y
, __v
), true);
916 if (_M_key_compare(_S_key(__j
._M_node
), _KeyOfValue()(__v
)))
917 return pair
<iterator
,bool>(_M_insert(__x
, __y
, __v
), true);
918 return pair
<iterator
,bool>(__j
, false);
922 template <class _Key
, class _Val
, class _KeyOfValue
,
923 class _Compare
, class _Alloc
>
924 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
925 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>
926 ::insert_unique(iterator __position
, const _Val
& __v
)
928 if (__position
._M_node
== _M_header
->_M_left
) { // begin()
930 _M_key_compare(_KeyOfValue()(__v
), _S_key(__position
._M_node
)))
931 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
932 // first argument just needs to be non-null
934 return insert_unique(__v
).first
;
935 } else if (__position
._M_node
== _M_header
) { // end()
936 if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v
)))
937 return _M_insert(0, _M_rightmost(), __v
);
939 return insert_unique(__v
).first
;
941 iterator __before
= __position
;
943 if (_M_key_compare(_S_key(__before
._M_node
), _KeyOfValue()(__v
))
944 && _M_key_compare(_KeyOfValue()(__v
), _S_key(__position
._M_node
))) {
945 if (_S_right(__before
._M_node
) == 0)
946 return _M_insert(0, __before
._M_node
, __v
);
948 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
949 // first argument just needs to be non-null
951 return insert_unique(__v
).first
;
955 template <class _Key
, class _Val
, class _KeyOfValue
,
956 class _Compare
, class _Alloc
>
957 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
958 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>
959 ::insert_equal(iterator __position
, const _Val
& __v
)
961 if (__position
._M_node
== _M_header
->_M_left
) { // begin()
963 !_M_key_compare(_S_key(__position
._M_node
), _KeyOfValue()(__v
)))
964 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
965 // first argument just needs to be non-null
967 return insert_equal(__v
);
968 } else if (__position
._M_node
== _M_header
) {// end()
969 if (!_M_key_compare(_KeyOfValue()(__v
), _S_key(_M_rightmost())))
970 return _M_insert(0, _M_rightmost(), __v
);
972 return insert_equal(__v
);
974 iterator __before
= __position
;
976 if (!_M_key_compare(_KeyOfValue()(__v
), _S_key(__before
._M_node
))
977 && !_M_key_compare(_S_key(__position
._M_node
), _KeyOfValue()(__v
))) {
978 if (_S_right(__before
._M_node
) == 0)
979 return _M_insert(0, __before
._M_node
, __v
);
981 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
982 // first argument just needs to be non-null
984 return insert_equal(__v
);
988 template <class _Key
, class _Val
, class _KoV
, class _Cmp
, class _Alloc
>
990 void _Rb_tree
<_Key
,_Val
,_KoV
,_Cmp
,_Alloc
>
991 ::insert_equal(_II __first
, _II __last
)
993 for ( ; __first
!= __last
; ++__first
)
994 insert_equal(*__first
);
997 template <class _Key
, class _Val
, class _KoV
, class _Cmp
, class _Alloc
>
999 void _Rb_tree
<_Key
,_Val
,_KoV
,_Cmp
,_Alloc
>
1000 ::insert_unique(_II __first
, _II __last
) {
1001 for ( ; __first
!= __last
; ++__first
)
1002 insert_unique(*__first
);
1005 template <class _Key
, class _Value
, class _KeyOfValue
,
1006 class _Compare
, class _Alloc
>
1007 inline void _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
1008 ::erase(iterator __position
)
1011 (_Link_type
) _Rb_tree_rebalance_for_erase(__position
._M_node
,
1012 _M_header
->_M_parent
,
1014 _M_header
->_M_right
);
1019 template <class _Key
, class _Value
, class _KeyOfValue
,
1020 class _Compare
, class _Alloc
>
1021 typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::size_type
1022 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::erase(const _Key
& __x
)
1024 pair
<iterator
,iterator
> __p
= equal_range(__x
);
1026 distance(__p
.first
, __p
.second
, __n
);
1027 erase(__p
.first
, __p
.second
);
1031 template <class _Key
, class _Val
, class _KoV
, class _Compare
, class _Alloc
>
1032 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1033 _Rb_tree
<_Key
,_Val
,_KoV
,_Compare
,_Alloc
>
1034 ::_M_copy(_Link_type __x
, _Link_type __p
)
1036 // structural copy. __x and __p must be non-null.
1037 _Link_type __top
= _M_clone_node(__x
);
1038 __top
->_M_parent
= __p
;
1042 __top
->_M_right
= _M_copy(_S_right(__x
), __top
);
1047 _Link_type __y
= _M_clone_node(__x
);
1049 __y
->_M_parent
= __p
;
1051 __y
->_M_right
= _M_copy(_S_right(__x
), __y
);
1059 __throw_exception_again
;
1064 template <class _Key
, class _Value
, class _KeyOfValue
,
1065 class _Compare
, class _Alloc
>
1066 void _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
1067 ::_M_erase(_Link_type __x
)
1069 // erase without rebalancing
1071 _M_erase(_S_right(__x
));
1072 _Link_type __y
= _S_left(__x
);
1078 template <class _Key
, class _Value
, class _KeyOfValue
,
1079 class _Compare
, class _Alloc
>
1080 void _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
1081 ::erase(iterator __first
, iterator __last
)
1083 if (__first
== begin() && __last
== end())
1086 while (__first
!= __last
) erase(__first
++);
1089 template <class _Key
, class _Value
, class _KeyOfValue
,
1090 class _Compare
, class _Alloc
>
1091 void _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
1092 ::erase(const _Key
* __first
, const _Key
* __last
)
1094 while (__first
!= __last
) erase(*__first
++);
1097 template <class _Key
, class _Value
, class _KeyOfValue
,
1098 class _Compare
, class _Alloc
>
1099 typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1100 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::find(const _Key
& __k
)
1102 _Link_type __y
= _M_header
; // Last node which is not less than __k.
1103 _Link_type __x
= _M_root(); // Current node.
1106 if (!_M_key_compare(_S_key(__x
), __k
))
1107 __y
= __x
, __x
= _S_left(__x
);
1109 __x
= _S_right(__x
);
1111 iterator __j
= iterator(__y
);
1112 return (__j
== end() || _M_key_compare(__k
, _S_key(__j
._M_node
))) ?
1116 template <class _Key
, class _Value
, class _KeyOfValue
,
1117 class _Compare
, class _Alloc
>
1118 typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1119 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::find(const _Key
& __k
) const
1121 _Link_type __y
= _M_header
; /* Last node which is not less than __k. */
1122 _Link_type __x
= _M_root(); /* Current node. */
1125 if (!_M_key_compare(_S_key(__x
), __k
))
1126 __y
= __x
, __x
= _S_left(__x
);
1128 __x
= _S_right(__x
);
1130 const_iterator __j
= const_iterator(__y
);
1131 return (__j
== end() || _M_key_compare(__k
, _S_key(__j
._M_node
))) ?
1135 template <class _Key
, class _Value
, class _KeyOfValue
,
1136 class _Compare
, class _Alloc
>
1137 typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::size_type
1138 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
1139 ::count(const _Key
& __k
) const
1141 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
1143 distance(__p
.first
, __p
.second
, __n
);
1147 template <class _Key
, class _Value
, class _KeyOfValue
,
1148 class _Compare
, class _Alloc
>
1149 typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1150 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
1151 ::lower_bound(const _Key
& __k
)
1153 _Link_type __y
= _M_header
; /* Last node which is not less than __k. */
1154 _Link_type __x
= _M_root(); /* Current node. */
1157 if (!_M_key_compare(_S_key(__x
), __k
))
1158 __y
= __x
, __x
= _S_left(__x
);
1160 __x
= _S_right(__x
);
1162 return iterator(__y
);
1165 template <class _Key
, class _Value
, class _KeyOfValue
,
1166 class _Compare
, class _Alloc
>
1167 typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1168 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
1169 ::lower_bound(const _Key
& __k
) const
1171 _Link_type __y
= _M_header
; /* Last node which is not less than __k. */
1172 _Link_type __x
= _M_root(); /* Current node. */
1175 if (!_M_key_compare(_S_key(__x
), __k
))
1176 __y
= __x
, __x
= _S_left(__x
);
1178 __x
= _S_right(__x
);
1180 return const_iterator(__y
);
1183 template <class _Key
, class _Value
, class _KeyOfValue
,
1184 class _Compare
, class _Alloc
>
1185 typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1186 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
1187 ::upper_bound(const _Key
& __k
)
1189 _Link_type __y
= _M_header
; /* Last node which is greater than __k. */
1190 _Link_type __x
= _M_root(); /* Current node. */
1193 if (_M_key_compare(__k
, _S_key(__x
)))
1194 __y
= __x
, __x
= _S_left(__x
);
1196 __x
= _S_right(__x
);
1198 return iterator(__y
);
1201 template <class _Key
, class _Value
, class _KeyOfValue
,
1202 class _Compare
, class _Alloc
>
1203 typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1204 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
1205 ::upper_bound(const _Key
& __k
) const
1207 _Link_type __y
= _M_header
; /* Last node which is greater than __k. */
1208 _Link_type __x
= _M_root(); /* Current node. */
1211 if (_M_key_compare(__k
, _S_key(__x
)))
1212 __y
= __x
, __x
= _S_left(__x
);
1214 __x
= _S_right(__x
);
1216 return const_iterator(__y
);
1219 template <class _Key
, class _Value
, class _KeyOfValue
,
1220 class _Compare
, class _Alloc
>
1222 pair
<typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
,
1223 typename _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
>
1224 _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>
1225 ::equal_range(const _Key
& __k
)
1227 return pair
<iterator
, iterator
>(lower_bound(__k
), upper_bound(__k
));
1230 template <class _Key
, class _Value
, class _KoV
, class _Compare
, class _Alloc
>
1232 pair
<typename _Rb_tree
<_Key
, _Value
, _KoV
, _Compare
, _Alloc
>::const_iterator
,
1233 typename _Rb_tree
<_Key
, _Value
, _KoV
, _Compare
, _Alloc
>::const_iterator
>
1234 _Rb_tree
<_Key
, _Value
, _KoV
, _Compare
, _Alloc
>
1235 ::equal_range(const _Key
& __k
) const
1237 return pair
<const_iterator
,const_iterator
>(lower_bound(__k
),
1242 __black_count(_Rb_tree_node_base
* __node
, _Rb_tree_node_base
* __root
)
1248 if (__node
->_M_color
== _S_rb_tree_black
)
1250 if (__node
== __root
)
1252 __node
= __node
->_M_parent
;
1257 template <class _Key
, class _Value
, class _KeyOfValue
,
1258 class _Compare
, class _Alloc
>
1259 bool _Rb_tree
<_Key
,_Value
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
1261 if (_M_node_count
== 0 || begin() == end())
1262 return _M_node_count
== 0 && begin() == end() &&
1263 _M_header
->_M_left
== _M_header
&& _M_header
->_M_right
== _M_header
;
1265 int __len
= __black_count(_M_leftmost(), _M_root());
1266 for (const_iterator __it
= begin(); __it
!= end(); ++__it
) {
1267 _Link_type __x
= (_Link_type
) __it
._M_node
;
1268 _Link_type __L
= _S_left(__x
);
1269 _Link_type __R
= _S_right(__x
);
1271 if (__x
->_M_color
== _S_rb_tree_red
)
1272 if ((__L
&& __L
->_M_color
== _S_rb_tree_red
) ||
1273 (__R
&& __R
->_M_color
== _S_rb_tree_red
))
1276 if (__L
&& _M_key_compare(_S_key(__x
), _S_key(__L
)))
1278 if (__R
&& _M_key_compare(_S_key(__R
), _S_key(__x
)))
1281 if (!__L
&& !__R
&& __black_count(__x
, _M_root()) != __len
)
1285 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1287 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1293 // Class rb_tree is not part of the C++ standard. It is provided for
1294 // compatibility with the HP STL.
1296 template <class _Key
, class _Value
, class _KeyOfValue
, class _Compare
,
1297 class _Alloc
= allocator
<_Value
> >
1298 struct rb_tree
: public _Rb_tree
<_Key
, _Value
, _KeyOfValue
, _Compare
, _Alloc
>
1300 typedef _Rb_tree
<_Key
, _Value
, _KeyOfValue
, _Compare
, _Alloc
> _Base
;
1301 typedef typename
_Base::allocator_type allocator_type
;
1303 rb_tree(const _Compare
& __comp
= _Compare(),
1304 const allocator_type
& __a
= allocator_type())
1305 : _Base(__comp
, __a
) {}
1312 #endif /* __GLIBCPP_INTERNAL_TREE_H */