Anton Pevtsov wrote:
The attached file contains my attempt to update lib.alg.unique tests and
port them to new test driver.
I forgot to answer your question below:
I noticed that the complexity for unique_copy is (last - first) - 1
applications of the predicate, but according to the standard it should
be exactly (last - first).
Generally speaking, the complexity requirements are upper bounds and
implementations are allowed and encouraged to do better (see 17.3.1.3,
p5). That said, the use of the word "exactly" here does suggest that
the standard requires exactly that many applications of the predicate
and not less. Unless it's actually a bug in our implementation of the
algorithm (if it is, we should be able to produce a test case showing
that our unique() fails under some conditions), the word ought to be
be stricken from the standard.
In other hand the complexity of the unique according to the standard
should be exactly (last - first) - 1.
And I have a question: is the complexity (last - first) - 1 correct for
the unique_copy algorithm?
Unless you can come up with a situation where our unique fails to
satisfy any of the the other requirements it's correct. (I encourage
you to try! :) Btw., what do other implementations (gcc or MSVC) do?
Martin
