Vector and list iterators and efficiency

Discussion in 'C++' started by Thormod Johansen, Mar 26, 2007.

  1. Hi,

    I have just read the article about iterators at
    http://www.oreillynet.com/pub/a/network/2005/10/18/what-is-iterator-in-c-plus-plus.html?page=last
    and I am wondering about what is ment by the sentence "list does not provide
    random access iterators, though, not because it's impossible to implement,
    but because it can't be implemented efficiently."

    As I understand it, a vector is a single linked list and list is a double
    linked list. Why is it harder to implement a efficient iterator in a double
    linked than in a single linked list?

    If I have the following requirements for a datastructure - be it vector or
    list - which would you consider most efficient (fastest running time):
    1 ) Be able to iterate through it looking for a specific value
    2 ) Remove an element from the middle of the structure
    3 ) Add an element in the front and in the back

    I reckon that in the case of 2) a list would be fastest but how about the
    two other cases?

    Best regards.
    Thormod Johansen, Mar 26, 2007
    #1
    1. Advertising

  2. Thormod Johansen wrote:
    > I have just read the article about iterators at
    > http://www.oreillynet.com/pub/a/network/2005/10/18/what-is-iterator-in-c-plus-plus.html?page=last
    > and I am wondering about what is ment by the sentence "list does not
    > provide random access iterators, though, not because it's impossible
    > to implement, but because it can't be implemented efficiently."
    >
    > As I understand it, a vector is a single linked list


    Incorrect. A vector is very much like an array in C++.

    > and list is a
    > double linked list. Why is it harder to implement a efficient
    > iterator in a double linked than in a single linked list?
    >
    > If I have the following requirements for a datastructure - be it
    > vector or list - which would you consider most efficient (fastest
    > running time): 1 ) Be able to iterate through it looking for a
    > specific value 2 ) Remove an element from the middle of the structure
    > 3 ) Add an element in the front and in the back
    >
    > I reckon that in the case of 2) a list would be fastest but how about
    > the two other cases?


    When 1) is concerned, they are the same. Adding to front of a vector
    is expensive.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Mar 26, 2007
    #2
    1. Advertising

  3. Thormod Johansen

    mlimber Guest

    On Mar 26, 1:14 pm, "Thormod Johansen" <> wrote:
    > I have just read the article about iterators athttp://www.oreillynet.com/pub/a/network/2005/10/18/what-is-iterator-i...
    > and I am wondering about what is ment by the sentence "list does not provide
    > random access iterators, though, not because it's impossible to implement,
    > but because it can't be implemented efficiently."
    >
    > As I understand it, a vector is a single linked list and list is a double
    > linked list.


    No, a vector is guaranteed to be contiguous memory and is
    interoperable with an array. It is not a singly linked list.

    > Why is it harder to implement a efficient iterator in a double
    > linked than in a single linked list?


    It's not (significantly), but this is irrelevant. See above.

    > If I have the following requirements for a datastructure - be it vector or
    > list - which would you consider most efficient (fastest running time):
    > 1 ) Be able to iterate through it looking for a specific value
    > 2 ) Remove an element from the middle of the structure
    > 3 ) Add an element in the front and in the back
    >
    > I reckon that in the case of 2) a list would be fastest but how about the
    > two other cases?


    If your data is unsorted, then in theory, either std::vector or
    std::list would be the same in terms of iteration, but in practice
    your hardware cache may give vectors a significant speed improvement.
    If it is sorted, you probably want some sort of tree-based structure
    like a std::set or std::map.

    Removing a given element from a list (or set or map) is O(1) but from
    a vector is O(N), and inserting an element at a given point is O(1).
    Whereas insertion and deletion are both O(N) for vector (though it
    amortizes back-insertions over time).

    std::deque, which is something like a cross between a list and a
    vector, can insert at the front and back in O(1) but also allows
    random access. You may want to look into that.

    Cheers! --M
    mlimber, Mar 26, 2007
    #3
    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. Jim West
    Replies:
    14
    Views:
    6,203
    Alex Vinokur
    Dec 18, 2003
  2. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    475
    Kai-Uwe Bux
    May 8, 2005
  3. David Crawford

    Question on vector of vector iterators

    David Crawford, Dec 15, 2005, in forum: C++
    Replies:
    3
    Views:
    468
  4. Replies:
    8
    Views:
    1,890
    Csaba
    Feb 18, 2006
  5. , India
    Replies:
    10
    Views:
    1,059
    James Kanze
    Aug 8, 2009
Loading...

Share This Page