std::map is an associative container that stores elements in a sorted order. It is implemented as a balanced binary search tree, usually red-black, which allows for logarithmic lookups and insertions. This upper bound works great for random inputs, but is not ideal for special cases like already sorted inputs, since, it’s easy to create a balanced binary search tree in O(N)
for such cases,
instead of O(N*log(N))
if we use std::map insert/emplace.
Fortunately, not all is lost and since C++11, emplace_hint can help.
Let’s compare regular emplace with emplace_hint for handling sorted inputs.
Since all input elements are sorted, we know that the each element should be inserted at the end and that’s exactly what we use as a hint.
1.5X speedup! What’s the moral of the story? It’s not a secret that it’s very useful to ask questions about inputs during coding interviews and adjust algorithms to take advantage of this knowledge. And for library authors it’s important to provide APIs that can capture as much knowledge about inputs as possible and use it to pick the best algorithm.