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

pair<In1, In2> mismatch(In1 first1, In1 last1, In2 first2, BinPred);

Два возвращаемых итератора указывают на различные элементы каждой из последовательностей. Рассмотрим пример 7.4.

string s1 = 'abcde';
string s2 = 'abcdf';
pair<string::iterator, string::iterator> iters =
 mismatch(s1.begin(), s1.end(), s2.begin());
cout << 'first mismatch = ' << *(iters.first) << '
'; // 'e'
cout << 'second mismatch = ' << *(iters.second) << '
'; // 'f'

Вы должны убедиться, что длина второго диапазона не меньше первого. Если вторая последовательность короче первой, mismatch не сможет узнать этого и продолжит выполнение сравнения элементов за границей второй последовательности, что приведет к непредсказуемому поведению. Кроме того, если несовпадений нет, то первый итератор будет указывать на last1, который может оказаться недействительным (например, если в качестве last1 передать end().

Вы, должно быть, заметили по объявлениям каждой из этих функций, что типы итераторов для каждой из этих последовательностей различны. Это означает, что две последовательности могут быть контейнерами разных типов, но при условии, что типы элементов, на которые указывают итераторы, имеют определенный для них operator<. Например, можно сравнивать string и vector<char>.

string s = 'Coke';
vector<char> v;
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()) << '
';

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

Стандартная библиотека 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 выглядит так.

-----