Д. Стефенс - C++. Сборник рецептов

BinPred comp)

Использование mergeдовольно просто. Обе последовательности должны быть отсортированы (иначе вывод будет представлять собой мусор), и ни одна из них при использовании mergeне изменяется. Итератор вывода, в который помещаются результаты, должен иметь достаточно места для помещения в него числа элементов, равного сумме длин входных последовательностей. Этого можно добиться, явно зарезервировав достаточно места либо, как это сделано в примере 7.5, использовав back_inserter:

merge(v1.begin(), v1.end(), v2.begin(), v2.end(),

back_inserter(v3));

back_inserter— это класс, определенный в , который предоставляет удобный способ создания выходного итератора, который каждый раз, когда ему присваивается значение, вызывает для последовательности метод push_back. Таким образом, вам не требуется явно изменять размер выходной последовательности. Следующий вызов создает back_inserterдля vectorс именем v3.

back_inserter(v3);

Указывать аргументы шаблона не требуется, так как back_inserter— это шаблон функции, а не класса, так что тип аргументов, с которыми он вызван, определяется автоматически. Эквивалентный вызов с явным указанием аргументов шаблона выглядит вот так.

back_inserter >(v3);

Однако заметьте, что иногда вам потребуется явно указывать размер выходной последовательности, особенно при использовании в качестве такой последовательности vector, vectorпри добавлении в него элементов с помощью push_backможет потребовать изменений своего размера, а это очень дорогостоящая операция. За подробностями обратитесь к рецепту 6.2.

Если в последовательностях есть два одинаковых элемента, то элемент из первой последовательности будет предшествовать элементу из второй. Следовательно, если дважды вызвать merge, поменяв для второго вызова последовательности местами, результирующие выходные последовательности будут различаться (предсказуемо и правильно, но различаться).

Объединение двух list— это хороший пример ситуации, где можно использовать метод последовательности или аналогичный стандартный алгоритм. Следует предпочесть метод стандартному алгоритму, делающему то же самое, но это не всегда работает, и вот пример, который показывает, почему.

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

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

lstStr2.sort(),

lstStr1.merge(lstStr2); // Это list::merge

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

void merge(list& lst);

template

void merge(list& 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.

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

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

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

#include

#include

#include

#include

#include

#include

#include

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

int main() {

cout << "Введите набор строк: ";

istream_iterator start(cin);

istream_iterator end; // Здесь создается "маркер"

vector 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 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, имеющей несколько опций.