如何在 STL 中合并两个地图并应用冲突函数？

Question

我已阅读Merge two STL maps question, and though it's close, I was looking for functionality like the one described here。

简而言之，我想将两个 std::map 实例 （具有相同的键和值类型） 合并为一个，但我想如果对象存在于两个映射中，则将值相加。

是否有可以执行此操作的现有 boost, range-v3, or std 函数？如果没有，实现它的最佳方法是什么？

示例代码：

double mergePredicate(double lhs, double rhs)
{
    return lhs + rhs;
}

int main()
{
    std::map<int, double> mapA = { {0, 1.0}, {1, 2.0} };
    std::map<int, double> mapB = { {1, 1.5}, {2, 2.5} };

    // Merge maps in some way...
    merge(mapA, mapB, mergePredicate);

    // result: mapA == { {0, 1.0}, {1, 3.5}, {2, 2.5} }
    for (const auto& p : mapA) {
        std::cout << p.first << " " << p.second << std::endl;
    }
}

Answer 1

对于这种特定情况，因为 operator[] 会在不存在的情况下创建一个键，您可以使用简单的循环来添加两个值：

for (const auto& pair : mapB) {
    mapA[pair.first] += pair.second;
}

当你想使用一个函数，但在没有键存在的情况下使用默认初始化值是可以的：

for (const auto& pair : mapB) {
    mapA[pair.first] = mergePredicate(mapA[pair.first], pair.second);
}

Answer 2

我不知道有任何现有功能可以执行此操作，但您可以使用 std::map 的 merge function (live example):

template<typename K, typename V, typename F>
void mergeWithConflicts(std::map<K, V>& base, std::map<K, V> toMerge, F combine) {
    base.merge(toMerge);

    // All that's left in toMerge is conflicting keys
    for (const auto& [k, v] : toMerge) { 
        base[k] = combine(base[k], toMerge[k]);
    }
}

作为奖励，merge 的实现比您手动执行的操作效率更高，除非您使用 extract 之类的方法重新实现它。它不是复制或移动元素，而是调整内部指针以将节点从一张地图移动到另一张地图。但是，这意味着它修改了另一个地图。正如建议的那样，该参数是按值获取的，因此如果不再需要，可以将另一个地图移入，否则复制。

Answer 3

我不知道有任何现有的功能，但您可以从类似于 std::merge 实现的东西中推出自己的功能以具有线性复杂性：

template<class Map, class Merger>
void merge(Map& dest, const Map& source, Merger merger)
{
    auto it1 = dest.begin();
    auto it2 = source.begin();
    auto&& comp = dest.value_comp();

    for (; it1 != dest.end() && it2 != source.end(); ) {
        if (comp(*it1, *it2)) {
            ++it1;
        } else if (comp(*it2, *it1)) {
            dest.insert(it1, *it2); // with hint to have correct complexity
            ++it2;
        } else { // equivalent
            it1->second = merger(it1->second, it2->second);
            ++it1;
            ++it2;
        }
    }
    dest.insert(it2, source.end());
}

Demo

如何在 STL 中合并两个地图并应用冲突函数？

How do I merge two maps in STL and apply a function for conflicts?

c++

merge

stdmap