wrapper class for STL lists

[Christian Chrismann]

Hi,

an application uses a wrapper class for an STL list. Basically,
this template class provides the same functions (delete, append, find...)
as an ordinary STL list. Additionally, there are some convenient functions
for iterating through the list.

For instance, to go through all elements of the list (after fetching the
first list element), the class provides a function that looks as follows:

template <class ELEMENT>
ELEMENT* myList<ELEMENT>::GetNextElement()
{
if (mylist.empty() || current_elem == NULL)
{
current_elem = NULL;
return NULL;
}

ELEMENT *element = *current_elem;

if (current_elem != (--(mylist.end() ) ) )
++current_elem;
else
current_elem = NULL;

return element;
}

The fast access to the next list element is given by "current_elem". This
is just an iterator pointing to an element of the wrapped STL list in the
class myList:

list<ELEMENT*>::iterator current_elem;

I've profiled an application that uses this wrapper class "myList" with
gprof and figured out that a substantial fraction of the program run-time
is spent in the function "GetNextElement" and some other function of the
class myList. I suppose that this wrapper class is not very efficient
since the iterator "current_elem" has to be adjusted at many porgram
points in order to update the currently considered list element. So, the
benefit of having a pointer to the current element and saving searching
for it in the list is degraded by the frequent update of the iterator.

Are you of the opinion that this wrapper class is redundant and that it
might be implemented more efficiently when pure STL lists and their
functions would be used?

Regards,
Chris

 

[Victor Bazarov]

an application uses a wrapper class for an STL list. Basically,
this template class provides the same functions (delete, append,
find...) as an ordinary STL list. Additionally, there are some
convenient functions for iterating through the list.

What's the convenience of them? What's not convenient about, say,
'std::list::erase' or 'std::list:ush_back'?

For instance, to go through all elements of the list (after fetching
the first list element), the class provides a function that looks as
follows:

Why? What's not fitting about 'std::for_each'?

template <class ELEMENT>
ELEMENT* myList<ELEMENT>::GetNextElement()
{ [..]
}

[..]
I've profiled an application that uses this wrapper class "myList"
with gprof and figured out that a substantial fraction of the program
run-time is spent in the function "GetNextElement" and some other
function of the class myList. I suppose that this wrapper class is
not very efficient since the iterator "current_elem" has to be
adjusted at many porgram points in order to update the currently
considered list element. So, the benefit of having a pointer to the
current element and saving searching for it in the list is degraded
by the frequent update of the iterator.

Are you of the opinion that this wrapper class is redundant and that
it might be implemented more efficiently when pure STL lists and their
functions would be used?

I am of the opinion that reinveting the wheel, especially if the results
are not satisfactory, is a waste of time.

V

 

[peter koch]

Christian Chrismann skrev:

Hi,

an application uses a wrapper class for an STL list. Basically,
this template class provides the same functions (delete, append, find...)
as an ordinary STL list. Additionally, there are some convenient functions
for iterating through the list.

This makes me wonder why you wrap it at all.

For instance, to go through all elements of the list (after fetching the
first list element), the class provides a function that looks as follows:

template <class ELEMENT>
ELEMENT* myList<ELEMENT>::GetNextElement()
{
if (mylist.empty() || current_elem == NULL)
{
current_elem = NULL;
return NULL;
}

ELEMENT *element = *current_elem;

if (current_elem != (--(mylist.end() ) ) )
++current_elem;
else
current_elem = NULL;

return element;
}

The fast access to the next list element is given by "current_elem". This
is just an iterator pointing to an element of the wrapped STL list in the
class myList:

list<ELEMENT*>::iterator current_elem;

I've profiled an application that uses this wrapper class "myList" with
gprof and figured out that a substantial fraction of the program run-time
is spent in the function "GetNextElement" and some other function of the
class myList. I suppose that this wrapper class is not very efficient
since the iterator "current_elem" has to be adjusted at many porgram
points in order to update the currently considered list element. So, the
benefit of having a pointer to the current element and saving searching
for it in the list is degraded by the frequent update of the iterator.

That function does not look as if it is the fastest on the earth. But
you will not get a substantially faster functionality (e.g. twice as
fast) for std::list if it has a reasonable size. Most time spent with
modern processors on large lists is time to read from primary memory
and you can't eliminate that time ever - except by using a structure
different from list.

Are you of the opinion that this wrapper class is redundant and that it
might be implemented more efficiently when pure STL lists and their
functions would be used?

Yes. Use std::for_each or one of its cousins.