c ++ векторная сортировка
Это общий вопрос о механизме сортировки с использованием функции STL std :: sort. Я читал несколько постов о сортировке и о том, что в общем случае сортировка векторов происходит быстрее, чем сортировка связанных списков. Это правда для векторов и связанных списков структур / объектов? Для связного списка структур, я чувствую, что сортировка может быть легко достигнута, только изменяя индексы. С другой стороны, сортировка векторов выглядит так, как будто она включает физическое переключение местоположений данных структуры / объекта, поскольку они являются смежными (это правда?). В этом случае кажется, что сортировка связанных списков будет быстрее.
РЕДАКТИРОВАТЬ !!!: теперь с картинкой:
Поэтому я думаю, что вопрос лучше сформулировать: что быстрее для сортировки объектов, сортировки связанного списка или вектора (хотя это может зависеть от размера объекта)? Кроме того, выполняется ли сортировка для связанного списка, как показано в 3), и выполняется ли сортировка для вектора, как показано в 2)?
Решение
Вы правы, своего рода std::vector будет медленным, если копирование элемента будет медленным. C ++ 11 представляет семантику перемещения, которая может помочь, элементы можно перемещать, а не копировать.
Связанный список довольно легко сортировать с помощью сортировки слиянием, которая равна O (n log n) так же, как и любой другой хороший алгоритм сортировки. Разница в накладных расходах.
Как всегда, сравнительный анализ вашего конкретного случая — хорошая идея, если результаты важны для вас.
Другие решения
Сортировка list является специализированным (т.е. list имеет функцию сортировки и не может быть отсортирован с std::sort).
void sort();
template <class Compare> void sort(Compare comp);
Сложность: приблизительно N log (N) сравнений, где N == size ().
std::sort в обобщенном виде.
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Сложность: O (N log (N)) (где N == последний — первый) сравнений.
Обратите внимание, что результат std::list::sort такой же как std::stable_sort,
Обратите внимание, что в стандарте нет информации о том, как sort должно быть реализовано. Это определяется реализацией.
Вы всегда можете отсортировать, отсортировав параллельный набор индексов или указателей или что-то еще. Это работает как для списков, так и для векторов.
Причина, по которой сортировка списка происходит медленнее, заключается в том, что для самых быстрых алгоритмов сортировки требуется произвольный доступ, т. Е. Возможность немедленного извлечения значения по заданному индексу. Вы не получите это со списками. Чтобы получить 10-й элемент в связанном списке (скажем), вы должны начать с начала и двигаться вперед 10 раз.