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

Используйте член-контейнера std::list::sort(). Он предназначен для сортировки связного списка, работает с его двунаправленными итераторами и сохраняет стабильность сортировки; std::sort для std::list неприменим, поскольку требует итераторы произвольного доступа.

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

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

У std::list элементы связаны узлами, поэтому эффективный способ перестановки — менять связи между узлами, а не перемещать сами объекты. Для этого контейнер предоставляет собственный алгоритм сортировки.

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

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

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

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

Вызов std::list::sort() сортирует элементы непосредственно внутри списка. Он не требует итераторов произвольного доступа, сохраняет относительный порядок эквивалентных элементов и не инвалидирует итераторы и ссылки на элементы.

#include <list>
#include <string>

struct Record {
    int priority;
    std::string name;
};

int main() {
    std::list<Record> records{{2, "b"}, {1, "a"}, {2, "c"}};
    records.sort([](const Record& x, const Record& y) {
        return x.priority < y.priority;
    });
}

Сложность сортировки списка — O(n log n) сравнений. Важное практическое преимущество — объекты не требуется перемещать между позициями как элементы вектора; меняется порядок узлов. Это особенно полезно для тяжёлых или невмещаемых типов и для кода, который должен сохранить действительность ссылок и итераторов.

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

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

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

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

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

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

Сохраняет ли list::sort итераторы и ссылки на элементы?

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

Почему нельзя заменить list::sort на std::stable_sort?

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

Всегда ли std::list::sort быстрее сортировки std::vector?

Нет. У list::sort есть преимущество в перестановке узлов и сохранении ссылок, но каждый переход между узлами может приводить к промахам кэша, а узлы содержат дополнительные указатели. Для компактных перемещаемых объектов std::vector часто быстрее при сортировке и последующем последовательном обходе.