   List vs. Vector?
  I've used vectors for a while and was recently introduced to lists which seem to have very similar functionality.  In what cases would lists be more beneficial than vectors?   
  If you want a long description there's 1000s of hits for this common question. Otherwise enjoy this simple chart:;  Long story short, a vector is contiguous in memory, and thus inserting, erasing and resizing are potentially expensive, as slow as O(n). A list is a linked list,  more complicated and discontinuous, however insert and remove operate in constant time, or O(1), which is a lot faster (at least in notation, this may not be true is practice, big O is deceiving). There are many other differences with regard to iterators and specific functionality, but above is the primary differentiation between the two as concepts.   ;Long story short, a vector is contiguous in memory, and thus inserting, erasing and resizing are potentially expensive, as slow as O(n). A list is a linked list,  more complicated and discontinuous, however insert and remove operate in constant time, or O(1), which is a lot faster (at least in notation, this may not be true is practice, big O is deceiving). There are many other differences with regard to iterators and specific functionality, but above is the primary differentiation between the two as concepts.The tradeoff here is that while linked list can grow and contract very easily, it is comparatively slow to traverse, O(n) I believe (I'm not that great with algorithmic complexity, to be honest).  Since a linked list isn't contiguous in memory, the only way to find a given element is to traverse the list from node to node until you reach your destination, making random access (especially for a large linked list), not that cheap.A vector, being contiguous in memory, can be accessed like an array.  The program knows how big the vector is, where it starts, and how large each element is, allowing it to calculate the memory location of any given element in one step.  Random access in a vector should be O(1), if I'm not mistaken.Rule of thumb:  If your collection doesn't need to change size much, if ever, a vector is a really good collection to use.  Vectors have a very similar performance profile to arrays, but can be resized if need be, making them a popular alternative.  If your collection will be changing size a lot or require lots of dynamic insertion, a linked list might be more suited.However, in reality I use vectors more than most other collections, simply because I tend to use variable pools pretty heavily when I do game programming.   ;  [font="arial, verdana, tahoma, sans-serif"]The tradeoff here is that while linked list can grow and contract very easily, it is comparatively slow to traverse, O(n) I believe (I'm not that great with algorithmic complexity, to be honest).  Since a linked list isn't contiguous in memory, the only way to find a given element is to traverse the list from node to node until you reach your destination, making random access (especially for a large linked list), not that cheap.[/font]Yes, traversing a linked list is worst case O(n), however there is a lot that can be done to mitigate these problems. Sorting, for example, can increase real world performance in certain situations. Also consider that erasing from a vector may invalidate all and will certainlty invalidate iterators pointing to members subsequent to the one that was erased or inserted. Lists do not suffer from this behaviour.Your rule of thumb is generally correct, however one should not be naive about the implications of using either container (such as the behaviour of iterators), and often such rules are hard to apply in more complex, high performance systems. Personally, I favour lists, and will fall back on a vector where the benefits of random access or contiguous allocation are obvious. I like the graphic posted by karwosts, it's a good summary and shows a lot of the other containers which aren't as widely discussed.Who said C++ was easy? ;Who said C++ was easy? In reality, this really doesn't have anything to do with C++ specifically, just about the behavior and differences between various data structures.  The same conversation could be applied to C,C#, Java, etc.   ;  vector is a good start for any "bag" of objects. That is, if the objects aren't in a particular order and you generally want to add, remove or iterate quickly over all of them. Techniques such as the "swap and pop" trick and the remove/erase idiom mean that in practice vector can outperform despite the theoretical advantage of lists when it comes to random removals.Also in games you'll find that 97% of the time you are iterating and that removing an object is actually a rare event. While the above chart is very good, you also need to weigh the options by how frequently each operation is used. In this case it doesn't make sense to pick a data structure based on the fact that you rarely need to perform an expensive operation but spend most of your time desiring cheap iteration.As always, the "right answer" is subtle and elusive. There are always corner cases that invalidate the general answer.   ;  Kind of OT but will add to  the discussion: roughly how large does a data set need to be before convenience is outweighed by performance needs in modern computers?   ;Kind of OT but will add to  the discussion: roughly how large does a data set need to be before convenience is outweighed by performance needs in modern computers?Depends on the nature of the problem and the specific "modern computer" involved.For example, if the nature of your problem is an array of pointers or simple integers generally being accessed sequentially, this is very different from arrays of very large structures that jump around a lot which is also different from jumping through deeply nested pointer trees.Then, what is the "modern computer"?  An IBM z196 server that is fully maxed out with 80*24MB (about 2GB) of combined cache, you can have a lot before data access patterns become an issue, you'll face other performance issues first.  If you're talking about a PC with an intel i7 with 6 cores and 12MB on-die cache, you'll need a a few megabytes of data before memory access patterns becomes an issue.  If you're talking about a modern yet low-end low-power laptop's Core2 Celeron with 512K cache, it doesn't take much data before memory access patterns are important.   ;  That image is great. I've saved myself a copy.One thing though is that one could say it is somewhat incomplete. The number of paths leading to vector should be greater. For example if you have a bunch of items, order is not important, you need to find elements by key, but the container is filled during an initialisation phase and thereafter only finds are performed on it, then a using a sorted vector with lower_bound is more space and time efficient than a [multi]map/set.Also, when the maximum number of items the container will ever need to hold is small then other container types become preferably once again. Or if the object is expensive to copy, then that changes things.Obviously if everything had to be taken into account then the flowchart would be huge. On the whole though, it's fairly good as-is.   