Имеет смысл, что при сортировке данных эти алгоритмы будут давать более быстрые результаты, но почему они не могут обрабатывать и несортированные данные? Почему большинство алгоритмов разработаны с такими зависимостями данных?.
Для алгоритмов, в которых «имеет смысл» сортировать данные, разработчик должен знать, будет ли это так или нет, и может легко сортировать входные данные, если это необходимо. Алгоны могли проверить, сначала ли сортируются данные, но это будет тратить время, когда это не нужно. Например, upper_bound
может быть O (logN) на предварительно отсортированном входе, тогда как проверка сортировки будет O (N). Имейте в виду также, что в целом у algos негде хранить статус: «Я проверил один раз, и данные были отсортированы» (и как они могли знать, как долго это пройдет, не понимая, какие потоки существуют, как они используют блокировки и т. Д.), , поэтому они должны были бы сделать это для каждого звонка по данным.
Кроме того, некоторые из указанных вами алгоритмов - например, std::merge
- может использоваться на InputIterators, что означает, что вы можете обрабатывать ввод, который может быть прочитан только один раз, например, с клавиатуры, где он мгновенно предоставляется, но не сохраняется автоматически, где бы вы ни пересматривали, поэтому, имея дополнительный проход, чтобы проверить, значения someones typing уже отсортированы непрактично.
Это потому, что это потребует проверки сортировки последовательности и изменения сложности алгоритмов, таких как 'std :: lower_bound', от O (log n) до O (n). Также нет ничего, что мешало бы вам сортировать заранее, если вы не уверены. – milleniumbug
Это очень распространенные алгоритмы, которые не должны тратить время на проверку, если данные будут отсортированы до продолжения. Вы всегда можете сделать функцию обертки, которая предварительно сортирует данные перед вызовом алгоритма. Я полагаю, вы могли бы иметь отладочную версию алгоритмов, которая генерирует исключение, если данные не отсортированы заранее. – Galik