c – 为什么大多数STL算法需要将数据排序为输入？

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 ?.

对于排序数据的“有意义”的算法,开发人员应该知道是否是这种情况,并且可以根据需要轻松地对输入进行排序.算法可以检查数据是否先排序,但这会浪费时间.例如,upper_bound在预先排序的输入上可以是O(logN),而检查排序则是O(N).还要记住,一般情况下,算法无处可存储状态,说“我检查了一次并且数据已经排序”(他们怎么能知道在不了解线程存在的情况下会持续多长时间,如何使用锁等),所以他们必须为每次调用数据做这件事.

此外,您提到的一些算法 – 例如std::merge – 可以在InputIterators上使用,这意味着您可以处理只能读取一次的输入,例如从键盘中暂时可用但不会自动保留在任何地方以供您重新访问,因此需要额外的通行证来检查是否某人打字已经排序的值是不切实际的.