std::map try emplace vs emplace strange behaviour

The common advice is to prefer using std::map::try_emplace in preference to std::map::emplace in almost every instance.

I wrote a simple test to trace object creation/copying/moving/destruction when calling those functions, with and without clashes, and the results show that try_emplace incurs an extra move and destruction of the key when it is not already in the map.

Why the difference in behaviour?

I do know that moves and destructions of moved-from objects are usually cheap, especially so for trivial keys, but I was still surprised by the results as they seem to imply that for some cases emplace might be more efficient.

Compiler explorer link (Clang 14, libc++, -O3)

Source:

#include <map>
#include <iostream>

struct F {
    F(int i): i(i) { std::cout << "- ctor (" << i << ")\n"; }
    ~F() { std::cout << "- dtor (" << i << ")\n"; }
    F(const F& f): i(f.i) { std::cout << "- copy ctor (" << i << ")\n"; }
    F(F&& f): i(f.i) { std::cout << "- move ctor (" << i << ")\n"; }
    F& operator=(const F& f) { i = f.i; std::cout << "- copy (" << i << ")\n"; return *this; }
    F& operator=(F&& f) { i = f.i; std::cout << "- move (" << i << ")\n"; return *this; }
    bool operator <(const F& f) const { return i < f.i; }
    int i{};
};

int main() {
    std::map<F, F> m;
    std::cout << "emplace 1:\n";
    m.emplace(1, 2);
    std::cout << "emplace 2:\n";
    m.emplace(1, 3);
    std::cout << "clear:\n";
    m.clear();
    std::cout << "try_emplace 1:\n";
    m.try_emplace(1, 2);
    std::cout << "try_emplace 2:\n";
    m.try_emplace(1, 3);
    std::cout << "done:\n";
}

Results:

emplace 1:
- ctor (1)
- ctor (2)
emplace 2:
- ctor (1)
- ctor (3)
- dtor (3)
- dtor (1)
clear:
- dtor (2)
- dtor (1)
try_emplace 1:
- ctor (1)
- move ctor (1)
- ctor (2)
- dtor (1)
try_emplace 2:
- ctor (1)
- dtor (1)
done:
- dtor (2)
- dtor (1)

The difference between the two functions is:

• std::map::emplace constructs a value_type, i.e. a std::pair in-place, and then attempts to insert this pair.
• std::map::try_emplace attempts to find an insert location first, and if one is found, it will construct the value_type, i.e. a std::pair in-place.

try_emplace appears to save us some work, but remember that even if we don't insert anything new into the map with try_emplace, we still have to check whether we can, and where. This happens with std::less by default, which ends up calling:

bool operator<(const F& f) const { return i < f.i; }

An F object must exist to perform this comparison, and is being constructed once during try_emplace.

Let's annotate your example with what is happening:

emplace 1:
 - ctor (1) // construct node{1, 2}
 - ctor (2)
emplace 2:
 - ctor (1) // construct node{1, 3}
 - ctor (3)
 - dtor (3) // can't insert, destroy node{1, 3}
 - dtor (1)

clear:
 - dtor (2) // destroy node{1, 2}
 - dtor (1)

try_emplace 1:
 - ctor (1) // construct temporary key
 - move_ctor (1) // location found, move key to node
 - ctor (2) // construct value
 - dtor (1) // destroy temporary key
try_emplace 2:
 - ctor (1) // construct temporary key
 - dtor (1) // destroy temporary key
done:
 - dtor (2) // destroy node{1, 2}
 - dtor (1)

Conclusion

We can't say that emplace is universally better or worse than try_emplace, rather there is a trade-off:

The trade-off changes when we have a pre-existing key instead of initializing one inside of try_emplace or emplace:

In conclusion, try_emplace is at worst wasting one move constructor compared to emplace, and at best, it's strictly better. Prefer it in most, but not all cases.

¹⁾ "overhead" is relative to magically knowing the right location (or absence thereof) in the map and initializing a node in-place. Initialization of the pre-existing key is considered free.