STL vector VS list

Discussion in 'C++' started by silverburgh.meryl@gmail.com, Jan 13, 2006.

  1. Guest

    , Jan 13, 2006
    #1
    1. Advertising

  2. wrote:
    > in STL, why vector has an API to return the n-th element, but list does
    > not have such API?
    > [..]


    According to the design intent, 'list' is not a container that allows
    random access to its elements. It's designed to allow quick insertions
    and deletions, while not invalidating any references or iterators except
    the ones to the deleted element. Providing efficient random access to
    elements would not be possible. If you need random access to elements
    of a container, use 'vector'. If you need robust and fast insertions
    in any part of the container, use 'list'.

    Read more books.

    V
     
    Victor Bazarov, Jan 13, 2006
    #2
    1. Advertising

  3. Andre Kostur Guest

    wrote in news:1137173258.277178.298990
    @g49g2000cwa.googlegroups.com:

    > in STL, why vector has an API to return the n-th element, but list does
    > not have such API?
    >
    > http://www.sgi.com/tech/stl/Vector.html
    > http://www.sgi.com/tech/stl/List.html


    Vector is basically an array, so going to the n-th element of a vector is
    only pointer arithmetic. List is a chain of nodes, so in order to get to
    the n-th element, you must traverse the list from .begin() to the n-th
    element.

    Note that you can do something very similar by using std::advance on an
    iterator into the list.
     
    Andre Kostur, Jan 13, 2006
    #3
  4. Ben Pope Guest

    Ben Pope, Jan 13, 2006
    #4
  5. Artie Gold Guest

    Artie Gold, Jan 13, 2006
    #5
  6. Neil Cerutti Guest

    On 2006-01-13,
    <> wrote:
    > in STL, why vector has an API to return the n-th element, but
    > list does not have such API?


    The standard containers attempt to provide an interface that's
    reasonably efficient. If an efficient implementation is not
    possible for a given container, it does not provide it.
    A list could offer an operator[] interface that provides random
    access, but it would be very inefficient, so it does not.

    The same type of reasoning dicates that vector provide push_back,
    but not push_front, while deque provides both.

    It's more of a guideline than a rule, though. There's usually a
    way to get the inefficient behavior if you really want it.

    --
    Neil Cerutti
     
    Neil Cerutti, Jan 13, 2006
    #6
  7. Calum Grant Guest

    Artie Gold wrote:
    > wrote:
    >
    >> in STL, why vector has an API to return the n-th element, but list does
    >> not have such API?
    >>
    >> http://www.sgi.com/tech/stl/Vector.html
    >> http://www.sgi.com/tech/stl/List.html
    >>
    >> Thank you.
    >>

    > A vector is a container that supports random access. A list is not.
    > It's as simple as that.


    One could quite easily implement access to the nth element on a list.
    But it was deliberately omitted.

    Why?

    Because it would not be efficient. The list would perform n operations,
    while a vector could go straight to the element in one operation.
    Providing an operator[] would just tempt people (who didn't get around
    to reading every minutiae on the subject) to actually use it and
    inadvertently write inefficient code.
     
    Calum Grant, Jan 13, 2006
    #7
  8. persenaama Guest

    You already got good answers, but here's a question for you: describe
    how you would implement the operator [] ?

    Background information:

    - std::vector is fundamentally, an array
    - std::list is fundamentally, a linked list

    For an array, providing [] is trivial. For list, it is not-so trivial
    to do efficiently. If you have any good ideas I'm all ears.

    I don't expect any reasonably efficient solution to be found at this
    time, but, it would be interesting to discuss any approach you come up
    with, because, once upon a time I put some thinking into the very same
    question and came up with compromises and tradeoffs between various
    aspects of the implementation. It all boils down to the fundamentals of
    what you expect from array and linked list.

    It would make more sense to ask what use is container which is
    jack-of-all-trades but master of none. The answer won't be all black
    and white, that's why there are containers like std::map, std::deque
    and so on.

    Let's take a look at container, where we have [], doing pointer
    arithmetic is going to be hard to beat:

    struct container {
    type* base;
    type& operator [] (int index) { return base[index]; }
    };

    Now, the problem with this setup is that inserting into the middle is
    going to be rather cumbersome to say the least, we have to *move*
    elements after the insertion point to make room for the new elements
    being inserted into the sequence. That goes without saying, but you
    surely see the problem this imposes?

    Linked list is the next step, here's similiarly naive framework:

    template <typename x>
    struct container {
    struct node { x data; node* next; node* prev; };
    node* head;
    node* tail;
    };

    Eg. each object has pointer to previous, and next one in the sequence.
    That makes implementing [] efficiently rather tricky. That's why
    std::list doesn't do [].

    If you want both "traits" in one container, you start designing and see
    what you trade for what. Most likely you'll be balancing between these
    things:

    - insert/remove runtime performance
    - operator [] performance
    - iteration performance
    - memory footprint
    - and more

    Sometimes it is more critical that iteration, or some other operation
    is very efficient. It all depends what's the design purpose of the
    container.

    Please discuss this further.
     
    persenaama, Jan 15, 2006
    #8
    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. Dennis
    Replies:
    1
    Views:
    2,612
    Dennis
    Jun 7, 2004
  2. CD
    Replies:
    2
    Views:
    819
    Victor Bazarov
    Oct 5, 2004
  3. Replies:
    8
    Views:
    1,984
    Csaba
    Feb 18, 2006
  4. ehui928
    Replies:
    2
    Views:
    477
    ehui928
    May 29, 2006
  5. Luca Risolia

    STL map to STL vector

    Luca Risolia, Jan 13, 2014, in forum: C++
    Replies:
    32
    Views:
    413
    Seungbeom Kim
    Jan 18, 2014
Loading...

Share This Page