为什么大多数STL算法都需要排序后的数据作为输入？
Why sorted data as input is required for most of STL algorithms?
在C++中使用STL算法时，我发现了很多方法，如std::merge、std::inplace_merge、std::set_union、std::upper_bound、std::lower-bound等。 . 仅将排序后的数据作为输入。
这些算法在排序数据上会给出更快的结果是有道理的，但为什么它们不能处理未排序的数据呢？为什么大多数算法的设计都具有这样的数据依赖性？
It makes sense that, on sorted data these algorithms will give faster results, but why can't they handle unsorted data too ? Why most of the algorithms are designed with data dependencies like these ?.
对于 "It makes sense" 对数据进行排序的算法，开发人员应该知道是否会出现这种情况，并且可以在需要时轻松对输入进行排序。算法可以检查数据是否首先自行排序，但在不必要时会浪费时间。例如，upper_bound 在预排序输入上的复杂度为 O(logN)，而检查排序的复杂度为 O(N)。还要记住，一般来说，算法无处可存储状态 "I checked once and the data was sorted"（如果不了解存在哪些线程，它们如何使用，他们怎么知道会持续多久锁等），所以他们必须对数据进行每次调用。
此外，您提到的一些算法 - 例如std::merge - can be used on InputIterators，这意味着您可以处理只能读取一次的输入，例如来自键盘的输入，它暂时可用但不会自动保留在任何地方供您重新访问，因此有一个额外的通道来检查值是否有人输入已经排序是不切实际的。
这些算法说：
If you have sorted data, we'll perform some actions for you, quite efficiently.
就像您要实现的普通二分查找函数希望对数据进行排序一样，这些函数确实希望对数据进行排序。如果您没有对数据进行排序，请不要使用它们。
就像您不期望 sort 为您插入元素一样，您也不应期望这些算法为您排序。
在C++中使用STL算法时，我发现了很多方法，如std::merge、std::inplace_merge、std::set_union、std::upper_bound、std::lower-bound等。 . 仅将排序后的数据作为输入。
这些算法在排序数据上会给出更快的结果是有道理的，但为什么它们不能处理未排序的数据呢？为什么大多数算法的设计都具有这样的数据依赖性？
It makes sense that, on sorted data these algorithms will give faster results, but why can't they handle unsorted data too ? Why most of the algorithms are designed with data dependencies like these ?.
对于 "It makes sense" 对数据进行排序的算法，开发人员应该知道是否会出现这种情况，并且可以在需要时轻松对输入进行排序。算法可以检查数据是否首先自行排序，但在不必要时会浪费时间。例如，upper_bound 在预排序输入上的复杂度为 O(logN)，而检查排序的复杂度为 O(N)。还要记住，一般来说，算法无处可存储状态 "I checked once and the data was sorted"（如果不了解存在哪些线程，它们如何使用，他们怎么知道会持续多久锁等），所以他们必须对数据进行每次调用。
此外，您提到的一些算法 - 例如std::merge - can be used on InputIterators，这意味着您可以处理只能读取一次的输入，例如来自键盘的输入，它暂时可用但不会自动保留在任何地方供您重新访问，因此有一个额外的通道来检查值是否有人输入已经排序是不切实际的。
这些算法说：
If you have sorted data, we'll perform some actions for you, quite efficiently.
就像您要实现的普通二分查找函数希望对数据进行排序一样，这些函数确实希望对数据进行排序。如果您没有对数据进行排序，请不要使用它们。
就像您不期望 sort 为您插入元素一样，您也不应期望这些算法为您排序。