I am making a first person shooter and I know about about a lot of different container types but I would like to find the container that is the most efficient for storing dynamic objects that will be added and deleted from the game quite frequently. EX-Bullets.

I think in that case it would be a list so that the memory is not contiguous and there is never any re sizing that is going on. But then I am also contemplating using a map or set. If anyone has any helpful information I would appreciate it.

I am writing this in c++ by the way.

Also I came up with a solution that I think will work.

To start off I am going to allocate a vector of a big size.. say 1000 objects. I am going to keep track of the last added index in this vector so that I know where the end of the objects are. Then I will also create a queue that will hold the indices of all objects that are "deleted" from the vector. (No actual deleting will be done, I will just know that that slot it free). So if the queue is empty I will add to the last added index in the vector + 1, else I add to the index of the vector that was at the front of the queue.

  • \$\begingroup\$ Any specific language you are targeting? \$\endgroup\$
    – Phill.Zitt
    Commented Aug 8, 2012 at 20:17
  • \$\begingroup\$ This question is too hard to answer without a good many more specifics, including hardware platform, language/frameworks, etc. \$\endgroup\$ Commented Aug 8, 2012 at 20:20
  • 1
    \$\begingroup\$ Pro tip, you can store the free list in the memory of the deleted elements (so you don't need the extra queue). \$\endgroup\$
    – Jeff Gates
    Commented Aug 8, 2012 at 22:54
  • 2
    \$\begingroup\$ Is there a question in this question? \$\endgroup\$ Commented Aug 9, 2012 at 1:02
  • \$\begingroup\$ Note that you don't have to keep track of the largest index nor have to preallocate a number of elements. std::vector takes care of all that for you. \$\endgroup\$
    – API-Beast
    Commented Aug 9, 2012 at 1:37

4 Answers 4


The answer is always to use an array or std::vector. Types like a linked list or a std::map are usually absolutely horrendous in games, and that definitely includes cases like collections of game objects.

You should store the objects themselves (not pointers to them) in the array/vector.

You want contiguous memory. You really really want it. Iterating over any data in non-contiguous memory imposes a lot of cache misses in general and removes the ability for the compiler and CPU to do effective cache prefetching. This alone can kill performance.

You also want to avoid memory allocations and deallocations. They are very slow, even with a fast memory allocator. I've seen games get a 10x FPS bump by just removing a few hundred memory allocations each frame. Doesn't seem like it should be that bad, but it can be.

Lastly, most data structures that you care about for managing game objects can be far more efficiently implemeted on an array or a vector than they can with a tree or a list.

For instance, for removing game objects, you can use swap-and-pop. Easily implemented with something like:

std::swap(objects[index], objects.back());

You could also just mark objects as deleted and put their index on a free list for the next time you need to create a new object, but doing the swap-and-pop is better. It lets you do a simple for loop over all live objects with no branching aside from the loop itself. For bullet physics integration and the like, this can be a significant performance boost.

More importantly, you can find objects with a simple pair of table lookups from a stable unique is using the slot map structure.

Your game objects have an index in their main array. They can be very efficiently looked up with just this index (much faster than a map or even a hash table). However, the index is not stable due to the swap and pop when removing objects.

A slot map requires two layers of indirection, but both are simple array lookups with constant indices. They are fast. Really fast.

The basic idea is that you have three arrays: your main object list, your indirection list, and a free list for the indirection list. Your main object list contains your actual objects, where each object knows its own unique ID. The unique ID is composed of an index and a version tag. The indirection list is simply an array of indices to the main object list. The free list is a stack of indices into the indirection list.

When you create an object in the main list, you find an unused entry in the indirection list (using the free list). The entry in the indirection list points to an unused entry in the main list. You initialize your object in that location, and set its unique ID to the index of the indirection list entry you chose and the existing version tag in the main list element, plus one.

When you destroy an object, you do the swap-and-pop as normal, but you also increment the version number. You then also add the indirection list index (part of the object's unique ID) to the free list. When moving an object as part of the swap-and-pop, you also update its entry in the indirection list to its new location.

Example pseudo-code:

  int index
  int version
  other data

  Object objects[]
  int slots[]
  int freelist[]
  int count

    index = indirection[id.index]
    if objects[index].version = id.version:
      return &objects[index]
      return null

    index = freelist.pop()

    objects[count].index = id
    objects[count].version += 1

    indirection[index] = count

    Object* object = &objects[count].object

    count += 1

    return object

    index = indirection[id.index]
    if objects[index].version = id.version:
      objects[index].version += 1
      objects[count - 1].version += 1

      swap(objects[index].data, objects[count - 1].data)

The indirection layer allows you to have a stable identifier (the index into the indirection layer, where entries do not move) for a resource that can move during compaction (the main object list).

The version tag allows you to store an ID to an object that might be deleted. For example, you have the id (10,1). The object with index 10 is deleted (say, your bullet hits an object and is destroyed). The object in that location of memory in the main object list then has its version number bumped, giving it (10,2). If you try to look up (10,1) again from a stale ID, the lookup returns that object through index 10, but can see that the version number has changed, so the ID is no longer valid.

This is the absolute fastest data structure you can have with a stable ID that allows objects to move in memory, which is important for data locality and cache coherence. This is faster than any implementation of a hash table possible; a hash table at the very least needs to calculate a hash (more instructions than a table lookup) and then has to follow the hash chain (either a linked list in the horrible case of std::unordered_map, or an open-addressed list in any not-stupid implementation of a hash table), and then has to do a value compare on each key (no more expensive, but possible less expensive, than the version tag check). A very good hash table (not the one in any implementation of the STL, as the STL mandates a hash table that optimizes for different use cases than you game about for a game object list) might save on one indirection, but wil be a larger bloated structure that you can't iterate over at maximum efficiency, and loses out in real-world performance for use cases like this one.

There are various improvements you can make to the base algorithm. Using something like a std::deque for the main object list, for instance; one extra layer of indirection, but allows objects to be inserted into a full list without invalidating any temporary pointers you've acquired from the slotmap.

You can also avoid storing the index inside the object, as the index can be calculated from the object's memory address (this - objects), and even better is only needed when removing the object in which case you already have the object's id (and hence index) as a parameter.

Apologies for the write-up; I don't feel it's the clearest description it could be. It's late and it's difficult to explain without spending more time than I have on code samples.

  • 1
    \$\begingroup\$ You are trading off an extra deref and a high alloc/free cost (swap) every access for 'compact' storage. In my experience with video games, that's a bad trade :) YMMV of course. \$\endgroup\$
    – Jeff Gates
    Commented Aug 9, 2012 at 8:32
  • 1
    \$\begingroup\$ You don't actually do the dereference that often in real world scenarios. When you do, you can store the returned pointer locally, especially if you use the deque variant or know you won't be creating new objects while you have the pointer. Iterating over the collections is a very expensive and frequent operation, you need the stable id, you want memory compaction for volatile objects (like bullets, particles, etc), and the indirection is very efficient on modem hardware. This technique is used in more than a few very high performance commercial engines. :) \$\endgroup\$ Commented Aug 9, 2012 at 20:37
  • 1
    \$\begingroup\$ In my experience: (1) Video games are judged on worst case performance, not average case performance. (2) You normally have 1 iteration over a collection per frame, thus compacting simply 'makes your worst case less frequent'. (3) You often have many allocs/frees in a single frame, high cost means you limit that capability. (4) You have unbounded derefs per frame (in games I've worked on, including Diablo 3, often the deref was the highest perf cost op after moderate optimization, >5% of server load ). I don't mean to dismiss other solutions, just pointing out my experiences and reasoning! \$\endgroup\$
    – Jeff Gates
    Commented Aug 10, 2012 at 20:05
  • 3
    \$\begingroup\$ I love this data structure. I'm surprised it's not more well-known. It's simple and solves all the problems that have been making me bang my head for months. Thanks for sharing. \$\endgroup\$
    – jbatez
    Commented Nov 23, 2013 at 3:17
  • 3
    \$\begingroup\$ Any newbie reading this should be very wary of this advice. This is a very misleading answer. "The answer is always to use an array or std::vector. Types like a linked list or a std::map are usually absolutely horrendous in games, and that definitely includes cases like collections of game objects." is greatly exaggerated. There is no "ALWAYS" answer, otherwise these other containers wouldn't have been created. To say maps/lists are "horrendous" is also hyperbole. There are A LOT of video games which use these. "Most Efficient" is not "Most Practical" and can be misread as a subjective "Best". \$\endgroup\$
    – user50286
    Commented May 20, 2015 at 7:04

fixed size array (linear memory)
with internal free list (O(1) alloc/free, stable indicies)
with weak reference keys (reuse of slot invalidates key)
zero overhead dereferences (when known-valid)

struct DataArray<T>
  void Init(int count); // allocs items (max 64k), then Clear()
  void Dispose();       // frees items
  void Clear();         // resets data members, (runs destructors* on outstanding items, *optional)

  T &Alloc();           // alloc (memclear* and/or construct*, *optional) an item from freeList or items[maxUsed++], sets id to (nextKey++ << 16) | index
  void Free(T &);       // puts entry on free list (uses id to store next)

  int GetID(T &);       // accessor to the id part if Item

  T &Get(id)            // return item[id & 0xFFFF]; 
  T *TryToGet(id);      // validates id, then returns item, returns null if invalid.  for cases like AI references and others where 'the thing might have been deleted out from under me'

  bool Next(T *&);      // return next item where id & 0xFFFF0000 != 0 (ie items not on free list)

  struct Item {
    T item;
    int id;             // (key << 16 | index) for alloced entries, (0 | nextFreeIndex) for free list entries

  Item *items;
  int maxSize;          // total size
  int maxUsed;          // highest index ever alloced
  int count;            // num alloced items
  int nextKey;          // [1..2^16] (don't let == 0)
  int freeHead;         // index of first free entry

Handles everything from bullets to monsters to textures to particles, etc. This is the best data structure for video games. I think it came from Bungie (back in the marathon/myth days), I learned about it at Blizzard, and I think it was in a game programming gems back in the day. It's probably all over the games industry at this point.

Q: "Why not use a dynamic array?" A: Dynamic arrays cause crashes. Simple example:

foreach(Foo *foo in array)
  if (ShouldSpawnBaby(*foo))
    Foo &baby = array.Alloc();
    foo->numBabies++; // crash!

You can imagine cases with more complication (like deep callstacks). This is true for all array like containers. When making games, we have enough understanding of our problem to force sizes and budgets on everything in exchange for performance.

And I can't say it enough: Really, this is the best thing ever. (If you don't agree, post your better solution! Caveat - must address the issues listed at the top of this post: linear memory/iteration, O(1) alloc/free, stable indices, weak references, zero overhead derefs or have an amazing reason why you don't need one of those ;)

  • \$\begingroup\$ What do you mean with dynamic array? I am asking this because DataArray seems also allocating an array dynamically in ctor. So it might have some different meaning with my understanding. \$\endgroup\$
    – Eonil
    Commented Mar 9, 2014 at 16:18
  • \$\begingroup\$ I mean an array that resizes/memmoves during its use (as opposed to its construction). An stl vector is an example of what I'd call a dynamic array. \$\endgroup\$
    – Jeff Gates
    Commented Mar 12, 2014 at 3:34
  • \$\begingroup\$ @JeffGates Really like this answer. Fully agree re accepting worst case as standard case runtime cost. Backing the free linked list using existing array is very elegant. Questions Q1: Purpose of maxUsed? Q2: What's the purpose of storing index in the low-order bits of id for alloc'ed entries? Why not 0? Q3: How does this handle entity generations? If it doesn't, I'd suggest using Q2's low-order bits for ushort generation count. - Thanks. \$\endgroup\$
    – Engineer
    Commented Nov 30, 2015 at 18:39
  • 2
    \$\begingroup\$ A1: Max used allows you to cap your iteration. Also you amortize any construction cost. A2: 1)You often go from item -> id. 2)It makes the compare cheap/obvious. A3: I'm not sure what 'generations' means. I'll interpret this as 'how do you differentiate the 5th item allocated in slot 7 from the 6th item?' where 5 and 6 are the generations. The proposed scheme uses one counter globally for all slots. (We actually start this counter at a different number for each DataArray instance to more easily differentiate ids.) I'm sure you could rejigger the bits per item tracking was important. \$\endgroup\$
    – Jeff Gates
    Commented Nov 30, 2015 at 19:31
  • 1
    \$\begingroup\$ @JeffGates - I know this is an old topic but I really like this idea, could you give me some info on the inner workings of void Free(T &) over void Free(id)? \$\endgroup\$
    – TheStatehz
    Commented Mar 16, 2017 at 1:36

There is no right answer to this. It all depends on the implementation of your algorithms. Just go with one you think is best. Don't try to optimize at this early stage.

If you are often deleting objects and recreate them, I suggest you look at how object-pools are implemented.

Edit: Why complicate things with slots and what not. Why not just use a stack and pop the last item off and reuse it? So when you add one, you will do ++, when you pop one you do -- to keep track of your end index.

  • \$\begingroup\$ A simple stack doesn't handle the case where items are deleted in arbitrary order. \$\endgroup\$
    – Jeff Gates
    Commented Aug 9, 2012 at 8:39
  • \$\begingroup\$ To be fair, his goal wasn't exactly clear. At least not to me. \$\endgroup\$
    – Sidar
    Commented Aug 9, 2012 at 12:30

It depends on your game. The containers are different in how fast the access to a specific element is, how quickly a element is removed and how quickly a element is added.

  • std::vector - Fast access and removing and adding to the end is fast. Removing from the beginning and the middle is slow.
  • std::list - Iterating over the list is not much slower than a vector but accessing a specific point of the list is slow (because iterating is basically the only thing you can do with a list). Adding and Removing items anywhere is fast. Most memory overhead. Non-continous.
  • std::deque - Fast access and removing/adding to the end and beginning is fast but slow in the middle.

Usually you want to use a list if you want your object list sorted in a different way than chronocially and thus have to insert new objects rather then append, a deque otherwise. A deque has increased flexiblity over a vector but doesn't really have much of a downside.

If you have really a lot entities you should take a look at Space Partitioning.

  • \$\begingroup\$ Not true re: list. Deque advice depends entirely on deque implementations, which vary wildly in speed and execution. \$\endgroup\$ Commented Jul 31, 2017 at 9:23

Not the answer you're looking for? Browse other questions tagged .