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 typename _Alloc_traits<_Tp, _Alloc>::allocator_type 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();
253 _Rb_tree_base(__move_source<_Self> src) :
254 _M_header(__move_source<_AllocProxy>(src.get()._M_header)) {
255 _M_rebind(&src.get()._M_header._M_data);
256 src.get()._M_empty_initialize();
258 void _M_empty_initialize() {
259 _M_header._M_data._M_color = _S_rb_tree_red; // used to distinguish header from
260 // __root, in iterator.operator++
261 _M_header._M_data._M_parent = 0;
262 _M_header._M_data._M_left = &_M_header._M_data;
263 _M_header._M_data._M_right = &_M_header._M_data;
266 void _M_rebind(_Node_base *__static_node) {
267 if (_M_header._M_data._M_parent != 0) {
268 _M_header._M_data._M_parent->_M_parent = &_M_header._M_data;
270 if (_M_header._M_data._M_right == __static_node) {
271 _M_header._M_data._M_right = &_M_header._M_data;
273 if (_M_header._M_data._M_left == __static_node) {
274 _M_header._M_data._M_left = &_M_header._M_data;
278 _AllocProxy _M_header;
281 #if defined (_STLP_DEBUG)
282 # define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree)
285 template <class _Key, class _Compare,
286 class _Value, class _KeyOfValue, class _Traits,
287 _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
288 class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {
289 typedef _Rb_tree_base<_Value, _Alloc> _Base;
290 typedef _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> _Self;
292 typedef _Rb_tree_node_base * _Base_ptr;
293 typedef _Rb_tree_node<_Value> _Node;
294 typedef _Node* _Link_type;
295 typedef _Rb_tree_Color_type _Color_type;
297 typedef _Key key_type;
298 typedef _Value value_type;
299 typedef typename _Traits::pointer pointer;
300 typedef const value_type* const_pointer;
301 typedef typename _Traits::reference reference;
302 typedef const value_type& const_reference;
303 typedef size_t size_type;
304 typedef ptrdiff_t difference_type;
305 typedef bidirectional_iterator_tag _Iterator_category;
306 typedef typename _Base::allocator_type allocator_type;
310 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
311 _Base_ptr _M_create_node(const value_type& __x) {
312 _Link_type __tmp = this->_M_header.allocate(1);
314 _Copy_Construct(&__tmp->_M_value_field, __x);
316 _STLP_UNWIND(this->_M_header.deallocate(__tmp,1))
322 _Base_ptr _M_clone_node(_Base_ptr __x) {
323 _Base_ptr __tmp = _M_create_node(_S_value(__x));
324 _S_color(__tmp) = _S_color(__x);
328 size_type _M_node_count; // keeps track of size of tree
329 _Compare _M_key_compare;
331 _Base_ptr _M_root() const
332 { return this->_M_header._M_data._M_parent; }
333 _Base_ptr _M_leftmost() const
334 { return this->_M_header._M_data._M_left; }
335 _Base_ptr _M_rightmost() const
336 { return this->_M_header._M_data._M_right; }
339 { return this->_M_header._M_data._M_parent; }
340 _Base_ptr& _M_leftmost()
341 { return this->_M_header._M_data._M_left; }
342 _Base_ptr& _M_rightmost()
343 { return this->_M_header._M_data._M_right; }
345 static _Base_ptr& _STLP_CALL _S_left(_Base_ptr __x)
346 { return __x->_M_left; }
347 static _Base_ptr& _STLP_CALL _S_right(_Base_ptr __x)
348 { return __x->_M_right; }
349 static _Base_ptr& _STLP_CALL _S_parent(_Base_ptr __x)
350 { return __x->_M_parent; }
351 static value_type& _STLP_CALL _S_value(_Base_ptr __x)
352 { return __STATIC_CAST(_Link_type, __x)->_M_value_field; }
353 static const _Key& _STLP_CALL _S_key(_Base_ptr __x)
354 { return _KeyOfValue()(_S_value(__x));}
355 static _Color_type& _STLP_CALL _S_color(_Base_ptr __x)
356 { return (_Color_type&)(__x->_M_color); }
358 static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
359 { return _Rb_tree_node_base::_S_minimum(__x); }
361 static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
362 { return _Rb_tree_node_base::_S_maximum(__x); }
365 typedef typename _Traits::_NonConstTraits _NonConstTraits;
366 typedef typename _Traits::_ConstTraits _ConstTraits;
367 typedef _Rb_tree_iterator<value_type, _NonConstTraits> iterator;
368 typedef _Rb_tree_iterator<value_type, _ConstTraits> const_iterator;
369 _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS;
372 iterator _M_insert(_Base_ptr __parent, const value_type& __val, _Base_ptr __on_left = 0, _Base_ptr __on_right = 0);
373 _Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p);
374 void _M_erase(_Base_ptr __x);
377 // allocation/deallocation
379 : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare())
382 _Rb_tree(const _Compare& __comp)
383 : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp)
386 _Rb_tree(const _Compare& __comp, const allocator_type& __a)
387 : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp)
390 _Rb_tree(const _Self& __x)
391 : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()),
392 _M_node_count(0), _M_key_compare(__x._M_key_compare) {
393 if (__x._M_root() != 0) {
394 _S_color(&this->_M_header._M_data) = _S_rb_tree_red;
395 _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
396 _M_leftmost() = _S_minimum(_M_root());
397 _M_rightmost() = _S_maximum(_M_root());
399 _M_node_count = __x._M_node_count;
402 _Rb_tree(__move_source<_Self> src)
403 : _Rb_tree_base<_Value, _Alloc>(__move_source<_Base>(src.get())),
404 _M_node_count(src.get()._M_node_count),
405 _M_key_compare(_AsMoveSource(src.get()._M_key_compare)) {
406 src.get()._M_node_count = 0;
409 ~_Rb_tree() { clear(); }
410 _Self& operator=(const _Self& __x);
414 _Compare key_comp() const { return _M_key_compare; }
416 iterator begin() { return iterator(_M_leftmost()); }
417 const_iterator begin() const { return const_iterator(_M_leftmost()); }
418 iterator end() { return iterator(&this->_M_header._M_data); }
419 const_iterator end() const { return const_iterator(__CONST_CAST(_Base_ptr, &this->_M_header._M_data)); }
421 reverse_iterator rbegin() { return reverse_iterator(end()); }
422 const_reverse_iterator rbegin() const
423 { return const_reverse_iterator(end()); }
424 reverse_iterator rend() { return reverse_iterator(begin()); }
425 const_reverse_iterator rend() const
426 { return const_reverse_iterator(begin()); }
427 bool empty() const { return _M_node_count == 0; }
428 size_type size() const { return _M_node_count; }
429 size_type max_size() const { return size_type(-1); }
431 void swap(_Self& __t) {
433 if (this->empty()) return;
434 __t._M_header.swap(this->_M_header);
435 __t._M_rebind(&this->_M_header._M_data);
436 this->_M_empty_initialize();
438 else if (this->empty()) {
443 this->_M_header.swap(__t._M_header);
444 this->_M_rebind(&__t._M_header._M_data);
445 __t._M_rebind(&this->_M_header._M_data);
447 _STLP_STD::swap(_M_node_count, __t._M_node_count);
448 _STLP_STD::swap(_M_key_compare, __t._M_key_compare);
453 pair<iterator,bool> insert_unique(const value_type& __x);
454 iterator insert_equal(const value_type& __x);
456 iterator insert_unique(iterator __pos, const value_type& __x);
457 iterator insert_equal(iterator __pos, const value_type& __x);
459 #if defined (_STLP_MEMBER_TEMPLATES)
460 template<class _II> void insert_equal(_II __first, _II __last) {
461 for ( ; __first != __last; ++__first)
462 insert_equal(*__first);
464 template<class _II> void insert_unique(_II __first, _II __last) {
465 for ( ; __first != __last; ++__first)
466 insert_unique(*__first);
469 void insert_unique(const_iterator __first, const_iterator __last) {
470 for ( ; __first != __last; ++__first)
471 insert_unique(*__first);
473 void insert_unique(const value_type* __first, const value_type* __last) {
474 for ( ; __first != __last; ++__first)
475 insert_unique(*__first);
477 void insert_equal(const_iterator __first, const_iterator __last) {
478 for ( ; __first != __last; ++__first)
479 insert_equal(*__first);
481 void insert_equal(const value_type* __first, const value_type* __last) {
482 for ( ; __first != __last; ++__first)
483 insert_equal(*__first);
487 void erase(iterator __pos) {
488 _Base_ptr __x = _Rb_global_inst::_Rebalance_for_erase(__pos._M_node,
489 this->_M_header._M_data._M_parent,
490 this->_M_header._M_data._M_left,
491 this->_M_header._M_data._M_right);
492 _STLP_STD::_Destroy(&_S_value(__x));
493 this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1);
497 size_type erase(const key_type& __x) {
498 pair<iterator,iterator> __p = equal_range(__x);
499 size_type __n = distance(__p.first, __p.second);
500 erase(__p.first, __p.second);
504 size_type erase_unique(const key_type& __x) {
505 iterator __i = find(__x);
506 if (__i._M_node != &this->_M_header._M_data) {
513 void erase(iterator __first, iterator __last) {
514 if (__first._M_node == this->_M_header._M_data._M_left && // begin()
515 __last._M_node == &this->_M_header._M_data) // end()
518 while (__first != __last) erase(__first++);
521 void erase(const key_type* __first, const key_type* __last) {
522 while (__first != __last) erase(*__first++);
526 if (_M_node_count != 0) {
528 _M_leftmost() = &this->_M_header._M_data;
530 _M_rightmost() = &this->_M_header._M_data;
537 _STLP_TEMPLATE_FOR_CONT_EXT
538 iterator find(const _KT& __k) { return iterator(_M_find(__k)); }
539 _STLP_TEMPLATE_FOR_CONT_EXT
540 const_iterator find(const _KT& __k) const { return const_iterator(_M_find(__k)); }
542 _STLP_TEMPLATE_FOR_CONT_EXT
543 _Base_ptr _M_find(const _KT& __k) const {
544 _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); // Last node which is not less than __k.
545 _Base_ptr __x = _M_root(); // Current node.
548 if (!_M_key_compare(_S_key(__x), __k))
549 __y = __x, __x = _S_left(__x);
553 if (__y != &this->_M_header._M_data) {
554 if (_M_key_compare(__k, _S_key(__y))) {
555 __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);
561 _STLP_TEMPLATE_FOR_CONT_EXT
562 _Base_ptr _M_lower_bound(const _KT& __k) const {
563 _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is not less than __k. */
564 _Base_ptr __x = _M_root(); /* Current node. */
567 if (!_M_key_compare(_S_key(__x), __k))
568 __y = __x, __x = _S_left(__x);
575 _STLP_TEMPLATE_FOR_CONT_EXT
576 _Base_ptr _M_upper_bound(const _KT& __k) const {
577 _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is greater than __k. */
578 _Base_ptr __x = _M_root(); /* Current node. */
581 if (_M_key_compare(__k, _S_key(__x)))
582 __y = __x, __x = _S_left(__x);
590 _STLP_TEMPLATE_FOR_CONT_EXT
591 size_type count(const _KT& __x) const {
592 pair<const_iterator, const_iterator> __p = equal_range(__x);
593 return distance(__p.first, __p.second);
595 _STLP_TEMPLATE_FOR_CONT_EXT
596 iterator lower_bound(const _KT& __x) { return iterator(_M_lower_bound(__x)); }
597 _STLP_TEMPLATE_FOR_CONT_EXT
598 const_iterator lower_bound(const _KT& __x) const { return const_iterator(_M_lower_bound(__x)); }
599 _STLP_TEMPLATE_FOR_CONT_EXT
600 iterator upper_bound(const _KT& __x) { return iterator(_M_upper_bound(__x)); }
601 _STLP_TEMPLATE_FOR_CONT_EXT
602 const_iterator upper_bound(const _KT& __x) const { return const_iterator(_M_upper_bound(__x)); }
603 _STLP_TEMPLATE_FOR_CONT_EXT
604 pair<iterator,iterator> equal_range(const _KT& __x)
605 { return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x)); }
606 _STLP_TEMPLATE_FOR_CONT_EXT
607 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const
608 { return pair<const_iterator, const_iterator>(lower_bound(__x), upper_bound(__x)); }
609 _STLP_TEMPLATE_FOR_CONT_EXT
610 pair<iterator,iterator> equal_range_unique(const _KT& __x) {
611 pair<iterator, iterator> __p;
612 __p.second = lower_bound(__x);
613 if (__p.second._M_node != &this->_M_header._M_data &&
614 !_M_key_compare(__x, _S_key(__p.second._M_node))) {
615 __p.first = __p.second++;
618 __p.first = __p.second;
622 _STLP_TEMPLATE_FOR_CONT_EXT
623 pair<const_iterator, const_iterator> equal_range_unique(const _KT& __x) const {
624 pair<const_iterator, const_iterator> __p;
625 __p.second = lower_bound(__x);
626 if (__p.second._M_node != &this->_M_header._M_data &&
627 !_M_key_compare(__x, _S_key(__p.second._M_node))) {
628 __p.first = __p.second++;
631 __p.first = __p.second;
636 #if defined (_STLP_DEBUG)
639 bool __rb_verify() const;
643 #if defined (_STLP_DEBUG)
647 _STLP_MOVE_TO_STD_NAMESPACE
651 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
652 # include <stl/_tree.c>
655 #if defined (_STLP_DEBUG)
656 # include <stl/debug/_tree.h>
659 _STLP_BEGIN_NAMESPACE
661 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
662 #define _STLP_TEMPLATE_CONTAINER _STLP_PRIV _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>
663 #include <stl/_relops_cont.h>
664 #undef _STLP_TEMPLATE_CONTAINER
665 #undef _STLP_TEMPLATE_HEADER
667 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
668 template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
669 struct __move_traits<_STLP_PRIV _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> >
670 : _STLP_PRIV __move_traits_help2<_Compare, _Alloc> {};
675 #endif /* _STLP_INTERNAL_TREE_H */