intersect two maps using only keys as a comparator

Question

Hi all, I have two maps and I would like to get map which is intersection of two using only key as a comparator and in the same time do simple math operation on values of common elements such as +/-

for example :

map<int, double> m1,m2;
m1[1] = 1.1;
m1[2] = 2.2

m2[2] = 0.1;
m2[4] = 3.3;

after intersection i will get m3 which will have pair : (2, 2.1) if I use subtraction operator.

What would be the efficient way to do it using algorithm library?

Thank you.

Answer 1

You could do it in two steps. First one is to find intersection, it could be done using set_intersection algorithm. Second step will be using transform algorithm to do math operations using supplied functor.

---

I've found that set_intersection doesn't allow to supply access functor, so in the following code there is a lazy replacement for it. I wrote a sample functor that will do subtraction for you. I believe that you can easily write all other functors. Also you can write template function that will do the same as set_intersection do, but with allowing to supply functor that will dereference iterator.

// sample functor for substruction
template<typename T1, typename T2>
struct sub
{
  // it will be better to use const references, but then you'll not be able
  // to use operator[], and should be use `find` instead 
  sub( std::map<T1, T2>& m1, std::map<T1, T2>& m2 ) : m1(m1), m2(m2) {}
  std::pair<T1,T2> operator()( const T1& index )
  { return make_pair( index, m1[index]-m2[index] ); }    
private:
  std::map<T1, T2>& m1, & m2;
};

int main()
{
 map<int, double> m1,m2;
 m1[1] = 1.1;
 m1[2] = 2.2;

 m2[2] = 0.1;
 m2[4] = 3.3;

 vector<int> v; // here we will keep intersection indexes

 // set_intersection replacement
 // should be moved to stand alone function
 map<int, double>::const_iterator begin1 = m1.begin();
 map<int, double>::const_iterator begin2 = m2.begin();
 for (; begin1 != m1.end() && begin2 != m2.end(); ) {
  if ( begin1->first < begin2->first ) ++begin1;
  else if (begin2->first < begin1->first) ++begin2;
  else v.push_back( begin1->first ), ++begin1, ++begin2;
 }

 map<int, double> m3;
 transform( v.begin(), v.end(), std::inserter(m3, m3.begin()), sub<int, double>( m1, m2 ) );
}

Answer 2

What operations do we want to perform in this function?

• iterate through the maps
• combine values that have the same key
• add elements to a map

Then we have to consider what other containers besides std::map fit this model. Do you want to include multimaps and combine all elements with the same key (let's assume not)? The map doesn't have to be sorted, so hashmaps should work, too. Unfortunately, there is no STL concept that include maps and hashmaps but not multimaps. So let's make one up: Unique Pair Associative Container. Our function should work on both types.

template <typename UPAC, // UPAC models Unique Pair Associative Container
          typename BF>   // BF models Binary Function on UPAC::value_type
UPAC combine_upacs(const UPAC& c1, const UPAC& c2, BF func) {
  UPAC result;
  typename UPAC::const_iterator it1 = c1.begin();
  while (it1 != c1.end()) {
    typename UPAC::const_iterator it2 = c2.find(it1->first);
    if (it2 != c2.end())
      result.insert(make_pair(it1->first, func(it1->second,it2->second));
    ++it1;
  }
  return result;
}

Now, if you are concerned about the running time of combine_upacs on std::map, you may want to take advantage of the fact that maps are sorted, and iterate through both c1 and c2. But this is the most general code that solves the problem.

Answer 3

I don't know of a standard algorithm to do this, but it is simple to write one. This will work for both ordered and un-ordered maps.

  template <class MapT, typename OperationT>
  void intersect_maps(const MapT &map1, const MapT &map2, MapT &target, OperationT op) {
  const MapT *m1, *m2;
  // Pick the smaller map to iterate over
  if (map1.size() < map2.size()) {
    m1 = &map1;
    m2 = &map2;
  } else {
    m1 = &map2;
    m2 = &map1;
  }
  typename MapT::const_iterator it_end = m1->end();
  for (typename MapT::const_iterator it = m1->begin(); it != it_end; ++it) {
    typename MapT::const_iterator pos = m2->find(it->first);
    if (pos != m2->end()) {
      if (m1 == &map1) {
        target.insert(typename MapT::value_type(it->first, op(it->second, pos->second)));
      } else {
        // we swapped the inputs so we need to swap the operands
        target.insert(typename MapT::value_type(it->first, op(pos->second, it->second)));
      }
    }
  }
}

double sub(double v1, double v2) {
  return v1 - v2;
}

// And use it.    
m1[1] = 1.1;
m1[2] = 2.2;

m2[2] = 0.1;
m2[4] = 3.3;

intersect_maps(m1, m2, m3, sub);