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

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() 假设
序列使用排序
运算符<()，或使用谓词
比较。

跑进

最多 ((完成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}));