c++ - 检查 unordered_set 是否包含其他 unordered_set 中的所有元素 - C++

Question

我是 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;
}

Answer 1

对于未排序的集合，没有比迭代较小的集契约(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() 进行测试)

---

请注意，我们按引用传递集合，而不是按值传递，因为您已经指出集合太大，您无法复制和排序它们。