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?

Answer 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.

Answer 2

The following is a simplification of my previous answer, mostly taking advantage of the fact that set_intersection CAN be used with maps as input, but only if you make the output a set of std::pairs. The result also cuts down intermediates to a single "common keys" list.

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

struct cK { //This function object does double duty, the two argument version is for
            //the set_intersection, the one argument version is for the transform
    std::map<int,double> &m1,&m2;
    cK(std::map<int,double> &im1, std::map<int,double> &im2) : m1(im1), m2(im2)
    std::pair<int,std::pair<double,double> > operator() (std::pair<int,double> v
        return std::make_pair(v.first, std::make_pair(m1[v.first],m2[v.first]));
    }
    bool operator() (std::pair<int,double> v1, std::pair<int,double> v2) {
        return v1.first < v2.first;
    }
};

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;

    // Get the subset of map1 that has elements in map2
    std::set<std::pair<int,double> > sIntersection;
    cK compareKeys(m1,m2);
    std::set_intersection(m1.begin(),m1.end(),m2.begin(),m2.end(),
            std::inserter(sIntersection,sIntersection.begin()),compareKeys);

    // Use a custom transform to produce an output set
    std::map<int, std::pair<double,double> > result;
    std::transform(sIntersection.begin(),sIntersection.end(),
            std::inserter(result,result.begin()), compareKeys);
    return 0;
}

Answer 3

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.

Answer 4

Okay, let's get ready to get your hands dirty :)

I'll be using std::mismatch and std::transform

First of all, some types:

typedef std::map<int, double> input_map;
typedef input_map::const_reference const_reference;
typedef input_map::const_iterator const_iterator;
typedef std::pair<const_iterator,const_iterator> const_pair;

typedef std::map<int, std::pair<double,double> > result_map;

Then predicates

bool less(const_reference lhs, const_reference rhs)
{
  return lhs.first < rhs.first;
}

result_map::value_type pack(const_reference lhs, const_reference rhs)
{
  assert(lhs.first == rhs.first);
  return std::make_pair(lhs.first, std::make_pair(lhs.second, rhs.second));
}

Now main:

result_map func(input_map const& m1, input_map const& m2)
{
  if (m1.empty() || m2.empty()) { return result_map(); }

  // mismatch unfortunately only checks one range
  // god do I hate those algorithms sometimes...
  if (*(--m1.end()) < *(--m2.end()) { return func(m2, m1); }

  const_pair current = std::make_pair(m1.begin(), m2.begin()),
             end = std::make_pair(m1.end(), m2.end());

  result_map result;

  // Infamous middle loop, the check is middle-way in the loop
  while(true)
  {
    const_pair next = std::mismatch(p.first, end.first, p.second, less);

    std::transform(current.first, next.first, current.second,
      std::inserter(result, result.begin()), pack);

    // If any of the iterators reached the end, then the loop will stop
    if (next.first == end.first || next.second == end.second) { break; }

    // Advance the lesser "next"
    if (less(*next.first, *next.second)) { ++next.first; }
    else                                 { ++next.second; }

    current = next;
  }

  return result;
}

I find this solution quite elegant... notwithstanding the awkard setup part since we need to ensure that the first range ends up quicker than the second because of mismatch...

Notice that the advance is really stupid, we could loop specifically here until we had *next.first.key == *next.second.key but it would complicate the loop.

I really don't find this better than a handcrafted loop though... consider:

result_map func2(input_map const& lhs, input_map const& rhs)
{
  result_map result;

  for (const_iterator lit = lhs.begin(), lend = lhs.end(),
                      rit = rhs.begin(), rend = rhs.end();
       lit != lend && rit != rend;)
  {
    if (lit->first < rit->first)      { ++lit; }
    else if (rit->first < lit->first) { ++rit; }
    else
    {
      result[lit->first] = std::make_pair(lit->second, rit->second);
      ++lit, ++rit;
    }
  }

  return result;
}

It's much more compact, probably more efficient... sometimes the functions you're looking are not general enough to be in the STL :)

Answer 5

Almost a year after... but nevertheless :)

This one is for a set container, but you can easily change it to use a map:

template <class InputIterator, class OutputIterator>
OutputIterator intersect(InputIterator lf, InputIterator ll, 
                         InputIterator rf, InputIterator rl, 
                         OutputIterator result)
{
    while(lf != ll && rf != rl)
    {
        if(*lf < *rf)
            ++lf;
        else if(*lf > *rf)
            ++rf;
        else
        {
            *result = *lf;
            ++lf;
            ++rf;
        }
    }
    return result;
}

Usage:

intersect(set1.begin(), set1.end(), 
          set2.begin(), set2.end(), 
          inserter(output_container, output_container.begin()));

set1 and set2 are both set containers whilst output_container can be set, list, array etc..

inserter generates an insert iterator

Answer 6

template<typename K, typename V>
std::map<K, V> UnionMaps(const std::map<K, V> & left, const std::map<K, V> & right)
{
    std::map<K, V > result;
    typename std::map<K, V>::const_iterator il = left.begin();
    typename std::map<K, V>::const_iterator ir = right.begin();
    while (il != left.end() && ir != right.end())
    {
        if ((il->first < ir->first)){
            result.insert(make_pair(il->first, il->second));
            ++il;
        }else if ((ir->first < il->first)){
            result.insert(make_pair(ir->first, ir->second));
            ++ir;
        }else{
            result.insert(make_pair(il->first, il->second+ir->second));//add 
            ++il;
            ++ir;
        }
    }
    while (il != left.end() ){
        result.insert(make_pair(il->first, il->second));
        il++;
    }
    while (ir != right.end() ){
        result.insert(make_pair(ir->first, ir->second));
        ir++;
    }
    return result;
}