Issue 2150: Unclear specification of find_end (original) (raw)

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: 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]:

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

  1. 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 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 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 anyevery nonnegative integer n less than last2 - first2the 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 lastif no such iterator is found. 3. 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 anyevery non-negative integer i < (last - first) the following assignment takes place: *(result + (last - first) - i) = *(first + i). 4. 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 anyevery iterator jin the range [first,i) pred(*j) != false, and for anyevery iterator kin 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 jin the range [first,i), pred(*j) != false, and for anyevery iterator kin the range [i,last), pred(*k) == false. The relative order of the elements in both groups is preserved. 5. Change 26.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 26.8.3 [alg.nth.element] p1 as indicated:
template
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 iin 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 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 anyevery iterator j in the range [first,i) the following corresponding conditions hold: *j < value or comp(*j, value) != false. 8. 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 anyevery iterator j in the range [first,i) the following corresponding conditions hold: !(value < *j) or comp(value, *j) == false. 9. Change 26.8.9 [alg.min.max] p21 and p23 as indicated:
template
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
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.