如何实现两个标准：：map<无符号，无符号>的乘法合并？

Question

想象两个这样的地图：

const std::map<unsigned, unsigned> s0{{0, 1}, {2, 2}};
const std::map<unsigned, unsigned> s1{{0, 2}, {1, 3}};

我想要的是

{{0, 3/*1+2*/}, {1, 3/*0+3*/}, {2, 2/*2+0*/}};

意味着目标中的映射值应该是源中映射值的总和。关键值是索引。

BTW——这适用于多项式的两个系数相互相乘——幂累加。例如，想象具有多个自变量x0..x2的两个多项式。可能有一个x0*x1^2*x2^3的系数。该系数的映射将是{{0,1}、{1,2}、{2,3}}。乘以x0^3，得到x0^4*x1^2*x2^3。

for (auto p0 = s0.begin(), p1 = s1.begin();
p0 != s0.end() || p1 != s1.end();)
if (p0 != s0.end())
if (p1 != s1.end())
if (p0->first < p1->first)
s.insert(*p0++);
else
if (p0->first > p1->first)
s.insert(*p1++);
else
{    s.insert(std::make_pair(p0->first, p0->second + p1->second));
++p0;
++p1;
}
else
{    s.insert(p0, s0.end());
p0 = s0.end();
}
else
{    s.insert(p1, s1.end());
p1 = s1.end();
}

我知道如何使用for循环来实现这一点(见上文(。但我想知道是否可以使用std:：merge((之类的东西来完成。我认为其中一个需要一个重载的std:：inserter((来累积映射的值。还有什么更优雅的方式吗？

Answer 1

循环遍历第二个映射，并将其键的值添加到第一个映射中同一个键的值中。

for (const auto& p: s1)
s0[p.first] += p.second;

如果无法修改第一张地图，请在第三张地图中复制并添加到其中。

Answer 2

我不知道有什么标准算法可以开箱即用。std::merge是对两个已排序的范围进行排序，因此在这里没有帮助。不过，这个循环可以更简单：

#include <map>
#include <iostream>
int main(){
const std::map<unsigned, unsigned> s0{{0, 1}, {2, 2}};
const std::map<unsigned, unsigned> s1{{0, 2}, {1, 3}};
std::map<unsigned,unsigned> result = s0;
for (const auto& e : s1) result[e.first] += e.second;

for (const auto& e : result){
std::cout << e.first << " " << e.second << "n";
}
}

输出：

0 3
1 3
2 2

PS：也许我误解了，但我不明白这是如何乘以多项式的。如果一个多项式是2x^2 + 1，另一个是3x + 2，那么它们的乘积是6x^3 + 4x^2 + 3x + 2，您可以通过：获得

std::map<unsigned,unsigned> result;
for (const auto& e0 : s0) {
for (const auto& e1 : s1){
result[e0.first + e1.first] += e0.second * e1.second;
}
}