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] | |
Hello,
This is a patch for stl_tree.h, which makes the _M_key_compare data
member s function, so that the specialization of _M_impl for PODs can be
used correctly.
I have attached another test, which shows the difference between the
sizes when used with a function comparator.
--
-Dhruv Matani.
http://www.geocities.com/dhruvbird/
Proud to be a Vegetarian.
http://www.vegetarianstarterkit.com/
http://www.vegkids.com/vegkids/index.html
*** stl_tree.h 2004-03-31 02:34:19.000000000 +0530
--- /home/dhruv/TEMP/stl_tree.h 2004-04-15 08:10:22.000000000 +0530
*************** namespace std
*** 391,405 ****
protected:
template<typename _Key_compare,
bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type>
! struct _Rb_tree_impl : public _Node_allocator
{
- _Key_compare _M_key_compare;
_Rb_tree_node_base _M_header;
size_type _M_node_count; // Keeps track of size of tree.
_Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
const _Key_compare& __comp = _Key_compare())
! : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
{
this->_M_header._M_color = _S_red;
this->_M_header._M_parent = 0;
--- 391,408 ----
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 = _Node_allocator(),
const _Key_compare& __comp = _Key_compare())
! : _Node_allocator(__a), _Key_compare(__comp), _M_node_count(0)
{
this->_M_header._M_color = _S_red;
this->_M_header._M_parent = 0;
*************** namespace std
*** 413,425 ****
template<typename _Key_compare>
struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator
{
! _Key_compare _M_key_compare;
_Rb_tree_node_base _M_header;
size_type _M_node_count; // Keeps track of size of tree.
_Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
const _Key_compare& __comp = _Key_compare())
! : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
{
this->_M_header._M_color = _S_red;
this->_M_header._M_parent = 0;
--- 416,432 ----
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)
{
this->_M_header._M_color = _S_red;
this->_M_header._M_parent = 0;
*************** namespace std
*** 428,434 ****
}
};
! _Rb_tree_impl<_Compare> _M_impl;
protected:
_Base_ptr&
--- 435,441 ----
}
};
! mutable _Rb_tree_impl<_Compare> _M_impl;
protected:
_Base_ptr&
*************** namespace std
*** 461,467 ****
_Const_Link_type
_M_begin() const
! { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_parent); }
_Link_type
_M_end()
--- 468,477 ----
_Const_Link_type
_M_begin() const
! {
! return static_cast<_Const_Link_type>
! (this->_M_impl._M_header._M_parent);
! }
_Link_type
_M_end()
*************** namespace std
*** 550,556 ****
{ }
_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)
{
--- 560,566 ----
{ }
_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)
{
*************** namespace std
*** 570,576 ****
// Accessors.
_Compare
key_comp() const
! { return _M_impl._M_key_compare; }
iterator
begin()
--- 580,586 ----
// Accessors.
_Compare
key_comp() const
! { return _M_impl._M_key_compare(); }
iterator
begin()
*************** namespace std
*** 578,584 ****
const_iterator
begin() const
! { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); }
iterator
end()
--- 588,597 ----
const_iterator
begin() const
! {
! return static_cast<_Const_Link_type>
! (this->_M_impl._M_header._M_left);
! }
iterator
end()
*************** namespace std
*** 760,766 ****
{
// 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());
--- 773,779 ----
{
// 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());
*************** namespace std
*** 782,788 ****
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,
--- 795,801 ----
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,
*************** namespace std
*** 802,808 ****
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);
--- 815,821 ----
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
*** 850,856 ****
}
// 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,
--- 863,869 ----
}
// 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
*** 866,872 ****
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);
--- 879,885 ----
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
*** 875,881 ****
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);
}
--- 888,894 ----
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
*** 890,896 ****
{
// 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.
--- 903,909 ----
{
// 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.
*************** namespace std
*** 900,906 ****
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
--- 913,919 ----
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
*************** namespace std
*** 910,918 ****
{
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)
--- 923,931 ----
{
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)
*************** namespace std
*** 936,942 ****
{
// 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
--- 949,955 ----
{
// 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
*** 946,952 ****
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
--- 959,965 ----
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
*************** namespace std
*** 956,964 ****
{
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)
--- 969,977 ----
{
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
*** 1000,1007 ****
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
{
_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;
}
--- 1013,1021 ----
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
{
_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;
}
*************** namespace std
*** 1099,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;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
--- 1113,1126 ----
_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;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
*************** namespace std
*** 1120,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;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
--- 1134,1147 ----
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;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
*************** namespace std
*** 1151,1157 ****
_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);
--- 1165,1171 ----
_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
*** 1169,1175 ****
_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);
--- 1183,1189 ----
_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
*** 1187,1193 ****
_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);
--- 1201,1207 ----
_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
*** 1205,1211 ****
_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);
--- 1219,1225 ----
_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
*** 1260,1268 ****
|| (__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)
--- 1274,1282 ----
|| (__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)
Attachment:
ChangeLog
Description: Text document
#include <iostream>
#include <map>
using namespace std;
template <typename Map_Type>
void do_test(typename Map_Type::key_compare _comp = typename Map_Type::key_compare())
{
typename Map_Type::value_type temp[10] =
{
make_pair(0, 0),
make_pair(1, 10),
make_pair(2, 20),
make_pair(5, 90),
make_pair(3, 6),
};
Map_Type _map(temp, temp+10, _comp);
std::cout<<"Size of std::map is: "<<sizeof(Map_Type)<<std::endl;
typename Map_Type::const_iterator i = _map.begin();
i = _map.find(i->first);
}
bool less_int(int a, int b) { return a < b; }
int main()
{
do_test<std::map<int, int> >();
do_test<const std::map<int, int> >();
do_test<const std::map<int, int, const std::less<int> > >();
do_test<std::map<int, int, const std::less<int> > >();
do_test<const std::map<int, int, typeof(&less_int) > >(less_int);
do_test<std::map<int, int, typeof(&less_int) > >(less_int);
do_test<const std::map<int, int, const typeof(&less_int) > >(less_int);
do_test<std::map<int, int, const typeof(&less_int) > >(less_int);
}
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |