c++ - 如何优化 std::set 交集算法 (C++)

Question

我正在努力完成我的一部分大学作业。我有两个 std::set 容器子集，其中包含指向相当复杂对象的指针，但按不同的标准排序(这就是为什么我不能使用 std::set_intersection())。我需要尽快找到包含在两个子集中的元素。作业有时间/复杂性要求。

我可以在 n*log(m) 时间内完成，其中 n 是第一个子集的大小，m 是大小通过执行以下操作的第二个子集:

for(auto it = subset1.begin(), it != subset1.end(), it++){
    if(find(subset2.begin(), subset2.end(), *it))
        result.insert(*it);
}

这不符合时间要求，即最坏情况是线性的，但平均优于线性。

我找到了以下 question在这里，我发现哈希表方法很有趣。但是，我担心哈希表的创建可能会产生太多开销。集合中包含的类看起来像这样:

class containedInSets {
   //methods
private: 
    vector<string> member1;
    SomeObject member2;
    int member3;
}

我无法控制 SomeObject 类，因此无法为其指定哈希函数。我必须散列指针。此外， vector 可能会增长相当大(在数千个条目中)。

最快的方法是什么？

Answer 1

您的代码不是O(n log(m))，而是O(n * m)。

std::find(subset2.begin(), subset2.end(), *it) 是线性的，但是 std::set 有方法 find 和 count 在 O(log(n)) 中(他们进行二进制搜索)。

所以你可以简单地做:

for (const auto& e : subset1) {
    if (subset2.count(e) != 0) {
        result.insert(e);
    }
}

其复杂度为 n*log(m) 而不是您的 n * m。