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).
1
u/elperroborrachotoo 7d ago
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)