c++ - 使用key的map无序交集的高效算法

Question

按键相交两张地图的最有效方法是什么？

例如：给定

map<int, float> m1;
map<int, float> m2;

m1[1] = 1.0;
m1[2] = 4.0;
m1[3] = 3.0;
m1[7] = 5.0;

m2[7] = 3.0;
m2[4] = 2.0;
m2[2] = 4.0;
m2[9] = 6.0;

我需要一个vector<int>与交集的结果！

预期结果将是：2和7

Answer 1

由于键是排序的，这很容易在 O(n) 时间内完成。只需遍历它们中的每一个，只要键相等，就将该键添加到向量并递增两个迭代器。否则递增具有最低键的迭代器。

Answer 2

答案与设置交集相同。循环遍历第一组，并查询该元素是否在第二组中。复杂度为 O(n lg m)，而 n 和 m 分别是 2 个集合的大小。

如果您使用由哈希表而不是红黑树支持的 unordered_map，您可以获得复杂度为 O(n)。

Answer 3

我可以认为这是m1并且m2已经有排序的元素在得到一个向量O(n)

std::vector<int> v_intersection;

map<int, float> ::iterator i,j;

i=m1.begin(),j=m2.begin();

for(; i!=m1.end() && j!=m2.end() ;) 
   if (i->first < j->first)
            ++i;
   else if (i->first > j->first)
            ++j;
   else{ 
        v_intersection.push_back(i->first);       
        ++i,++j;
    }

Answer 4

我为我的场景 修改了两张 STL 地图的交集。

template<typename keyType, typename leftValue, typename rightValue>
vector<keyType> intersectMaps(const map<keyType, leftValue>& left, const map<keyType, rightValue>& right) {
    vector<keyType> result;
    typename map<keyType, leftValue>::const_iterator itrL = left.begin();
    typename map<keyType, rightValue>::const_iterator itrR = right.begin();
    while (itrL != left.end() && itrR != right.end()) {
        if (itrL->first < itrR->first) {
            ++itrL;
        } else if (itrR->first < itrL->first) {
            ++itrR;
        } else {
            result.push_back(itrL->first);
            ++itrL;
            ++itrR;
        }
    }
    return result;
}

例如。使用：

map<int, float> m1;
map<int, float> m2;

m1[1] = 1.0;
m1[2] = 4.0;
m1[3] = 3.0;
m1[7] = 5.0;

m2[7] = 3.0;
m2[4] = 2.0;
m2[2] = 4.0;
m2[9] = 6.0;

vector<int> result = intersectMaps<int, float, float> (m1, m2);