Introduction
hive is a formalization, extension and optimization of what is typically known as bucket arrays in game programming circles. Similar data-structures are used in high-performance computing, high performance trading, 3D-simulation, particle simulations, robotics fields.
In a typical game engine, data is heavily interlinked, iterated often(everytime a frame is rendered) and changing continuously. Most games have an Entity class. Entities link to shared resources such as sprites, sounds etc. These shared resources are usually located in separated containers so that they can be reused by multiple entities. Entities in turn are referenced by other superstructures within a game engine, such as quadtrees / octrees, level structures and so forth.
Entities may be erased at any time (for example, a wall gets destroyed and no longer is required to be processed by the game engine) and new entities may also be inserted (for example, a new enemy is spawned). While this is all happening, the links between entities, shared resources and superstructures such as levels and quadtrees, must stay valid in order for the game to run.
If we use vector as a container to store game entities, it loses pointer validity to elements within it upon insertion, and pointer/index validity upon erasure.
We desire a container that allows constant-time insertion / erasure, fast iteration performance, yet offers pointer stability.
References
- Introduction of
std::hiveto the standard library, proposal, by Matt Bentley.