Файл заголовка mismatch.hpp содержит два варианта алгоритма stl.<mismatch>. Алгоритм находит первую точку в двух последовательностях, где они не совпадают.

До (предложенного) C++14 алгоритм<std::mismatch>взяли три итератора и необязательный сравнительный предикат. Первые два итератора<[first1,last1)>определили последовательность, а второй<first2>определил начало второй последовательности. Предполагается, что вторая последовательность имеет ту же длину, что и первая.

В C++14 были введены два новых варианта, берущие четыре итератора и необязательный сравнительный предикат. Четыре итератора определяют две последовательности<[first1,last1)>и<[first2,last2)>явно, а не определяют вторую неявно. Это приводит к правильным ответам в большем количестве случаев (и избегать неопределенного поведения в других).

Рассмотрим две последовательности:

auto seq1 = { 0, 1, 2 };
auto seq2 = { 0, 1, 2, 3, 4 };
std::mismatch ( seq1.begin (), seq1.end (), seq2.begin ()); // <3, 3>
std::mismatch ( seq2.begin (), seq2.end (), seq1.begin ()); // Undefined behavior
std::mismatch ( seq1.begin (), seq1.end (), seq2.begin (), seq2.end ()); // <3, 3>

Первые N в<seq2>те же, что и в<seq1>, но это не все, что в<seq2>. Во втором случае алгоритм будет читать дальше конца<seq1>, что приведет к неопределенному поведению (большое землетрясение, неправильные результаты, беременная кошка и т. д.).

Однако, если две последовательности указаны полностью, ясно, что где происходит несоответствие.

interface

Функция<mismatch>возвращает пару итераторов, которые обозначают первые несоответствующие элементы в каждой последовательности. Если последовательности совпадают полностью,<mismatch>возвращает их конечные итераторы. Одна версия использует<std::equal_to>для сравнения; другая позволяет абоненту передать предикат для сравнения.

template <class InputIterator1, class InputIterator2>
std::pair<InputIterator1, InputIterator2>
mismatch ( InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2 );
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
std::pair<InputIterator1, InputIterator2>
mismatch ( InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred );

Examples

<c1>, содержащее<{0,1, 2,3,14,15}>, и<c2>содержащее<{1, 2,3}>, то

mismatch ( c1.begin(),     c1.end(),       c2.begin(), c2.end()) --> <c1.begin(), c2.begin()> // first elements do not match
mismatch ( c1.begin() + 1, c1.begin() + 4, c2.begin(), c2.end()) --> <c1.begin() + 4, c2.end ()> // all elements of `c2` match
mismatch ( c1.end(),       c1.end(),       c2.end(),   c2.end()) --> <c1.end(), c2.end()> // empty sequences don't match at the end.

Iterator Requirements

<mismatch>работает на всех итераторах, кроме выходных итераторов.

Complexity

Оба варианта<mismatch>работают вO(N)(линейное) время; то есть они сравниваются с каждым элементом в списке один раз. Если последовательность не будет найдена равной в какой-либо точке, рутина прекратится немедленно, без изучения остальных элементов.

Exception Safety

Оба варианта<mismatch>берут свои параметры по стоимости и не зависят ни от какого глобального государства. Таким образом, все процедуры в этом файле обеспечивают сильную гарантию исключения.

Notes