Как написать общую функцию сортировки в C++?

Question

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

Answer 1

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

Вы можете использовать operator< для сравнения любых элементов или функции Compare.

Вы можете разрешить свой список в качестве ввода и вернуть отсортированный список в качестве вывода.

Сложность упадет до O(n^2) со вставкой сортировки, но это самый простой способ ИМО. И я не думаю, что вы можете сделать лучше с помощью контейнера с произвольным доступом. Возможно, сортировка merge может быть реализована для списка. Похоже, хороший кандидат.

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

Answer 2

Есть несколько измерений к тому, что вы могли бы означать, общее:

1. родовое по отношению к данным
2. родовое по отношению к контейнеру

Первый самый простой для решения , Нам нужно подумать о том, какая сортировка требует работы: strict weak ordering наших данных. Теперь мы знаем природу функции, которую нам нужно предоставить нашему алгоритму сортировки, и нам нужен способ передать функцию. В C++ стало нормой считать, что operator< реализует такой порядок или передает Functor алгоритму, который его реализует. Таким образом, подпись стала бы:

template<typename T, typename Comp = std::less<T>> 
my_sort(my_list<T>& l, Comp c = Comp()); 

Существует еще одна операция, которую наш алгоритм сортировки обязательно выполнит: замена элементов. Поскольку мы находимся в нашем собственном маленьком мире, мы можем просто предположить, что все наши типы имеют функцию-член T::swap(T& rhs), которая выполняет именно это. В реальном мире мы будем использовать свободную функцию std::swap (с неквалифицированным вызовом и директивой по использованию, но это неясная техничность).

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