Combine two cards by summing the values ​​for the same keys in C ++

Question

I have two std::map<int,int> cards and you want to combine them into a third card as follows: if the same key is found on both cards, create a pair on the third card with the same key and value, which is the sum values ​​from the first and second card, otherwise just copy the pair to the third card. I suspect that this can be done using std::accumulate , but I don't understand it well enough.

Answer 1

Too general solution inspired by std::set_union . Unlike the first suggested answer, this should be done in O (n) instead of O (n log n).

Edit : it is still O (n log n) due to insertions in the final map.

 #include <map> #include <iostream> #include <iterator> #include <algorithm> template<class InputIterT1, class InputIterT2, class OutputIterT, class Comparator, class Func> OutputIterT merge_apply( InputIterT1 first1, InputIterT1 last1, InputIterT2 first2, InputIterT2 last2, OutputIterT result, Comparator comp, Func func) { while (true) { if (first1 == last1) return std::copy(first2, last2, result); if (first2 == last2) return std::copy(first1, last1, result); if (comp(*first1, *first2) < 0) { *result = *first1; ++first1; } else if (comp(*first1, *first2) > 0) { *result = *first2; ++first2; } else { *result = func(*first1, *first2); ++first1; ++first2; } ++result; } } template<class T> int compare_first(T a, T b) { return a.first - b.first; } template<class T> T sum_pairs(T a, T b) { return std::make_pair(a.first, a.second + b.second); } using namespace std; int main(int argc, char **argv) { map<int,int> a,b,c; a[1] = 10; a[2] = 11; b[2] = 100; b[3] = 101; merge_apply(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.begin()), compare_first<pair<int, int> >, sum_pairs<pair<int, int> >); for (auto item : c) cout << item.first << " " << item.second << endl; } 

Answer 2

I don't think it will be easy (if not impossible) to find a suitable std::algorithm that serves the purpose.

The easiest way is to make a copy of map1 to map_result .

Then go through map2 and see if key already exists in map_result , then add values , add a key_value pair to map_result .

 std::map<int,int> map_result( map1 ); for (auto it=map2.begin(); it!=map2.end(); ++it) { if ( map_result[it->first] ) map_result[it->first] += it->second; else map_result[it->first] = it->second; } 

Answer 3

Here is an example of how to complete a task using std :: accumulate

 #include <iostream> #include <map> #include <numeric> int main() { std::map<int, int> m1 = { { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 } }; std::map<int, int> m2 = { { 2, 5 }, { 3, 1 }, { 5, 5 } }; for ( const auto &p : m1 ) { std::cout << "{ " << p.first << ", " << p.second << " } "; } std::cout << std::endl; for ( const auto &p : m2 ) { std::cout << "{ " << p.first << ", " << p.second << " } "; } std::cout << std::endl; std::map<int, int> m3 = std::accumulate( m1.begin(), m1.end(), std::map<int, int>(), []( std::map<int, int> &m, const std::pair<const int, int> &p ) { return ( m[p.first] +=p.second, m ); } ); m3 = std::accumulate( m2.begin(), m2.end(), m3, []( std::map<int, int> &m, const std::pair<const int, int> &p ) { return ( m[p.first] +=p.second, m ); } ); for ( const auto &p : m3 ) { std::cout << "{ " << p.first << ", " << p.second << " } "; } std::cout << std::endl; return 0; } 

Output signal

 { 1, 1 } { 2, 2 } { 3, 3 } { 4, 4 } { 2, 5 } { 3, 1 } { 5, 5 } { 1, 1 } { 2, 7 } { 3, 4 } { 4, 4 } { 5, 5 } 

In fact, only for the second card you need to use std :: accumulate. The first card can simply be copied or assigned to m3.

for instance

  std::map<int, int> m3 = m1; m3 = std::accumulate( m2.begin(), m2.end(), m3, []( std::map<int, int> &m, const std::pair<const int, int> &p ) { return ( m[p.first] +=p.second, m ); } );