Another name for that is "B* tree". Or anyway a thing with similar performance characteristics.
I would hate to have to do a full balanced b-tree on short notice. (We also had rather terrible extra requirements that made using an off-the-shelf thing from, say, the STL work in our environment).
another implementation strategy, at the cost of using some extra memory, is to allocate the new space, but only copy over a bit at a time, each time a new element is added -- so every add is still O(1). no long pauses.
(well, assuming the memory alloc is still fast. which i think it should be in practice? tho i'm not super familiar w/ that stuff.)
just curious, do you think that solution would have worked for your situation too?
You can start playing games by accelerating capacity allocation when a vector rapidly starts growing extremely large. This doesn't solve the problem that vectors sometimes guarantee too much for what you need.
https://github.com/samsquire/btree
I tried to keep the implementation as simple as I could.
Targeting MSVC, use boost::deque or something, instead. Boost containers are generally fairly good, although they are more or less unmaintained nowadays. (E.g., boost::unordered_map::reserve doesn't work.) Or, like many of us, ignore performance on MS targets because anybody who cares about performances is running something else.
Longer answer is that the size of the "blocks" is limited to 512 bytes or one element, whichever is larger. So unless your elements are really tiny, it is strictly a pessimization.
I think there's a very good reason why old gamedevs who were stuck with developing on Windows largely ignored the STL and made their own containers / utility functions: MSVC's STL was just awful.
Here's a link to an old HN discussion that offers some insight on the performance of MSVC's STL in debug.
https://news.ycombinator.com/item?id=18939260
The "cursed" keyword hand-waves over the problem and suggests it originates in the acritical propagation of ignorant beliefs. Sometimes clarifying these is just a Google search away.
That's a strange take. Surely games still represent a significant chunk of the demand for C++ developers that need to care about performance?