Intersection of Two 'Std::Map'S

Intersection of two `std::map`s

#include <map>
#include <utility>
template <typename KeyType, typename LeftValue, typename RightValue>
std::map<KeyType, std::pair<LeftValue, RightValue>>
IntersectMaps(const std::map<KeyType, LeftValue>& left, 
              const std::map<KeyType, RightValue>& right) {
    std::map<KeyType, std::pair<LeftValue, RightValue>> result;
    typename std::map<KeyType, LeftValue>::const_iterator il  = left.begin();
    typename std::map<KeyType, RightValue>::const_iterator ir = right.begin();
    while (il != left.end() && ir != right.end()) {
        if (il->first < ir->first)
            ++il;
        else if (ir->first < il->first)
            ++ir;
        else {
            result.insert(std::make_pair(il->first, std::make_pair(il->second, ir->second)));
            ++il;
            ++ir;
        }
    }
    return result;
}

I haven't tested this, or even compiled it... but it should be O(n). Because it's templated it should work with any two maps that share the same key type.

Intersection of two std::unordered_map

You could use std::set_intersection to fill a new container containing the key, value pairs that exists in both maps. set_intersection needs the ranges to be sorted (which is exactly what you won't get from an unordered_map) so either, replace the unordered_maps with map or create temporary maps (or temporary std::set<std::pair<int, int>>s) before using set_intersection.

I would recommend replacing your original unordered_maps with ordered maps for efficiency if you need intersections often:

#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

If you want to stay with unordered_maps and to not have to create temporary sets or maps, you can just replace set_intersection above with a manual filler:

    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
    }

The reason for iterating over the smallest map is to keep the number of find operations down to a minimum. Consider a case where one map contains 1 element and the other 1000000 elements. You then want 1 lookup and not 1000000.

A more generic solution could be making a function template out of it:

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;
}

How do I get a set intersection of two std::unordered_map's?

The most straightforward implementation is:

MapType intersectFilter(const MapType& mapA, const MapType& mapFilter)
{
    MapType result;
    for (const auto& pair: mapA)
    {
        if (mapFilter.find(pair.first) != mapFilter.end())
            result.insert(pair);
    }

    return result;
}

I've changed type of parameters to const references, since probably you don't want to copy the parameters.

Simultaneous Union and Intersection between two maps in C++

Add these two loops just after your main while loop.

while (it1 != Kmer1.cend()){
    U += it1->second;
    it1++;
}
while (it2 != Kmer2.cend()){
    U += it2->second;
    it2++;
}

Intersection of two unordered_maps

I know you don't want to hear it, but I'm going to say it anyway: you should cache the hash value on the instances so that hashing reduces to simple member lookup. If the instances are immutable (or at least, the parts that go into the hash function are immutable), then the easiest way to do this is to compute the hash in the constructor.

std::map and performance, intersecting sets

I figured something out: if I attach the debugger to either RELEASE or DEBUG builds (e.g. hit F5 in the IDE), then I get horrible times.

C++ Intersect two maps on keys, keep value of first map

You need to iterate map1 and map2 independently. You cannot use an iterator of map1 to manipulate another map (to erase from map2 or to perform any other operations with map2).

So the code should be something like this:

map<int, double> map1, map2;
map<int, CustomType> map3;
for (auto it = map1.cbegin(); it != map1.cend(); )
{
    if ( map3.find(it->first) == map3.end() )
        it = map1.erase(it);
    else
        ++it;
}

for (auto it = map2.cbegin(); it != map2.cend(); )
{
    if ( map3.find(it->first) == map3.end() )
        it = map2.erase(it);
    else
        ++it;
}

Using a map with set_intersection

MoneyMap map2;
map1.insert( MoneyPair( 3, mn[3] ) );  // (3)
map1.insert( MoneyPair( 4, mn[4] ) );  // (4)
map1.insert( MoneyPair( 5, mn[5] ) );
map1.insert( MoneyPair( 6, mn[6] ) );
map1.insert( MoneyPair( 7, mn[7] ) );

Unless this is a typo, you are just reinserting stuff into map1 instead of inserting into map2. I tested it out with the corrected code and it outputted "Intersection has 2 elements."

---

Related Topics