Difference between revisions of "cpp/algorithm/mismatch"

Latest revision as of 01:37, 3 April 2024

Returns a pair of iterators to the first mismatching of elements from [first1, last1) and a range starting from first2:

• For overloads (1-4), the second range has std::distance(first1, last1) elements.
• For overloads (5-8), the second range is [first2, last2).

• If std::distance(first1, last1) and std::distance(first2, last2) are different, the comparison stops when last1 or last2 is reached.

[edit] Parameters

[edit] Return value

std::pair with iterators to the first two non-equal elements.

If last1 is reached, the second iterator in the pair is the std::distance(first1, last1)th iterator after first2.

For overloads (5-8), if last2 is reached, the first iterator in the pair is the std::distance(first2, last2)th iterator after first1.

[edit] Complexity

Given \(\scriptsize N_1\)N1 as std::distance(first1, last1) and \(\scriptsize N_2\)N2 as std::distance(first2, last2):

[edit] Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

[edit] Possible implementation

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);
}

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);
}

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);
}

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);
}

[edit] Example

#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

[edit] See also