1338. LWG 1205 incorrectly applied

Section: 28.5.13 [alg.search] Status: C++11 Submitter: Howard Hinnant Opened: 2010-06-25 Last modified: 2016-02-10

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 28.5.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.