When should vector/list be used?

Question

I can understand when to use lists, but I don't understand when it is better to use vectors than using lists in video games: when it is better to have fast random access ?

(And I understand why it's faster to insert/delete in lists because it just removes/adds pointers, but it still has to find the corresponding item...)

Answer 1

My rule of thumb, and I'm sure there will be debate on this, is to never use lists (unless you need to very, very frequently remove things from the middle of large lists).

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.

Answer 2

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 flexable.

Answer 3

Your choice should reflect your needs. All the elements of the vectors are continous in memory and lists has pointers to next / previous elements so they each have their advantage / disavantages :

Lists :

• Each elements takes 2 integers to point previous and next elements, so most commonly, that's 8 bytes more for each elements in your list
• Insert is linear in time : O(n)
• Remove is a constant operation : O(1)
• Access the x element is linear in time : O(n)

Vectors :

• Needs less memory (no pointers to other elements, it's a simple math algorithm)
• Remove is linear in time : O(n)
• Access the x element is constant : O(1) (That's because the elements are continious in memory so it's a simple math operation vectorPtr + ( x * bytesOfTheType ) )
• Insert can be in linear time, but most commonly, it's a constant operation : O(1) (That's because the vector in an array but always reserve 2 times it's capacity when the array is full so array copy is not frequent )

So list is better when you program needs to add and remove elements frequently, but never access (or rarely access) a particular element without the need of the others before. The vector should be used for better access time, but lacks effeciency when you need to remove or add elements.

Check this post on stackoverflow, it present a really nice graph with basic questions on your needs that drives you to a specific container depending on your answers :

https://stackoverflow.com/questions/366432/extending-stdlist

Answer 4

Usually lists are used for structures like queues where there are lots of append and remove operations. Example: An ever changing list of entities that should be updated. The list itself only contains entities on screen and therefore changes frequently.

Vectors (or arrays) are better suited for a collection that doesn't change that much and where you need fast access to individual items within the collection. Example: A tile-map where you have to lookup tiles at a given index.

Tetrads opinion might be true, but it depends on the programming language that is used. I see that you tagged your question c++, but I tried to give an answer that isn't language-specific.

Answer 5

In console games we never, ever use std::list because:

1. it does memory allocations whenever you add a new item. memory allocations are slow.
2. it's full of pointers. pointers are bad. a pointer is a cache miss. a cache miss is bad.

even std::vector is losing favor on consoles because:

1. you often care only about, for example, the positions of all the objects. like for example you want to collide the objects with each other, in which case you don't care what their color is. so you want all the positions to be contiguous in memory and you want the colors to be somewhere else far away, to avoid polluting the cache. but std::vector requires you to store everything for each object in a contiguous chunk of memory (e.g. position then color.) so if you do work that reads only the positions, you need to read all the colors into the cache too, even if you don't use them. this is wasteful.