Title
Complexity of adjacent_find() is meaningless
Status
cd1
Section
[alg.adjacent.find]
Submitter
Angelika Langer

Created on 2000-05-15.00:00:00 last changed 163 months ago

Messages

Date: 2010-10-21.18:28:33

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

Date: 2010-10-21.18:28:33

Proposed resolution:

Change the complexity section in [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.

Date: 2000-05-15.00:00:00

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.

History
Date User Action Args
2010-10-21 18:28:33adminsetmessages: + msg1974
2010-10-21 18:28:33adminsetmessages: + msg1973
2000-05-15 00:00:00admincreate