3178. std::mismatch is missing an upper bound

Section: 99 [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 99 [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 99 [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:

Proposed resolution: