Any better alternative to std::vector<std::unique_ptr<T>>?

Viewed 2724

I'm looking for a container (targeted towards game-development, especially for entity management) that needs to satisfy these requirements:

  1. Fast iteration
  2. No copies of stored elements
  3. No invalidation of pointers to the elements
  4. Removal and insertion of elements

Example:

Container<Entity> container;

// This pointer will always point to the player
Entity* player{new Entity};          
container.add(player);               

// Set some entities to "dead"
for(auto& e : container) if(e->type == "Enemy") e->die(); 

// Use erase-remove idiom on "dead" entities
container.cleanup();                 

// Player pointer is still valid
player->doSomething();               

I've tried two different container types so far:

  • std::vector<std::unique_ptr<T>>
    1. Cache-friendly (fast iteration)
    2. No copies (thanks to std::unique_ptr)
    3. No invalidation of pointers (thanks to std::unique_ptr)

...and...

  • std::list<T>
    1. Non cache-friendly (slower iteration)
    2. No copies
    3. No invalidation of pointers

Even if it seems counter-intuitive, std::vector<std::unique_ptr<T>> is more performant than std::list<T> according to my benchmarks.

(For bigger types, std::list<T> is more performant during insertion, but std::vector<std::unique_ptr<T>> still wins).


I was wondering if there is a better alternative to std::vector<std::unique_ptr<T>>.

Ideally, the alternative should be cache-friendly, for fast iteration, and allow the user to refer to the same items even after adding/removing existing items (pointers should not be invalidated).

2 Answers
Related