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.
The complexity of unique and unique_copy are inconsistent with each other and inconsistent with the implementations. The standard specifies:
-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.
-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.
Change both complexity sections in 28.6.9 [alg.unique] to:
Complexity: For nonempty ranges, exactly last - first - 1 applications of the corresponding predicate.