Adding two maps together

Question

I want to add two maps together with the following behavior.

if key exists -> add two key values together.

if key does not exist -> Insert pair to map.

I have looked at a few of the standard library algorithms. Namely transform, but doesn't seem to do what I want.

Taken from this LINK

template < class InputIterator, class OutputIterator, class UnaryOperator >
  OutputIterator transform ( InputIterator first1, InputIterator last1,
                             OutputIterator result, UnaryOperator op )
{
  while (first1 != last1)
    *result++ = op(*first1++);  // or: *result++=binary_op(*first1++,*first2++);
  return result;
}

My thoughts from this where that I would only have one iterator from my second map when using and the appropriate functor

 *result++=binary_op(*first1++,*first2++);

Therefore I will not be able to loop over my second map to find the key value.

One thought was just to make my own algorithm with a subtle change.

template < class InputIterator, class ContainerType, class BinaryOperator >
  void myTransform ( InputIterator first1, InputIterator last1,
                               ContainerType cont2,  
                               BinaryOperator binary_op )
{
  while (first1 != last1)
    binary_op(first1++, cont2); //cont2 passed by reference 
}

I would then be able to use:

cont2.find() in my functor to search the whole map.

Here would be a more complete example of what I was thinking, but I seem to get a compiling error that I can not solve ( I am kind of guessing the BinaryOperator type...see below)?

#include <map>
#include <string>
#include <iostream>

template < class InputIterator, class ContainerType, class BinaryOperator >
void myTransform ( InputIterator first1, InputIterator last1,
                 ContainerType &cont2, 
                 BinaryOperator binary_op )
{
  while (first1 != last1)
    binary_op(first1++, cont2); //cont2 passed by reference
}

template<class IteratorType, class ContainerType>
struct AddMapValues:
  std::binary_function<IteratorType, ContainerType, void>
{
  void operator()(IteratorType itr, ContainerType& cont)
  {
    if( cont.find(itr->first) != cont.end() ) cont[itr->first] = cont.find(itr->first).second + itr->second;
    else cont.insert( (*itr) );
  }
};


int main()
{
  typedef std::map<std::string, double> stringDoubleMap;
  typedef std::map<std::string, double>::iterator stringDoubleMapItr;
  typedef void (*ptrfnt)(stringDoubleMapItr, stringDoubleMap& );

  stringDoubleMap map1;
  stringDoubleMap map2;

  map1.insert( stringDoubleMap::value_type("Test1",1.0) );
  map1.insert( stringDoubleMap::value_type("Test2",2.0) );
  map1.insert( stringDoubleMap::value_type("Test3",3.0) );

  map2.insert( stringDoubleMap::value_type("Test1",1.0) );
  map2.insert( stringDoubleMap::value_type("Test2",2.0) );
  map2.insert( stringDoubleMap::value_type("Test3",3.0) );

  myTransform( map1.begin(), map1.end(),
               map2, 
               AddMapValues< stringDoubleMapItr, stringDoubleMap >() );

  return 0;

}

Here is my compiler error:

testingMapTransforms.cxx: In function ‘int main()’:

testingMapTransforms.cxx:52:85: error: no matching function for call to     ‘myTransform(std::map<std::basic_string<char>, double>::iterator, std::map<std::basic_string<char>, double>::iterator, stringDoubleMap&, std::map<std::basic_string<char>, double>::iterator, AddMapValues<std::_Rb_tree_iterator<std::pair<const std::basic_string<char>, double> >, std::map<std::basic_string<char>, double> >)’

testingMapTransforms.cxx:52:85: note: candidate is:

testingMapTransforms.cxx:12:20: note: template<class InputIterator, class ContainerType, class   OutputIterator, class BinaryOperator> OutputIterator myTransform(InputIterator, InputIterator,  ContainerType, OutputIterator, BinaryOperator)

There seems to be another iterator coming from somewhere and the container type is not read properly?

Any ideas?

I am using

gcc - GNU project C and C++ compiler

with

Ubuntu/Linaro 4.6.3-1ubuntu5

Thanks

NOTE:

I have updated a working version of the code above in an answer. If you think I should just change the question code instead let me know. Not sure of the best practice

Answer 1

I want to add two maps together with the following behavior:
If key exists add two key values together.
If key does not exist. Insert pair to map.

I think a simple for loop would do what you want:

for(auto it = map2.begin(); it != map2.end(); ++it) map1[it->first] += it->second;

If the key exists, the value will be added to the existing one. If the key doesn't exist, operator[] will insert it and it's value will be default initialized (0.0 for double).

I don't think going for a generic function that would work on any container would be sensible here. The semantics of say vector's and map's insert() and operator[] are just too different.

Answer 2

I don't think you can do it with transform. You have two containers, you'll need two iterator pairs, and you'll need to advance them separately when an element is only in one of them. The two sequence version of transform advances them in lockstep.

It shouldn't be too hard to do by hand. Something like the following, perhaps:

typedef std::map<std::string, std::double> Map

Map
addValues( Map const& m1, Map const& m2 )
{
    Map results;
    Map::const_iterator i1 = m1.begin();
    Map::const_iterator i2 = m2.begin();
    while ( i1 != m1.end() && i2 != m2.end() ) {
        if ( i1->first < i2->first ) {
            results.insert( results.end(), *i1 );
            ++ i1;
        } else if ( i2->first < i1->first ) {
            results.insert( results.end(), *i2 );
            ++ i2;
        } else {
            results.insert( results.end(),
                            Map::value_type( i1->first, i1->second + i2->second ) );
            ++ i1;
            ++ i2;
        }
    }
    results.insert( i1, m1.end() );
    results.insert( i2, m2.end() );
    return results;
}

(I'd get it working like this first, before making it a template.)