This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
| Other format: | [Raw text] | |
This patch basically applies the same things to the rb_tree as the other container + one more thing which is to detect whether the comparison function is actually a function or an optimizable struct/class which can be derived from, and does accordingly. Also, the __is_pod struct has been changed. I have however (without telling anyone!) introduced a new namespace, which might not always be a welcome change. It's called __gnu_type_traits, because I could not find another way out! The compiler was not ready to accept the code when I put it inside the class __is_pod!??? If anyone has any objections/other better ideas, the namespace will be removed. (As it is I do not control what gets merged!) -- -Dhruv Matani. http://www.geocities.com/dhruvbird/
Attachment:
changelog_17022004
Description: Text document
diff -Ncp ./cvs_libstdc++/include/bits/cpp_type_traits.h ./modified_cvs_libstdc++/include/bits/cpp_type_traits.h
*** ./cvs_libstdc++/include/bits/cpp_type_traits.h 2004-02-09 18:23:04.000000000 +0530
--- ./modified_cvs_libstdc++/include/bits/cpp_type_traits.h 2004-02-17 18:27:57.000000000 +0530
*************** namespace std
*** 317,328 ****
//
// For the immediate use, the following is a good approximation
//
template<typename _Tp>
struct __is_pod
{
enum
{
! _M_type = __is_fundamental<_Tp>::_M_type
};
};
--- 317,344 ----
//
// For the immediate use, the following is a good approximation
//
+
+ //Dhruv: I've taken the liberty to introduce this extra namespace,
+ //because g++ can not compile these if declared within the class
+ //__is_pod itself.
+ namespace __gnu_type_traits
+ {
+ typedef char __one;
+ typedef char __two[2];
+
+ template <typename _Tp>
+ __one __test_type (int _Tp::*);
+ template <typename _Tp>
+ __two& __test_type (...);
+ }
+
+
template<typename _Tp>
struct __is_pod
{
enum
{
! _M_type = (sizeof(__gnu_type_traits::__test_type<_Tp>(0)) != sizeof(__gnu_type_traits::__one))
};
};
Common subdirectories: ./cvs_libstdc++/include/bits/CVS and ./modified_cvs_libstdc++/include/bits/CVS
diff -Ncp ./cvs_libstdc++/include/bits/stl_tree.h ./modified_cvs_libstdc++/include/bits/stl_tree.h
*** ./cvs_libstdc++/include/bits/stl_tree.h 2004-02-09 18:23:10.000000000 +0530
--- ./modified_cvs_libstdc++/include/bits/stl_tree.h 2004-02-17 18:09:17.000000000 +0530
*************** iterators invalidated are those referrin
*** 87,92 ****
--- 87,93 ----
#include <bits/allocator.h>
#include <bits/stl_construct.h>
#include <bits/stl_function.h>
+ #include <bits/cpp_type_traits.h>
namespace std
{
*************** namespace std
*** 325,331 ****
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc = allocator<_Val> >
class _Rb_tree
- : protected _Alloc::template rebind<_Rb_tree_node<_Val> >::other
{
typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
_Node_allocator;
--- 326,331 ----
*************** namespace std
*** 349,364 ****
typedef _Alloc allocator_type;
allocator_type get_allocator() const
! { return *static_cast<const _Node_allocator*>(this); }
protected:
_Rb_tree_node*
_M_get_node()
! { return _Node_allocator::allocate(1); }
void
_M_put_node(_Rb_tree_node* __p)
! { _Node_allocator::deallocate(__p, 1); }
_Link_type
_M_create_node(const value_type& __x)
--- 349,364 ----
typedef _Alloc allocator_type;
allocator_type get_allocator() const
! { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
protected:
_Rb_tree_node*
_M_get_node()
! { return _M_impl._Node_allocator::allocate(1); }
void
_M_put_node(_Rb_tree_node* __p)
! { _M_impl._Node_allocator::deallocate(__p, 1); }
_Link_type
_M_create_node(const value_type& __x)
*************** namespace std
*** 392,441 ****
}
protected:
! _Rb_tree_node_base _M_header;
! size_type _M_node_count; // keeps track of size of tree
! _Compare _M_key_compare;
protected:
_Base_ptr&
_M_root()
! { return this->_M_header._M_parent; }
_Const_Base_ptr
_M_root() const
! { return this->_M_header._M_parent; }
_Base_ptr&
_M_leftmost()
! { return this->_M_header._M_left; }
_Const_Base_ptr
_M_leftmost() const
! { return this->_M_header._M_left; }
_Base_ptr&
_M_rightmost()
! { return this->_M_header._M_right; }
_Const_Base_ptr
_M_rightmost() const
! { return this->_M_header._M_right; }
_Link_type
_M_begin()
! { return static_cast<_Link_type>(this->_M_header._M_parent); }
_Const_Link_type
_M_begin() const
! { return static_cast<_Const_Link_type>(this->_M_header._M_parent); }
_Link_type
_M_end()
! { return static_cast<_Link_type>(&this->_M_header); }
_Const_Link_type
_M_end() const
! { return static_cast<_Const_Link_type>(&this->_M_header); }
static const_reference
_S_value(_Const_Link_type __x)
--- 392,470 ----
}
protected:
! template <typename _Key_compare,
! bool _Is_Pod_Comparator = std::__is_pod<_Key_compare>::_M_type >
! struct _Rb_tree_impl
! : public _Node_allocator, public _Key_compare {
! _Rb_tree_node_base _M_header;
! size_type _M_node_count; // keeps track of size of tree
!
! _Key_compare& _M_key_compare()
! { return static_cast<_Key_compare&>(*this); }
!
! _Rb_tree_impl (const _Node_allocator& __a, const _Key_compare& __comp = _Key_compare())
! : _Node_allocator(__a), _Key_compare(__comp), _M_node_count(0) { }
! };
!
! //Specialization for _Comparison types that are not capable of
! //being base classes / super classes.
! template <typename _Key_compare>
! struct _Rb_tree_impl <_Key_compare, true>
! : public _Node_allocator {
! _Key_compare _M_key_compare_data;
! _Rb_tree_node_base _M_header;
! size_type _M_node_count; // keeps track of size of tree
!
! _Key_compare& _M_key_compare()
! { return _M_key_compare_data; }
!
! _Rb_tree_impl (const _Node_allocator& __a = _Node_allocator(),
! const _Key_compare& __comp = _Key_compare())
! : _Node_allocator(__a), _M_key_compare_data(__comp), _M_node_count(0) { }
! };
!
! _Rb_tree_impl<_Compare> _M_impl;
protected:
_Base_ptr&
_M_root()
! { return this->_M_impl._M_header._M_parent; }
_Const_Base_ptr
_M_root() const
! { return this->_M_impl._M_header._M_parent; }
_Base_ptr&
_M_leftmost()
! { return this->_M_impl._M_header._M_left; }
_Const_Base_ptr
_M_leftmost() const
! { return this->_M_impl._M_header._M_left; }
_Base_ptr&
_M_rightmost()
! { return this->_M_impl._M_header._M_right; }
_Const_Base_ptr
_M_rightmost() const
! { return this->_M_impl._M_header._M_right; }
_Link_type
_M_begin()
! { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
_Const_Link_type
_M_begin() const
! { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_parent); }
_Link_type
_M_end()
! { return static_cast<_Link_type>(&this->_M_impl._M_header); }
_Const_Link_type
_M_end() const
! { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
static const_reference
_S_value(_Const_Link_type __x)
*************** namespace std
*** 505,542 ****
public:
// allocation/deallocation
_Rb_tree()
- : _Node_allocator(allocator_type()),
- _M_node_count(0),
- _M_key_compare()
{ _M_empty_initialize(); }
_Rb_tree(const _Compare& __comp)
! : _Node_allocator(allocator_type()),
! _M_node_count(0),
! _M_key_compare(__comp)
{ _M_empty_initialize(); }
_Rb_tree(const _Compare& __comp, const allocator_type& __a)
! : _Node_allocator(__a),
! _M_node_count(0),
! _M_key_compare(__comp)
{ _M_empty_initialize(); }
_Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
! : _Node_allocator(__x.get_allocator()),
! _M_node_count(0),
! _M_key_compare(__x._M_key_compare)
{
if (__x._M_root() == 0)
_M_empty_initialize();
else
{
! this->_M_header._M_color = _S_red;
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
}
! _M_node_count = __x._M_node_count;
}
~_Rb_tree()
--- 534,562 ----
public:
// allocation/deallocation
_Rb_tree()
{ _M_empty_initialize(); }
_Rb_tree(const _Compare& __comp)
! : _M_impl(allocator_type(), __comp)
{ _M_empty_initialize(); }
_Rb_tree(const _Compare& __comp, const allocator_type& __a)
! : _M_impl(__a, __comp)
{ _M_empty_initialize(); }
_Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
! : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare())
{
if (__x._M_root() == 0)
_M_empty_initialize();
else
{
! this->_M_impl._M_header._M_color = _S_red;
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
}
! _M_impl._M_node_count = __x._M_impl._M_node_count;
}
~_Rb_tree()
*************** namespace std
*** 549,555 ****
void _M_empty_initialize()
{
// Used to distinguish header from __root, in iterator.operator++.
! this->_M_header._M_color = _S_red;
_M_root() = 0;
_M_leftmost() = _M_end();
_M_rightmost() = _M_end();
--- 569,575 ----
void _M_empty_initialize()
{
// Used to distinguish header from __root, in iterator.operator++.
! this->_M_impl._M_header._M_color = _S_red;
_M_root() = 0;
_M_leftmost() = _M_end();
_M_rightmost() = _M_end();
*************** namespace std
*** 559,581 ****
// Accessors.
_Compare
key_comp() const
! { return _M_key_compare; }
iterator
begin()
! { return static_cast<_Link_type>(this->_M_header._M_left); }
const_iterator
begin() const
! { return static_cast<_Const_Link_type>(this->_M_header._M_left); }
iterator
end()
! { return static_cast<_Link_type>(&this->_M_header); }
const_iterator
end() const
! { return static_cast<_Const_Link_type>(&this->_M_header); }
reverse_iterator
rbegin()
--- 579,601 ----
// Accessors.
_Compare
key_comp() const
! { return _M_impl._M_key_compare(); }
iterator
begin()
! { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
const_iterator
begin() const
! { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); }
iterator
end()
! { return static_cast<_Link_type>(&this->_M_impl._M_header); }
const_iterator
end() const
! { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
reverse_iterator
rbegin()
*************** namespace std
*** 595,605 ****
bool
empty() const
! { return _M_node_count == 0; }
size_type
size() const
! { return _M_node_count; }
size_type
max_size() const
--- 615,625 ----
bool
empty() const
! { return _M_impl._M_node_count == 0; }
size_type
size() const
! { return _M_impl._M_node_count; }
size_type
max_size() const
*************** namespace std
*** 648,654 ****
_M_leftmost() = _M_end();
_M_root() = 0;
_M_rightmost() = _M_end();
! _M_node_count = 0;
}
// Set operations.
--- 668,674 ----
_M_leftmost() = _M_end();
_M_root() = 0;
_M_rightmost() = _M_end();
! _M_impl._M_node_count = 0;
}
// Set operations.
*************** namespace std
*** 749,761 ****
{
// Note that _Key may be a constant type.
clear();
! _M_key_compare = __x._M_key_compare;
if (__x._M_root() != 0)
{
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
! _M_node_count = __x._M_node_count;
}
}
return *this;
--- 769,781 ----
{
// Note that _Key may be a constant type.
clear();
! _M_impl._M_key_compare() = __x._M_impl._M_key_compare();
if (__x._M_root() != 0)
{
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
! _M_impl._M_node_count = __x._M_impl._M_node_count;
}
}
return *this;
*************** namespace std
*** 771,780 ****
bool __insert_left;
__insert_left = __x != 0 || __p == _M_end()
! || _M_key_compare(_KeyOfValue()(__v), _S_key(__p));
! _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, this->_M_header);
! ++_M_node_count;
return iterator(__z);
}
--- 791,800 ----
bool __insert_left;
__insert_left = __x != 0 || __p == _M_end()
! || _M_impl._M_key_compare()(_KeyOfValue()(__v), _S_key(__p));
! _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, this->_M_impl._M_header);
! ++_M_impl._M_node_count;
return iterator(__z);
}
*************** namespace std
*** 789,795 ****
while (__x != 0)
{
__y = __x;
! __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
_S_left(__x) : _S_right(__x);
}
return _M_insert(__x, __y, __v);
--- 809,815 ----
while (__x != 0)
{
__y = __x;
! __x = _M_impl._M_key_compare()(_KeyOfValue()(__v), _S_key(__x)) ?
_S_left(__x) : _S_right(__x);
}
return _M_insert(__x, __y, __v);
*************** namespace std
*** 836,843 ****
__t._M_root()->_M_parent = __t._M_end();
}
// No need to swap header's color as it does not change.
! std::swap(this->_M_node_count, __t._M_node_count);
! std::swap(this->_M_key_compare, __t._M_key_compare);
}
template<typename _Key, typename _Val, typename _KeyOfValue,
--- 856,863 ----
__t._M_root()->_M_parent = __t._M_end();
}
// No need to swap header's color as it does not change.
! std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
! std::swap(this->_M_impl._M_key_compare(), __t._M_impl._M_key_compare());
}
template<typename _Key, typename _Val, typename _KeyOfValue,
*************** namespace std
*** 853,859 ****
while (__x != 0)
{
__y = __x;
! __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
__x = __comp ? _S_left(__x) : _S_right(__x);
}
iterator __j = iterator(__y);
--- 873,879 ----
while (__x != 0)
{
__y = __x;
! __comp = _M_impl._M_key_compare()(_KeyOfValue()(__v), _S_key(__x));
__x = __comp ? _S_left(__x) : _S_right(__x);
}
iterator __j = iterator(__y);
*************** namespace std
*** 862,868 ****
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
else
--__j;
! if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
return pair<iterator,bool>(__j, false);
}
--- 882,888 ----
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
else
--__j;
! if (_M_impl._M_key_compare()(_S_key(__j._M_node), _KeyOfValue()(__v)))
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
return pair<iterator,bool>(__j, false);
}
*************** namespace std
*** 877,883 ****
{
// begin()
if (size() > 0
! && _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
return _M_insert(__position._M_node, __position._M_node, __v);
// first argument just needs to be non-null
else
--- 897,903 ----
{
// begin()
if (size() > 0
! && _M_impl._M_key_compare()(_KeyOfValue()(__v), _S_key(__position._M_node)))
return _M_insert(__position._M_node, __position._M_node, __v);
// first argument just needs to be non-null
else
*************** namespace std
*** 886,892 ****
else if (__position._M_node == _M_end())
{
// end()
! if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
return _M_insert(0, _M_rightmost(), __v);
else
return insert_unique(__v).first;
--- 906,912 ----
else if (__position._M_node == _M_end())
{
// end()
! if (_M_impl._M_key_compare()(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
return _M_insert(0, _M_rightmost(), __v);
else
return insert_unique(__v).first;
*************** namespace std
*** 895,902 ****
{
iterator __before = __position;
--__before;
! if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v))
! && _M_key_compare(_KeyOfValue()(__v),_S_key(__position._M_node)))
{
if (_S_right(__before._M_node) == 0)
return _M_insert(0, __before._M_node, __v);
--- 915,922 ----
{
iterator __before = __position;
--__before;
! if (_M_impl._M_key_compare()(_S_key(__before._M_node), _KeyOfValue()(__v))
! && _M_impl._M_key_compare()(_KeyOfValue()(__v),_S_key(__position._M_node)))
{
if (_S_right(__before._M_node) == 0)
return _M_insert(0, __before._M_node, __v);
*************** namespace std
*** 919,925 ****
{
// begin()
if (size() > 0
! && !_M_key_compare(_S_key(__position._M_node),
_KeyOfValue()(__v)))
return _M_insert(__position._M_node, __position._M_node, __v);
// first argument just needs to be non-null
--- 939,945 ----
{
// begin()
if (size() > 0
! && !_M_impl._M_key_compare()(_S_key(__position._M_node),
_KeyOfValue()(__v)))
return _M_insert(__position._M_node, __position._M_node, __v);
// first argument just needs to be non-null
*************** namespace std
*** 929,935 ****
else if (__position._M_node == _M_end())
{
// end()
! if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
return _M_insert(0, _M_rightmost(), __v);
else
return insert_equal(__v);
--- 949,955 ----
else if (__position._M_node == _M_end())
{
// end()
! if (!_M_impl._M_key_compare()(_KeyOfValue()(__v), _S_key(_M_rightmost())))
return _M_insert(0, _M_rightmost(), __v);
else
return insert_equal(__v);
*************** namespace std
*** 938,945 ****
{
iterator __before = __position;
--__before;
! if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
! && !_M_key_compare(_S_key(__position._M_node),
_KeyOfValue()(__v)))
{
if (_S_right(__before._M_node) == 0)
--- 958,965 ----
{
iterator __before = __position;
--__before;
! if (!_M_impl._M_key_compare()(_KeyOfValue()(__v), _S_key(__before._M_node))
! && !_M_impl._M_key_compare()(_S_key(__position._M_node),
_KeyOfValue()(__v)))
{
if (_S_right(__before._M_node) == 0)
*************** namespace std
*** 982,990 ****
{
_Link_type __y =
static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
! this->_M_header));
destroy_node(__y);
! --_M_node_count;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
--- 1002,1010 ----
{
_Link_type __y =
static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
! this->_M_impl._M_header));
destroy_node(__y);
! --_M_impl._M_node_count;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
*************** namespace std
*** 1080,1092 ****
_Link_type __y = _M_end(); // Last node which is not less than __k.
while (__x != 0)
! if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
iterator __j = iterator(__y);
! return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
end() : __j;
}
--- 1100,1112 ----
_Link_type __y = _M_end(); // Last node which is not less than __k.
while (__x != 0)
! if (!_M_impl._M_key_compare()(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
iterator __j = iterator(__y);
! return (__j == end() || _M_impl._M_key_compare()(__k, _S_key(__j._M_node))) ?
end() : __j;
}
*************** namespace std
*** 1101,1113 ****
while (__x != 0)
{
! if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
}
const_iterator __j = const_iterator(__y);
! return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
end() : __j;
}
--- 1121,1133 ----
while (__x != 0)
{
! if (!_M_impl._M_key_compare()(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
}
const_iterator __j = const_iterator(__y);
! return (__j == end() || _M_impl._M_key_compare()(__k, _S_key(__j._M_node))) ?
end() : __j;
}
*************** namespace std
*** 1132,1138 ****
_Link_type __y = _M_end(); // Last node which is not less than __k.
while (__x != 0)
! if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
--- 1152,1158 ----
_Link_type __y = _M_end(); // Last node which is not less than __k.
while (__x != 0)
! if (!_M_impl._M_key_compare()(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
*************** namespace std
*** 1150,1156 ****
_Const_Link_type __y = _M_end(); // Last node which is not less than __k.
while (__x != 0)
! if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
--- 1170,1176 ----
_Const_Link_type __y = _M_end(); // Last node which is not less than __k.
while (__x != 0)
! if (!_M_impl._M_key_compare()(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
*************** namespace std
*** 1168,1174 ****
_Link_type __y = _M_end(); // Last node which is greater than __k.
while (__x != 0)
! if (_M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
--- 1188,1194 ----
_Link_type __y = _M_end(); // Last node which is greater than __k.
while (__x != 0)
! if (_M_impl._M_key_compare()(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
*************** namespace std
*** 1186,1192 ****
_Const_Link_type __y = _M_end(); // Last node which is greater than __k.
while (__x != 0)
! if (_M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
--- 1206,1212 ----
_Const_Link_type __y = _M_end(); // Last node which is greater than __k.
while (__x != 0)
! if (_M_impl._M_key_compare()(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
*************** namespace std
*** 1224,1233 ****
bool
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
{
! if (_M_node_count == 0 || begin() == end())
! return _M_node_count == 0 && begin() == end()
! && this->_M_header._M_left == _M_end()
! && this->_M_header._M_right == _M_end();
unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
for (const_iterator __it = begin(); __it != end(); ++__it)
--- 1244,1253 ----
bool
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
{
! if (_M_impl._M_node_count == 0 || begin() == end())
! return _M_impl._M_node_count == 0 && begin() == end()
! && this->_M_impl._M_header._M_left == _M_end()
! && this->_M_impl._M_header._M_right == _M_end();
unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
for (const_iterator __it = begin(); __it != end(); ++__it)
*************** namespace std
*** 1241,1249 ****
|| (__R && __R->_M_color == _S_red))
return false;
! if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
return false;
! if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
return false;
if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
--- 1261,1269 ----
|| (__R && __R->_M_color == _S_red))
return false;
! if (__L && _M_impl._M_key_compare()(_S_key(__x), _S_key(__L)))
return false;
! if (__R && _M_impl._M_key_compare()(_S_key(__R), _S_key(__x)))
return false;
if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |