Containers: List vs Vector

This is a discussion on Containers: List vs Vector within the C++ Programming forums, part of the General Programming Boards category; Say I want to implement a buffer that stores the last fifty lines of input should I use a list ...

  1. #1
    Registered User
    Join Date
    Mar 2002
    Posts
    15

    Containers: List vs Vector

    Say I want to implement a buffer that stores the last fifty lines of input should I use a list or a vector? The list seems as though it would have less overhead but I was wondering if there was some hidden caveat to using the list container.

    Thanks,

    PetrolMan

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,954
    Besides storing the input, how will you access the input?
    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

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    It seems like a queue, then, for which std::deque might be good?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Generally speaking you should use vector unless you have some reason to do otherwise. I don't see any reason to use list based on the information you've provided.

    Since it is a buffer then a deque might be a good idea, as inserting or removing from the front would probably be necessary and vector doesn't do that so well compared to deque. The advantage of deque over list is that deque will have closer to constant time access if you need to look at one of the lines in the middle of the container.

    I would think that between the three the list would have the most overhead in terms of size, but that shouldn't be noticeable.

  5. #5
    Registered User
    Join Date
    Mar 2002
    Posts
    15
    I actually probably didn't give you all enough information. One thing I need to be able to do is to cycle through the data so in case someone wants to reuse the same input they can. This shouldn't really be a problem with any of the containers.

    Say the container stores 50 lines of input, when the newest one is entered I want to just add it to the front of the container and then remove the oldest. There would never really be any need to do random insertions in the middle of the container or anything else.

    Again, I figure any of these could do the job just fine but I was just kind of wondering about the overhead involved with each type of container.

    Thanks,

    PetrolMan

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    For 50 elements, I don't really see much reason to use anything other than vector - unless your text is REALLY long, in which case it may be better to store a (smart) pointer to your string, so that the vector itself is smaller and thus copies the elements faster when inserting in the middle.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,158
    Some people might object to this solution, but another option would be to implement a simple ring buffer instead of using an STL container directly (you could implement the ring buffer on top of a std::vector).

    A std::deque provides the features you want, but there is the possibility that the deque slowly "walks around" in memory due to your specific access pattern (always pop-back then push-front).
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    I believe std::vector has the least overhead in size (0 bytes), whereas std::list has to have pointers to the head, and each node has a pointer to the next & previous node...
    But for what you're describing, using an std::deque would be perfect because you'd only have to use the push_back() and pop_front() member functions to remove the oldest line and add a new one.
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,260
    Quote Originally Posted by brewbuck View Post
    Some people might object to this solution, but another option would be to implement a simple ring buffer instead of using an STL container directly (you could implement the ring buffer on top of a std::vector).

    A std::deque provides the features you want, but there is the possibility that the deque slowly "walks around" in memory due to your specific access pattern (always pop-back then push-front).
    I was going to suggest a circular-buffer myself.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  2. Vector class
    By Desolation in forum C++ Programming
    Replies: 2
    Last Post: 05-12-2007, 05:44 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  5. Certain functions
    By Lurker in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2003, 12:26 AM

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