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

### 1338. LWG 1205 incorrectly applied

Section: 25.6.13 [alg.search] Status: C++11 Submitter: Howard Hinnant Opened: 2010-06-25 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [alg.search].

View all issues with C++11 status.

Discussion:

LWG 1205 (currently in WP) clarified the return value of several algorithms when dealing with empty ranges. In particular it recommended for 25.6.13 [alg.search]:

>     template<class ForwardIterator1, class ForwardIterator2>
>       ForwardIterator1
>         search(ForwardIterator1 first1, ForwardIterator1 last1,
>                ForwardIterator2 first2, ForwardIterator2 last2);

>     template<class ForwardIterator1, class ForwardIterator2,
>              class BinaryPredicate>
>       ForwardIterator1
>         search(ForwardIterator1 first1, ForwardIterator1 last1,
>                ForwardIterator2 first2, ForwardIterator2 last2,
>                BinaryPredicate pred);

> > 1 Effects: ...

> > 2 Returns: ... Returns `last1` if no such iterator is found.

> > 3 Remarks: Returns `first1` if `[first2,last2)` is empty.

Unfortunately this got translated to an incorrect specification for what gets returned when no such iterator is found (N3092):

>     template<class ForwardIterator1, class ForwardIterator2>
>       ForwardIterator1
>         search(ForwardIterator1 first1, ForwardIterator1 last1,
>                ForwardIterator2 first2, ForwardIterator2 last2);

>     template<class ForwardIterator1, class ForwardIterator2,
>              class BinaryPredicate>
>       ForwardIterator1
>         search(ForwardIterator1 first1, ForwardIterator1 last1,
>                ForwardIterator2 first2, ForwardIterator2 last2,
>                BinaryPredicate pred);

> > 1 Effects: ...

> > 2 Returns: ... Returns `first1` if `[first2,last2)` is empty or if no such iterator is found.

LWG 1205 is correct and N3092 is not equivalent nor correct.

I have not reviewed the other 10 recommendations of 1205.

[ Post-Rapperswil ]

> It was verified that none of the remaining possibly affected algorithms does have any similar problems and a concrete P/R was added that used a similar style as has been applied to the other cases.

> Moved to Tentatively Ready after 5 positive votes on c++std-lib.

[ Adopted at 2010-11 Batavia ]

Proposed resolution:

1. Change [alg.search] p.2 as indicated:

   >     template<class ForwardIterator1, class ForwardIterator2>
   >       ForwardIterator1
   >         search(ForwardIterator1 first1, ForwardIterator1 last1,
   >                ForwardIterator2 first2, ForwardIterator2 last2);

   >     template<class ForwardIterator1, class ForwardIterator2,
   >                 class BinaryPredicate>
   >       ForwardIterator1
   >         search(ForwardIterator1 first1, ForwardIterator1 last1,
   >                ForwardIterator2 first2, ForwardIterator2 last2,
   >                BinaryPredicate pred);

   > > 1 - [...]

   > > 2 - Returns: The first iterator `i` in the range `[first1,last1 - (last2-first2))` such that for any 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 or, otherwise returns `last1` if no such iterator is found.