c++ - 两个 std::unordered_map 的交集
问题描述
我有两个 std::unordered_map
std::unordered_map<int, int> mp1;
std::unordered_map<int, int> mp2;
我需要找到键值对的交集并将其存储在表单的另一个映射中。
std::unordered_map<int, int> mp;
我怎样才能做到这一点??
解决方案
您可以使用std::set_intersection
来填充一个新容器,其中包含两个地图中都存在的key
,对。需要对范围进行排序(这正是您不会从 a 中得到的)所以要么在使用.value
set_intersection
unordered_map
unordered_map
map
map
std::set<std::pair<int, int>>
set_intersection
如果您经常需要交叉点,我建议您将原始unordered_map
s 替换为有序s 以提高效率: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
s 并且不必创建临时set
s 或map
s,则可以将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
操作次数降到最低。考虑一个地图包含 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;
}
推荐阅读
- jquery - 如何在单击/加载时滑入新加载的图像
- java - 如何从 eclispe rcp 中的包中加载文件
- r - 在 R 中:如何连接具有相似名称的所有数据框?
- tfs - TFS 源代码控制 - 有没有办法撤消文件中的特定行?
- logging - Serilog 不会解构对象的集合
- angular - 获取嵌入式 power bi 报告的所有页面
- qt - 如何在 QtApp 上获取移动应用生命周期事件
- polymer-2.x - 铬聚合物 3 IIS 中的相对路径
- xpages - isAnonymous 与在 Xpages 中的 ACL 上检查分配给匿名用户的角色
- node.js - 为什么 Node.js 扩展在 Linux 上有效,但在 Windows 上无效?