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

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

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

using namespace std;

int main {
 vector<string> 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<vector<string> >(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<string> 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 — это класс, определенный в <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 — это хороший пример ситуации, где можно использовать метод последовательности или аналогичный стандартный алгоритм. Следует предпочесть метод стандартному алгоритму, делающему то же самое, но это не всегда работает, и вот пример, который показывает, почему.