我正在努力完成我的一部分大学作业。我有两个 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 可能会增长相当大(在数千个条目中)。
最快的方法是什么?
最佳答案
您的代码不是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
。
关于c++ - 如何优化 std::set 交集算法 (C++),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49964288/