两个\`std::map\`的交集

Question

鉴于我有两个 std::map s，说：

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

我想得到两张地图的交集，形式如下：

 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.有没有使用标准库的干净方法？

原文由 Hooked 发布，翻译遵循 CC BY-SA 4.0 许可协议

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

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

原文由 Mark Ransom 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

我不认为有一个纯粹的 STL 方式来实现你想要的。手动实现应该不会太复杂。

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

虽然完整取消引用迭代器的比较包括关联值（我知道您不想将其视为 键 的一部分），但可以通过提供仅测试键的比较函子来解决（ 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;
}

原文由 David Rodríguez - dribeas 发布，翻译遵循 CC BY-SA 3.0 许可协议