Почему std:: sort и partial_sort требуют итераторов с произвольным доступом?

Мне было интересно, почему стандарт С++ требует, чтобы std::sort должен использовать только итераторы с произвольным доступом? Я не вижу преимущества, поскольку std:: sort и std:: list:: sort имеют сложность N*log(N). Ограничение std::sort для итераторов с произвольным доступом (RAI), по-видимому, потребовало записи отдельной функции для списков с одинаковой сложностью.

То же самое относится к partial_sort, где счетчик-не-RAI для списка просто отсутствует по сей день.

Эта конструкция, потому что люди использовали варианты quick_sort для реализации std::sort исторически?

Если есть преимущества для написания алгоритмов сортировки на контейнерах RAI, лучше ли сделать std::sort более общим, и пусть контейнеры RAI, такие как std::vector, предоставляют специализированные v.sort?

Ответ 1

O(N*log(N)) Сложность не означает, что контейнер итерируется по порядку, или что изменения в нем сделаны только в порядке сканирования. Для использования последовательных итераторов приходилось бы на O(N) стоимость памяти для хранения всех этих итераторов.

Ответ 2

Сложность алгоритма не говорит все. Фактически в С++ (с формальной точки зрения) он ничего не говорит, потому что вы не можете расти N до бесконечности (size_t не является произвольным числом точности), поэтому каждый алгоритм сортировки, написанный на С++ (формально) также O(1).

С практической точки зрения std::sort является внуком qsort, и он реализован, скорее всего, как вариация quicksort.

Использование сортировки слияния для массивов потребует дополнительного хранилища, пропорционального размеру массива (ссылка на следующий элемент), в то время как сортировка слияния для списков не требует дополнительного пространства, потому что вы можете повторно использовать ссылку, уже присутствующую в node (что он будет уничтожен путем сортировки в любом случае).

Идея программирования, не зная, в каком контейнере вы имеете дело, в основном представляет собой иллюзию, поэтому, имея два разных явных способа эффективного сортировки двух разных типов контейнеров, само по себе не считается плохим.

Это действительно раздражает, что std::sort не содержит специализации также для итераторов списков (я не шаблонный метапрограммирующий гуру, но это было бы довольно просто).