Game Programming : C++ Vector/list for better performance

Use a list when iterator invalidation caused by modifying the middle of your data structure is going to cause a problem, or you need to keep your elements sorted so the swap and pop trick for quick middle collection deletes won’t work and you have a large number of mid collection deletes.

You may also want to consider using a Deque. It has similar performance characteristics to a vector but doesn’t have vector’s need for contiguous memory, and is a little more flexible.

The speed you’ll gain by having all your elements in your container in contiguous memory (and therefore more cache-friendly) is worth the offset of the additional costs of adding/removing/resizing the vector.

Edit: Just to clarify a bit more, of course it should go without saying that any kind of “which is faster” question should be tested on whatever platform with whatever data sets are pertinent to your particular needs. If I just need a collection of elements I just use vector (or deque, which is almost the same thing) unless there’s a good reason not to.

Advertisements