C++. Сборник рецептов

Рассмотрим список строк из примера 7.5:

lstStr1.sort; // Сортируем, или объединение даст мусор!
lstStr2.sort,
 lstStr1.merge(lstStr2); // Это list::merge

Есть две причины, по которым этот код отличается от вызова std::merge. Во-первых, оба списка list должны иметь один и тот же тип элементов. Это требование следует из объявления list::merge, которое имеет вид:

void merge(list<T, Alloc>& lst);
template <typename Compare>
void merge(list<T, Alloc>& lst, Compare comp)

Где T — это такой же тип, как и в самом шаблоне класса списка. Так что, например, невозможно объединить список из символьных массивов с завершающим нулем со списком из строк типа string.

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

Также объединить две непрерывные последовательности можно с помощью inplace_merge. inplace_merge отличается от merge, так как он объединяет две последовательности «на месте». Другими словами, если есть две непрерывные последовательности (т.е. они являются частями одной и той же последовательности) и они отсортированы и требуется отсортировать общую последовательность, то вместо алгоритма сортировки можно использовать inplace_merge. Преимущество inplace_merge заключается в том, что при наличии достаточного объема памяти его работа занимает линейное количество времени. Если же памяти недостаточно, то он занимает n log n, что равно средней сложности сортировки.

Объявление inplace_merge несколько отличается от merge:

void inplace_merge(Bid first, Bid mid, Bid last);
void inplace_merge(Bid first, Bid mid, Bid last, BinPred comp)

inplace_merge требует двунаправленных итераторов, так что он не является взаимозаменяемым с merge, но в большинстве случаев должен работать. Как и merge, для определения относительного порядка элементов он по умолчанию использует operator<, а при наличии — comp.

7.6. Сортировка диапазона

Проблема

Имеется диапазон элементов, которые требуется отсортировать.

Решение

Для сортировки диапазонов имеется целый набор алгоритмов. Можно выполнить обычную сортировку (в восходящем или нисходящем порядке) с помощью sort, определенного в <algorithm>, а можно использовать одну из других функций сортировки, таких как partial_sort. Посмотрите на пример 7.6, показывающий как это сделать

Пример 7.6. Сортировка

#include <iostream>
#include <istream>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <iterator>
#include "utils.h" // Для printContainer: см. 7.10

using namespace std;

int main {
 cout << "Введите набор строк: ";
 istream_iterator<string> start(cin);
 istream_iterator<string> end; // Здесь создается "маркер"
 vector<string> v(start, end);
 // Стандартный алгоритм sort сортирует элементы диапазона. Он
 // требует итератор произвольного доступа, так что он работает для vector.
 sort(v.begin, v.end);
 printContainer(v);
 random_shuffle(v.begin, v.end); // См. 7.2
 string* arr = new string[v.size];
 // Копируем элементы в массив
 copy(v.begin, v.end, &arr[0]);
 // Сортировка работает для любого типа диапазонов, но при условии, что
 // ее аргументы ведут себя как итераторы произвольного доступа.
 sort(&arr[0], &arr[v.size]);
 printRange(&arr[0], &arr[v.size]);
 // Создаем список с такими же элементами
 list<string> lst(v.begin, v.end);
 lst.sort; // Самостоятельная версия sort работать не будет, здесь требуется
 // использовать list::sort. Заметьте, что невозможно отсортировать
 // только часть списка.
 printContainer(lst);
}

Запуск примера 7.6 может выглядеть вот так.

Введите набор строк: a z b y c x d w
^Z
– ----
a b c d w x y z
– ----
w b y c a x z d
– ----
a b c d w x y z
– ----
a b c d w x y z

Обсуждение

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

Стандартный алгоритм sort делает именно то, что от него ожидается: он сортирует элементы диапазона в восходящем порядке с помощью operator<. Он объявлен вот так.

void sort(Rnd first, Rnd last);
void sort(Rnd first, Rnd last, BinPred comp);

Как и в большинстве других алгоритмов, если operator< не удовлетворяет вашим требованиям, можно указать собственный оператор сравнения. В среднем случае сложность имеет зависимость n log n. В худшем случае она может быть квадратичной.