This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofCD1 status.
Section: 26.6.10[alg.adjacent.find]Status:CD1Submitter: Angelika LangerOpened: 2000-05-15Last modified: 2016-01-28
Priority:Not Prioritized
View all otherissues in [alg.adjacent.find].
View all issues withCD1 status.
Discussion:
The complexity section of adjacent_find is defective:
template <class ForwardIterator>ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last BinaryPredicate pred);-1- Returns: The first iterator i such that both i and i + 1 are inthe range [first, last) for which the following correspondingconditions hold: *i == *(i + 1), pred(*i, *(i + 1)) != false. Returnslast if no such iterator is found.
-2- Complexity: Exactly find(first, last, value) - first applicationsof the corresponding predicate.
In the Complexity section, it is not defined what "value"is supposed to mean. My best guess is that "value" means anobject for which one of the conditions pred(*i,value) orpred(value,*i) is true, where i is the iterator defined in the Returnssection. However, the value type of the input sequence need not beequality-comparable and for this reason the term find(first, last,value) - first is meaningless.
A term such as find_if(first, last, bind2nd(pred,*i)) - first orfind_if(first, last, bind1st(pred,*i)) - first might come closer tothe intended specification. Binders can only be applied to functionobjects that have the function call operator declared const, which isnot required of predicates because they can have non-const datamembers. For this reason, a specification using a binder could only bean "as-if" specification.
Proposed resolution:
Change the complexity section in 26.6.10[alg.adjacent.find] to:
For a nonempty range, exactly
min((i -first) + 1,(last -first) - 1)applications of thecorresponding predicate, wherei isadjacent_find'sreturn value.
[Copenhagen: the original resolution specified an upperbound. The LWG preferred an exact count.]