std::mismatch

Определено в заголовочном файле `<algorithm>`
template< class InputIt1, class InputIt2 > std::pair<InputIt1, InputIt2> mismatch( InputIt1 first1, InputIt1 last1, InputIt2 first2 );	(1)	(constexpr с C++20)
template< class InputIt1, class InputIt2, class BinaryPred > std::pair<InputIt1, InputIt2> mismatch( InputIt1 first1, InputIt1 last1, InputIt2 first2, BinaryPred p );	(2)	(constexpr с C++20)
template< class InputIt1, class InputIt2 > std::pair<InputIt1, InputIt2> mismatch( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );	(3)	(с C++14) (constexpr с C++20)
template< class InputIt1, class InputIt2, class BinaryPred > std::pair<InputIt1, InputIt2> mismatch( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, BinaryPred p );	(4)	(с C++14) (constexpr с C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > std::pair<ForwardIt1, ForwardIt2> mismatch( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );	(5)	(с C++17)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > std::pair<ForwardIt1, ForwardIt2> mismatch( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, BinaryPred p );	(6)	(с C++17)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > std::pair<ForwardIt1, ForwardIt2> mismatch( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(7)	(с C++17)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > std::pair<ForwardIt1, ForwardIt2> mismatch( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(8)	(с C++17)

Возвращает пару итераторов, указывающих на первую пару несовпадающих элементов в двух целевых диапазонах [first1, last1) и [first2, last2). Для перегрузок без параметра last2 значение last2 равно std::next(first2, std::distance(first1, last1).

1,3) Элементы сравниваются с помощью operator==.

2,4) Элементы сравниваются с помощью заданного бинарного предиката p.

5-8) То же, что и (1-4), но выполнение осуществляется согласно policy.

Эти перегрузки участвуют в разрешении перегрузки, только если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(начиная с C++20)

Параметры

first1, last1	-	пара итераторов, задающих первый целевой диапазон
first2, last2	-	пара итераторов, задающих второй целевой диапазон
p	-	бинарный предикат, возвращающий `true`, если элементы следует считать равными. Сигнатура функции-предиката должна быть эквивалентна следующей: boolpred(constType1&a,constType2&b); Хотя сигнатура не обязана содержать `const &`, функция не должна изменять переданные ей объекты и должна принимать любые значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (поэтому `Type1 &` не допускается, как и `Type1`, если для `Type1` перемещение не эквивалентно копированию(начиная с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объекты типов InputIt1 и InputIt2 можно было разыменовать, а затем неявно преобразовать соответственно в Type1 и Type2.
policy	-	политика выполнения, которую следует использовать
Требования к типам
-`InputIt1` должен соответствовать требованиям LegacyInputIterator.
-`InputIt2` должен соответствовать требованиям LegacyInputIterator.
-`ForwardIt1` должен соответствовать требованиям LegacyForwardIterator.
-`ForwardIt2` должен соответствовать требованиям LegacyForwardIterator.
-`BinaryPred` должен соответствовать требованиям BinaryPredicate.

Возвращаемое значение

Пара итераторов, указывающих на первую пару несовпадающих элементов.

Если достигнут last1, он становится первым итератором в паре. Второй итератор в паре — это std::next(first2, std::distance(first1, last1)).

Если достигнут last2, он становится вторым итератором в паре. Первый итератор в паре — это std::next(first1, std::distance(first2, last2)).

Сложность

Пусть \(\scriptsize N_1\)N₁ — std::distance(first1, last1), а \(\scriptsize N_2\)N₂ — std::distance(first2, last2):

1) Не более \(\scriptsize N_1\)N₁ сравнений с помощью operator==.

2) Не более \(\scriptsize N_1\)N₁ применений p.

3) Не более \(\scriptsize \min(N_1,N_2)\)min(N₁,N₂) сравнений с помощью operator==.

4) Не более \(\scriptsize \min(N_1,N_2)\)min(N₁,N₂) применений p.

5) \(\scriptsize \mathcal{O}(N_1)\)𝓞(N₁) сравнений с помощью operator==.

6) \(\scriptsize \mathcal{O}(N_1)\)𝓞(N₁) применений p.

7) \(\scriptsize \mathcal{O}(\min(N_1,N_2))\)𝓞(min(N₁,N₂)) сравнений с помощью operator==.

8) \(\scriptsize \mathcal{O}(\min(N_1,N_2))\)𝓞(min(N₁,N₂)) применений p.

Исключения

5-8) Во время выполнения:

Если временные ресурсы памяти, необходимые для распараллеливания, недоступны, выбрасывается std::bad_alloc.
Если при обращении к объектам через аргумент алгоритма возникает необработанное исключение, поведение определяется политикой выполнения (для стандартных политик вызывается std::terminate).

Возможная реализация

mismatch (1)
template<class InputIt1, class InputIt2> std::pair<InputIt1, InputIt2> mismatch(InputIt1 first1, InputIt1 last1, InputIt2 first2) { while (first1 != last1 && first1 == first2) ++first1, ++first2; return std::make_pair(first1, first2); }
mismatch (2)
template<class InputIt1, class InputIt2, class BinaryPred> std::pair<InputIt1, InputIt2> mismatch(InputIt1 first1, InputIt1 last1, InputIt2 first2, BinaryPred p) { while (first1 != last1 && p(first1, first2)) ++first1, ++first2; return std::make_pair(first1, first2); }
mismatch (3)
template<class InputIt1, class InputIt2> std::pair<InputIt1, InputIt2> mismatch(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) { while (first1 != last1 && first2 != last2 && first1 == first2) ++first1, ++first2; return std::make_pair(first1, first2); }
mismatch (4)
template<class InputIt1, class InputIt2, class BinaryPred> std::pair<InputIt1, InputIt2> mismatch(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, BinaryPred p) { while (first1 != last1 && first2 != last2 && p(first1, first2)) ++first1, ++first2; return std::make_pair(first1, first2); }

Пример

Эта программа определяет самую длинную подстроку, которая одновременно находится в самом начале заданной строки и в самом её конце в обратном порядке (возможно, с перекрытием).

#include <algorithm>
#include <iostream>
#include <string>

std::string mirror_ends(const std::string& in)
{
    return std::string(in.begin(),
                       std::mismatch(in.begin(), in.end(), in.rbegin()).first);
}

int main()
{
    std::cout << mirror_ends("abXYZba") << '\n'
              << mirror_ends("abca") << '\n'
              << mirror_ends("aba") << '\n';
}

Вывод:

ab
a
aba

См. также

ranges::mismatch (C++20)	находит первую позицию, в которой два диапазона различаются (объект-функция алгоритма)
equal	определяет, совпадают ли два набора элементов (шаблон функции и объект-функция алгоритма)
ranges::equal (C++20)
findfind_iffind_if_not (C++11)	находит первый элемент, удовлетворяющий заданным критериям (шаблон функции и объект-функция алгоритма)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)
lexicographical_compare	лексикографически сравнивает два диапазона (шаблон функции и объект-функция алгоритма)
ranges::lexicographical_compare (C++20)
search	ищет первое вхождение диапазона элементов (шаблон функции и объект-функция алгоритма)
ranges::search (C++20)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/mismatch