I'm looking for a container (targeted towards game-development, especially for entity management) that needs to satisfy these requirements:
- Fast iteration
- No copies of stored elements
- No invalidation of pointers to the elements
- 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>>- Cache-friendly (fast iteration)
- No copies (thanks to
std::unique_ptr) - No invalidation of pointers (thanks to
std::unique_ptr)
...and...
std::list<T>- Non cache-friendly (slower iteration)
- No copies
- 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).