239. Complexity of unique() and/or unique_copy incorrect

Section: 28.6.9 [alg.unique] Status: CD1 Submitter: Angelika Langer Opened: 2000-05-15 Last modified: 2016-02-10

Priority: Not Prioritized

View all other issues in [alg.unique].

View all issues with CD1 status.

Discussion:

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.

Proposed resolution:

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

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