Section: 26.7.9 [alg.unique] Status: CD1 Submitter: Angelika Langer Opened: 2000-05-15 Last modified: 2016-01-28
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 26.7.9 [alg.unique] to:
Complexity: For nonempty ranges, exactly last - first - 1 applications of the corresponding predicate.