I saw an answer a while ago on StackOverflow regarding a provably optimal
std::vector-like data structure, which, if I remember correctly, lazily copied elements onto a larger vector so that it wouldn't cause a huge pause every time the vector reallocated.
I remember it needed O(sqrt(n)) extra space for bookkeeping, and that the answer linked to a published paper, but that's about all I remember.
The problem: I'm having a really hard time searching for it -- you can imagine that searches like optimal vector or based on the tag
vector are getting me nowhere.
How can I search for questions like this?
I was actually considering posting this on StackOverflow, and waiting for it to be closed as a dupe... would that be considered bad practice? (!)