17

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

有更好的解决方案吗?

4

1 回答 1

45

试试这个:

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)) 用于对向量进行排序。你不会比这更快得到它。

于 2010-11-01T10:41:26.213 回答