两个std::unordered_map的交集

Question

我有两个 std::unordered_map。

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

我需要找到键值对的交集并将其存储在另一个具有相同格式的映射中。

std::unordered_map<int, int> mp;

我该如何做到这一点？？

- Sagar Barapatre

---

关于键、值或键值对的交集？ - Lukas-T

键值对的交集 - Sagar Barapatre

将该信息添加到问题中，而不是作为评论。此外，如果您显示输入和输出的示例，将会很有帮助。 - cigien

我想到了std::set_intersection。 - Jesper Juhl

你需要在给定某个键x的情况下，明确指定交集的含义，即使mp1[x]和mp2[x]都存在但mp1[x] != mp2[x]。在这种情况下，以x为键的键值对是否会在输出中不出现？ - jwezorek

Answer 1

您可以使用std::set_intersection来填充一个新容器，其中包含在两个映射中都存在的key，value对。set_intersection需要范围已排序（这正是您从unordered_map中无法获得的），因此请将unordered_map替换为map，或者在使用set_intersection之前创建临时的map（或临时std::set<std::pair<int，int>>）。 如果您经常需要交集，我建议将原始的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';
    }
}

Possible output:

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
    }

遍历最小的地图的原因是为了尽可能减少查找操作的数量。考虑一种情况，其中一个地图包含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;
}

- Ted Lyngmo

Answer 2

for(auto it=mp1.begin();it!=mp1.end();it++)
  {
    auto it1=mp2.find(it->first);
    if(it1==mp2.end())
      continue;
    if((*it1)==(*it))
      mp.insert(*it);
  }

将制作一个 <k,v> 的映射，其中 <k,v> 在 mp1 和 mp2 中都存在。

或更快

auto it1=mp1.begin();
auto it2=mp2.begin();
while(it1!=mp1.end() && it2!=mp2.end())
  {
    if((*it1)==(*it2))
      {
        mp.insert(*it1);       
        it1++;
        it2++;
        continue;
      }
    if((*it1)<(*it2))
      it1++;
    else
      it2++;
  }

- Danila Smirnov

---

使用std::set_intersection并不像这种方法那样高效，因为该函数利用了map是有序容器的事实，因此不需要每次进行查找。 - Martin York

抱歉，现在应该更好了。 - Danila Smirnov

@D.Smirnov 第二个版本需要有序的 map。这可能值得注意。 - Ted Lyngmo

Answer 3

这是一个使用 std::set 的手动解决方案：

#include <iostream>
#include <set>
#include <unordered_map>

std :: unordered_map <int, int> intersection (std :: unordered_map <int, int> m1, std :: unordered_map <int, int> m2)
{
    std :: set <std :: pair <int, int>> s (m1.begin(), m1.end());

    std :: unordered_map <int, int> i;
    for (auto p: m2)
        if (s.find (p) != s.end())
            i.insert (p);
    
    return i;
}

int main()
{
    std :: unordered_map <int, int> m1 = { { 2, 3 }, { 5, 7 }, { 11, 5 }, { 6, 7 } };
    std :: unordered_map <int, int> m2 = { { 21, 13 }, { 2, 3 }, { 6, 7 }, { 3, 2 } };

    std :: unordered_map <int, int> i = intersection (m1, m2);

    for (auto p: i)
        std :: cout << p.first << ' ' << p.second << '\n';
    
    return 0;
}

输出：

6 7
2 3

- Arkajyoti Banerjee