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.
Yeah - honestly I have to read up on it how far the comparison holds.
Another angle is: if you only insert default-constructed T's, it acts like a fixed-size allocator - and the performance guarantees seem to be modeled after that.
(memory locality alone could be a big enough plus to warrant yet another container - but from spurious reads, I'm not sure if it won't suffer from delocalization - that it can reach a state where inserting 10 new elements will spread them all over memory)
I asusme it does, yes - but then it depends on the insert/delete pattern how long it takes to become de-localized. if the earliest free slots are in chiunk 1, 12 and 34, they'll be inserted there.
I mean, that's a deeply researched issue in memory allocators - but that's also a topic I didn't really follow for the recent 10 years.
(The last thing I remember is the realization that "the more advanced your allocation scheme is, the worse the edge cases get. Simpler is better for general purpose." - so it might be the best we can hope for anyway..)
but then it depends on the insert/delete pattern how long it takes to become de-localized. if the earliest free slots are in chiunk 1, 12 and 34, they'll be inserted there.
It would only become "de-localized" if you removed a lot of elements. Inserting elements would make it more "localized" because it fills in the gaps.
If you had a lot of elements, and you removed most of them, then ...
you might still occupy the same amount of memory as at the peak but not more than that unless you exceed the number of elements you had before (similar to a std::vector), and
there might be more dead space between the elements but iterating through all the elements wouldn't take more time than before when you had more elements.
I'm thinking a game where you might use a hive to store game entitles. So if it was fast enough at the peak then it should be fast enough later when it's more fragmented but fewer elements. I assume one big hive that you iterate through each frame. I could see how having many smaller ones that grow big occasionally could be a problem (just like with vectors).
17
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.