合并两个映射，对C ++中相同键的值求和 [英] Merge two maps, summing values for same keys in C++

问题描述

我有两个std::map<int,int>映射，希望将它们合并成第三张这样的映射: 如果在两个映射中都找到了相同的键，则在第三张映射中创建一个具有相同键和一个值的值对，该值必须是第一张和第二张图的值之和，否则只需将一对复制到第三张图即可. 我怀疑可以使用std::accumulate来完成此操作，但是我对此不太了解.

I have two std::map<int,int> maps and wish to merge them into a third map like this: if the same key is found in both maps, create a pair in the third map with the same key and a value which a sum of values from the first and second map, otherwise just copy a pair to the third map. I suspect it can be done with std::accumulate, but I don't understand it well enough.

推荐答案

受std::set_union启发的过于通用的解决方案.与第一个建议的答案不同，此方法应在O(n)中运行，而不是O(n log n).

An overly generic solution inspired by std::set_union. Unlike the first suggested answer, this should run in O(n) instead of O(n log n).

编辑:由于插入到最终地图中，因此仍为O(n log n).

Edit: it's still O(n log n) because of insertions into 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;
}

这篇关于合并两个映射，对C ++中相同键的值求和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！