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

Question

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

Answer 1

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

Answer 2

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.