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

Когсуэлл Джефф

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

 back_inserter(v3));

back_inserter

— это класс, определенный в

<iterator>

, который предоставляет удобный способ создания выходного итератора, который каждый раз, когда ему присваивается значение, вызывает для последовательности метод

push_back

. Таким образом, вам не требуется явно изменять размер выходной последовательности. Следующий вызов создает

back_inserter

для

vector<string>

с именем

v3

.

back_inserter(v3);

Указывать

аргументы шаблона не требуется, так как

back_inserter

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

back_inserter<vector<string> >(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<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);