c++ - 两个std::unordered_map的交集

Question

我有两个std::unordered_map

std::unordered_map<int, int> mp1;
std::unordered_map<int, int> mp2;

我需要找到键值对的交集并将其存储在表单的另一张 map 中。

std::unordered_map<int, int> mp;

我怎样才能做到这一点？？

Answer 1

您可以使用 std::set_intersection 填充包含两个 map 中都存在的key和value对的新容器。 set_intersection需要对范围进行排序(这正是您不会从unordered_map获得的范围)，因此，在使用unordered_map之前，用map替换map或创建临时std::set<std::pair<int, int>> s(或临时set_intersection s)。
如果您经常需要交叉路口，建议您使用有序unordered_map替换原始map，以提高效率:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <unordered_map>
#include <vector>

int main() {
    std::map<int, int> mp1 {{1,0}, {2,0}, {3,0}};
    std::map<int, int> mp2 {{0,0}, {2,0}, {3,0}};

    // this can be unordered unless you plan to use it in an intersection later:
    std::unordered_map<int, int> mp;

    std::set_intersection(
        mp1.begin(), mp1.end(),
        mp2.begin(), mp2.end(), 
        std::inserter(mp, mp.begin())
    );

    for(auto[key, val] : mp) {
        std::cout << key << ',' << val << '\n';
    }
}

可能的输出:

3,0
2,0

如果您想保留 unordered_map，而不必创建临时的 set或 map，则可以使用手动填充符替换上面的 set_intersection:

    const auto& [min, max] = std::minmax(mp1, mp2,
                                         [](auto& a, auto& b) {
                                             return a.size() < b.size();
                                         });
    for(auto& [key, value] : min) {               // iterate over the smallest map
        auto fi = max.find(key);                  // find in the bigger map
        if(fi != max.end() && fi->second == value)
            mp.emplace(key, value);               // add the pair if you got a hit
    }

迭代最小映射的原因是将 find操作的数量保持在最低水平。考虑一种情况，其中一个 map 包含1个元素，而其他1000000个元素。然后，您需要1个查询而不是1000000。
一个更通用的解决方案可能是使用它来制作功能模板:

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
>
auto unordered_map_intersection(
    const std::unordered_map<Key,T,Hash,KeyEqual,Allocator>& mp1,
    const std::unordered_map<Key,T,Hash,KeyEqual,Allocator>& mp2)
{
    std::unordered_map<Key,T,Hash,KeyEqual,Allocator> mp;

    const auto& [min, max] = std::minmax(mp1, mp2,
                                         [](auto& a, auto& b) {
                                             return a.size() < b.size();
                                         });
    for(auto& [key, value] : min) {               // iterate over the smallest map
        auto fi = max.find(key);                  // find in the bigger map
        if(fi != max.end() && fi->second == value)
            mp.emplace(key, value);               // add the pair if you got a hit
    }
    return mp;
}