基本上,我的问题与Intersection of two STL maps相同,但有两个unordered_maps
std::unordered_map<Key, Value> A;
std::unordered_map<Key, Value> B;我想要那个十字路口,类似于
std::unordered_map<Key, std::pair<Value, Value>> C;其中键是A和B中的值,值分别是来自A和B的值的一对。
实现这一目标的最快方法是什么?目前,我对两者中最小的进行迭代,并在第二次中查询密钥。幸运的是,我的键类型对于哈希非常简单,但是我没有找到一种方法来获得迭代映射的键的散列值,以便在第二次计算哈希时省去哈希的计算(需要明确的是:我不知道如何在不重新计算的情况下恢复哈希,以及在哪里找到像find这样的参数1计算的哈希)。
谢谢。
1是的,我知道,早期优化是很多疾病的根源。然而,我想知道这是否可能,而不是解释这将是如何的一罐错误。实际上,在某些情况下,取决于用户的输入,密钥可能很复杂,而且哈希成本很高。
发布于 2014-01-21 12:27:46
我知道您不想听,但我还是要说:您应该缓存实例上的散列值,这样散列就可以简化为简单的成员查找。如果实例是不可变的(或者至少哈希函数中的部分是不可变的),那么最简单的方法就是在构造函数中计算哈希。
发布于 2014-01-29 06:40:05
如果密钥是真的很昂贵的哈希,您可以避免一次哈希,代价是从一开始就有A和B类型的std::unordered_map<Key, std::pair<Value, Value>>。(使用pair.second到缺省的构造值)
假设在求交后不需要原始的A和B,则只需迭代2中最小的一个(假设B是最小的):
->C中移动B
for (auto it = C.begin(); it != C.end();it++ ) {
auto res = A.find(it->first);
if(res == A.end() )
{
//Can't call C.erase(it) here as it would cause problem in the loop
v.push_back(it);
}
else
{
// Assign the second value of the pair to the value obtained in A.
it->second.second = res->second.first;
}
}
for( auto it : v)
C.erase(it);这将使C充满成对,其中pair.first是B中的值,pair.second是A中的值
如果你需要保持A和B不动,而不是在C中移动B,只需在C中复制B。
https://stackoverflow.com/questions/21255187
复制相似问题