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?

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)

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)

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.