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

 

[Markus Moll]

Hi

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.

Think about the complexity of erasing or inserting elements at arbitrary
positions. Also think about what happens to iterators when doing so.

Markus

 

[Michiel.Salters]

Hi



Think about the complexity of erasing or inserting elements at arbitrary
positions. Also think about what happens to iterators when doing so.

Splicing subvectors is also rather tricky

HTH,
Michiel Salters

 

[pepp]

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.

 

[Earl Purple]

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

constant time insertion and deletion at any point in the list. (i.e.
regardless of the current size of the list).

list would seem to be at its most optimal (compared to other
containers) when you are a large list of relatively small objects
rather than a small list of large objects (latter can be implemented
using smart-pointers so the objects are not so large after all), and
you are inserting/deleting in the middle.

 

[Robbie Hatley]

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

std::list is best any time you have one or more of the
following situations:

1. Wildly variable amount of data.
2. Data needs to be inserted or deleted in the middle.
3. Data needs to be sorted frequently.

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

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.

But with std::list, those things are fast and efficient,
and don't require re-allocation.

 

[Axter]

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.

 

[Axter]

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

You should use vector as your default container.

Normally, std::list is rarely the best choice. In most requirements,
std::list will perform worse, or the same as std::vector.

You should consider using std::list if you have a requirement that
performs many inserts and/or deletes from the center of the container.

If you only perform a few insertions and/or deletions from the center,
then you should still prefer to use std::vector or std::deque.

Sorting requirements should not be a motivating factor for using
std::list, because you're more then likely using the wrong set of
containers if you have a (repeat) sorting requirement.
If you have a requirement that needs to do a lot of sorting, then you
should consider using std::map or std::set instead.

In general, std::list should be your least used container.

 

[Axter]

std::list is best any time you have one or more of the
following situations:

1. Wildly variable amount of data.

Should not be a factor in considering using std::list instead of
std::vector

2. Data needs to be inserted or deleted in the middle.

This should be the primary factor, and is usually only important when
there are MANY inserts and deletes from the center.

3. Data needs to be sorted frequently.

If data needs to be frequently sorted, then consider using std::set or
std::map instead.

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.

It's optimized for middle insertions. However, compare to std::vector
and std::deque, std::list is poorly optimized for end insertions. And
compare to std::deque, std::list is poorly optimized for beginning
insertions.

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.

Only when inserting in the beginning or middle of the container.

Most experts, (like Herb Sutters and Scott Meyers) recommend using
std::vector as the default container.
The Official C++ standard also recommends using std::vector as the
default container.
In most container requirements, std::vector will out perform std::list.

 

[roberts.noah]

You should use vector as your default container.

Normally, std::list is rarely the best choice. In most requirements,
std::list will perform worse, or the same as std::vector.

You should consider using std::list if you have a requirement that
performs many inserts and/or deletes from the center of the container.

Or if you perform a lot of push_back operations and will be accessing
in a linear fassion 99% of the time or better. A list has to allocate
for a new node but it doesn't have to copy the whole list to the new
memory, it can just assign values. A vector on the other hand is
*almost* guaranteed to be contiguous memory and therefore will most
likely copy the entire contents upon a need to resize.

However, because of the lack of a random access iterator it can still
be more efficient to use a vector if you need random access. If you
are just running the whole list every time you access it then a list is
a very efficient implementation unless you know ahead of time exactly
how big to make your vector (or at least a good usual upper bound).

If you only perform a few insertions and/or deletions from the center,
then you should still prefer to use std::vector or std::deque.

Sorting requirements should not be a motivating factor for using
std::list, because you're more then likely using the wrong set of
containers if you have a (repeat) sorting requirement.

Not only that, but because std::list doesn't have a random access
iterator sorting a list will be considerably slower than a
vector...most of the time. There are rare cases when it might not be,
but usually you will find sort to work faster with a random access than
without.

If you have a requirement that needs to do a lot of sorting, then you
should consider using std::map or std::set instead.

In general, std::list should be your least used container.

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.

 

[Axter]

Or if you perform a lot of push_back operations and will be accessing
in a linear fassion 99% of the time or better. A list has to allocate
for a new node but it doesn't have to copy the whole list to the new
memory, it can just assign values. A vector on the other hand is
*almost* guaranteed to be contiguous memory and therefore will most
likely copy the entire contents upon a need to resize.

However, because of the lack of a random access iterator it can still
be more efficient to use a vector if you need random access. If you
are just running the whole list every time you access it then a list is
a very efficient implementation unless you know ahead of time exactly
how big to make your vector (or at least a good usual upper bound).

Not only that, but because std::list doesn't have a random access
iterator sorting a list will be considerably slower than a
vector...most of the time. There are rare cases when it might not be,
but usually you will find sort to work faster with a random access than
without.


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.

IMHO, std::list is one of the most misused STL containers. You often
find programmers that transfer from programming in C to programming in
C++ to use std::list as there default container, because they're use to
using link list in their old C language code.

I'm not saying you should never use std::list. I'm just saying (in
general), that it's rarely the best choice.

 

[Kai-Uwe Bux]

Or if you perform a lot of push_back operations and will be accessing
in a linear fassion 99% of the time or better. A list has to allocate
for a new node but it doesn't have to copy the whole list to the new
memory, it can just assign values. A vector on the other hand is
*almost* guaranteed to be contiguous memory and therefore will most
likely copy the entire contents upon a need to resize.

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

b) Even accounting for reallocations, appending an item to a vector is
guaranteed to be amortized constant time. Whether vector (accounting for
reallocations) or list is more efficient has to be decided by measurement.
In my experience, for small typesize, vector always beats list:

#include <ctime>
#include <vector>
#include <list>
#include <iostream>

class timer {
private:

std::clock_t ticks;

public:

timer ( void )
: ticks ( std::clock() )
{}

std::clock_t passed ( void ) const {
return( std::clock() - ticks );
}

double seconds ( void ) const {
return( double( this->passed() ) / CLOCKS_PER_SEC );
}

}; // timer

class print_timer {
private:

std:stream & o_str;
std::string banner;
timer watch;

public:

print_timer ( std:stream & str, std::string msg = std::string() )
: o_str ( str )
, banner ( msg )
, watch ()
{}

~print_timer ( void ) {
o_str << banner << " " << watch.seconds() << "sec" << '\n';
}

}; // print_timer


template < template <class> class cont >
void allocate ( cont<unsigned long> & i_cont,
unsigned long length ) {
print_timer dummy ( std::cout );
for ( unsigned long i = 0; i < length; ++i ) {
i_cont.push_back( i );
}
}

int main ( void ) {
std::list< unsigned long > l_list;
//std::vector< unsigned long > l_list;
allocate( l_list, 10000000 );
std::cout << l_list.back() << '\n';
}

On my machine, vector<unsigned long> beats list<unsigned long> by a factor
of 6; and you bet that the vector was reallocated several times.

So, for a sequence of, say, pointers the concern about reallocation is not
justified. For bigger objects, however, you may have a point. As I said,
this should be left to measurements.


Best

Kai-Uwe Bux

 

[g]

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........

 

[Greg]

(e-mail address removed) wrote:


On my machine, vector<unsigned long> beats list<unsigned long> by a factor
of 6; and you bet that the vector was reallocated several times.

So, for a sequence of, say, pointers the concern about reallocation is not
justified. For bigger objects, however, you may have a point. As I said,
this should be left to measurements.

All the items would have to be appended to the very end of the
container for a vector to stand any chance of being faster than a list
at insertion. And as soon as any insertions have to be performed any
where else within the container, the performance characteristics of a
vector start to fall fall off a cliff.

Consider revising your benchmark to compare a std::list vs. a
std::vector when insertions are made at the the head of the container.
Here's the change:

for ( unsigned long i = 0; i < length; ++i ) {
i_cont.insert(cont.begin(), i );
}

How much faster will the std::list be than the std::vector when
inserting items at the beginning according to this benchmark? 6 times?
60? 600?

Probably more like 5,000,000. The time it takes to fill the list will
be approximately the same in either benchmark, while the time it takes
the vector would increase quite a bit more. If it takes 5 seconds to
fill the vector when appending 10 million items to its end, it would
take about 9 months(!) of dedicated computer time to do the same when
when all items are inserted at the beginning (though I lost patience
when I tried to time the benchmark just now).

So whatever edge a vector may have over a list when inserting items in
the ideal case, is by no means comparable to the edge that the list has
over a vector in the worst case. So unless all the insertions will be
at the end, I would choose a list over a vector, just to be on the safe
side.

Greg

 

[Jerry Coffin]

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.

There are a few situations in which std::list is quite useful, but they
are pretty rare.

About the only time it works out well is when the task involves a (or
more than one) semi-permanent "cursor" that maintains a current
position in the list, and you do a lot of inserting/deleting at that
point (which hopefully doesn't change very often, except maybe by one
item at a time).

Otherwise, the list will normally lose -- in particular, even though
inserting/deleting in the middle of the list is constant complexity,
getting TO that spot in the list is linear. For a constrasting example,
consider storing items in a tree, in which case you can find a spot
with roughly log2(N) complexity, and insert or delete in about the
same. These operations will typically have somewhat higher constants,
but the complexity reduction is so great that it'll still win over
anything but quite a short/small list.

If you really expect your list to remain quite small, you're probably
better off with a deque or vector. These reverse the shortcomings of a
list: searching has low complexity, but insertion/deletion in the
middle are linear. The difference is in the constants: vectors (for
example) use contiguous memory, so they're much more cache friendly,
and give much lower per-operation constants as a general.rule.

It might seem right off that there should be some middle ground: that a
vector/deque would be best for a really small number of items, and a
tree for a really large number of items, but a list would be best
somewhere in the middle. My experience is the opposite: lists always
lose -- there is a cross-over point when a tree becomes faster than a
vector, but even right at the cross-over point, they're BOTH faster
than a list.

 

[Kai-Uwe Bux]

All the items would have to be appended to the very end of the
container for a vector to stand any chance of being faster than a list

[snip]

Do not snip the relevant context! I replied to:

Or if you perform a lot of push_back operations and will be accessing
in a linear fassion 99% of the time or better. A list has to allocate
for a new node but it doesn't have to copy the whole list to the new
memory, it can just assign values. A vector on the other hand is
almost guaranteed to be contiguous memory and therefore will most
likely copy the entire contents upon a need to resize.

Thus, I was addressing the overhead of reallocation only. It is *consensus*
that list is better if insertions/deletions occur in other places than the
end.


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... ;-)

 

[Kai-Uwe Bux]

* Kai-Uwe Bux:

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:

I ended up implementing a
rope like data structure that also supports efficient line numbering and
that helps with the undo feature, too.

Well, I'm getting senile, I think, can't remember how well I remembered or
not, so I had to look it up, found

<url:
http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf>,

no such in Boost, unfortunately!

But there is in the SGI STL.

 

[Niklas Norrthon]

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_iterator 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;
}