4 * Hewlett-Packard Company
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
10 * Moscow Center for SPARC Technology
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
30 #ifndef _STLP_INTERNAL_TREE_H
31 #define _STLP_INTERNAL_TREE_H
35 Red-black tree class, designed for use in implementing STL
36 associative containers (set, multiset, map, and multimap). The
37 insertion and deletion algorithms are based on those in Cormen,
38 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
41 (1) the header cell is maintained with links not only to the root
42 but also to the leftmost node of the tree, to enable constant time
43 begin(), and to the rightmost node of the tree, to enable linear time
44 performance when used with the generic set algorithms (set_union,
47 (2) when a node being deleted has two children its successor node is
48 relinked into its place, rather than copied, so that the only
49 iterators invalidated are those referring to the deleted node.
53 #ifndef _STLP_INTERNAL_ALGOBASE_H
54 # include <stl/_algobase.h>
57 #ifndef _STLP_INTERNAL_ALLOC_H
58 # include <stl/_alloc.h>
61 #ifndef _STLP_INTERNAL_ITERATOR_H
62 # include <stl/_iterator.h>
65 #ifndef _STLP_INTERNAL_CONSTRUCT_H
66 # include <stl/_construct.h>
69 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H
70 # include <stl/_function_base.h>
75 _STLP_MOVE_TO_PRIV_NAMESPACE
77 typedef bool _Rb_tree_Color_type
;
78 //const _Rb_tree_Color_type _S_rb_tree_red = false;
79 //const _Rb_tree_Color_type _S_rb_tree_black = true;
81 #define _S_rb_tree_red false
82 #define _S_rb_tree_black true
84 struct _Rb_tree_node_base
{
85 typedef _Rb_tree_Color_type _Color_type
;
86 typedef _Rb_tree_node_base
* _Base_ptr
;
93 static _Base_ptr _STLP_CALL
_S_minimum(_Base_ptr __x
) {
94 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
98 static _Base_ptr _STLP_CALL
_S_maximum(_Base_ptr __x
) {
99 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
104 template <class _Value
>
105 struct _Rb_tree_node
: public _Rb_tree_node_base
{
106 _Value _M_value_field
;
107 __TRIVIAL_STUFF(_Rb_tree_node
)
110 struct _Rb_tree_base_iterator
;
112 template <class _Dummy
>
115 typedef _Rb_tree_node_base
* _Base_ptr
;
116 // those used to be global functions
117 static void _STLP_CALL
_Rebalance(_Base_ptr __x
, _Base_ptr
& __root
);
118 static _Base_ptr _STLP_CALL
_Rebalance_for_erase(_Base_ptr __z
,
120 _Base_ptr
& __leftmost
,
121 _Base_ptr
& __rightmost
);
122 // those are from _Rb_tree_base_iterator - moved here to reduce code bloat
123 // moved here to reduce code bloat without templatizing _Rb_tree_base_iterator
124 static _Base_ptr _STLP_CALL
_M_increment (_Base_ptr
);
125 static _Base_ptr _STLP_CALL
_M_decrement (_Base_ptr
);
126 static void _STLP_CALL
_Rotate_left (_Base_ptr __x
, _Base_ptr
& __root
);
127 static void _STLP_CALL
_Rotate_right(_Base_ptr __x
, _Base_ptr
& __root
);
130 # if defined (_STLP_USE_TEMPLATE_EXPORT)
131 _STLP_EXPORT_TEMPLATE_CLASS _Rb_global
<bool>;
134 typedef _Rb_global
<bool> _Rb_global_inst
;
136 struct _Rb_tree_base_iterator
{
137 typedef _Rb_tree_node_base
* _Base_ptr
;
138 typedef bidirectional_iterator_tag iterator_category
;
139 typedef ptrdiff_t difference_type
;
141 _Rb_tree_base_iterator() : _M_node(0) {}
142 _Rb_tree_base_iterator(_Base_ptr __x
) : _M_node(__x
) {}
145 template <class _Value
, class _Traits
>
146 struct _Rb_tree_iterator
: public _Rb_tree_base_iterator
{
147 typedef _Value value_type
;
148 typedef typename
_Traits::reference reference
;
149 typedef typename
_Traits::pointer pointer
;
150 typedef _Rb_tree_iterator
<_Value
, _Traits
> _Self
;
151 typedef _Rb_tree_node_base
* _Base_ptr
;
152 typedef _Rb_tree_node
<_Value
>* _Link_type
;
154 typedef typename
_Traits::_NonConstTraits _NonConstTraits
;
155 typedef _Rb_tree_iterator
<_Value
, _NonConstTraits
> iterator
;
156 typedef typename
_Traits::_ConstTraits _ConstTraits
;
157 typedef _Rb_tree_iterator
<_Value
, _ConstTraits
> const_iterator
;
159 _Rb_tree_iterator() {}
160 #if !defined (_STLP_DEBUG)
161 /* In STL debug mode we need this constructor implicit for the pointer
162 * specialization implementation.
166 _Rb_tree_iterator(_Base_ptr __x
) : _Rb_tree_base_iterator(__x
) {}
167 //copy constructor for iterator and constructor from iterator for const_iterator
168 _Rb_tree_iterator(const iterator
& __it
) : _Rb_tree_base_iterator(__it
._M_node
) {}
170 reference
operator*() const {
171 return __STATIC_CAST(_Link_type
, _M_node
)->_M_value_field
;
174 _STLP_DEFINE_ARROW_OPERATOR
176 _Self
& operator++() {
177 _M_node
= _Rb_global_inst::_M_increment(_M_node
);
180 _Self
operator++(int) {
186 _Self
& operator--() {
187 _M_node
= _Rb_global_inst::_M_decrement(_M_node
);
190 _Self
operator--(int) {
196 bool operator == (const_iterator __rhs
) const {
197 return _M_node
== __rhs
._M_node
;
199 bool operator != (const_iterator __rhs
) const {
200 return _M_node
!= __rhs
._M_node
;
204 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
205 _STLP_MOVE_TO_STD_NAMESPACE
206 template <class _Value
, class _Traits
>
207 struct __type_traits
<_STLP_PRIV _Rb_tree_iterator
<_Value
, _Traits
> > {
208 typedef __false_type has_trivial_default_constructor
;
209 typedef __true_type has_trivial_copy_constructor
;
210 typedef __true_type has_trivial_assignment_operator
;
211 typedef __true_type has_trivial_destructor
;
212 typedef __false_type is_POD_type
;
214 _STLP_MOVE_TO_PRIV_NAMESPACE
215 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
217 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
218 _STLP_MOVE_TO_STD_NAMESPACE
219 template <class _Value
, class _Traits
>
220 inline _Value
* value_type(const _STLP_PRIV _Rb_tree_iterator
<_Value
, _Traits
>&)
221 { return (_Value
*)0; }
222 inline bidirectional_iterator_tag
iterator_category(const _STLP_PRIV _Rb_tree_base_iterator
&)
223 { return bidirectional_iterator_tag(); }
224 inline ptrdiff_t* distance_type(const _STLP_PRIV _Rb_tree_base_iterator
&)
225 { return (ptrdiff_t*) 0; }
226 _STLP_MOVE_TO_PRIV_NAMESPACE
227 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
229 // Base class to help EH
231 template <class _Tp
, class _Alloc
>
232 class _Rb_tree_base
{
234 typedef _Rb_tree_node_base _Node_base
;
235 typedef _Rb_tree_node
<_Tp
> _Node
;
236 _STLP_FORCE_ALLOCATORS(_Tp
, _Alloc
)
237 typedef _Alloc allocator_type
;
239 typedef _Rb_tree_base
<_Tp
, _Alloc
> _Self
;
240 typedef typename _Alloc_traits
<_Node
, _Alloc
>::allocator_type _M_node_allocator_type
;
241 typedef _STLP_alloc_proxy
<_Node_base
, _Node
, _M_node_allocator_type
> _AllocProxy
;
244 allocator_type
get_allocator() const {
245 return _STLP_CONVERT_ALLOCATOR(_M_header
, _Tp
);
249 _Rb_tree_base(const allocator_type
& __a
) :
250 _M_header(_STLP_CONVERT_ALLOCATOR(__a
, _Node
), _Node_base() ) {
251 _M_empty_initialize();
254 #if !defined (_STLP_NO_MOVE_SEMANTIC)
255 _Rb_tree_base(__move_source
<_Self
> src
) :
256 _M_header(__move_source
<_AllocProxy
>(src
.get()._M_header
)) {
257 _M_rebind(&src
.get()._M_header
._M_data
);
258 src
.get()._M_empty_initialize();
262 void _M_empty_initialize() {
263 _M_header
._M_data
._M_color
= _S_rb_tree_red
; // used to distinguish header from
264 // __root, in iterator.operator++
265 _M_header
._M_data
._M_parent
= 0;
266 _M_header
._M_data
._M_left
= &_M_header
._M_data
;
267 _M_header
._M_data
._M_right
= &_M_header
._M_data
;
270 void _M_rebind(_Node_base
*__static_node
) {
271 if (_M_header
._M_data
._M_parent
!= 0) {
272 _M_header
._M_data
._M_parent
->_M_parent
= &_M_header
._M_data
;
274 if (_M_header
._M_data
._M_right
== __static_node
) {
275 _M_header
._M_data
._M_right
= &_M_header
._M_data
;
277 if (_M_header
._M_data
._M_left
== __static_node
) {
278 _M_header
._M_data
._M_left
= &_M_header
._M_data
;
282 _AllocProxy _M_header
;
285 #if defined (_STLP_DEBUG)
286 # define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree)
289 template <class _Key
, class _Compare
,
290 class _Value
, class _KeyOfValue
, class _Traits
,
291 _STLP_DFL_TMPL_PARAM(_Alloc
, allocator
<_Value
>) >
292 class _Rb_tree
: public _Rb_tree_base
<_Value
, _Alloc
> {
293 typedef _Rb_tree_base
<_Value
, _Alloc
> _Base
;
294 typedef _Rb_tree
<_Key
, _Compare
, _Value
, _KeyOfValue
, _Traits
, _Alloc
> _Self
;
296 typedef _Rb_tree_node_base
* _Base_ptr
;
297 typedef _Rb_tree_node
<_Value
> _Node
;
298 typedef _Node
* _Link_type
;
299 typedef _Rb_tree_Color_type _Color_type
;
301 typedef _Key key_type
;
302 typedef _Value value_type
;
303 typedef typename
_Traits::pointer pointer
;
304 typedef const value_type
* const_pointer
;
305 typedef typename
_Traits::reference reference
;
306 typedef const value_type
& const_reference
;
307 typedef size_t size_type
;
308 typedef ptrdiff_t difference_type
;
309 typedef bidirectional_iterator_tag _Iterator_category
;
310 typedef typename
_Base::allocator_type allocator_type
;
314 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type
)
315 _Base_ptr
_M_create_node(const value_type
& __x
) {
316 _Link_type __tmp
= this->_M_header
.allocate(1);
318 _Copy_Construct(&__tmp
->_M_value_field
, __x
);
320 _STLP_UNWIND(this->_M_header
.deallocate(__tmp
,1))
326 _Base_ptr
_M_clone_node(_Base_ptr __x
) {
327 _Base_ptr __tmp
= _M_create_node(_S_value(__x
));
328 _S_color(__tmp
) = _S_color(__x
);
332 size_type _M_node_count
; // keeps track of size of tree
333 _Compare _M_key_compare
;
335 _Base_ptr
_M_root() const
336 { return this->_M_header
._M_data
._M_parent
; }
337 _Base_ptr
_M_leftmost() const
338 { return this->_M_header
._M_data
._M_left
; }
339 _Base_ptr
_M_rightmost() const
340 { return this->_M_header
._M_data
._M_right
; }
343 { return this->_M_header
._M_data
._M_parent
; }
344 _Base_ptr
& _M_leftmost()
345 { return this->_M_header
._M_data
._M_left
; }
346 _Base_ptr
& _M_rightmost()
347 { return this->_M_header
._M_data
._M_right
; }
349 static _Base_ptr
& _STLP_CALL
_S_left(_Base_ptr __x
)
350 { return __x
->_M_left
; }
351 static _Base_ptr
& _STLP_CALL
_S_right(_Base_ptr __x
)
352 { return __x
->_M_right
; }
353 static _Base_ptr
& _STLP_CALL
_S_parent(_Base_ptr __x
)
354 { return __x
->_M_parent
; }
355 static value_type
& _STLP_CALL
_S_value(_Base_ptr __x
)
356 { return __STATIC_CAST(_Link_type
, __x
)->_M_value_field
; }
357 static const _Key
& _STLP_CALL
_S_key(_Base_ptr __x
)
358 { return _KeyOfValue()(_S_value(__x
));}
359 static _Color_type
& _STLP_CALL
_S_color(_Base_ptr __x
)
360 { return (_Color_type
&)(__x
->_M_color
); }
362 static _Base_ptr _STLP_CALL
_S_minimum(_Base_ptr __x
)
363 { return _Rb_tree_node_base::_S_minimum(__x
); }
365 static _Base_ptr _STLP_CALL
_S_maximum(_Base_ptr __x
)
366 { return _Rb_tree_node_base::_S_maximum(__x
); }
369 typedef typename
_Traits::_NonConstTraits _NonConstTraits
;
370 typedef typename
_Traits::_ConstTraits _ConstTraits
;
371 typedef _Rb_tree_iterator
<value_type
, _NonConstTraits
> iterator
;
372 typedef _Rb_tree_iterator
<value_type
, _ConstTraits
> const_iterator
;
373 _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS
;
376 iterator
_M_insert(_Base_ptr __parent
, const value_type
& __val
, _Base_ptr __on_left
= 0, _Base_ptr __on_right
= 0);
377 _Base_ptr
_M_copy(_Base_ptr __x
, _Base_ptr __p
);
378 void _M_erase(_Base_ptr __x
);
381 // allocation/deallocation
383 : _Rb_tree_base
<_Value
, _Alloc
>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare())
386 _Rb_tree(const _Compare
& __comp
)
387 : _Rb_tree_base
<_Value
, _Alloc
>(allocator_type()), _M_node_count(0), _M_key_compare(__comp
)
390 _Rb_tree(const _Compare
& __comp
, const allocator_type
& __a
)
391 : _Rb_tree_base
<_Value
, _Alloc
>(__a
), _M_node_count(0), _M_key_compare(__comp
)
394 _Rb_tree(const _Self
& __x
)
395 : _Rb_tree_base
<_Value
, _Alloc
>(__x
.get_allocator()),
396 _M_node_count(0), _M_key_compare(__x
._M_key_compare
) {
397 if (__x
._M_root() != 0) {
398 _S_color(&this->_M_header
._M_data
) = _S_rb_tree_red
;
399 _M_root() = _M_copy(__x
._M_root(), &this->_M_header
._M_data
);
400 _M_leftmost() = _S_minimum(_M_root());
401 _M_rightmost() = _S_maximum(_M_root());
403 _M_node_count
= __x
._M_node_count
;
406 #if !defined (_STLP_NO_MOVE_SEMANTIC)
407 _Rb_tree(__move_source
<_Self
> src
)
408 : _Rb_tree_base
<_Value
, _Alloc
>(__move_source
<_Base
>(src
.get())),
409 _M_node_count(src
.get()._M_node_count
),
410 _M_key_compare(_AsMoveSource(src
.get()._M_key_compare
))
411 { src
.get()._M_node_count
= 0; }
414 ~_Rb_tree() { clear(); }
415 _Self
& operator=(const _Self
& __x
);
419 _Compare
key_comp() const { return _M_key_compare
; }
421 iterator
begin() { return iterator(_M_leftmost()); }
422 const_iterator
begin() const { return const_iterator(_M_leftmost()); }
423 iterator
end() { return iterator(&this->_M_header
._M_data
); }
424 const_iterator
end() const { return const_iterator(__CONST_CAST(_Base_ptr
, &this->_M_header
._M_data
)); }
426 reverse_iterator
rbegin() { return reverse_iterator(end()); }
427 const_reverse_iterator
rbegin() const
428 { return const_reverse_iterator(end()); }
429 reverse_iterator
rend() { return reverse_iterator(begin()); }
430 const_reverse_iterator
rend() const
431 { return const_reverse_iterator(begin()); }
432 bool empty() const { return _M_node_count
== 0; }
433 size_type
size() const { return _M_node_count
; }
434 size_type
max_size() const { return size_type(-1); }
436 void swap(_Self
& __t
) {
438 if (this->empty()) return;
439 __t
._M_header
.swap(this->_M_header
);
440 __t
._M_rebind(&this->_M_header
._M_data
);
441 this->_M_empty_initialize();
443 else if (this->empty()) {
448 this->_M_header
.swap(__t
._M_header
);
449 this->_M_rebind(&__t
._M_header
._M_data
);
450 __t
._M_rebind(&this->_M_header
._M_data
);
452 _STLP_STD::swap(_M_node_count
, __t
._M_node_count
);
453 _STLP_STD::swap(_M_key_compare
, __t
._M_key_compare
);
458 pair
<iterator
,bool> insert_unique(const value_type
& __x
);
459 iterator
insert_equal(const value_type
& __x
);
461 iterator
insert_unique(iterator __pos
, const value_type
& __x
);
462 iterator
insert_equal(iterator __pos
, const value_type
& __x
);
464 #if defined (_STLP_MEMBER_TEMPLATES)
465 template<class _II
> void insert_equal(_II __first
, _II __last
) {
466 for ( ; __first
!= __last
; ++__first
)
467 insert_equal(*__first
);
469 template<class _II
> void insert_unique(_II __first
, _II __last
) {
470 for ( ; __first
!= __last
; ++__first
)
471 insert_unique(*__first
);
474 void insert_unique(const_iterator __first
, const_iterator __last
) {
475 for ( ; __first
!= __last
; ++__first
)
476 insert_unique(*__first
);
478 void insert_unique(const value_type
* __first
, const value_type
* __last
) {
479 for ( ; __first
!= __last
; ++__first
)
480 insert_unique(*__first
);
482 void insert_equal(const_iterator __first
, const_iterator __last
) {
483 for ( ; __first
!= __last
; ++__first
)
484 insert_equal(*__first
);
486 void insert_equal(const value_type
* __first
, const value_type
* __last
) {
487 for ( ; __first
!= __last
; ++__first
)
488 insert_equal(*__first
);
492 void erase(iterator __pos
) {
493 _Base_ptr __x
= _Rb_global_inst::_Rebalance_for_erase(__pos
._M_node
,
494 this->_M_header
._M_data
._M_parent
,
495 this->_M_header
._M_data
._M_left
,
496 this->_M_header
._M_data
._M_right
);
497 _STLP_STD::_Destroy(&_S_value(__x
));
498 this->_M_header
.deallocate(__STATIC_CAST(_Link_type
, __x
), 1);
502 size_type
erase(const key_type
& __x
) {
503 pair
<iterator
,iterator
> __p
= equal_range(__x
);
504 size_type __n
= _STLP_STD::distance(__p
.first
, __p
.second
);
505 erase(__p
.first
, __p
.second
);
509 size_type
erase_unique(const key_type
& __x
) {
510 iterator __i
= find(__x
);
511 if (__i
._M_node
!= &this->_M_header
._M_data
) {
518 void erase(iterator __first
, iterator __last
) {
519 if (__first
._M_node
== this->_M_header
._M_data
._M_left
&& // begin()
520 __last
._M_node
== &this->_M_header
._M_data
) // end()
523 while (__first
!= __last
) erase(__first
++);
526 void erase(const key_type
* __first
, const key_type
* __last
) {
527 while (__first
!= __last
) erase(*__first
++);
531 if (_M_node_count
!= 0) {
533 _M_leftmost() = &this->_M_header
._M_data
;
535 _M_rightmost() = &this->_M_header
._M_data
;
542 _STLP_TEMPLATE_FOR_CONT_EXT
543 iterator
find(const _KT
& __k
) { return iterator(_M_find(__k
)); }
544 _STLP_TEMPLATE_FOR_CONT_EXT
545 const_iterator
find(const _KT
& __k
) const { return const_iterator(_M_find(__k
)); }
547 _STLP_TEMPLATE_FOR_CONT_EXT
548 _Base_ptr
_M_find(const _KT
& __k
) const {
549 _Base_ptr __y
= __CONST_CAST(_Base_ptr
, &this->_M_header
._M_data
); // Last node which is not less than __k.
550 _Base_ptr __x
= _M_root(); // Current node.
553 if (!_M_key_compare(_S_key(__x
), __k
))
554 __y
= __x
, __x
= _S_left(__x
);
558 if (__y
!= &this->_M_header
._M_data
) {
559 if (_M_key_compare(__k
, _S_key(__y
))) {
560 __y
= __CONST_CAST(_Base_ptr
, &this->_M_header
._M_data
);
566 _STLP_TEMPLATE_FOR_CONT_EXT
567 _Base_ptr
_M_lower_bound(const _KT
& __k
) const {
568 _Base_ptr __y
= __CONST_CAST(_Base_ptr
, &this->_M_header
._M_data
); /* Last node which is not less than __k. */
569 _Base_ptr __x
= _M_root(); /* Current node. */
572 if (!_M_key_compare(_S_key(__x
), __k
))
573 __y
= __x
, __x
= _S_left(__x
);
580 _STLP_TEMPLATE_FOR_CONT_EXT
581 _Base_ptr
_M_upper_bound(const _KT
& __k
) const {
582 _Base_ptr __y
= __CONST_CAST(_Base_ptr
, &this->_M_header
._M_data
); /* Last node which is greater than __k. */
583 _Base_ptr __x
= _M_root(); /* Current node. */
586 if (_M_key_compare(__k
, _S_key(__x
)))
587 __y
= __x
, __x
= _S_left(__x
);
595 _STLP_TEMPLATE_FOR_CONT_EXT
596 size_type
count(const _KT
& __x
) const {
597 pair
<const_iterator
, const_iterator
> __p
= equal_range(__x
);
598 return _STLP_STD::distance(__p
.first
, __p
.second
);
600 _STLP_TEMPLATE_FOR_CONT_EXT
601 iterator
lower_bound(const _KT
& __x
) { return iterator(_M_lower_bound(__x
)); }
602 _STLP_TEMPLATE_FOR_CONT_EXT
603 const_iterator
lower_bound(const _KT
& __x
) const { return const_iterator(_M_lower_bound(__x
)); }
604 _STLP_TEMPLATE_FOR_CONT_EXT
605 iterator
upper_bound(const _KT
& __x
) { return iterator(_M_upper_bound(__x
)); }
606 _STLP_TEMPLATE_FOR_CONT_EXT
607 const_iterator
upper_bound(const _KT
& __x
) const { return const_iterator(_M_upper_bound(__x
)); }
608 _STLP_TEMPLATE_FOR_CONT_EXT
609 pair
<iterator
,iterator
> equal_range(const _KT
& __x
)
610 { return pair
<iterator
, iterator
>(lower_bound(__x
), upper_bound(__x
)); }
611 _STLP_TEMPLATE_FOR_CONT_EXT
612 pair
<const_iterator
, const_iterator
> equal_range(const _KT
& __x
) const
613 { return pair
<const_iterator
, const_iterator
>(lower_bound(__x
), upper_bound(__x
)); }
614 _STLP_TEMPLATE_FOR_CONT_EXT
615 pair
<iterator
,iterator
> equal_range_unique(const _KT
& __x
) {
616 pair
<iterator
, iterator
> __p
;
617 __p
.second
= lower_bound(__x
);
618 if (__p
.second
._M_node
!= &this->_M_header
._M_data
&&
619 !_M_key_compare(__x
, _S_key(__p
.second
._M_node
))) {
620 __p
.first
= __p
.second
++;
623 __p
.first
= __p
.second
;
627 _STLP_TEMPLATE_FOR_CONT_EXT
628 pair
<const_iterator
, const_iterator
> equal_range_unique(const _KT
& __x
) const {
629 pair
<const_iterator
, const_iterator
> __p
;
630 __p
.second
= lower_bound(__x
);
631 if (__p
.second
._M_node
!= &this->_M_header
._M_data
&&
632 !_M_key_compare(__x
, _S_key(__p
.second
._M_node
))) {
633 __p
.first
= __p
.second
++;
636 __p
.first
= __p
.second
;
641 #if defined (_STLP_DEBUG)
644 bool __rb_verify() const;
648 #if defined (_STLP_DEBUG)
652 _STLP_MOVE_TO_STD_NAMESPACE
656 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
657 # include <stl/_tree.c>
660 #if defined (_STLP_DEBUG)
661 # include <stl/debug/_tree.h>
664 _STLP_BEGIN_NAMESPACE
666 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
667 #define _STLP_TEMPLATE_CONTAINER _STLP_PRIV _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>
668 #include <stl/_relops_cont.h>
669 #undef _STLP_TEMPLATE_CONTAINER
670 #undef _STLP_TEMPLATE_HEADER
672 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
673 template <class _Key
, class _Compare
, class _Value
, class _KeyOfValue
, class _Traits
, class _Alloc
>
674 struct __move_traits
<_STLP_PRIV _Rb_tree
<_Key
, _Compare
, _Value
, _KeyOfValue
, _Traits
, _Alloc
> >
675 : _STLP_PRIV __move_traits_help2
<_Compare
, _Alloc
> {};
680 #endif /* _STLP_INTERNAL_TREE_H */