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

Josh Mcfarlane wrote:

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]

Markus Moll wrote:

Hi

Josh Mcfarlane wrote:

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.

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]

Josh Mcfarlane wrote:

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]

"Josh Mcfarlane" <da*****@gmail. com> wrote:

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.

--
Robbie Hatley
Tustin, CA, USA
lone wolf intj at pac bell dot net
home dot pac bell dot net slant earnur slant

[Axter]

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.

[Axter]

Josh Mcfarlane wrote:

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]

Robbie Hatley wrote:

"Josh Mcfarlane" <da*****@gmail. com> wrote:

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.

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.

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.

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]

Axter wrote:

Josh Mcfarlane wrote:

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.

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.