When to use an Array vs When to use a Vector, when dealing with GameObjects?

Question

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.

Answer 1

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.