Issue 2150: Unclear specification of find

2150. Unclear specification of `find_end`

Section: 26.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:

26.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 26 [algorithms]:

26.6.15 [alg.search] p2 and p6
26.7.10 [alg.reverse] p4
26.8.5 [alg.partitions] p5 and p9
26.8 [alg.sorting] p5
26.8.3 [alg.nth.element] p1
26.8.4.2 [lower.bound] p2
26.8.4.3 [upper.bound] p2
26.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.

Change 26.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 ~~any~~every 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.

Change 26.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 ~~any~~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.

[…]

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 ~~any~~every 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.

Change 26.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 ~~any~~every non-negative integer i < (last - first) the following assignment takes place: *(result + (last - first) - i) = *(first + i).
Change 26.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 ~~any~~every iterator j in the range [first,i) pred(*j) != false, and for ~~any~~every 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 ~~any~~every iterator j in the range [first,i), pred(*j) != false, and for ~~any~~every iterator k in the range [i,last), pred(*k) == false. The relative order of the elements in both groups is preserved.
Change 26.8 [alg.sorting] p5 as indicated:

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

Change 26.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 ~~any~~every iterator i in the range [first,nth) and ~~any~~every iterator j in the range [nth,last) it holds that: !(*i > *j) or comp(*j, *i) == false.

Change 26.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 ~~any~~every iterator j in the range [first,i) the following corresponding conditions hold: *j < value or comp(*j, value) != false.

Change 26.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 ~~any~~every iterator j in the range [first,i) the following corresponding conditions hold: !(value < *j) or comp(value, *j) == false.

Change 26.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 ~~any~~every 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 ~~any~~every iterator j in the range [first,last) the following corresponding conditions hold: !(*i < *j) or comp(*i, *j) == false. Returns last if first == last.

2150. Unclear specification of find_end

2150. Unclear specification of `find_end`