合并两个映射,在C++中对相同键的值求和

Question

我有两个std::map<int,int>地图,并希望将它们合并到第三个地图中:如果在两个地图中找到相同的键,则在第三个地图中使用相同的键创建一对,并使用一个值来表示第一个和第二个的值之和映射,否则只需将一对复制到第三个映射.我怀疑它可以用std::accumulate,但我不太了解它.

Answer 1

灵感来自于过于通用的解决方案std::set_union.与第一个建议的答案不同,这应该在O(n)而不是O(n log n)中运行.

编辑:由于插入最终地图,它仍然是O(n log n).

#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

以下是如何使用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;
}

输出是

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

实际上只有第二个映射才需要使用std :: accumulate.第一张地图可以简单地复制或分配给m3.

例如

    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 );
        } );