Краткий ответ

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

Исторический контекст

Итераторы в STL отделяют алгоритм от конкретного контейнера. Благодаря этому один алгоритм может работать с vector, deque или другими совместимыми структурами, если они предоставляют необходимый набор операций.

Такое разделение потребовало формально описать возможности итераторов: одно направление движения, двунаправленное движение, произвольный доступ и другие свойства. Алгоритм получает возможность выразить требования к обходу диапазона, не зная внутреннее устройство контейнера.

Постановка проблемы

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

Попытка использовать такой итератор без учёта его возможностей приводит либо к ошибке компиляции, либо к алгоритму с другой сложностью. Нельзя считать, что наличие операторов увеличения и уменьшения автоматически означает возможность эффективного произвольного доступа.

Подробное решение

В стандартной модели итератор произвольного доступа поддерживает арифметику смещений, вычисление расстояния между итераторами и сравнение их порядка. Эти операции имеют константную сложность для подходящих контейнеров.

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

Это не означает, что сортировка двунаправленного диапазона невозможна вообще. Можно применить другой алгоритм, например сортировку слиянием, или использовать специализированный метод контейнера. Однако такой алгоритм будет иметь другую реализацию, а иногда — другие свойства стабильности, использования памяти и перемещения элементов.

Важное различие: произвольный доступ не равен непрерывному хранению. Итераторы deque поддерживают произвольный доступ, хотя элементы deque не обязаны находиться в одном непрерывном блоке памяти. Поэтому deque может использоваться со std::sort, а list — нет.

#include <algorithm>
#include <deque>
#include <list>
#include <vector>

int main() {
    std::vector<int> v{3, 1, 2};
    std::deque<int> d{3, 1, 2};
    std::list<int> l{3, 1, 2};
    std::sort(v.begin(), v.end());
    std::sort(d.begin(), d.end());
    l.sort();
}

Для vector и deque вызов использует общий алгоритм std::sort. Для list применяется метод контейнера, поскольку его итераторы двунаправленные, а не произвольного доступа.

Ситуация из практики

В системе хранился большой список объектов с частыми сортировками по разным полям. Рассматривались два варианта: оставить std::list и вызывать его sort либо переносить указатели на объекты в std::vector и сортировать вектор.

Сортировка списка сохраняла стабильные адреса узлов и не требовала копирования самих объектов, но страдала от переходов по связанным узлам и плохой локальности кэша. Вектор указателей обеспечивал произвольный доступ, лучшую локальность массива указателей и совместимость с большим числом алгоритмов, однако требовал отдельного управления индексом и косвенного доступа к объектам.

Был выбран вектор указателей, потому что сортировки выполнялись часто, а стабильность адресов объектов сохранялась за счёт сортировки указателей, а не самих объектов. Если бы главной операцией было удаление элементов из середины по уже известному узлу, преимущество могло бы остаться у list.

Что кандидаты часто упускают

Можно ли адаптером превратить двунаправленный итератор в итератор произвольного доступа?

Формально можно написать тип, предоставляющий нужные операторы, но это не создаст быстрый произвольный доступ. Если операция перехода на произвольное смещение внутри адаптера выполняет последовательный проход, нарушается требуемая сложность и смысл категории итератора. Такой адаптер будет некорректным решением для алгоритмов, рассчитывающих на константное время доступа.

Почему deque подходит для std::sort, хотя его элементы не обязаны быть непрерывными в памяти?

Требование std::sort относится к операциям итератора, а не к физической непрерывности хранения. Итератор deque умеет за константное время вычислять позицию со смещением и расстояние между позициями, хотя внутри контейнер может использовать несколько блоков памяти. Непрерывное хранение требуется алгоритмам или операциям, которым нужна именно категория contiguous_iterator, а не random_access_iterator.

Почему std::list::sort не является просто менее эффективным вызовом std::sort?

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

Оба подхода имеют сложность порядка O(N log N) по числу сравнений, но реальное время зависит от размера объектов, локальности памяти, стоимости перемещений и требований к памяти. Поэтому выбор определяется не только асимптотикой, но и структурой данных и характером операций.