• Advertisement

Archived

This topic is now archived and is closed to further replies.

Which is faster stl:list or stl:vector

This topic is 5095 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I want to use the fastest one of the two to store my GameObject classes. I don''t think I really need to be using one or to other.

Share this post


Link to post
Share on other sites
Advertisement
If you need to insert/delete objects in the middle of the container, use a list. Otherwise, use a vector.

Share this post


Link to post
Share on other sites
Which is faster depends on how you use them. std::vectors tend to give better performance accessing and iterating and inserting/deleting at the end. std::lists tend to give better performance for insertion and deletion at the front and middle. Some algorithms you can only use on a vector and not on a list.

Share this post


Link to post
Share on other sites
Short answer:Both.

Long answer: How are you using the container, are there frequent inserts, many inserts in the middle, is random access required, etc. etc. Decide how you are using the container before choosing a particular one. Each has it''s own strengths and weaknesses.

Share this post


Link to post
Share on other sites
quote:
Original post by antareus
To say nothing of a deque! The oft-ignored dunce of the containers!


And there you go, spilling out all our secrets.

Share this post


Link to post
Share on other sites
I don''t care about inserting at the middle but I will need to delete anywhere so I guess I''m better off with a list.

Share this post


Link to post
Share on other sites
That depends on how often you need to delete compared to how often you need to iterate / access and also on how big the objects you''re storing are. In a typical case you''ll be storing GameObject pointers (because GameObject is a base class with virtual functions) and you''ll be iterating more frequently than you''ll be deleting. Since pointers are small (and therefore cheap to copy when you delete from the middle) a vector is probably a better choice than a list in that case. A list also wastes space when storing small objects - for a list of pointers you have two list pointers for every pointer you''re storing...

Share this post


Link to post
Share on other sites
Depending on if the order of objects in the container is important or not, you can get reasonably fast deletion in the middle of a vector by swapping the element to be deleted with the last element of the vector and then calling pop_back().

Share this post


Link to post
Share on other sites
Just use a std::vector first, then, if the program becomes too slow, you could try a std::list to see if it''s faster. If you put a typedef std::vector GameObjects; in a header file all you need to do to change to list is that line. The difference between the two containers is probably not significant, don''t waste your time on it.

Share this post


Link to post
Share on other sites
you will find that deque is the best general purpose list you can use, if you don''t have any clue about the usage idiom ... use it ... and then change to a list or a vector if the usage characteristics warrant it.

for this to work you need to do one thing though .. NEVER write a simple for each type loop using ints and random access subscript operators if you don''t need to ... use iterators ... only by using iterators where possible can you A) get the real speed benifit in vectors, and B) be able to substituite a list for a vector or deque that doesn''t need random access.

Also, don''t forget the "set" for cases where you want to write code that "adds an element to the list, if not already in the list" ... (just remember not to try to delete elements from sets like lists ... don''t delete an element you wanted to add twice, twice

And the "map" is my hero, in combination with the other classes, you can build extrodinary abilities by using maps where appropriate.

Share this post


Link to post
Share on other sites
I did a few tests of just iterating over a fairly big number of objects in a list, vector and a standard array. The vector was ALOT faster than the list and pretty much the same as an array. I tend to use vectors more often now if i''m doing repeated itteration.

Share this post


Link to post
Share on other sites
Bleakcabal: Don''t you think that if it were simply the case that one is faster than the other then there wouldn''t be both?!?!

Clearly you need to provide SOME information about what you plan to do with it. Preferably give ALL the information you can. Everyone is going to have to ask you otherwise.

You still have not provided enough information for anyone here to give tell you definately which is better for what you want to do. It may even be neither list nor vector which is best for what you are doing.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
std::vector is almost always faster. It should be the default choice unless you have a good reason to think otherwise. Someone tested in a CUJ article that std::vector is faster than std::list for containers with size less than 100, almost independent of the type of operations you do (insert/delete in middle etc.) because it''s constants are so much lower. Also, even if it''s O(N) to delete from within a vector, it''s common to loop through all the items to see what item satisfies the delete condition, so the tests would make it O(N) for lists as well (of course there are cases where should looping wouldn''t be necessary, and if such deletion would be common in a 1000+ element, that''d fall to the rare case group). Often order isn''t important so one can gain some speed in vectors by swapping with last element and popping the last one. People really give too much credit for std::list. It''s memory requirements are larger and iteration in it is slower, and it''s good properties usually don''t give that much benefit.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Someone tested in a CUJ article that std::vector is faster than std::list for containers with size less than 100, almost independent of the type of operations you do (insert/delete in middle etc.) because it''s constants are so much lower.


That''s not a meaningful number. If the stored type is expensive to copy, then vector is going to lose out in the insert/erase at beginning/middle at much sooner than 100 elements.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by SiCrane
That''s not a meaningful number. If the stored type is expensive to copy, then vector is going to lose out in the insert/erase at beginning/middle at much sooner than 100 elements.
Nobody''s requiring you to put heavy stuff in a vector. You can choose to use vector<T*> instead of list<T>, and the former will be faster almost always.

Share this post


Link to post
Share on other sites
Yeah, put a typedef, write your code, profile both solutions, and choose the fastest one.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
quote:
Original post by SiCrane
That''s not a meaningful number. If the stored type is expensive to copy, then vector is going to lose out in the insert/erase at beginning/middle at much sooner than 100 elements.
Nobody''s requiring you to put heavy stuff in a vector. You can choose to use vector<T*> instead of list<T>, and the former will be faster almost always.

Now you''re changing the premise of your original claim. Furthermore, it still doesn''t make it a meaningful number. Systems with slower memory access are still going to shift the break even point in favor of the list. If you''re going to post numbers like that you should list the benchmarking machine and compiler. Otherwise, you get people who don''t know any better memorizing a stupid arbitrary number without thinking for themselves.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You''re a *bit* too concerned about that particular number. I bet nobody''s going to just memoize it and use it as the holy guideline for all platforms. Given that I didn''t even specify how the benchmark weighted between different uses of the container and said that it''s "almost independent of the type of operations", note the vague "almost", how can you really read it so strictly? I think you''re seriously underestimating the other readers here.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
You''re a *bit* too concerned about that particular number. I bet nobody''s going to just memoize it and use it as the holy guideline for all platforms. Given that I didn''t even specify how the benchmark weighted between different uses of the container and said that it''s "almost independent of the type of operations", note the vague "almost", how can you really read it so strictly?

If I hadn''t made any posts complaining about it, I''d have taken you up on the bet. And I''d give you 4 to 1 odds in your favor, too. If you didn''t want the number to be taken seriously, then you should have said yourself that it was compiler, stored type and platform dependent. But you didn''t, so I had to point it out. Plus, you''re post about T * vs. T implied that you, yourself believed that it was a meaningful number.
quote:
I think you''re seriously underestimating the other readers here.

LOL. You haven''t been hanging around these boards long, have you? This kind of thing has happened here before. list vs. vector threads are fairly common, and someone, like you, will say vector is better for 50, 100 or whatever number of elements, and some newbie will parrot that number in the next thread without understanding anything behind it. Even with the amount of stink I''ve made about it here, I''m still not betting that someone hasn''t already walked away with the wrong idea already. You get the same kind of parrotting with people saying C++ is x% faster than VB, or ints are x% faster than shorts, or other similar meaningless numbers. And since you''re hiding behind the Anonymous Poster moniker, there''s no post history to go by to see whether or not you''re one of these parrotting posters; hence no basis to see whether or not you believe that 100 was some magic number yourself.

Share this post


Link to post
Share on other sites
Performance isn''t a reason to choose list, you use list when the order matters, and either you need to perserve existing iterators during mutations (insertion & deletion) or you need atomic mutations (minimal bus-locking in SMP and minimal mutex hanging in multi-threaded environments). In exchange for this low-latency design objective, you sacrafice some throughput.

You can achieve decent insertion/deletion speed using a node cache (and splice them on), but every other operation on a list is slower than any other container. If the collection size is so large that vector is incapable, a list isn''t likely to solve the problem (a map, set, or hash is needed).

Share this post


Link to post
Share on other sites

  • Advertisement