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

user_1667513 0
Viewed 1712

I have read the Merge two STL maps question, and though it's close, I was looking for functionality like the one described here.

In short, I would like to merge two std::map instances (having the same key and value type) into one, with the caveat that I would like to add the values together if the object exists in both maps.

Is there an existing boost, range-v3, or std function that can do this? And if not, what would be the best way to achieve it?

Example code:

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;
    }
}
stdmap merge c++
3 Answers

I don't know of any existing function for that, but you can roll your own from something similar to std::merge implementation to have linear complexity:

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

user_26845390

I don't know of any existing function to do this, but you can make use of std::map's 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]);
    }
}

As a bonus, the implementation of merge is rather efficient compared to what you can do by hand unless you reimplement it using the likes of extract. Instead of copying or moving elements, it adjusts internal pointers to move nodes from one map to the other. However, this means it modifies the other map. As suggested, the parameter is taken by value, so the other map can be moved in if it is no longer needed and copied otherwise.

user_9620890

For this specific case, because operator[] creates a key if it doesn't exist, you can use simple loop to add the two values:

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

And when you want to use a function, but it is okay to use a default-initialized value where no key exists:

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