Thread: vector/list

  1. #1
    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
    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
    28,412
    Inserting into the middle of a linked list (constant time) would be faster than inserting into the middle of a vector (linear time).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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
    39,656
    <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.

  8. #8
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    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.
    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,366
    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, 10:22 PM