This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Resolved status.

### 3178. `std::mismatch` is missing an upper bound

Section: 25.6.10 [mismatch] Status: Resolved Submitter: Geoffrey Romer Opened: 2018-12-20 Last modified: 2020-05-02

Priority: 0

View all other issues in [mismatch].

View all issues with Resolved status.

Discussion:

Consider the following code:

>     std::vector<int> v1 = {1, 2, 3, 4};
>     std::vector<int> v2 = {1, 2, 3, 5};
>     auto result = std::mismatch(v1.begin(), v1.begin() + 2, v2.begin(), v2.begin() + 2);

The current wording of [mismatch] seems to require `result` to be `{v1.begin() + 3, v2.begin() + 3}`, because 3 is the smallest integer `n` such that `*(v1.begin() + n) != *(v2.begin + n)`. In other words, if there's a mismatch that's reachable from `first1` and `first2`, then `std::mismatch` must find and return it, even if it's beyond the end iterators passed by the user.

This is doubly unimplementable: the library has no way of knowing that it's safe to keep going past the end of the user-supplied range, and even if it could, doing so would violate the complexity requirements. More importantly, it would violate the fundamental convention that STL algorithms operate on user-supplied ranges, not on the underlying containers.

[2019-01-26 Priority to 0 and Status to Tentatively Ready after discussions on the reflector]

During that reflector discussion several contributers argued in favour for changing the current wording in 25.6.10 [mismatch] p3 from "smallest integer" to "smallest nonnegative integer". This minor wording delta has also been added to the original proposed wording.

Previous resolution [SUPERSEDED]:

> This wording is relative to N4791.

> 1. Change 25.6.10 [mismatch] as indicated:

>    >     template<class InputIterator1, class InputIterator2>
>    >       constexpr pair<InputIterator1, InputIterator2>
>    >         mismatch(InputIterator1 first1, InputIterator1 last1,
>    >                  InputIterator2 first2);
>    >     […]
>    >     namespace ranges {
>    >       template<InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
>    >                class Proj1 = identity, class Proj2 = identity,
>    >                IndirectRelation<projected<I1, Proj1>,
>    >                projected<I2, Proj2>> Pred = ranges::equal_to<>>
>    >         constexpr mismatch_result<I1, I2>
>    >           mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
>    >                    Proj1 proj1 = {}, Proj2 proj2 = {});
>    >       template<InputRange R1, InputRange R2,
>    >                class Proj1 = identity, class Proj2 = identity,
>    >                IndirectRelation<projected<iterator_t<R1>, Proj1>,
>    >                projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to<>>
>    >         constexpr mismatch_result<safe_iterator_t<R1>, safe_iterator_t<R2>>
>    >           mismatch(R1&& r1, R2&& r2, Pred pred = {},
>    >                    Proj1 proj1 = {}, Proj2 proj2 = {});
>    >     }

>    > > -1- Let `last2` be `first2 + (last1 - first1)` for the overloads with no parameter `last2` or `r2`.

>    > > -2- Let `E` be:

>    > > 1. (2.1) — `!(*(first1 + n) == *(first2 + n))` for the overloads with no parameter `pred`,

>    > > 2. (2.2) — `pred(*(first1 + n), *(first2 + n)) == false` for the overloads with a parameter `pred` and no parameter `proj1`,

>    > > 3. (2.3) — `!invoke(pred, invoke(proj1, *(first1 + n)), invoke(proj2, *(first2 + n)))` for the overloads with both parameters `pred` and `proj1`.

>    > > -?- Let `N` be `min(last1 - first1, last2 - first2)`.

>    > > -3- Returns: `{ first1 + n, first2 + n }`, where `n` is the smallest nonnegative integer such that `E` holds, or `min(last1 - first1, last2 - first2)N` if no such integer less than `N` exists.

>    > > -4- Complexity: At most `min(last1 - first1, last2 - first2)N` applications of the corresponding predicate and any projections.

[2019-03-15; Daniel comments]

The editorial issue #2611 had been resolved via this pull request #2613. The editorial changes should make the suggested wording changes obsolete and I recommend to close this issue as Resolved.

[2020-05-02; Reflector discussions]

It seems that the editorial change has fixed the issue already. If the issue author objects, we can reopen it. Therefore:

Resolved by editorial pull request #2613.

Rationale:

Resolved by editorial pull request #2613.

Proposed resolution: