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 understand that from other answers, Arrays and Vectors are the best choices. Many on SE claim that Linked Lists and Maps are bad for video game programming.

I understand that for the most part, I can use Arrays. However, I don't really understand exactly when to use Vectors over Arrays.

Why even use Vectors? Wouldn't it be best if I simply always used an Array, that way I know how much memory my game needs?

Specifically my game would only ever load a single "Map" area of tiles, such as Map[100][100], so I could very easily have an array of GameObjectContainer GameObjects[100][100], which would reserve an entire map's worth of possible gameobjects, correct?

So why use a Vector instead? Memory is quite large on modern hardware.

share|improve this question
    
related: gamedev.stackexchange.com/questions/4887/… –  Tetrad Jun 25 '13 at 20:07
1  
There are times you want things to be fixed sized, and there are times you want to dynamically sized. The use cases for that determines which one you'll be using. But as an aside, you should probably be using std::array for fixed-sized arrays instead of C-arrays since they're designed for similar safety that vectors are. –  Tetrad Jun 25 '13 at 20:15
    
Thank you @Tetrad –  user1123 Jun 25 '13 at 22:32
    
linked lists are fine for games - just not naively heap-allocated structures like std::list. an inline (zero-allocation overhead) linked list is great if used properly. likewise, std::map and std::unordered_map can be problematic, but a well-written tree or hash table that plays nicely with memory and cache is invaluable. be wary of any advice that claims some technique is always too slow or perfectly fast - as much truth as those claims might be founded in, there's always more details you have to consider (and measure!) for each situation. –  Sean Middleditch Jun 25 '13 at 23:46
add comment

1 Answer

Vectors are dynamically sized (usually) random access containers. They facilitate constant time look ups to any location within the array, and better yet, their direct storage is contiguous. The biggest (and its a big one) downside to vectors is the performance hit when they need to grow. Vectors typically allocate a certain capacity, and this capacity is expanded whenever it is either full, or when the vector size reaches a specific threshold. Due to vectors requiring contiguous memory to maintain constant time random access, they must allocate an entirely new block of memory of the appropriate size, and copy over the contents. This is slow.

Linked lists on the other hand are linear access containers, requiring you to walk the list (either from beginning or end), this makes it difficult if you need access to a specific member of the list. The major benefit of linked lists is the ability to add, and remove data members in constant time. Linked lists are not contiguous.

Maps/Hash maps are often built on top of a container such as a vector (though it could just be a standard C-style array), and provide constant time look ups via key, as opposed to index. They suffer the same disadvantages that vectors do. The efficiency of a hash map depends on the efficiency of the hash function. It is not uncommon for a hashing algorithm to be unique to the data set, as opposed to a simple modulus bucket count operation

All data types are suitable at times, and you should always approach each problem differently.

EDIT - There are numerous reasons to avoid standard C-style arrays, and they usually come back to user error. One of the biggest issues is the risk of writing beyond the bounds of the array, and modifying something else in memory. This can be an extremely difficult bug to detect, and even harder to fix. Additionally, c-style arrays dont have integrated support for STL algorithms, iterators, and allocators.

share|improve this answer
add comment

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.