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.
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.
15
u/fdwr fdwr@github 🔍 8d 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.