Does the C++ standard guarantee that a failed insertion into an associative container will not modify the rvalue-reference argument?

Question

#include <set>
#include <string>
#include <cassert>

using namespace std::literals;

int main()
{
    auto coll = std::set{ "hello"s };
    auto s = "hello"s;
    coll.insert(std::move(s));
    assert("hello"s == s); // Always OK?
}

Does the C++ standard guarantee that a failed insertion into an associative container will not modify the rvalue-reference argument?

Antiquated

Answer 1

Explicit and unequivocal NO. Standard doesn't have this guarantee, and this is why try_emplace exists.

See notes:

Unlike insert or emplace, these functions do not move from rvalue arguments if the insertion does not happen, which makes it easy to manipulate maps whose values are move-only types, such as std::map<std::string, std::unique_ptr<foo>>. In addition, try_emplace treats the key and the arguments to the mapped_type separately, unlike emplace, which requires the arguments to construct a value_type (that is, a std::pair)

Comstock

If the constructor of the type being inserted throws after moving one of its arguments, the insertion will fail, but an rvalue will have been moved from. I don't understand how try_emplace() can make such a guarantee. – Jenelljenelle

Answer 2

No.

While @NathanOliver points out that an element will not be inserted if and only if there is no equivalent key, it does not guarantee that the arguments will not be modified.

In fact, [map.modifiers] says the following

template <class P>
pair<iterator, bool> insert(P&& x);

equivalent to return emplace(std::forward<P>(x)).

Where emplace may perfectly forward the arguments to construct another P, leaving x in some valid but indeterminate state.

Here's an example that also demonstrates (not proves) that with std::map (an associative container), a value gets moved around a bit:

#include <iostream>
#include <utility>
#include <string>
#include <map>

struct my_class
{
    my_class() = default;
    my_class(my_class&& other)
    {
        std::cout << "move constructing my_class\n";
        val = other.val;
    }
    my_class(const my_class& other)
    {
        std::cout << "copy constructing my_class\n";
        val = other.val;
    }
    my_class& operator=(const my_class& other)
    {
        std::cout << "copy assigning my_class\n";
        val = other.val;
        return *this;
    }
    my_class& operator=(my_class& other)
    {
        std::cout << "move assigning my_class\n";
        val = other.val;
        return *this;
    }
    bool operator<(const my_class& other) const
    {
        return val < other.val;
    }
    int val = 0;
};

int main()
{
    std::map<my_class, int> my_map;
    my_class a;
    my_map[a] = 1;
    std::pair<my_class, int> b = std::make_pair(my_class{}, 2);
    my_map.insert(std::move(b)); // will print that the move ctor was called
}

• gcc (2 moves)
• clang (1 move)

Splashy

@user877329 std::set has no try_emplace, so the case of type conversion (or lack thereof) doesn't apply to it. In unordered_map and map, the key argument of try_emplace is received by const reference so it cannot be moved from. The value in both scenarios is received via perfect forwarding, so it is eligible to be moved from only if received by rvalue reference, meaning try_emplace cannot modify the argument unless you allow it to. – Splashy

Answer 3

(Answer for C++17 only)

I believe that the correct answer is somewhere in between NathanOliver's (now deleted) answer and AndyG's answer.

As AndyG points out, such a guarantee cannot exist in general: sometimes, the library must actually perform a move construction just to determine whether or not the insertion can take place. This will be the case for the emplace function, whose behaviour is specified by the standard as:

Effects: Inserts a value_type object t constructed with std::forward<Args>(args)... if and only if there is no element in the container with key equivalent to the key of t.

We can interpret this as saying that the object t is constructed no matter what, and then is disposed of if the insertion cannot happen because the value t or t.first already exists in the set or map, respectively. And since the method template <class P> pair<iterator, bool> insert(P&&) of std::map is specified in terms of emplace, as AndyG points out, it has the same behaviour. As SergeyA points out, the try_emplace methods are designed to avoid this issue.

However, in the specific example given by the OP, the value being inserted is of exactly the same type as the container's value type. The behaviour of such an insert call is specified by the general requirements paragraph previously given by NathanOliver:

Effects: Inserts t if and only if there is no element in the container with key equivalent to the key of t.

In this case, there no license is given for the library to modify the argument in the case where the insertion does not take place. I believe that calling a library function is not supposed to have any observable side effects besides what the standard explicitly allows. Thus, this case, t must not be modified.

Nunn