5

I fill a std::unordered_map using the insert or emplace methods and the move semantics. When a key clash occurs the element is not inserted in the map but the moved element is erased anyway:

#include <unordered_map>
#include <iostream>

int main(){
    std::unordered_map<int, std::string> m;
    m.insert(std::make_pair<int, std::string>(0, "test"));
    std::string s = "test";
    
    // try insert
    auto val = std::make_pair<int, std::string>(0, std::move(s));
    if(m.insert(std::move(val)).second){
        std::cout << "insert successful, ";
    }else{
        std::cout << "insert failed, ";
    }
    std::cout << "s: " << s << ", val.second: " << val.second <<  std::endl;
    
    // try emplace
    s = "test";
    if(m.emplace(0, std::move(s)).second){
        std::cout << "emplace successful, ";
    }else{
        std::cout << "emplace failed, ";
    }
    std::cout << "s: " << s << std::endl;
    
    return 0;
}

Output:

insert failed, s: , val.second:
emplace failed, s:

Thus nothing is inserted but the object (the string in the example) is erased anyway, making it impossible to use it for any other purpose. Possible fixes would be to not use move semantics or to check for the key prior to the insertion/emplacement, both of which have a performance penalty.

To resume, I understand that move semantics implies that a moved object is left in a state which is useful just for destruction, but I don't fully understand why a failed move operation in std::unordered_map should anyway lead to that state, and if there is any code pattern that allows to avoid this without too much performance penalty.

Nicola Mori
  • 777
  • 1
  • 5
  • 19
  • 2
    Can you use [`try_emplace`](https://en.cppreference.com/w/cpp/container/unordered_map/try_emplace) instead? – Hasturkun Jan 26 '21 at 11:13
  • 1
    There is even this note about `try_emplace` on [cppreference](https://en.cppreference.com/w/cpp/container/unordered_map/try_emplace): _Unlike insert or emplace, these functions do not move from rvalue arguments if the insertion does not happen..._. – Daniel Langr Jan 26 '21 at 11:15
  • @Hasturkun `try_emplace` does exactly the job, thank you. Unfortunately its C++17 and I cannot use it in my code. Anyway I think that this is a good answer to my question, namely there's no way to do what I want without C++17. – Nicola Mori Jan 26 '21 at 11:16
  • I think you should be able to make your own version using `find` and `emplace` (which is what the libstdc++ implementation seems to be doing). – Hasturkun Jan 26 '21 at 11:33
  • @Hasturkun if really `try_emplace` is implemented by first searching and then emplacing then I see little value in it... – Nicola Mori Jan 26 '21 at 13:09
  • The library implementation of `try_emplace` will be more efficient than a separate `find` and `emplace` (since it can use the knowledge that the item isn't present to avoid the second search which `emplace` would have to perform, as the map keys must be unique). My suggestion is functionally equivalent, though obviously not as efficient. – Hasturkun Jan 26 '21 at 13:30
  • @Hasturkun I see your point, thanks for the clarification. – Nicola Mori Jan 26 '21 at 13:59
  • @Hasturkun If you care about adding an answer then I'll flag it as the chosen one. – Nicola Mori Jan 26 '21 at 16:27

3 Answers3

2

If using C++17 features is an option, try_emplace will only move the arguments if the key doesn't already exist in the map.

Otherwise, you can have your own version to get (functionally) the same effect, by combining find and emplace (or insert).

Note that this will likely be less efficient than the try_emplace implementation, if it exists (as you have 2 searches through the container if the key isn't in the map).

Hasturkun
  • 35,395
  • 6
  • 71
  • 104
  • As mentioned above I can't use C++17 but this is definitely the answer to my question. Thanks. – Nicola Mori Jan 28 '21 at 07:32
  • Note however, that this creates a new object in place in the map, when the key is not there, forwarding the parameters and avoiding the creation of temporaries. This doesn't answer the original question, that is about recovering objects after move, something I believe can't be done. – ragazzojp Jan 29 '21 at 08:57
0

As workaround on C++11 you could write proxy function insert, which will look for an element before trying to insert it. For unordered_map the search could take at most O(n) but this is the worst case, normally (or average) take O(1). Something like this:

#include <unordered_map>
#include <iostream>

template <typename T, typename V> 
std::pair<typename T::iterator, bool> insert(T& m, V&& val) 
{ 
    auto res = m.find(val.first);
    if (res == m.end())
        return m.insert(std::forward<V>(val));
    else
        return std::make_pair(res, false);
} 

int main(){
    std::unordered_map<int, std::string> m;
    m.insert(std::make_pair<int, std::string>(0, "test"));
    std::string s = "test";
    
    // try insert
    auto val = std::make_pair<int, std::string>(0, std::move(s));
    if(insert(m, std::move(val)).second)
        std::cout << "insert successful, ";
    else
        std::cout << "insert failed, ";        
    std::cout << "s: " << s << ", val.second: " << val.second <<  std::endl;    
  
    return 0;
}
alex_noname
  • 26,459
  • 5
  • 69
  • 86
  • This is what I am doing now, but as I said there is a performance penalty since the map have to search twice (first for an eventual already existing element and the for the insertion position). Regardless how much overhead this introduces, it might not be acceptable in some cases. – Nicola Mori Jan 26 '21 at 13:06
  • You're using `s` and `val` after passing them to `std::move`, this should not happen. – ragazzojp Jan 26 '21 at 18:09
  • I know this is just for demo, based on the TS's example, besides, the object is in a valid state after being moved. – alex_noname Jan 26 '21 at 18:14
0

I think what you're trying to do goes against the true meaning of the move semantic.

With std::move, you declare you're not going to use that object anymore so C++ compiler can optimize various aspects. The function, in this case insert or emplace, is free to do what it wants with the object because you declare it moved, including deleting it. To continue to use the object under certain conditions, e.g. failed insert, the function should give it back to you returning it, possibly also using std::move.

Back to your example, you can't use val or s with std::cout after std::move.

ragazzojp
  • 477
  • 3
  • 14
  • I understand your point, I even mentioned this point of view in my original post. What I don't understand is why the moved element should vanish if actually it is not moved at all. This prevents some possible use cases (e.g. moving to a container and eventually moving to a fallback container if the first move fails) without much added value, in my opinion. – Nicola Mori Jan 26 '21 at 13:11
  • Moving and vanishing are synonyms. The object is always moved, if the function then doesn't store it in the map is an implementation detail of the function. The object vanishes when it goes out of scope from inside the function if not stored or returned, as any other parameter would. It's not the first move that _fails_, it never fails, it's the behavior of the function you're calling that drops it. Also note you can't use variables after you've moved them, regardless of what happens to them inside the function you call. – ragazzojp Jan 26 '21 at 18:01
  • I feel that your interpretation of the move semantics is somehow too extreme. In fact, also the standard library have cases when moved variables are still usable, as the `std::unordered_map::try_emplace` method mentioned in other answers. When `try_emplace` fails the object passed as argument as an rvalue reference (thus moved) is found to be in the same state as it was prior to the call, even if it has not been stored. – Nicola Mori Jan 28 '21 at 07:31
  • My interpretation is sad but true. Use-after-move is not supposed to happen. There's no way to check if the move succeeded, and there's no assurance the object is still usable. The move _never_ fails. You're confused by the "failure" of the insertion in the map if the key is already present. https://stackoverflow.com/questions/42795683/using-an-object-after-stdmove-doesnt-result-in-a-compilation-error. `try_emplace` potentially creates a new object in place, _forwarding_ the parameters to the constructor, not moving the object. – ragazzojp Jan 29 '21 at 08:54
  • Ok, but if the parameter is an object of the same class passed as an rvalue reference then it is forwarded to the move constructor and thus moved into the newly built object. If `try_emplace` fails then the move constructor is not called and thus the original object is still valid and usable even if I passed it to `try_emplace(std::string &&obj)`. And actually I am supposed to use it (after checking the result of `try_emplace`, of course), otherwise `try_emplace` has no sense at all. – Nicola Mori Jan 29 '21 at 14:29
  • `try_emplace` is supposed to be used with `std::forward`, the goal is to create the object in place only when necessary. You're passing what you obtain from `std::move` and invoke the move/copy constructor. In case key is there, nothing changes. But the move happens in the calling function, the object _is moved_ into one of the function parameters. It works in the sense that doesn't break, but it's borderline and, to me, beyond the line. Look at the link I posted above, use-after-move is a problem, also https://stackoverflow.com/questions/20850196/what-lasts-after-using-stdmove-c11 – ragazzojp Jan 29 '21 at 16:59