CODEWITHSUNDEEP
c++data-structures
kapesu8
kapesu8

Reputation: 95

Storing large numbers of short-lived game objects in C++

How would I store massive amount of objects (Like bullets or such changing constantly), and then remove them by their index? I've heard that vector::erase isn't very efficient.

Upvotes: 3

Views: 965

Answers (6)

permeakra
permeakra

Reputation: 622

(in)Famous Alexandrescu considers main problem with short-living dynamic small object slow new/free operators and recommends use of custom allocator. std::map will use much of such objects (it uses red-black tree internally), so it is a good idea to either use a pool of preallocated objects or std::map with custom allocator (possibly one taken from Alexandresu's Loki library)

Upvotes: 1

Mike Seymour
Mike Seymour

Reputation: 254431

vector::erase isn't very efficient since it needs to move all the following elements to fill the space in order to preserve the order. However, it sounds like you don't need to preserve the order, in which case you can remove an element much more quickly by replacing it with the one at the end, and then dropping the last element:

std::swap(bullets[index_to_remove], bullets.back());
bullets.pop_back();

Upvotes: 0

japreiss
japreiss

Reputation: 11251

From my extremely limited secondhand knowledge of game engine programming, dynamic memory allocation is avoided when possible. So an unordered_set or list would be a major no for a "massive amount" with frequent removals.

Edit: after reading @James Kanze's answer I realize that @Cameron's suggestion of swapping removed bullets with the last element doesn't work because it changes the indices of live bullets. I guess you'd have to use James's suggestion, or possibly a bit vector to mark dead bullets.

Keeping the bullets compacted in an array would be great for cache performance too. A hash table would cache better than std::map's red-black tree, but why incur the overhead of hashing if you already refer to the bullets by index?

Upvotes: 0

James Kanze
James Kanze

Reputation: 153909

If you're identifying the bullets by their index in the vector, then erase isn't a good idea; it will change the index of all of the following elements. The fact that a bullet is identified by its index constrains your choices somewhat. The best solution in that case is probably to simply mark the entry as invalid, and reuse it later, either by keeping a list of invalid indexes (easily done in an std::vector), or simply by scanning the vector each time you want to create a new bullet. If you have different types of bullets (and you probably will, as the game evolves), you'll need to allocate the bullets dynamically anyway, keeping a pointer in the vector; a null pointer is then a good choice for invalid.

Upvotes: 0

Puppy
Puppy

Reputation: 146910

unordered_set<Bullet*> will do fine. Then you can simply use a Bullet* everywhere and forget indexing. Best allocated from an object pool or something like that.

Or, since the Standard kindly screwed up the interface, you may need instead std::unordered_map<Bullet*, std::unique_ptr<Bullet>> for the better exception safety and such.

Upvotes: 1

Alexander Gessler
Alexander Gessler

Reputation: 46607

Use std::map (or C++11s std::unordered_map), these containers have better amortized runtime complexity for insertion and erase operations. std::list is also an option (its the obvious option, but I mentioned the others first since they also allow quick lookup/search which is in many game scenarios even more important).

At a higher level, you should definitely read up on C++ containers and what runtime complexity is in general. A wise choice of container structures is essential to good performance.

Upvotes: 2

Related Questions