我是 C++ 的新手,被要求将 Java 程序转换为 C++。 我正在尝试编写一种方法来检查一个 unordered_set 中的所有元素是否存在于另一个 unordered_set 中。我发现下面的示例使用了 hash_set,但 hash_set 已被弃用,建议现在使用 unordered_set。
// returns true if one contains all elements in two
bool SpecSet::containsAll(hash_set<Species*> one, hash_set<Species*> two) {
sort(one.begin(), one.end());
sort(two.begin(), two.end());
return includes(one.begin(), one.end(), two.begin(), two.end());
}
所以我需要一种使用 unordered_set 来完成此操作的方法。排序不适用于无序集,查找速度很重要,所以我不想使用有序集。
bool SpecSet::containsAll(unordered_set<Species*> one, unordered_set<Species*> two) {
return ?;
}
我非常感谢您提供有效执行此操作的方法。
编辑: 我想这会奏效。似乎没有更有效的方法,只能一分为二地循环。
bool SpecSet::containsAll(unordered_set<Species*> one, unordered_set<Species*> two) {
if(two.size() > one.size())
{
return false;
}
for(Species *species : two)
{
if(one.find(species) == one.end())
{
return false;
}
}
return true;
}
最佳答案
对于未排序的集合,没有比迭代较小的集契约(Contract)时测试每个元素都是较大集合的成员更快的算法了。这自然会扩展为 O(n),其中 n 是假定子集的大小,因为我们执行 O(1) 查找操作 n 次。
这是一些带有测试的演示代码:
#include <unordered_set>
template <typename T>
bool is_subset_of(const std::unordered_set<T>& a, const std::unordered_set<T>& b)
{
// return true if all members of a are also in b
if (a.size() > b.size())
return false;
auto const not_found = b.end();
for (auto const& element: a)
if (b.find(element) == not_found)
return false;
return true;
}
int main()
{
const std::unordered_set<int> empty{ };
const std::unordered_set<int> small{ 1, 2, 3 };
const std::unordered_set<int> large{ 0, 1, 2, 3, 4 };
const std::unordered_set<int> other{ 0, 1, 2, 3, 9 };
return 0
+ is_subset_of(small, empty) // small ⊄ ∅
+ !is_subset_of(empty, small) // ∅ ⊂ small
+ is_subset_of(large, small) // large ⊄ small
+ !is_subset_of(small, large) // small ⊂ large
+ is_subset_of(large, other) // large ⊄ other
+ is_subset_of(other, large) // other ⊄ large
+ !is_subset_of(empty, empty) // ∅ ⊂ ∅
+ !is_subset_of(large, large) // x ⊂ x, ∀x
;
}
一个等价物,使用标准算法而不是编写显式循环:
#include <algorithm>
#include <unordered_set>
template <typename T>
bool is_subset_of(const std::unordered_set<T>& a, const std::unordered_set<T>& b)
{
// return true if all members of a are also in b
auto const is_in_b = [&b](auto const& x){ return b.find(x) != b.end(); };
return a.size() <= b.size() && std::all_of(a.begin(), a.end(), is_in_b);
}
(显然使用相同的 main()
进行测试)
请注意,我们按引用传递集合,而不是按值传递,因为您已经指出集合太大,您无法复制和排序它们。
关于c++ - 检查 unordered_set 是否包含其他 unordered_set 中的所有元素 - C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48299390/