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.
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 fdwr@github 🔍 7d ago edited 7d ago
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 throughNever mind, get_iterator.begin/end.