31

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

3 Answers 3

21

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

3
  • 1
    This is what I came up with as well, and it's a common approach (see intersection of sorted arrays). But I feel like there should be a library feature that gives me this already... Commented Nov 8, 2018 at 11:18
  • This is great! I'd pass *it1 and *it2 to merger though, just in case that the keys are useful for merging. (I'm aware the OP does not currently need this functionality, though.)
    – Arne Vogel
    Commented Nov 8, 2018 at 11:43
  • 1
    By the way, there is a (probably very rare) possibility that dest.value_comp() and source.value_comp() have state and are not equivalent. Unfortunately, there is no generic way to test for that.
    – Arne Vogel
    Commented Nov 8, 2018 at 12:07
8

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.

4
  • 2
    Note that complexity is O(N log N).
    – Jarod42
    Commented Nov 8, 2018 at 11:00
  • @Jarod42, Fair point. It depends what the expectations are in terms of conflicts vs. map size. I believe your linear approach could be made to have the same benefits rearranging nodes as well, though I'd say the tradeoff between that and this version is in code complexity.
    – chris
    Commented Nov 8, 2018 at 11:04
  • @Jarod42 Shouldn't there be 2 variables in your complexity representing the lengths of the 2 different maps, i.e. O( M ... N )? Are you saying that the merge() is O(N log N) or the whole thing? Commented Nov 8, 2018 at 11:24
  • 3
    @nonsensickle: std::map::merge is N*log(size()+N)) (I would have imagined linear though...). Then conflict resolution is not done linearly (about "new" base.size()) but done in O(N3 log (size() + N3)) (N3: conflict's size). So indeed to be more precise, we should have 3 parameter base.size(), toMerge.size() and conflicts.size(), but my original note hasn't that precision :-).
    – Jarod42
    Commented Nov 8, 2018 at 12:26
6

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);
}
2
  • 2
    Note that complexity is O(N log N).
    – Jarod42
    Commented Nov 8, 2018 at 10:59
  • Is there a good reason to use auto&& and then not std::fwd() the contents? I'm not used to seeing one without the other like that. Commented Nov 8, 2018 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.