Intersection of two `std::map`s

Question

Given that I have two std::maps, say:

map<int, double> A;
map<int, double> B;

I'd like to get the intersection of the two maps, something of the form:

map<int, pair<double,double> > C;

Where the keys are the values in both A and B and the value is a pair of the values from A and B respectively. Is there a clean way using the standard-library?

Answer 1

#include <map>
#include <utility>
template <typename KeyType, typename LeftValue, typename RightValue>
std::map<KeyType, std::pair<LeftValue, RightValue>>
IntersectMaps(const std::map<KeyType, LeftValue>& left, 
              const std::map<KeyType, RightValue>& right) {
    std::map<KeyType, std::pair<LeftValue, RightValue>> result;
    typename std::map<KeyType, LeftValue>::const_iterator il  = left.begin();
    typename std::map<KeyType, RightValue>::const_iterator ir = right.begin();
    while (il != left.end() && ir != right.end()) {
        if (il->first < ir->first)
            ++il;
        else if (ir->first < il->first)
            ++ir;
        else {
            result.insert(std::make_pair(il->first, std::make_pair(il->second, ir->second)));
            ++il;
            ++ir;
        }
    }
    return result;
}

I haven't tested this, or even compiled it... but it should be O(n). Because it's templated it should work with any two maps that share the same key type.