为什么大多数STL算法都需要排序数据作为输入？

Question

在C++中使用STL算法时，我发现了很多方法，如std::merge、std::inplace_merge、std::set_union、std::upper_bound、std::lower-bound等。只接受已排序的数据作为输入。

这是合理的，在排序的数据，这些算法将提供更快的结果，但他们为什么不能处理未排序的数据也？为什么大多数算法都设计有这样的数据依赖关系呢？

Answer 1

这是合理的，在排序的数据，这些算法将提供更快的结果，但他们为什么不能处理未排序的数据也？为什么大多数算法都设计有这样的数据依赖关系呢？

对于“有意义”对数据进行排序的算法，开发人员应该知道是否会出现这种情况，并且在需要时可以轻松地对输入进行排序。这些标识可以检查数据是否是先排序的，但如果没有必要的话，这会浪费时间。例如，对于预先排序的输入，upper_bound可以是O(logN)，而检查排序则是O(N)。请记住，通常情况下，algos没有地方存储状态，上面写着“我检查过一次，数据被排序了”(如果不了解存在哪些线程、如何使用锁等等，他们怎么知道保存时间)，所以他们必须对数据上的每个调用都这样做。

此外，您提到的一些算法--例如std::merge --可以在InputIterators上使用，这意味着您可以处理只能读取一次的输入，例如在键盘上随时可用，但不会自动保存到任何地方供您重新访问，因此，有一个额外的通行证来检查有人键入的值是否已经排序是不切实际的。

Answer 2

这些算法说：

如果您已经对数据进行了排序，我们将为您执行一些操作，非常有效。

就像您实现的普通二进制搜索函数期望数据被排序一样，这些函数也期望数据被排序。如果没有对数据进行排序，就不要使用它们。

就像您不希望sort为您插入元素一样，您也不应该期望这些算法为您排序项。