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

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

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

Смотри также

Рецепт 7.1.

7.5. Объединение данных

Проблема

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

Решение

Используйте либо шаблон функции 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)