1000. adjacent_find is over-constrained

Section: 26.6.10 [alg.adjacent.find] Status: NAD Concepts Submitter: Chris Jefferson Opened: 2009-03-09 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [alg.adjacent.find].

View all issues with NAD Concepts status.

Discussion:

Addresses UK 296

adjacent_find in C++03 allows an arbitrary predicate, but in C++0x EqualityComparable/EquivalenceRelation is required. This forbids a number of use cases, including:

adjacent_find(begin, end, less<double>)	Find the first place where a range is not ordered in decreasing order - in use to check for sorted ranges.
adjacent_find(begin, end, DistanceBiggerThan(6) ) )	Find the first place in a range where values differ by more than a given value - in use to check an algorithm which produces points in space does not generate points too far apart.

A number of books use predicate which are not equivalence relations in examples, including "Thinking in C++" and "C++ Primer".

Adding the requirement that the predicate is an EquivalenceRelation does not appear to open up any possibility for a more optimised algorithm.

Proposed resolution:

Change the definition of adjacent_find in the synopsis of 26 [algorithms] and 26.6.10 [alg.adjacent.find] to:

template<ForwardIterator Iter> 
  requires EqualityComparableHasEqualTo<Iter::value_type, Iter::value_type>
  Iter adjacent_find(Iter first, Iter last);

template<ForwardIterator Iter, EquivalenceRelationPredicate<auto, Iter::value_type, Iter::value_type> Pred> 
  requires CopyConstructible<Pred> 
  Iter adjacent_find(Iter first, Iter last, Pred pred);