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

Question

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

有更好的解决办法吗？

Answer 1

试试这个：

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

关于 includes().

includes() 算法比较两个 排序序列并返回 true if [start2, finish2) 包含在范围内 [开始1，结束1)。它返回错误 否则。 include() 假设 序列使用排序 操作员<(), or using the predicate comp.

跑入

最多 ((完成1 - 开始1) + (完成2 - start2)) * 执行 2 - 1 次比较。

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

Answer 2

如果您使用的是 c++-20 或更高版本，则可以使用

std::ranges::includes

执行相同操作。

assert(ranges::includes(vector<int>{2, 4, 6, 8, 10}, vector<int>{4}));
assert(ranges::includes(vector<int>{2, 4, 6, 8, 10}, vector<int>{4, 6}));