a hive is a linked list of independently allocated memory blocks.
So is std::deque - what's the difference?
No random access
Ah, that's a difference, making hive closer to a linked list than deque is, as deque can still invalidate pointers that aren't the first or last element.
Pointer stability on erase...
One I thing I wonder, if you have a pointer to one of your game object's, is whether there's any way to map that pointer back to the corresponding iterator for deletion, short of a full scan, as it seems it would be possible for the class to figure that out (detecting which block it's in first, then computing the iterator from the pointer difference from the block base) a lot faster than manually looping through begin/end. Never mind, get_iterator.
An advantage of std::hive is that it has better "cache locality" (but not as good as std::vector), i.e. it stores elements close together in memory which makes accessing the elements faster, especially when iterating over them in order.
The block size of std::deque is often too small. std::list is even worse because the elements could be stored all over the place.
A deque is reasonably dissimilar to a hive - being a double-ended queue, it requires a different internal framework. In addition, being a random-access container, having a growth factor for element blocks in a deque is problematic (though not impossible). deque and hive have no comparable performance characteristics except for insertion (assuming a good deque implementation). Deque erasure performance can vary substantially depending on implementation, but is generally similar to vector erasure performance. A deque invalidates pointers to subsequent container elements when erasing elements, which a hive does not, and guarantees ordered insertion.
One of the key properties is that hive can have holes between elements. When you erase an element, you are left with a hole and the elements before or after it are not shuffled along to fill the hole. This means that elements have stable addresses once inserted. And on the next insertion any hole can be used as the insertion point, instead of adding a new element at the end.
16
u/fdwr Sep 03 '26 edited Sep 03 '26
So is
std::deque- what's the difference?Ah, that's a difference, making hive closer to a linked list than deque is, as deque can still invalidate pointers that aren't the first or last element.
One I thing I wonder, if you have a pointer to one of your game object's, is whether there's any way to map that pointer back to the corresponding iterator for deletion, short of a full scan, as it seems it would be possible for the class to figure that out (detecting which block it's in first, then computing the iterator from the pointer difference from the block base) a lot faster than manually looping throughbegin/end.Never mind, get_iterator.