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

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

v.push.back('c');

v.push_back('o');

v.push_back('k');

v.push_back('e');

std::cout << std::lexicographical_compare(s.begin, s.end,

 v.begin, v.end) << '\n';

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

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

надо писать собственные эффективные обобщенные алгоритмы.

Смотри также

Рецепт 7.1.

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

Проблема

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

Решение

Используйте либо шаблон функции

merge

, либо шаблон функции

inplace_merge

.

merge

объединяет две последовательности и помещает результат в третью, a

inplace_merge

объединяет две последовательно расположенные последовательности. Пример 7.5 показывает, как это делается.

Пример 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

: