如何在c ++中检查向量是否是另一个向量的子集

Question

我试图找到一种简单的方法来检查向量是否是另一个的子集而不排序向量中的元素的顺序.两个向量都包含随机数元素.

std::includes似乎只适用于排序范围.我怎么能做到这一点？

Answer 1

复制向量.对副本进行排序.然后std::includes在副本上使用.

template <typename T>
bool IsSubset(std::vector<T> A, std::vector<T> B)
{
    std::sort(A.begin(), A.end());
    std::sort(B.begin(), B.end());
    return std::includes(A.begin(), A.end(), B.begin(), B.end());
}

Answer 2

我的回答是假设当你说"子集"时,你真的在​​寻找相当于"子串"的东西; 也就是说,在搜索过程中维护元素的顺序.

最终,我无法看到你如何能够做到这一点O(n*m).鉴于此,您可以简单地自己动手:

template <typename T1, typename T2>
bool contains(std::vector<T1> const& a, std::vector<T2> const& b) {
   for (typename std::vector<T1>::const_iterator i = a.begin(), y = a.end(); i != y; ++i) {
      bool match = true;

      typename std::vector<T1>::const_iterator ii = i;
      for (typename std::vector<T2>::const_iterator j = b.begin(), z = b.end(); j != z; ++j) {
          if (ii == a.end() || *j != *ii) {
              match = false;
              break;
          }
          ii++;
      }

      if (match)
         return true;
   }

   return false;
}

现场演示.

(你可能会对模板参数更有创意.)