How does C++26's std::hive work for inserting and erasing?
I'm trying to make my own (very basic) implementation of std::hive in C and to do that, I of course have to understand exactly how inserting and erasing works.
As I understand it, the index of a given block to insert into can be tracked by its free list, where the free head stores an index and the indices of the actual data itself is repurposed to form a linked list for empty slots
If the free head stores an individual index, and we need to insert into an index that is in the middle of an empty region, how do you figure out the left and right ends of the empty region in O(1) time without looping leftwards and rightwards?
For example, let's take this scenario, where slot 2 marks the start of a 5 slot empty region:
Slot index: 0 1 2 3 4 5 6 7 8 9
Skipfield: 0 0 5 X X X 5 0 0 0
I've used X in the middle as these can contain junk values as I understand. Now let's say that the free head stores index 4, and so when we insert into index 4, we need to update the values in the skipfield for slot indexes 2, 3, 5 and 6 to match their new values (2), so that we get:
Slot index: 0 1 2 3 4 5 6 7 8 9
Skipfield: 0 0 2 2 0 2 2 0 0 0
But how do we actually figure out in constant time where these boundaries are? If we are only given the index to insert to? Do we somehow store ranges of values instead of individual indicies on the free list?
Posted Sep 2, 2026, 12:45 PM UTC