4179. Wrong range in [alg.search]

Section: 26.6.15 [alg.search] Status: WP Submitter: Oscar Slotosch Opened: 2024-12-05 Last modified: 2025-02-16

Priority: Not Prioritized

View all other issues in [alg.search].

View all issues with WP status.

Discussion:

Originally reported as editorial request #7474:

During the qualification of the C++ STL Validas has pointed me to the following issue:

The specification of 26.6.15 [alg.search] has a wrong range. Currently the range is "[first1, last1 - (last2 - first2))" (exclusive) but should be "[first1, last1 - (last2 - first2)]" (inclusive). So please correct the closing ")" to "]". Otherwise the last occurrence will not be found. We observed the issue in C++14 and C++17 and cppreference.com.

The implementations do the right thing and work correctly and find even the last occurrence.

For example in the list {1, 2, 3, 4, 5} the pattern {4, 5} should be found (obviously). In the case the last element is not included it will not be found.

Demonstration on godbolt shows that the implementation is working and finds the pattern.

[2024-12-07; Daniel comments and provides wording]

The mentioned wording issue is present in all previous standard versions, including the SGI STL. It needs to be fixed in all search variants specified in 26.6.15 [alg.search] (except for the form using a Searcher).

[2025-02-07; Reflector poll]

Set status to Tentatively Ready after ten votes in favour during reflector poll.

[Hagenberg 2025-02-16; Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4993.

  1. Modify 26.6.15 [alg.search] as indicated:

    template<class ForwardIterator1, class ForwardIterator2>
  constexpr ForwardIterator1
    search(ForwardIterator1 first1, ForwardIterator1 last1,
           ForwardIterator2 first2, ForwardIterator2 last2);
[…]
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
         class BinaryPredicate>
ForwardIterator1
  search(ExecutionPolicy&& exec,
         ForwardIterator1 first1, ForwardIterator1 last1,
         ForwardIterator2 first2, ForwardIterator2 last2,
         BinaryPredicate pred);

    -1- Returns: The first iterator i in the range [first1, last1 - (last2 - first2)]) such that for every nonnegative integer n less than last2 - first2 the following corresponding conditions hold: *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false. Returns first1 if [first2, last2) is empty, otherwise returns last1 if no such iterator is found.

    -2- […] 

    template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
         sentinel_for<I2> S2, class Pred = ranges::equal_to,
         class Proj1 = identity, class Proj2 = identity>
  requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
  constexpr subrange<I1>
    ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {});
template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
         class Proj1 = identity, class Proj2 = identity>
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
  constexpr borrowed_subrange_t<R1>
    ranges::search(R1&& r1, R2&& r2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {});

    -3- Returns:

    1. (3.1) — {i, i + (last2 - first2)}, where i is the first iterator in the range [first1, last1 - (last2 - first2)]) such that for every non-negative integer n less than last2 - first2 the condition

      bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))))

      is true.

    2. (3.2) — Returns {last1, last1} if no such iterator exists.

    -4- […] 

    template<class ForwardIterator, class Size, class T = iterator_traits<ForwardIterator>::value_type>
  constexpr ForwardIterator
    search_n(ForwardIterator first, ForwardIterator last,
             Size count, const T& value);
[…]
template<class ExecutionPolicy, class ForwardIterator, class Size,
         class T = iterator_traits<ForwardIterator>::value_type,
         class BinaryPredicate>
  ForwardIterator
    search_n(ExecutionPolicy&& exec,
             ForwardIterator first, ForwardIterator last,
             Size count, const T& value,
             BinaryPredicate pred);

    -5- […]

    -6- […]

    -7- Returns: The first iterator i in the range [first, last-count]) such that for every non-negative integer n less than count the condition E is true. Returns last if no such iterator is found.

    -8- […] 

    template<forward_iterator I, sentinel_for<I> S,
         class Pred = ranges::equal_to, class Proj = identity,
         class T = projected_value_t<I, Proj>>
  requires indirectly_comparable<I, const T*, Pred, Proj>
  constexpr subrange<I>
    ranges::search_n(I first, S last, iter_difference_t<I> count,
                     const T& value, Pred pred = {}, Proj proj = {});
template<forward_range R, class Pred = ranges::equal_to,
         class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
  requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
  constexpr borrowed_subrange_t<R>
    ranges::search_n(R&& r, range_difference_t<R> count,
                     const T& value, Pred pred = {}, Proj proj = {});

    -9- Returns: {i, i + count} where i is the first iterator in the range [first, last - count]) such that for every non-negative integer n less than count, the following condition holds: invoke(pred, invoke(proj, *(i + n)), value). Returns {last, last} if no such iterator is found.

    -10- […]