A "drop-in replacement" would commit to all the weird things about the standard library type which result in poor performance, some of them might be important to you, and you'll probably insist oh, it's not a "drop-in" replacement if I can't have those, and across the entire C++ population that means there is no high performance drop-in replacement, the type guarantees any number of weird properties and you could depend on all those, so, too bad.

The most likely reliance you'd have is reference stability, maybe you give out references to items in the table and they're long lived so you mustn't invalidate them when/ if there's a resize, let alone on unrelated changes to a table which keeps the same size. Abseil, Boost and Folly all provide types which lose some performance to get this back if it's all you need to be "drop-in".

The most unlikely reliances are two fold, firstly maybe you insist on messing with the bucket API, which makes no sense in open addressed tables (ie all the ones with great performance). In this case you're wedded to std::unordered_map because the details of how the type is structured are welded into your code. Sucks to be you. Secondly though, you might have decided you care about the order, the std::unordered_map says it doesn't promise an order, but on a single platform none of the implementations actually kick you if you assume the order is preserved, so you can merrily write a unit test which checks that after adding fake users Alice, Bob and Carol to your user hash table, when asked for the users back in no particular order you get exactly: Carol, Alice, Bob. Is that a good unit test? No. But the replacements will make it go red, they're not "drop-in" replacements.

Indeed, Google's initial migration from std::unordered_map to swisstables moved everyone to absl::node_hash_map since it was safer, even though flat_hash_map generally offers better performance.

> after adding fake users Alice, Bob and Carol to your user hash table, when asked for the users back in no particular order you get exactly: Carol, Alice, Bob.

Ow :(

This reminded me of Matt Kulukundis at cppcon talking about migrating away from std::unordered_map, wherein he brought up this point exactly: https://youtu.be/JZE3_0qvrMg?t=740

Matt then goes on to describe how Abseil adds a nondeterministic iteration offset to each hash table to prevent anyone from relying on this moving forward.

Also: Unit test people, it's great that it's easy to check that "foo == 5" is true, and I can see why you thought it should be equally easy to check "foo == Carol, Alice, Bob" but could you perhaps nudge the developer to check they didn't mean "foo contains all of Carol, Alice, Bob" instead when they do that? Maybe have them pick "in order" versus "any order" with no default ?

There are a few more like this, case sensitivity is one, my newest colleague is going to write a test for "dnsName = example.com" even though actually dnsName might sometimes be "EXAMPLE.COM" or "Example.Com" or even "eXAMplE.cOM" and it'd be nice if they were nudged to spend that extra moment to decide whether that's OK or not before a test goes red spuriously.

Growable arrays are a very popular idea. Your preferred language almost certainly has them, but they might be built in to the language as an optimisation, if "normal" arrays in your language can grow and that's fast enough, chances are you're got the growable array type just as the only array, which is fine (but won't fly on tiny embedded systems).

This type has amortized O(1) aka constant time growth, which is one of those tricks which is amazing if you've never seen it before, then it just seeps into your understanding of the world and so it's easy to imagine why C++ doesn't do any better.

As a necessary optimisation beyond the amortized growth we must be able to tell a growable array hints about its future size. The only hint provided in the C++ STL is reserve, which tells the array its maximum final size. Rust calls this hint Vec::reserve_exact, if our array isn't this big, we should grow immediately, makes sense.

Here's where the problem kicks in: Suppose I don't know the maximum final size, but I do know I need to put say, at least 50 more things in the container? Algorithmically the answer is actually yes, the amortized growth can be preserved if we either grow sooner or skip growth steps and otherwise the hint can be ignored, this is Rust's Vec::reserve

If we try to use the C++ reserve here (aka Vec::reserve_exact) even though this isn't the final size, we destroy our amortized growth performance, our container may have lousy performance. If we just don't bother because we can't express our hint, our container has worse performance than necessary because we grow more often or less optimally.

But I've burned myself on this a few times before.

But I wonder what use case there is where you can't just push_back() one by one? The only potential issue here is that there might be a reallocation happening while append this range of N elements, but can't imagine what might break.

This is a Quality of Implementation issue in the library standard itself.

Never had a problem myself with that though, my main use case for std::vector is with reserve() right at the beginning and never provoking a reallocation (so I often end up coding up my own container to assert reallocation can't happen accidentally).

Sometimes (infrequently) I use the script-style push_back()-only pattern. But I feel very uneasy about uncontrolled reallocations in larger systems, and anyway they constrain the implementation space because of pointer and iterator invaliation.