vector/list

This is a discussion on vector/list within the C++ Programming forums, part of the General Programming Boards category; Hello.. Whats the difference betwen vector and list? I know vector = array, list = linked list, and they can ...

  1. #1
    l2u
    l2u is offline
    Registered User
    Join Date
    May 2006
    Posts
    630

    vector/list

    Hello..

    Whats the difference betwen vector and list?
    I know vector = array, list = linked list, and they can be used the same way..

    When should I use vector and when list?

  2. #2
    Registered User SKeane's Avatar
    Join Date
    Sep 2006
    Location
    England
    Posts
    234
    Think about what happens if you wish to insert something in the middle of a vector or the middle of a linked-list.

  3. #3
    l2u
    l2u is offline
    Registered User
    Join Date
    May 2006
    Posts
    630
    Which is faster?

  4. #4
    Registered User SKeane's Avatar
    Join Date
    Sep 2006
    Location
    England
    Posts
    234
    (In theory) if you plan on doing insertions into the middle of a container then a linked-list would be quicker than a vector. Of course it depends on how the writer(s) of the STL actually implemented things.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,269
    Inserting into the middle of a linked list (constant time) would be faster than inserting into the middle of a vector (linear time).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    It depends on the situation, that's why both are available. You should learn the differences between different data structures. You should also read up on the efficiencies of the different standard library containers. In general, you should use vector for most of your containment needs, but in some cases it makes more sense to use list.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,824
    <town cryer>
    READ ALL ABOUT IT - http://www.sgi.com/tech/stl/table_of_contents.html
    </town cryer>
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,578
    There's also the matter of acessing the elements. What is good in terms of inserting, may not result so well if acessing the elements is the thick of the operations. If the container is going to be used mainly for random access, while the insert and erase operations are isolated events happening here and there, a vector is probably best.

    I may be wrong here, so do correct me:

    After analysing what is going to be the thich of the operations,

    - If random access use a vector or deque
    - If random insertions/deletions use a list
    - If insertions/deletions at the front or back, use a deque
    - if insertions at the middle and then random access, use a list and then copy it to a vector

    EDIT: Oops 3 replies between starting and finishing my post.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    In most of those cases I would actually use a vector first. If speed or efficiency were an issue, then I'd consider profiling and switching. Those are ok guidelines to follow, and it does make sense to use the right data structure from the beginning, but in many cases it actually turns out that vector is faster even when you would think that a list or deque should be. This is often because the overheads of other containers is larger than the vector overhead, and so it takes a large number of elements before the big-O performance improvements appear.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. difference betwen vector/list
    By l2u in forum C++ Programming
    Replies: 3
    Last Post: 03-31-2008, 11:22 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21