STL结构："insert if not present"运算？

Question

我正在开发一个处理一些指数时间算法的程序。因此，我的程序的主循环运行多次，我正在尝试尽可能地优化它。

分析表明，大部分时间花在了 std::unordered_map 的查找和哈希计算上。

我在想：

有没有办法缓存 std::unordered_map 的键的哈希值，然后将其作为参数提供以便稍后插入？
有没有一种方法可以在一次操作中完成以下操作：给定键和值 {x,y}，检查键 x 是否在映射中，如果不是，插入它和 return {x,y}，否则 return {x,z} 因为 z 已经在地图中。

我现在正在做类似的事情，但效率很低，因为我必须计算密钥的哈希值并检查它是否在映射中。但如果它不在地图中，我会执行完全独立的插入操作。理论上，检查它是否存在于地图中应该找到它在地图中的位置，如果插入。

我愿意尝试其他数据结构，例如 std::map 或来自 Boost 的东西，如果它们可以减少此操作的时间。

Answer 1

您可以只使用 std::unordered_map::insert() 的 return 值来实现密钥存在检查 + 通过单一哈希计算插入。

template<typename K, typename V>
std::pair<K, V> myinsert(std::unordered_map<K, V> &map, const std::pair<K, V> &kv)
{
    return *(map.insert(kv).first);
}

Answer 2

您无法缓存密钥的哈希值，但如果您有一个迭代器指向它上次所在的位置（从您最初插入的时间开始，或者从您最后一次成功找到该项目的时间开始），您可以使用insert( const_iterator hint, value_type&& value ); 成员，它也有助于 returns 新插入元素或阻止插入的先前存在元素的迭代器。

Answer 3

你可以直接使用 std::map::emplace().

仅当容器中没有其他元素具有与被放置的元素等效的键（地图容器中的键是唯一的）时，插入才会发生。

示例

#include <iostream> #include <utility> #include <string> #include <map> typedef std::map<std::string, std::string> StringMap; typedef std::pair<StringMap::iterator, bool> PairKey; int main() { std::map<std::string, std::string> m; // uses pair's template constructor m.emplace("a", "aaa"); m.emplace("b", "bbb"); m.emplace("d", "ddd"); PairKey pair = m.emplace("d", "dddddd"); if (pair.second == false) std::cout<< "d was existed so value didn't change" << std::endl; std::cout<<"-------MAP_LIST------" << std::endl; for (const auto &p : m) std::cout << p.first << " => " << p.second << '\n'; std::cout<<"-------========------" << std::endl; }

输出：

d was existed so value didn't change -------MAP_LIST------ a => aaa b => bbb d => ddd -------========------

STL结构："insert if not present"运算？

STL structures: "insert if not present" operation?

c++

optimization

stl

unordered-map

data-structures