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: 25.6.6 [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:

25.6.6 [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 25 [algorithms]:

1. 25.6.13 [alg.search] p2 and p6
2. 25.7.10 [alg.reverse] p4
3. 25.8.5 [alg.partitions] p5 and p9
4. 25.8 [alg.sorting] p5
5. 25.8.3 [alg.nth.element] p1
6. 25.8.4.2 [lower.bound] p2
7. 25.8.4.3 [upper.bound] p2
8. 25.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 25.6.6 [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.

2. Change 25.6.13 [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.

3. Change 25.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)`.

4. Change 25.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.

5. Change 25.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`.

6. Change 25.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`.

7. Change 25.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`.

8. Change 25.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`.

9. Change 25.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`.