This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Context diff for: Suggested improvement to std::list
- From: "Gawain Bolton" <boltong at nortelnetworks dot com>
- To: libstdc++ at gcc dot gnu dot org
- Date: Wed, 12 Feb 2003 18:15:55 +0100
- Subject: Context diff for: Suggested improvement to std::list
- Organization: Nortel Networks
Sorry for resending this but a context diff was requested. See attached
file.
Hello,
I would like to humbly suggest an improvement to the std::list container
class. This improvement does the following:
* reduces amount of memory required
o the _List_alloc_base class contains a _List_node_base member
rather than using _List_node<_Tp>.
* improve performance when creating and destroying lists
o the constructor no longer allocates memory, since the _M_node
member in the _List_alloc_base class is not a pointer.
o this offers a big improvement when creating temporary list
objects
Where's the catch? Well, the swap() function is seriously more
complicated. That said, it is still constant time and cannot generate
an exception. Is it reasonable to accept the hit for swap? I believe
so. The one function which makes heavy use of swap() is sort(). But
this function gets a big improvement because the 65 temporary list
objects are going to take much less time to be created and destroyed.
Please find attached the proposed patch for stl_list.h based on the
version in GCC 3.2.2.
This has been tested with all the list_* tests in
gcc-3.2.2/libstdc++-v3/testsuite/23_containers on Solaris.
A similar thing can be done for std::map, std::multimap, std::set and
std::multiset by changing the _M_header field in the _Rb_tree_alloc_base
class in stl_tree.h. Even better, the swap() function would still be
very simple. If people thing this is worth doing I would happy to
submit a patch.
Cheers,
Gawain
--
-------------------------------------------------------------------------------
Gawain Bolton | E-mail: boltong@nortelnetworks.com
Section 4808 | Internal mail stop: CT45
UMTS Development |
Nortel Networks | Voice: ESN 579-3763 +33
1.39.44.37.63
Guyancourt, France | FAX: ESN 579-3009 +33
1.39.44.30.09
-------------------------------------------------------------------------------
*** /home/boltong/gcc/include/c++/3.2.2/bits/stl_list.h.orig Fri Feb 7 12:13:08 2003
--- /home/boltong/gcc/include/c++/3.2.2/bits/stl_list.h Wed Feb 12 17:18:17 2003
***************
*** 122,128 ****
typedef _Ref reference;
typedef _List_node<_Tp> _Node;
! _List_iterator(_Node* __x)
: _List_iterator_base(__x)
{ }
--- 122,128 ----
typedef _Ref reference;
typedef _List_node<_Tp> _Node;
! _List_iterator(_List_node_base* __x)
: _List_iterator_base(__x)
{ }
***************
*** 210,216 ****
typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
_Node_allocator;
! _List_node<_Tp>* _M_node;
};
// Specialization for instanceless allocators.
--- 210,216 ----
typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
_Node_allocator;
! _List_node_base _M_node;
};
// Specialization for instanceless allocators.
***************
*** 242,248 ****
{ _Alloc_type::deallocate(__p, 1); }
protected:
! _List_node<_Tp>* _M_node;
};
template<typename _Tp, typename _Alloc>
--- 242,248 ----
{ _Alloc_type::deallocate(__p, 1); }
protected:
! _List_node_base _M_node;
};
template<typename _Tp, typename _Alloc>
***************
*** 259,273 ****
_List_base(const allocator_type& __a)
: _Base(__a)
{
! _M_node = _M_get_node();
! _M_node->_M_next = _M_node;
! _M_node->_M_prev = _M_node;
}
~_List_base()
{
clear();
- _M_put_node(_M_node);
}
void clear();
--- 259,271 ----
_List_base(const allocator_type& __a)
: _Base(__a)
{
! _M_node._M_next = &_M_node;
! _M_node._M_prev = &_M_node;
}
~_List_base()
{
clear();
}
void clear();
***************
*** 362,380 ****
iterator
begin()
! { return static_cast<_Node*>(_M_node->_M_next); }
const_iterator
begin() const
! { return static_cast<_Node*>(_M_node->_M_next); }
iterator
end()
! { return _M_node; }
const_iterator
end() const
! { return _M_node; }
reverse_iterator
rbegin()
--- 360,378 ----
iterator
begin()
! { return _M_node._M_next; }
const_iterator
begin() const
! { return _M_node._M_next; }
iterator
end()
! { return &_M_node; }
const_iterator
end() const
! { return const_cast<_List_node_base*>(&_M_node); }
reverse_iterator
rbegin()
***************
*** 394,400 ****
bool
empty() const
! { return _M_node->_M_next == _M_node; }
size_type
size() const
--- 392,398 ----
bool
empty() const
! { return _M_node._M_next == &_M_node; }
size_type
size() const
***************
*** 421,428 ****
{ return *(--end()); }
void
! swap(list<_Tp, _Alloc>& __x)
! { std::swap(_M_node, __x._M_node); }
iterator
insert(iterator __position, const _Tp& __x)
--- 419,425 ----
{ return *(--end()); }
void
! swap(list<_Tp, _Alloc>& __x);
iterator
insert(iterator __position, const _Tp& __x)
***************
*** 709,726 ****
void _List_base<_Tp,_Alloc>::
clear()
{
! _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next);
! while (__cur != _M_node) {
_List_node<_Tp>* __tmp = __cur;
__cur = static_cast<_List_node<_Tp>*>(__cur->_M_next);
_Destroy(&__tmp->_M_data);
_M_put_node(__tmp);
}
! _M_node->_M_next = _M_node;
! _M_node->_M_prev = _M_node;
}
template<typename _Tp, typename _Alloc>
template <typename _InputIter>
void list<_Tp, _Alloc>::
_M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last,
--- 706,756 ----
void _List_base<_Tp,_Alloc>::
clear()
{
! _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node._M_next);
! while (__cur != &_M_node) {
_List_node<_Tp>* __tmp = __cur;
__cur = static_cast<_List_node<_Tp>*>(__cur->_M_next);
_Destroy(&__tmp->_M_data);
_M_put_node(__tmp);
}
! _M_node._M_next = &_M_node;
! _M_node._M_prev = &_M_node;
}
template<typename _Tp, typename _Alloc>
+ void list<_Tp, _Alloc>::
+ swap(list<_Tp, _Alloc>& __x)
+ {
+ if ( _M_node._M_next == &_M_node )
+ {
+ if ( __x._M_node._M_next != &__x._M_node )
+ {
+ _M_node._M_next = __x._M_node._M_next;
+ _M_node._M_prev = __x._M_node._M_prev;
+
+ _M_node._M_next->_M_prev = _M_node._M_prev->_M_next = &_M_node;
+ __x._M_node._M_next = __x._M_node._M_prev = &__x._M_node;
+ }
+ }
+ else if ( __x._M_node._M_next == &__x._M_node )
+ {
+ __x._M_node._M_next = _M_node._M_next;
+ __x._M_node._M_prev = _M_node._M_prev;
+
+ __x._M_node._M_next->_M_prev = __x._M_node._M_prev->_M_next = &__x._M_node;
+ _M_node._M_next = _M_node._M_prev = &_M_node;
+ }
+ else
+ {
+ std::swap(_M_node._M_next,__x._M_node._M_next);
+ std::swap(_M_node._M_prev,__x._M_node._M_prev);
+
+ _M_node._M_next->_M_prev = _M_node._M_prev->_M_next = &_M_node;
+ __x._M_node._M_next->_M_prev = __x._M_node._M_prev->_M_next = &__x._M_node;
+ }
+ }
+
+ template<typename _Tp, typename _Alloc>
template <typename _InputIter>
void list<_Tp, _Alloc>::
_M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last,
***************
*** 871,877 ****
template<typename _Tp, typename _Alloc>
inline void list<_Tp, _Alloc>::
reverse()
! { __List_base_reverse(this->_M_node); }
template<typename _Tp, typename _Alloc>
void list<_Tp, _Alloc>::
--- 901,907 ----
template<typename _Tp, typename _Alloc>
inline void list<_Tp, _Alloc>::
reverse()
! { __List_base_reverse(&_M_node); }
template<typename _Tp, typename _Alloc>
void list<_Tp, _Alloc>::
***************
*** 878,884 ****
sort()
{
// Do nothing if the list has length 0 or 1.
! if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
list<_Tp, _Alloc> __carry;
list<_Tp, _Alloc> __counter[64];
int __fill = 0;
--- 908,914 ----
sort()
{
// Do nothing if the list has length 0 or 1.
! if (_M_node._M_next != &_M_node && _M_node._M_next->_M_next != &_M_node) {
list<_Tp, _Alloc> __carry;
list<_Tp, _Alloc> __counter[64];
int __fill = 0;
***************
*** 958,964 ****
sort(_StrictWeakOrdering __comp)
{
// Do nothing if the list has length 0 or 1.
! if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
list<_Tp, _Alloc> __carry;
list<_Tp, _Alloc> __counter[64];
int __fill = 0;
--- 988,994 ----
sort(_StrictWeakOrdering __comp)
{
// Do nothing if the list has length 0 or 1.
! if (_M_node._M_next != &_M_node && _M_node._M_next->_M_next != &_M_node) {
list<_Tp, _Alloc> __carry;
list<_Tp, _Alloc> __counter[64];
int __fill = 0;