### 240. Complexity of adjacent_find() is meaningless

**Section:** 28.5.8 [alg.adjacent.find] **Status:** CD1
**Submitter:** Angelika Langer **Opened:** 2000-05-15 **Last modified:** 2016-02-10

**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 28.5.8 [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.]*