是否存在未分类范围的std :: includes等价物？

Question

std::includes被记录为

如果在排序范围 [first1,last1]中找到排序范围 [first2,last2]中的每个元素,则返回true .如果[first2,last2]为空,也返回true.

重点是我的.

是否存在等效的C++算法,可以在容器的未排序范围内重现此功能,或者我是否必须通过循环返回自己实现此功能？

Answer 1

如果首先对范围进行排序,则排序将在O(n log n)时间内运行,搜索将在O(m + n)时间内运行.如果您尝试在未排序的范围内天真地执行此操作,它将在O(m · n)时间内运行.你通常最好只是排序.

但是,您可以search有效地对子字符串进行未排序的范围.这是我能想到的最接近你所要求的东西.

当然，但如果你要搜索单个元素，你可以只使用 `std::find`，如果 *m* 很小，你可以 `std::find` 每个元素并在一个元素不存在时立即中断'找到了。所以这就是你如何在 O(*mn*) 时间内使用 STL 在未排序的范围内完成它，如果这优于 O(*n* log *n*)。（由于引用的局部性，它在实际使用中可能不那么有效。） (2认同)