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

 cout << "first mismatch = " << *(iters.first) << endl;
 cout << "second mismatch = " << *(iters.second) << endl;
}

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

Два диапазона НЕ равны!
false
true
false
false
true
first mismatch = e
second mismatch = f

Обсуждение

Для сравнения двух последовательностей на равенство используйте equal. Он принимает три или четыре аргумента, в зависимости от используемой версии. Вот как объявлен equal.

bool equal(In1 first1, In1 last1, In2 first2);
bool equal(In1 first1, In1 last1, In2 first2, BinPred pred);

equal с помощью operator== сравнивает каждый элемент между first1 и last1 с элементами, начиная с first2. Если указать pred, то equal для проверки будет использовать его. Перед вызовом equal убедитесь, что каждая последовательность имеет одинаковую длину. Он предполагает, что второй диапазон не меньше первого, и если это не так, то его поведение не определено.

Если требуется узнать, где и как последовательности отличаются, используйте lexicographical_compare или mismatch. lexicographical_compare сравнивает две последовательности и возвращает истину, если первая лексикографически меньше второй, что означает, что каждая пара элементов в двух последовательностях сравнивается с помощью оператора <. Объявление lexicographical_compare выглядит вот так.

bool lexicographical_compare(In1 first1, In1 last1,
 In2 first2, In2 last2);
bool lexicographical_compare(In1 first1, In1 last1,
 In2 first2, In2 last2, Compare comp);

Если operator< возвращает истину или первая последовательность заканчивается раньше второй, то возвращается истина. В противном случае возвращается ложь. Рассмотрим последовательность символов из примера 7.4.

string s1 = "abcde";
string s2 = "abcdf";
string s3 = "abc";
lexicographical_compare(s1.begin, s1.end, // abcde < abcde
 s1.begin, s1.end); // = false
lexicographical_compare(s1.begin, s1.end, // abcde < abcdf
 s2.begin(s2.end); // = true
lexicographical_compare(s2.begin, s2.end, // abcdf < abcde
 s1.begin, s1.end); // = false
lexicographical_compare(s1.begin, s1.end, // abcde < abc
 s3.begin(s3.end); // = false
lexicographical_compare(s3.begin, s3.end, // abc < abcde
 s1.begin, s1.end); // = true

Сложность lexicographical_compare линейна и выполняет число сравнений, равное длине меньшей из двух последовательностей, или до тех пор, пока один из элементов в одной из последовательностей не окажется меньше соответствующего элемента другой. Сравнения реализованы полностью на основе operator<, так что если iter1 и iter2 — это итераторы двух последовательностей, то сравнение останавливается тогда, когда *iter1 < *iter2 или *iter2 < *iter1.

mismatch говорит, где две последовательности различаются. Однако его объявление несколько отличается от equal и lexicographical_compare, так как он возвращает не bool, a pair<> итераторов. Вот оно.

pair<In1, In2> mismatch(In1 first1, In1 last1, In2 first2);
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) << '\n'; // 'e'
cout << "second mismatch = " << *(iters.second) << '\n'; // '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) << '\n';

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

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

Смотри также

Рецепт 7.1.

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

Проблема

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

Решение

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