检查 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

免责声明：这不是最有效的方法。这是一种在支持无序迭代器范围的同时通用且灵活的解决方案的尝试std::includes。它不限于std::unordered_set并且应该适用于任何其他容器，例如std::vector或std::list。

正如所指出的，std::includes需要对输入范围进行排序。目前标准库不支持无序范围。

查看可以实现std::includes无序范围的版本的可能实现。例如像这样：

template<class InputIt1, class InputIt2>
bool includes_unordered(
    InputIt1 first1, InputIt1 last1,
    InputIt2 first2, InputIt2 last2)
{
    for (; first2 != last2; ++first2)
    {
        InputIt1 it1;
        for (it1 = first1; it1 != last1; ++it1)
        {
            if(*first2 == *it1)
                break;
        }
        if (it1 == last1)
            return false;
    }
    return true;
}

注意：不执行容器的大小比较优化来支持非唯一对象的容器。但如果需要的话可以使用 来完成std::distance。

这是采用等价运算符的版本：

template<class InputIt1, class InputIt2, class Equivalence>
bool includes_unordered(
    InputIt1 first1, InputIt1 last1,
    InputIt2 first2, InputIt2 last2,
    Equivalence equiv)
{
    for (; first2 != last2; ++first2)
    {
        InputIt1 it1;
        for (it1 = first1; it1 != last1; ++it1)
        {
            if(equiv(*first2, *it1))
                break;
        }
        if (it1 == last1)
            return false;
    }
    return true;
}

Small live-example

然后就includes_unordered可以像std::includes以前一样使用了。