[blahgeek]

While I very much appreciate and respect author's detailed analysis, I am still not 100% convinced without a corresponding benchmark result. If it's really O(log n) vs O(1), it should be very easy to verify in some micro-benchmark.

Instead of that, the author mentioned that:

> The tests that I did run, initially the libstdc++ and the libc++ versions have roughly the same performance, but the performance diverges after a number of insertions somewhere between 6,400 and 12,800. After that the runtime of the libc++ version is roughly 2-3 times that of the libstdc++ version. (...) the outcomes of which depend on the compiler version anyway.

This does not seem right.

[x1f604]

Here are the results of the benchmark that I did: https://imgur.com/a/2lCktTO

It didn't look quite right to me so I didn't post it.

Here's another benchmark that I did where you can clearly see that something has gone wrong: https://imgur.com/a/s2rA8qE