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

Стандартная библиотека C++ предоставляет несколько различных способов сравнения последовательностей. Если ни один из них вам не подходит, посмотрите на их исходный код — он является хорошим примером того, как надо писать собственные эффективные обобщенные алгоритмы.

Рецепт 7.1.

Имеется две отсортированные последовательности и их требуется объединить.

Используйте либо шаблон функции merge, либо шаблон функции inplace_merge. mergeобъединяет две последовательности и помещает результат в третью, a inplace_mergeобъединяет две последовательно расположенные последовательности. Пример 7.5 показывает, как это делается.

Пример 7.5. Объединение двух последовательностей

#include

#include

#include

#include

#include

#include

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

using namespace std;

int main() {

vector v1, v2, v3;

v1.push_back("a");

v1.push_back("c");

v1.push_back("e");

v2.push_back("b");

v2.push_back("d");

v2.push_back("f");

v3.reserve(v1.size() + v2.size() + 1);

// Используйте back_inserter от итератора, чтобы избежать необходимости

// помещать в контейнер набор объектов по умолчанию. Но это не означает,

// что не требуется использовать reserve!

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

back_inserter >(v3));

printContainer(v3);

// Теперь выполняем действия

random_shuffle(v3.begin(), v3.end());

sort(v3.begin(), v3.begin() + v3.size() / 2);

sort(v3.begin() + v3.size() / 2, v3.end());

printContainer(v3);

inplace_merge(v3.begin(), v3.begin() + 3, v3.end());

printContainer(v3);

// Однако если используется два списка, используйте list::merge.

// Как правило, ...

list lstStr1, lstStr2;

lstStr1.push_back("Frank");

lstStr1.push_back("Rizzo");

lstStr1.push_back("Bill");

lstStr1.push_back("Cheetoh");

lstStr2.push_back("Allie");

lstStr2.push_back("McBeal");

lstStr2.push_back("Slick");

lstStr2.push_back("Willie");

lstStr1.sort(); // Отсортировать, иначе объединение выдаст мусор!

lstStr2.sort();

lstStr1.merge(lstStr2); // Заметьте, что это работает только для другого

// списка того же типа

printContainer(lstStr1);

}

Вывод примера 7.5 выглядит так.

-----

a

b

с

d

e

f

-----

b

d

e

a

c

f

-----

a

b

с

d

e

f

Allie

Bill

Cheetoh

Frank

McBeal

Rizzo

Slick

Willie

mergeобъединяет две последовательности и помещает результат в третью — опционально используя функтор сравнения, указанный пользователем и определяющий, когда один элемент меньше другого, а по умолчанию используя operator<. Сложность линейна: число выполняемых mergeсравнений равно сумме длин двух последовательностей минус один. Типы элементов в обеих последовательностях должны быть сравниваемы с помощью operator<(или указанного вами функтора сравнения) и должны быть преобразуемы к типу элементов выходной последовательности при помощи конструктора копирования или присвоения; или должен быть определен оператор преобразования, определенный так, чтобы тип элементов выходной последовательности имел для обоих типов операторы присвоения и конструкторы копирования.

Объявления mergeвыглядят вот так

void merge(In1 first1, In1 last1, In2 first2, In2 last2, Out result);

void merge(In1 first1, In1 last1, In2 first2, In2 last2, Out result,

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.