两个STL地图的交集 [英] Intersection of two STL maps

问题描述

由于我有两个STL映射，例如：

Given that I have two STL 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;

其中键是 A和B中的值，是分别来自A和B的一对值。有没有一个干净的类似STL的方式去解决这个问题？

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 STL-like way to go about this?

推荐答案

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.

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