240. Complexity of adjacent_find() is meaningless

Section: 26.6.10 [alg.adjacent.find] Status: CD1 Submitter: Angelika Langer Opened: 2000-05-15 Last modified: 2016-01-28

Priority: Not Prioritized

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

View all issues with CD1 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 in the range [first, last) for which the following corresponding conditions hold: *i == *(i + 1), pred(*i, *(i + 1)) != false. Returns last if no such iterator is found.

-2- Complexity: Exactly find(first, last, value) - first applications of the corresponding predicate.

In the Complexity section, it is not defined what "value" is supposed to mean. My best guess is that "value" means an object for which one of the conditions pred(*i,value) or pred(value,*i) is true, where i is the iterator defined in the Returns section. However, the value type of the input sequence need not be equality-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 or find_if(first, last, bind1st(pred,*i)) - first might come closer to the intended specification. Binders can only be applied to function objects that have the function call operator declared const, which is not required of predicates because they can have non-const data members. For this reason, a specification using a binder could only be an "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 the corresponding predicate, where i is adjacent_find's return value.

[Copenhagen: the original resolution specified an upper bound. The LWG preferred an exact count.]