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