我有两个 std::unordered_map。
std::unordered_map<int, int> mp1;
std::unordered_map<int, int> mp2;
我需要找到键值对的交集并将其存储在另一个具有相同格式的映射中。
std::unordered_map<int, int> mp;
我该如何做到这一点??
我有两个 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
,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
}
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;
}
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++;
}
std::set_intersection
并不像这种方法那样高效,因为该函数利用了map是有序容器的事实,因此不需要每次进行查找。 - Martin Yorkmap
。这可能值得注意。 - Ted Lyngmostd::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