When is std::list more effective than the other containers?

[Josh Mcfarlane]

Just out of curiosity:

When would using std::list be more efficient / effective than using
other containers such as vector, deque, etc?

As far as I'm aware, list doesn't appear to be specialized for
anything.

Thanks,
Josh McFarlane

[Alf P. Steinbach]

* Niklas Norrthon:

... once vector has reserved some memory it's not returned
to the memory manager until the entire vector is destroyed, while
memory used by a list node is returned as soon as that node is
erased.

You can (in practice) "compact" a vector by copying and swapping,
something like

template< typename T >
void compact( std::vector<T>& v )
{
std::vector<T> copy( v.size() );
copy.assign( v.begin(), v.end() );
v.swap( copy );
}

Disclaimer: untested code.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Axter]

Niklas Norrthon wrote:

"Axter" <go****@axter.c om> writes:

pepp wrote:

The runtime of list for
deletion and insertion operation is better than vectors.

When you delete anything from vector, all the iterators after that item
must be reassigned. no such thing wtih list.

That's not entirely correct.
This only happens when deleting from the center or beginning of the
vector.

deleting from the end of the vector does not cause this.

Wrong:

#include <vector>
using std::vector;

typedef vector<int> Vec;
typedef Vec::const_iter ator Const_Iter;

int main()
{
/* first we set up things */
Vec foo;
foo.push_back(1 );
foo.push_back(2 );

/* get an iterator to after the last item of the vector: */
Const_iter last = foo.end();

/* now it's time to delete from the end of the vector */
foo.pop_back();

/* if pepp's statement had been correct the following
* would be ok, but last is invalidated by the pop_back
* and this is UB */

for (Const_Iter i = foo.begin(); i != last; ++i) {
/* do something here */
}
return 0;

Niklas Norrthon,
Exactly what was wrong?
Your code doesn't seem to prove anything related to my comment.
Are you sure you replied to the right post?

I stand my initial post, in the it's incorrect to say that "When you
delete anything from vector, all the iterators after that item must be
reassigned".
Because if you delete from the end, there are no more iterators after
that item.
Moreover, if you're using a std::deque, and you delete from the end or
beginning, you also don't have the reassignment issue.

[Axter]

Niklas Norrthon wrote:

"g" <ge*******@yaho o.com> writes:

It's optimized for insertions and sorting. Since the
order of elements is based on links, elements don't
have to be moved to sort or insert, which drastically
speeds those processes.

Try doing that with a vector! Oh, lordy...
You'd need to move thousands of bytes of data around,
possibly repeatedly re-allocating huge memory blocks.
Very inefficient.

not if you use pointers....... .

But then I have other problems, like ownership and lifetime
to worry about...

You can fix ownership and lifetime problem by using smart pointers like
boost::shared_p tr, clone smart pointers, or COW smart pointers:
http://www.boost.org/libs/smart_ptr/shared_ptr.htm (boost::shared_ ptr)
http://code.axter.com/copy_ptr.h (A clone smart pointer)
http://code.axter.com/cow_ptr.h (COW Copy On Write)

Don't try using auto_ptr on STL containers, because it's usage in
containers is not portable, and when fully implemented, not compilable.

[Kai-Uwe Bux]

Alf P. Steinbach wrote:

* Kai-Uwe Bux:

It is *consensus*
that list is better if insertions/deletions occur in other places than
the end.

I don't want to get into this analysis so won't discuss details (and I
think the most important property of container is how convenient it is for
the problem at hand!), but perhaps you haven't heard of cursor gaps, an
array
based logical list technique technique -- if you, or whoever is reading
this, haven't, look them up, or, just implement a simple text editor...
;-)

Ah, the fun of writing a text editor. At one point, I investigated how
different editors handle text. If I recall correctly, emacs features a
buffer gap. For an editor, this is a reasonable thing, since most of the
time consecutive insertions happen at the same place. Random insertions
and deletions, however, are still inefficient. I ended up implementing a
rope like data structure that also supports efficient line numbering and
that helps with the undo feature, too.
Best

Kai-Uwe Bux

[Alf P. Steinbach]

* Kai-Uwe Bux:

It is *consensus*
that list is better if insertions/deletions occur in other places than the
end.

I don't want to get into this analysis so won't discuss details (and I think
the most important property of container is how convenient it is for the
problem at hand!), but perhaps you haven't heard of cursor gaps, an array
based logical list technique technique -- if you, or whoever is reading
this, haven't, look them up, or, just implement a simple text editor... ;-)

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Diego Martins]

this is better:

template< typename T >
void compact( std::vector<T>& v )
{ std::vector<T>( v).swap(v); }

chapter 17 - Effective STL - Scott Meyers :-)

[roberts.noah]

Kai-Uwe Bux wrote:

a) A vector is not just "almost" guaranteed to be contiguous. It is
contiguous. The standard implies that.

Being guaranteed and being implied are two very different things. An
implementation is free to implement a vector any way they want. The
requirements of the interface mean that there will probably never be
anything but a contiguous vector but there could be if an
implementation could meet those requirements without being contiguous.

In Thinking in C++ V2, Bruce Eckel claims this is a shortsight of the
standard to be fixed in the future. So, someday maybe it will be
guaranteed but today it is not. Frankly I don't agree; if a vector
could be better made non-contiguous then it doesn't bother me one bit
so long as it appears to be to me (assuming I don't try direct access
to the memory *p = &vect[0]).

[roberts.noah]

Axter wrote:

roberts.n...@gm ail.com wrote:

I don't agree. Every container serves a particular purpose. It could
be that in YOUR case most development domains seem to be least served
by the list container there are certainly a lot of cases when a list is
a very appropriate choice. The best thing is to understand the
implementations of the different containers and where those kind of
algorithms are best used. Take a class or read a book on data
structures and implement your own list, vector, map, etc...and then you
will be able to understand their value and when to use what.

As a contractor, I've worked in many locations, and it's been my
experience when finding std::list used in code, that 9 out of 10 times,
std::list is being used inappropriately , and std::vector or std::deque
would have done the same job faster.

I'm sorry but I just don't buy your "credential s". Anyone that would
call that dynamic_array class of yours an example of how TO do
something doesn't meet my requirements of an expert. Judging by the
single code example I have seen from you I am not at all impressed.

[Alf P. Steinbach]

* Diego Martins:

this is better:

template< typename T >
void compact( std::vector<T>& v )
{ std::vector<T>( v).swap(v); }

chapter 17 - Effective STL - Scott Meyers :-)

A too smart implementation is free, I believe, to simply not copy
anything here, and with no actual copying, no memory usage reduction.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Kai-Uwe Bux]

ro**********@gm ail.com wrote:

Kai-Uwe Bux wrote:

a) A vector is not just "almost" guaranteed to be contiguous. It is
contiguous. The standard implies that.
Being guaranteed and being implied are two very different things. An
implementation is free to implement a vector any way they want. The
requirements of the interface mean that there will probably never be
anything but a contiguous vector but there could be if an
implementation could meet those requirements without being contiguous.

From the standard:

[23.2.4/1]

[...] The elements of a vector are stored contiguously, meaning that if v is
a vector<T, Allocator> where T is some type other than bool, then it obeys
the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

In Thinking in C++ V2, Bruce Eckel claims this is a shortsight of the
standard to be fixed in the future. So, someday maybe it will be
guaranteed but today it is not. [snip]

That book seems to be outdated.
Best regards

Kai-Uwe Bux