Created on 2000-05-15.00:00:00 last changed 172 months ago
Proposed resolution:
Change both complexity sections in [alg.unique] to:
Complexity: For nonempty ranges, exactly last - first - 1 applications of the corresponding predicate.
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:33 | admin | set | messages: + msg1971 |
2000-05-15 00:00:00 | admin | create |