Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
    
Re-added vector tag to this - if list is a valid tag, then vector is too. –  Kylotan Apr 18 '11 at 13:04
    
Presumably vector was removed because it's used to mean mathematical vector, not std::vector. –  user744 Apr 18 '11 at 13:34
1  
how about nix them both and put container. –  deft_code Apr 18 '11 at 14:32
    
@Kylotan: It's as Joe said. This question was definitely about vectors, but it didn't belong with the vector tag. –  Jonathan Hobbs Apr 19 '11 at 13:19
1  
So do we remove any ambiguous tag? That sounds like the wrong decision to me - better that your search turns up too much information than not enough. Skipping unwanted results is easier than brainstorming to find synonyms. –  Kylotan Apr 19 '11 at 14:22

5 Answers 5

up vote 26 down vote accepted

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.

share|improve this answer
1  
I think it highly depends on your needs, if you never need to access a specific element and just need to read all of them and you add and remove elements frequently, the list is a better solution. –  Frédérick Imbeault Oct 27 '10 at 16:48
    
Thanks, that gives me some ammo to shoot on my classmates... –  jokoon Oct 27 '10 at 16:49
7  
@Frédérick: That is the standard C++ wisdom, but it's also almost always wrong. Vectors, especially when dealing with vectors of pointers (which you almost always are for games), are extremely fast to remove stuff from the middle of - it is linear time, but it's a very very small overhead per item. It's also much faster to iterate sequentially over a vector. –  user744 Oct 27 '10 at 17:59
1  
@Frédérick Imbeault Modified isn't much of a problem it is Add\Remove that causes problems. From add\removed point to the end of the vector is copied to keep the vector contiguous. If element order doesn't matter you can swap the deleted element with the last element then pop that for delete and add to the end for add. –  stonemetal Oct 27 '10 at 20:41
3  
Well sure, taking the address of an element in a vector and storing that off isn't safe. But generally speaking you hardly ever do that, instead preferring to have a vector of pointers of elements and copying the pointer around (or something similar). –  Tetrad Oct 27 '10 at 22:48

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.

share|improve this answer
    
+1 for being the only person to mention deques - you get the contiguous memory and lookup speed benefits of vectors, with fast insert/remove at both ends. –  user744 Oct 27 '10 at 18:04

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 :

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

share|improve this answer
3  
That graph really needs to start with a "Are you storing pointers and less than a thousand? No -> vector" node. –  user744 Oct 27 '10 at 18:02
    
Yes maybe you are right, I did not consider the type stored it should also be analysed. –  Frédérick Imbeault Oct 27 '10 at 18:56

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.

share|improve this answer
    
Well I might have also put C in it, but there aren't such containers in C, but that's something to think about: is there some STL-like tibrary for C ? –  jokoon Oct 27 '10 at 16:48
    
I've used glib (library.gnome.org/devel/glib) in the past, which implements a number of standard data structures for C. I hated it because it's usually too verbose and desperately wants to be C++, but it's mature and stable. –  user744 Oct 27 '10 at 18:09

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.
share|improve this answer
2  
@bmcnett "[] .. but std::vector requires you to store everything for each object in a contiguous chunk of memory" - that's not a question of the container, its a question of your data-layout, you can have all position in a continuous chunk of memory with a std::vector: struct point{float x, y, z, w}; std::vector<point> positions; –  Maik Semder Apr 20 '11 at 7:14
    
my school are going to love this :) –  jokoon Apr 20 '11 at 9:51
    
-1 because this answer doesn't add anything to the list vs. vector discussion already here, and its claim about vector polluting the cache is wrong, as Maik says. –  user744 Apr 20 '11 at 14:18
    
you misunderstood my claim. i never said that among all the containers std::vector is particularly guilty of polluting the cache. all the containers, and in fact even arrays, are about equally guilty of that. std::vector is falling out of favor because C++ objects themselves are falling out of favor. C++ mandates that each object's data be contiguous in memory. you can get around that by avoiding C++ objects, for example by using std::vector<position> as mentioned above. –  bmcnett Apr 20 '11 at 17:13
1  
Except point is a C++ object (as is std::vector, as is something as simple as float). I know the distinction you're trying to draw, but you're doing a bad job of explaining it. –  user744 Apr 20 '11 at 18:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.