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

Discussion in 'C++' started by Josh Mcfarlane, Dec 12, 2005.

  1. 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
     
    Josh Mcfarlane, Dec 12, 2005
    #1
    1. Advertising

  2. Josh Mcfarlane

    Markus Moll Guest

    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
     
    Markus Moll, Dec 12, 2005
    #2
    1. Advertising

  3. Josh Mcfarlane

    Guest

    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
     
    , Dec 12, 2005
    #3
  4. Josh Mcfarlane

    pepp Guest

    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.
     
    pepp, Dec 12, 2005
    #4
  5. Josh Mcfarlane

    Earl Purple Guest

    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.
     
    Earl Purple, Dec 12, 2005
    #5
  6. "Josh Mcfarlane" <> 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
     
    Robbie Hatley, Dec 12, 2005
    #6
  7. Josh Mcfarlane

    Axter Guest

    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, Dec 12, 2005
    #7
  8. Josh Mcfarlane

    Axter Guest

    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, Dec 12, 2005
    #8
  9. Josh Mcfarlane

    Axter Guest

    Robbie Hatley wrote:
    > "Josh Mcfarlane" <> 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.
     
    Axter, Dec 12, 2005
    #9
  10. Josh Mcfarlane

    Guest

    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.
     
    , Dec 12, 2005
    #10
  11. Josh Mcfarlane

    Axter Guest

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


    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.
     
    Axter, Dec 12, 2005
    #11
  12. Josh Mcfarlane

    Kai-Uwe Bux Guest

    wrote:

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


    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::eek:stream & o_str;
    std::string banner;
    timer watch;

    public:

    print_timer ( std::eek: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
     
    Kai-Uwe Bux, Dec 12, 2005
    #12
  13. Josh Mcfarlane

    g Guest

    >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........
     
    g, Dec 12, 2005
    #13
  14. Josh Mcfarlane

    Greg Guest

    Kai-Uwe Bux wrote:
    > 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
     
    Greg, Dec 13, 2005
    #14
  15. Josh Mcfarlane

    Jerry Coffin Guest

    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.


    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.

    --
    The universe is a figment of its own imagination.
     
    Jerry Coffin, Dec 13, 2005
    #15
  16. Josh Mcfarlane

    Kai-Uwe Bux Guest

    Greg wrote:

    > Kai-Uwe Bux wrote:
    >> 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

    [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
     
    Kai-Uwe Bux, Dec 13, 2005
    #16
  17. * 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?
     
    Alf P. Steinbach, Dec 13, 2005
    #17
  18. Josh Mcfarlane

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Dec 13, 2005
    #18
  19. * 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.

    --
    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?
     
    Alf P. Steinbach, Dec 13, 2005
    #19
  20. "Axter" <> 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_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;
    }
     
    Niklas Norrthon, Dec 13, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Anton
    Replies:
    1
    Views:
    369
    Peter van Merkerk
    Aug 6, 2003
  2. Replies:
    7
    Views:
    554
    Pete Becker
    Jan 25, 2008
  3. Ian Collins
    Replies:
    5
    Views:
    390
    James Kanze
    Aug 25, 2010
  4. Steven D'Aprano
    Replies:
    0
    Views:
    99
    Steven D'Aprano
    Dec 23, 2013
  5. Replies:
    3
    Views:
    89
    Gary Herron
    Dec 23, 2013
Loading...

Share This Page