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

Question

目前，我认为我最好的选择是使用std::set_intersection，然后检查较小输入的大小是否与set_intersection填充的元素数相同。

有更好的解决方案吗？

Answer 1

试试这个：

if (std::includes(set_one.begin(), set_one.end(),
                  set_two.begin(), set_two.end()))
{
// ...
}

关于包括（）。

includes() 算法比较两个排序的序列，如果范围 [start2, finish2) 中的每个元素都包含在范围 [start1, finish1) 中，则返回 true。否则返回 false。includes() 假定使用 operator<() 或使用谓词 comp 对序列进行排序。

跑进去

最多执行 ((finish1 - start1) + (finish2 - start2)) * 2 - 1 次比较。

加上 O(nlog(n)) 用于对向量进行排序。你不会比这更快得到它。