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

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))用于排序向量.你不会比这更快.

最糟糕的情况是相同的,但如果结果为假,则包含将更快地完成它的工作.而且你还在交集中使用了一个矢量.正如名称所示,set_intersection应该用于查找该交集,并包括用于检查一个集合是否是另一个集合的子集. (3认同)
如果您的数据在`std :: set`中,您可以使用`std :: set_difference` (2认同)