在 std::unordered_map 中移动 insertion/emplace 失败后恢复移动的元素

Question

我使用 insert 或 emplace 方法和移动语义填充 std::unordered_map。当发生按键冲突时，元素不会插入到地图中，但无论如何都会删除移动的元素：

#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;
}

输出：

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

因此没有插入任何东西，但对象（示例中的字符串）无论如何都会被删除，因此无法将其用于任何其他目的。可能的修复方法是不使用移动语义或检查 insertion/emplacement 之前的密钥，这两者都会降低性能。

要继续，我知道移动语义意味着移动的对象处于仅对销毁有用的状态，但我不完全理解为什么 std::unordered_map 中的移动操作失败应该无论如何导致那种状态，如果有任何代码模式可以避免这种情况而不会造成太多性能损失。

Answer 1

作为 C++11 的解决方法，您可以编写代理函数 insert，它会在尝试插入元素之前查找它。对于 unordered_map，搜索最多需要 O(n)，但这是最坏的情况，通常（或平均）需要 O(1)。像这样：

#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;
}

Answer 2

我认为你试图做的事情违背了移动语义的真正含义。

使用 std::move，您声明您将不再使用该对象，因此 C++ 编译器可以优化各个方面。该函数，在本例中为 insert 或 emplace，可以自由地对对象执行它想做的事情，因为您声明它 moved，包括删除它。在某些条件下继续使用该对象，例如插入失败，函数应该给它 back 给你返回它，可能还使用 std::move.

回到您的示例，您不能在 std::move 之后将 val 或 s 与 std::cout 一起使用。

Answer 3

如果可以选择使用 C++17 功能，try_emplace 只会在键不存在于映射中时才移动参数。

否则，您可以拥有自己的版本，通过组合 find 和 emplace（或 insert）来获得（功能上）相同的效果。

请注意，这可能比 try_emplace 实现效率低（如果存在的话）（因为如果键不在映射中，您将在容器中进行 2 次搜索）。

在 std::unordered_map 中移动 insertion/emplace 失败后恢复移动的元素

Recover moved element after failed move insertion/emplace in std::unordered_map

c++

move-semantics

unordered-map