首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >两个unordered_maps的交点

问两个unordered_maps的交点
EN

Stack Overflow用户
提问于 2014-01-21 10:16:07
回答 2查看 1.7K关注 0票数 3

基本上,我的问题与Intersection of two STL maps相同,但有两个unordered_maps

代码语言:javascript
复制
std::unordered_map<Key, Value> A;
std::unordered_map<Key, Value> B;

我想要那个十字路口,类似于

代码语言:javascript
复制
std::unordered_map<Key, std::pair<Value, Value>> C;

其中键是A和B中的值,值分别是来自A和B的值的一对。

实现这一目标的最快方法是什么?目前,我对两者中最小的进行迭代,并在第二次中查询密钥。幸运的是,我的键类型对于哈希非常简单,但是我没有找到一种方法来获得迭代映射的键的散列值,以便在第二次计算哈希时省去哈希的计算(需要明确的是:我不知道如何在不重新计算的情况下恢复哈希,以及在哪里找到像find这样的参数1计算的哈希)。

谢谢。

1是的,我知道,早期优化是很多疾病的根源。然而,我想知道这是否可能,而不是解释这将是如何的一罐错误。实际上,在某些情况下,取决于用户的输入,密钥可能很复杂,而且哈希成本很高。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2014-01-21 12:27:46

我知道您不想听,但我还是要说:您应该缓存实例上的散列值,这样散列就可以简化为简单的成员查找。如果实例是不可变的(或者至少哈希函数中的部分是不可变的),那么最简单的方法就是在构造函数中计算哈希。

票数 1
EN

Stack Overflow用户

发布于 2014-01-29 06:40:05

如果密钥是真的很昂贵的哈希,您可以避免一次哈希,代价是从一开始就有A和B类型的std::unordered_map<Key, std::pair<Value, Value>>。(使用pair.second到缺省的构造值)

假设在求交后不需要原始的A和B,则只需迭代2中最小的一个(假设B是最小的):

->C中移动B

代码语言:javascript
复制
 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。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/21255187

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档