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

2150. Unclear specification of find_end

Section: 27.6.8 [alg.find.end] Status: C++14 Submitter: Andrew Koenig Opened: 2012-03-28 Last modified: 2016-01-28

Priority: Not Prioritized

View all issues with C++14 status.

Discussion:

27.6.8 [alg.find.end] describes the behavior of find_end as returning:

The last iterator i in the range [first1,last1 - (last2 - first2)) such that for any nonnegative integer n < (last2 - first2), the following corresponding conditions hold: *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false.

Does "for any" here mean "for every" or "there exists a"? I think it means the former, but it could be interpreted either way.

Daniel: The same problem exists for the following specifications from Clause 27 [algorithms]:

  1. 27.6.15 [alg.search] p2 and p6
  2. 27.7.10 [alg.reverse] p4
  3. 27.8.5 [alg.partitions] p5 and p9
  4. 27.8 [alg.sorting] p5
  5. 27.8.3 [alg.nth.element] p1
  6. 27.8.4.2 [lower.bound] p2
  7. 27.8.4.3 [upper.bound] p2
  8. 27.8.9 [alg.min.max] p21 and p23

[2013-04-20, Bristol]

Unanimous agreement on the wording.

Resolution: move to tentatively ready

[2013-09-29, Chicago]

Apply to Working Paper

Proposed resolution:

This wording is relative to N3376.

  1. Change 27.6.8 [alg.find.end] p2 as indicated:

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

    […]

    -2- Returns: The last iterator i in the range [first1,last1 - (last2 - first2)) such that for anyevery nonnegative integer n < (last2 - first2), the following corresponding conditions hold: *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false. Returns last1 if [first2,last2) is empty or if no such iterator is found.

  2. Change 27.6.15 [alg.search] p2 and p6 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);

    […]

    -2- Returns: The first iterator i in the range [first1,last1 - (last2-first2)) such that for anyevery 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.

    […] 

    template<class ForwardIterator, class Size, class T>
ForwardIterator
search_n(ForwardIterator first, ForwardIterator last, Size count,
         const T& value);
template<class ForwardIterator, class Size, class T,
         class BinaryPredicate>
ForwardIterator
search_n(ForwardIterator first, ForwardIterator last, Size count,
         const T& value, BinaryPredicate pred);

    […]

    -6- Returns: The first iterator i in the range [first,last-count) such that for anyevery non-negative integer n less than count the following corresponding conditions hold: *(i + n) == value, pred(*(i + n),value) != false. Returns last if no such iterator is found.

  3. Change 27.7.10 [alg.reverse] p4 as indicated:

    template<class BidirectionalIterator, class OutputIterator>
OutputIterator
reverse_copy(BidirectionalIterator first,
             BidirectionalIterator last, OutputIterator result);

    […]

    -4- Effects: Copies the range [first,last) to the range [result,result+(last-first)) such that for anyevery non-negative integer i < (last - first) the following assignment takes place: *(result + (last - first) - i) = *(first + i).

  4. Change 27.8.5 [alg.partitions] p5 and p9 as indicated:

    template<class ForwardIterator, class Predicate>
ForwardIterator
partition(ForwardIterator first,
          ForwardIterator last, Predicate pred);

    […]

    -5- Returns: An iterator i such that for anyevery iterator j in the range [first,i) pred(*j) != false, and for anyevery iterator k in the range [i,last), pred(*k) == false.

    […] 

    template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(BidirectionalIterator first,
                 BidirectionalIterator last, Predicate pred);

    […]

    -9- Returns: An iterator i such that for anyevery iterator j in the range [first,i), pred(*j) != false, and for anyevery iterator k in the range [i,last), pred(*k) == false. The relative order of the elements in both groups is preserved.

  5. Change 27.8 [alg.sorting] p5 as indicated:

    -5- A sequence is sorted with respect to a comparator comp if for anyevery iterator i pointing to the sequence and anyevery non-negative integer n such that i + n is a valid iterator pointing to an element of the sequence, comp(*(i + n), *i) == false.

  6. Change 27.8.3 [alg.nth.element] p1 as indicated:

    template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                 RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                 RandomAccessIterator last, Compare comp);

    -1- After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted. Also for anyevery iterator i in the range [first,nth) and anyevery iterator j in the range [nth,last) it holds that: !(*i > *j) or comp(*j, *i) == false.

  7. Change 27.8.4.2 [lower.bound] p2 as indicated:

    template<lass ForwardIterator, class T>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
            const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
            const T& value, Compare comp);

    […]

    -2- Returns: The furthermost iterator i in the range [first,last] such that for anyevery iterator j in the range [first,i) the following corresponding conditions hold: *j < value or comp(*j, value) != false.

  8. Change 27.8.4.3 [upper.bound] p2 as indicated:

    template<lass ForwardIterator, class T>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
            const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
            const T& value, Compare comp);

    […]

    -2- Returns: The furthermost iterator i in the range [first,last] such that for anyevery iterator j in the range [first,i) the following corresponding conditions hold: !(value < *j) or comp(value, *j) == false.

  9. Change 27.8.9 [alg.min.max] p21 and p23 as indicated:

    template<class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                            Compare comp);

    -21- Returns: The first iterator i in the range [first,last) such that for anyevery iterator j in the range [first,last) the following corresponding conditions hold: !(*j < *i) or comp(*j, *i) == false. Returns last if first == last.

    […] 

    template<class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
                            Compare comp);

    -23- Returns: The first iterator i in the range [first,last) such that for anyevery iterator j in the range [first,last) the following corresponding conditions hold: !(*i < *j) or comp(*i, *j) == false. Returns last if first == last.