hive is a formalisation, extension and optimization of what is typically known as a ‘bucket array’ container in game programming
The concept of a bucket array is: you have multiple memory blocks of elements, and a boolean token for each element which denotes whether or not that element is ‘active’ or ‘erased’, commonly known as a skipfield. If it is ‘erased’, it is skipped over during iteration. When all elements in a block are erased, the block is removed, so that iteration does not lose performance by having to skip empty blocks. If an insertion occurs when all the blocks are full, a new memory block is allocated.
It seems a little similar to a std::deque with the addition of flags to mark elements as erased to avoid reallocating blocks.
The main advantage is stable references and iterators with minimal extra allocations/deallocations.
I’ve built similar structures in my own game engine where I keep a sorted list of free indexes, so new entries fill up the earliest free index, and on average the empty entries stay at the end with valid entires staying packed together in contiguous memory at the beginning.
Just quoting from the introduction:
It seems a little similar to a std::deque with the addition of flags to mark elements as erased to avoid reallocating blocks.
The main advantage is stable references and iterators with minimal extra allocations/deallocations.
I’ve built similar structures in my own game engine where I keep a sorted list of free indexes, so new entries fill up the earliest free index, and on average the empty entries stay at the end with valid entires staying packed together in contiguous memory at the beginning.