Xtykutl

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 have merge two std::map instances (having thee 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;

    }

}

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

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.

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

}