两个`std :: map`s的交叉点

Question

鉴于我有两个std::map,说:

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

我想得到两张地图的交集,形式如下:

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

其中键是两者 中的值,A并且B值是分别来自A和的一对值B.使用标准库有一种干净的方式吗？

Answer 1

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).因为它是模板化的,它应该与任何两个共享相同键类型的映射一起使用.

Answer 2

我不认为有一种纯粹的STL方式来实现你想要的东西.手动实施不应该太复杂.

请注意,这std::set_intersection不是解决方案.主要原因是它比较了解除引用的迭代器,然后将其中一个元素复制到输出迭代器.

虽然完全取消引用的迭代器的比较包括相关的值(我理解你不想将其视为键的一部分),可以通过提供只测试key(std::pair<const Key, Value>::first)的比较函数来解决,算法的问题只能复制两个值中的一个而不能复制解决方案无法从外部解决.

编辑:函数的简单线性时间实现:

请注意,正如@Mark Ransom评论的那样,此解决方案增加了额外的要求:密钥必须具有可比性.这是不是与他解决一个问题在这里,或在同样由@Matthiew M中的答案在这里.用这个修复修改这个算法是可耻的:)

@ Mark的实现的另一个巨大优势是它可以从存储不同值类型的映射组成,只要键是相同的(这似乎是一个明显的要求).我希望我能在不止一次上升...

template <typename Key, typename Value>
std::map<Key,std::pair<Value,Value> > 
merge_maps( std::map<Key,Value> const & lhs, std::map<Key,Value> const & rhs )
{
    typedef typename std::map<Key,Value>::const_iterator input_iterator;
    std::map<Key, std::pair<Value,Value> > result;
    for ( input_iterator it1 = lhs.begin(), it2 = rhs.begin(),
                         end1 = lhs.end(), end2 = rhs.end();
            it1 != end1 && it2 != end2; )
    {
        if ( it1->first == it2->first )
        {
            result[it1->first] = std::make_pair( it1->second, it2->second );
            ++it1; ++it2;
        }
        else
        {
            if ( it1->first < it2->first )
                ++it1;
            else
                ++it2;
        }
    }
    return result;
}

Answer 3

#include <map>
using namespace std;
typedef int KeyType;
typedef double ValueType;
typedef map< KeyType, ValueType > MyMap;
typedef MyMap::iterator MyMapIter;
typedef MyMap::const_iterator MyMapConstIter;
typedef pair< ValueType, ValueType > ValueTypePair;
typedef map< KeyType, ValueTypePair > MyMapIntersection;

int main() {
    MyMap A;
    MyMap B;
    MyMapIntersection C;

    // fill up A, B

    for( MyMapConstIter cit = A.begin(); cit != A.end(); ++cit ) {
        const KeyType x = cit->first;
        MyMapConstIter found = B.find( x );
        if( found != B.end() ) {
            ValueTypePair valuePair =
                ValueTypePair( cit->second, found->second );
            C.insert( pair< KeyType, ValueTypePair>( x, valuePair ) );
        }
    }
}