Intersection of two `std::map`s

Question

Given that I have two std::maps, say:

map<int, double> A;
map<int, double> B;

I'd like to get the intersection of the two maps, something of the form:

map<int, pair<double,double> > C;

Where the keys are the values in both A and B and the value is a pair of the values from A and B respectively. Is there a clean way using the standard-library?

Solution 1

template<typename KeyType, typename LeftValue, typename RightValue>
map<KeyType, pair<LeftValue, RightValue> > IntersectMaps(const map<KeyType, LeftValue> & left, const map<KeyType, RightValue> & right)
{
    map<KeyType, pair<LeftValue, RightValue> > result;
    typename map<KeyType, LeftValue>::const_iterator il = left.begin();
    typename 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(make_pair(il->first, 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.

Solution 2

I don't think there is a pure STL way of implementing what you want. Manual implementation should not be too complicated.

Note that std::set_intersection is not a solution. The main reason being that it compares the dereferenced iterators and then copies one of the elements to the output iterator.

While comparison of the full dereferenced iterator includes the associated value (which I understand you do not want to consider as part of the key), can be solved by providing a comparison functor that would only test the key (std::pair<const Key, Value>::first), the problem of the algorithm copying only one of the two values and not composing the solution cannot be tackled externally.

EDIT: A simple linear time implementation of the function:

Note, as @Mark Ransom comments, that this solution adds an extra requirement: the keys must be equality comparable. That is not an issue with his solution here, or similarly in the answer by @Matthiew M here. It would be shameful to modify this algorithm with that fix :)

Another great advantage of @Mark's implementation is that it can compose from maps that store different value types as long as the keys are the same (which seems like an obvious requirement). I wish I would upvote more than once there..

template <typename Key, typename Value>
std::map<Key,std::pair<Value,Value> > 
merge_maps( std::map<Key,Value> const & lhs, std::map<Key,Value> const & rhs )
{
    typedef typename std::map<Key,Value>::const_iterator input_iterator;
    std::map<Key, std::pair<Value,Value> > result;
    for ( input_iterator it1 = lhs.begin(), it2 = rhs.begin(),
                         end1 = lhs.end(), end2 = rhs.end();
            it1 != end1 && it2 != end2; )
    {
        if ( it1->first == it2->first )
        {
            result[it1->first] = std::make_pair( it1->second, it2->second );
            ++it1; ++it2;
        }
        else
        {
            if ( it1->first < it2->first )
                ++it1;
            else
                ++it2;
        }
    }
    return result;
}

Solution 3

#include <map>
using namespace std;
typedef int KeyType;
typedef double ValueType;
typedef map< KeyType, ValueType > MyMap;
typedef MyMap::iterator MyMapIter;
typedef MyMap::const_iterator MyMapConstIter;
typedef pair< ValueType, ValueType > ValueTypePair;
typedef map< KeyType, ValueTypePair > MyMapIntersection;

int main() {
    MyMap A;
    MyMap B;
    MyMapIntersection C;

    // fill up A, B

    for( MyMapConstIter cit = A.begin(); cit != A.end(); ++cit ) {
        const KeyType x = cit->first;
        MyMapConstIter found = B.find( x );
        if( found != B.end() ) {
            ValueTypePair valuePair =
                ValueTypePair( cit->second, found->second );
            C.insert( pair< KeyType, ValueTypePair>( x, valuePair ) );
        }
    }
}

Solution 4

EDIT: Since I was pretty sure there was a better STL-like solution to this, I figured one out. It's different enough that I'm posting it as a separate answer.

There are a few tricks to this. Firstly, you'd like to use set_intersection, but you have two maps. The solution is a custom comparator and the std::transform algorithm. Someone more familiar with the standard library than me can probably optimize this, but it works. Note that boost::bind would allow you to cut down on the silly helper functions that make this work.

#include <algorithm>
#include <map>
#include <set>

bool myLess(const std::map<int,double>::value_type &v1,
            const std::map<int,double>::value_type &v2) {
    return v1.first < v2.first;
}
int getKey(const std::map<int,double>::value_type &v) {
    return v.first;
}

struct functor {
    std::map<int,double> &m1,&m2;
    functor(std::map<int,double> &im1, std::map<int,double> &im2) : m1(im1), m2(im2) {}
    std::pair<int,std::pair<double,double> > operator() (int x) {
        return std::make_pair(x, std::make_pair(m1[x],m2[x]));
    }
};

int main() {
    std::map<int,double> m1, m2;
    m1[0]=0;m1[1]=1; m1[2]=2; m1[3]=3;
            m2[1]=11;m2[2]=12;m2[3]=13;m2[4]=14;

    std::set<int> keys1,keys2,keys;
    //Extract the keys from each map with a transform
    std::transform(m1.begin(),m1.end(),std::inserter(keys1,keys1.begin()),getKey);
    std::transform(m2.begin(),m2.end(),std::inserter(keys2,keys2.begin()),getKey);
    //set_intersection to get the common keys
    std::set_intersection(keys1.begin(),keys1.end(),keys2.begin(),keys2.end(),
            std::inserter(keys,keys.begin()));

    std::map<int, std::pair<double,double> > result;
    functor f(m1,m2);  //stash our maps into the functor for later use
    //transform from the key list to the double-map
    std::transform(keys.begin(),keys.end(),std::inserter(result,result.begin()),f);
    return 0;
}

Like much of C++, the final use of everything is fairly slick (everything in main()), but the setup is more verbose than we would really like.

Solution 5

A (better) solution based on the fact that the maps are sorted. (Shame on me that I overlooked it.) Thanks to David Rodríguez - dribeas for the suggestion.

#include <map>
using namespace std;
typedef int KeyType;
typedef double ValueType;

typedef map< KeyType, ValueType > MyMap;
typedef MyMap::iterator MyMapIter;
typedef MyMap::const_iterator MyMapConstIter;

typedef pair< ValueType, ValueType > ValueTypePair;

typedef map< KeyType, ValueTypePair > MyMapIntersection;


void constructInsert( MyMapIntersection & c, MyMapConstIter const & acit,
    MyMapConstIter const & bcit ) {

    ValueTypePair valuePair = ValueTypePair( acit->second, bcit->second );

    c.insert( pair< KeyType, ValueTypePair>( acit->first, valuePair ) );
}


int main() {

    MyMap A;
    MyMap B;
    MyMapIntersection C;

    // fill up A, B

    MyMapConstIter acit, bcit;
    for( acit = A.begin(), bcit = B.begin();
        (acit != A.end()) && (bcit != B.end()); /* Inside loop */ ) {

        const KeyType aKey = acit->first;
        const KeyType bKey = bcit->first;

        if( aKey < bKey ) {

            ++acit;
        }
        else if( aKey == bKey ) {

            constructInsert( C, acit, bcit );

            ++acit;
            ++bcit;
        }
        else {

            ++bcit;
        }
    }

}

View more solutions