Здравствуйте, T4r4sB, Вы писали:

EP>>А у меня тот код который быстрый обычно оперирует обобщёнными абстракциями — это более высокий уровень — because I can. И в таком коде я спокойно могу использовать например ФВП и замыкания, а не расписывать вручную каждую комбинацию алгоритма, контейнера и предиката — because I can.
TB>А как написать сортировку, не расписав вручную для каждого контейнера?

Абстрагировав интерфейс доступа к элементам последовательности в отдельную концепцию, например в итераторы. Один вариант итератора соответствует множеству контейнеров.

TB>Хотя я задавался таким вопросом помню, и таки да, такая сортировка существует, но от оптимальной она далека.

С сортировкой много разных моментов связанно. Выбор оптимальной зависит не только от типа контейнера/элемента.
Например тот же связный список можно отсортировать слияниями через жонглирование связями (никак не перемещая сами элементы), а можно сначала переместить данные в массив, отсортировать интроспективной сортировкой, и переместить обратно. Оптимальный выбор зависит от ситуации, к примеру перелинковка может быть крайне нежелательна, так как может сильно нарушить последовательность узлов в памяти. Тем не менее, оба из этих вариантов сортировок могут быть реализованы обобщённо.

TB>Так что обобщённость тоже имеет свой предел.

Естественно имеет. В подобных случаях кстати отлично работает перегрузка/специализация. Каноничный пример std::advance — для RandomAccess он Θ(1), для остальных Θ(n).