Intersection of two `std::map`s

c++ dictionary std stdmap c++-standard-library
Hooked picture Hooked · Sep 22, 2010 · Viewed 11k times · Source

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

Mark Ransom picture Mark Ransom · Sep 22, 2010 
template<typename KeyType, typename LeftValue, typename RightValue>
map<KeyType, pair<LeftValue, RightValue> > IntersectMaps(const map<KeyType, LeftValue> & left, const map<KeyType, RightValue> & right)
{
    map<KeyType, pair<LeftValue, RightValue> > result;
    typename map<KeyType, LeftValue>::const_iterator il = left.begin();
    typename 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(make_pair(il->first, 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.

Related questions

Most efficient way to assign values to maps

Which way to assign values to a map is most efficient? Or are they all optimized to the same code (on most modern compilers)? // 1) Assignment using array index notation Foo["Bar"] = 12345; // 2) Assignment using member function insert() and STL pair Foo.…

Read More
How to iterate over a std::map full of strings in C++

I have the following issue related to iterating over an associative array of strings defined using std::map. -- snip -- class something { //... private: std::map<std::string, std::string> table; //... } In the constructor I populate table with …

Read More
Why Can't I store references in a `std::map` in C++?

I understand that references are not pointers, but an alias to an object. However, I still don't understand what exactly this means to me as a programmer, i.e. what are references under the hood? I think the best way …

Read More