两个unordered_map的交集

Question

我的问题与两个STL地图的交集类似，但是这里有两个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的值所组成的一对。

如何最快地实现这个目标？目前，我遍历两者中较小的那一个并查询第二个中的键。幸运的是，我的键类型通常很容易进行hash操作，但我并没有找到一种方法来获取迭代映射中我的键的hash值，以节省第二个操作的hash计算（明确一下：我不知道如何在不重新计算hash的情况下恢复hash，以及在哪里可以找到像 find 带有计算hash参数的函数 [1]）。

谢谢。

[1] 是的，我知道，早期优化会导致很多问题。但我想知道是否可能实现这一点，而不是解释这将是一个错误的做法。实际上，在某些情况下，根据用户输入，键可以是复杂且成本高昂的。

- akim

---

如果你已经排序了 map，那么它会更简单、更快。 - dyp

你能在类中缓存哈希值吗？在哈希函数中，您可以检查哈希是否已经计算并返回它。请记住，如果任何键发生更改，则需要重新计算存储的哈希。 - Alan

@Alan：是的，我考虑过那个，但我想避免那种情况。 - akim

我建议您提供样例输入和输出以澄清问题。如果在A中找到某个关键字但在B中没有，这个算法应该怎么做？ - Muxecoid

任何交叉口都可以：忽略。 - akim

目前的STL无法将预先计算的哈希值传递给unordered_map::insert或unordered_map::find。您可能需要记录您的需求并向标准委员会发送提案。如果这真的很关键，您可以修改您使用的STL实现。 - Muxecoid

Answer 1

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

- Fred Foo

---

你说得对，那不是我要找的 :) 不过还是谢谢。 - akim

Answer 2

如果哈希键非常昂贵，您可以从一开始就使用类型为std::unordered_map<Key, std::pair<Value, Value>>的A和B来避免其中一个哈希，代价是将pair.second设置为默认构造的值。

假设在计算交集后不再需要原始的A和B，您可以只迭代两个中较小的那个（假设B是最小的）：

--> 将B移动到C中。

 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 不变，而不是将 B 移动到 C 中，只需将 B 复制到 C 中即可。

- Vincent

---

谢谢，但这并不是我的问题，我的地图是独立的，不能从一开始就这样压缩。 - akim