12
you are viewing a single comment's thread
view the rest of the comments
[-] xthexder@l.sw0.com 5 points 6 days ago

Just quoting from the introduction:

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.

this post was submitted on 21 Aug 2026
12 points (100.0% liked)

C++

2348 readers
8 users here now

The center for all discussion and news regarding C++.

Rules

founded 3 years ago
MODERATORS