c++ - 两个 `std::map` 的交集

Question

鉴于我有两个 std::map，比如说:

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

我想得到两张 map 的交集，形式如下:

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

其中键是 both A 和 B 中的值，值是 A< 中的一对值 和 B 分别。 有没有使用标准库的干净方法？

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)。因为它是模板化的，所以它应该适用于任何两个共享相同键类型的 map 。