Вы можете использовать std::set_intersection
, чтобы заполнить новый контейнер, содержащий пары key
, value
, которые есть на обеих картах. set_intersection
требует сортировки диапазонов (это именно то, что вы не получите от unordered_map
), поэтому либо замените unordered_map
s на map
, либо создайте временные map
s (или временные std::set<std::pair<int, int>>
s) перед использованием set_intersection
.
Я бы рекомендовал заменить ваши исходные unordered_map
s упорядоченными map
s для эффективности, если вам часто нужны пересечения:
#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 элемент, а другая — 1 000 000 элементов. Затем вам нужен 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;
}
person
Ted Lyngmo
schedule
30.06.2020