两个`std :: map`s的交集 [英] Intersection of two `std::map`s

问题描述

鉴于我有两个std::map，例如:

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;

其中的键是 A和B中的值，并且该值分别是A和B中的一对值. 有没有使用标准库的干净方法?

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?

推荐答案

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

我没有测试过，甚至没有编译过……但是应该是O(n).因为它是模板化的，所以它应该可以与共享相同键类型的任何两个映射一起使用.

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.

这篇关于两个`std :: map`s的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！