std::unordered_set<T>::insert(T&&): is argument moved if it exists

Question

This question is about the specification of several functions in the C++11 Standard Library, that take their arguments as rvalue references, but do not consume them in all cases. One example is std::unordered_set<T>::insert(T&&).

It is pretty clear, that this method will use the move constructor of T to construct the element within the container, if it does not already exist. However, what happens if the element already exists in the container? I am pretty sure there is no reason the change the object in the case. However, I didn't find anything in the C++11 Standard supporting my claim.

Here is an example to show why this might be interesting. The following code reads lines from std::cin and remove the first occurrence of duplicate lines.

std::unordered_set<std::string> seen;
std::string line;
while (getline(std::cin, line)) {
    bool inserted = seen.insert(std::move(line)).second;
    if (!inserted) {
        /* Is it safe to use line here, i.e. can I assume that the
         * insert operation hasn't changed the string object, because 
         * the string already exists, so there is no need to consume it. */
        std::cout << line << '\n';
    }
}

Apparently, this example works with GCC 4.7. But I am not sure, if it is correct according to the standard.

Answer 1

I found this note in the standard (17.4.6.9):

[ Note: If a program casts an lvalue to an xvalue while passing that lvalue to a library function (e.g. by calling the function with the argument move(x)), the program is effectively asking that function to treat that lvalue as a temporary. The implementation is free to optimize away aliasing checks which might be needed if the argument was an lvalue. — end note ]

While it doesn't directly answer your question it does indicate that you've effectively "given" the argument to the library function as a temporary so I wouldn't rely on its value once you've called insert. As far as I can tell, a library implementation would be entitled to move from the parameter even if it subsequently determines that it isn't going to keep the value in the container.

Answer 2

The semantics given for insert on unordered associative containers in §23.2.5/Table 103 don't specify whether the the move constructor of the argument to insert is invoked if the insert fails, the wording only talks about whether the insertion happens:

a_uniq.insert(t)

Returns: pair<iterator, bool>

Requires: If t is a non-const rvalue expression, T shall be MoveInsertable into X; otherwise, T shall be CopyInsertable into X.

Effects: Inserts t if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair indicates whether the insertion takes place, and the iterator component points to the element with key equivalent to the key of t.

However, the specification for emplace is clearer (also from Table 103), and you should be able to use it instead of insert to get the guarantees you want:

a_uniq.emplace(args)

Returns: pair<iterator, bool>

Requires: T shall be EmplaceConstructible into X from args.

Effects: Inserts a T object t constructed with std::forward(args)... if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of t.

I interpret this to mean ((Inserts a T object t constructed ...) (if and only if there is no element in the container ...)), i.e. both the insertion and construction should only happen if there is no matching element already in the container. If no object is constructed , the std::string you pass in will never be passed to a move constructor, and therefore will still be valid after the failed emplace call.

gcc 4.7.0 doesn't seem to support unordered_set::emplace, but it is in the standard (§23.5.6.1)

As @NicolBolas pointed out in the comments, and despite the above, it's impossible to implement an emplace function that doesn't construct a T if a conflicting entry already exists.

So the only way to get the semantics you want in a way that is standards-conforming would be to do a find followed by, conditionally, an insert or emplace.