Title
Complexity of unique() and/or unique_copy incorrect
Status
cd1
Section
[alg.unique]
Submitter
Angelika Langer

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

Messages

Date: 2010-10-21.18:28:33

Proposed resolution:

Change both complexity sections in [alg.unique] to:

Complexity: For nonempty ranges, exactly last - first - 1 applications of the corresponding predicate.

Date: 2000-05-15.00:00:00

The complexity of unique and unique_copy are inconsistent with each other and inconsistent with the implementations.  The standard specifies:

for unique():

-3- Complexity: If the range (last - first) is not empty, exactly (last - first) - 1 applications of the corresponding predicate, otherwise no applications of the predicate.

for unique_copy():

-7- Complexity: Exactly last - first applications of the corresponding predicate.

The implementations do it the other way round: unique() applies the predicate last-first times and unique_copy() applies it last-first-1 times.

As both algorithms use the predicate for pair-wise comparison of sequence elements I don't see a justification for unique_copy() applying the predicate last-first times, especially since it is not specified to which pair in the sequence the predicate is applied twice.

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