Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > When is std::list more effective than the other containers?

Reply
Thread Tools

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

 
 
Josh Mcfarlane
Guest
Posts: n/a
 
      12-12-2005
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

 
Reply With Quote
 
 
 
 
Markus Moll
Guest
Posts: n/a
 
      12-12-2005
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

 
Reply With Quote
 
 
 
 
Michiel.Salters@tomtom.com
Guest
Posts: n/a
 
      12-12-2005

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

 
Reply With Quote
 
pepp
Guest
Posts: n/a
 
      12-12-2005
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.

 
Reply With Quote
 
Earl Purple
Guest
Posts: n/a
 
      12-12-2005

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.

 
Reply With Quote
 
Robbie Hatley
Guest
Posts: n/a
 
      12-12-2005
"Josh Mcfarlane" <(E-Mail Removed)> 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




 
Reply With Quote
 
Axter
Guest
Posts: n/a
 
      12-12-2005

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.

 
Reply With Quote
 
Axter
Guest
Posts: n/a
 
      12-12-2005

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.

 
Reply With Quote
 
Axter
Guest
Posts: n/a
 
      12-12-2005

Robbie Hatley wrote:
> "Josh Mcfarlane" <(E-Mail Removed)> 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.

 
Reply With Quote
 
roberts.noah@gmail.com
Guest
Posts: n/a
 
      12-12-2005

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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Like all great travelers, I have seen more than I remember andremember more than I have seen. shenrilaa@gmail.com Java 0 03-06-2008 08:11 AM
Like all great travelers, I have seen more than I remember andremember more than I have seen. shenrilaa@gmail.com C++ 0 03-05-2008 08:41 AM
Like all great travelers, I have seen more than I remember andremember more than I have seen. shenrilaa@gmail.com C Programming 0 03-05-2008 03:26 AM
How to access web.sitemap file from other virtual directories other than the current application root folder? hvajja@gmail.com ASP .Net 0 08-07-2006 08:26 PM
What other produces other than "PC Anywhere"? JnlSeb Computer Information 4 01-08-2004 06:12 PM



Advertisments