test for lib.alg.unique

[Anton Pevtsov <an...@moscow.vdiweb.com>]

The attached file contains my attempt to update lib.alg.unique tests and
port them to new test driver.

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).
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?

The current test vesrion suppose that (last  - first) - 1 is correct.


With best wishes,
Anton Pevtsov 

Re: test for lib.alg.unique

[Martin Sebor <se...@roguewave.com>]

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

Re: test for lib.alg.unique

[Martin Sebor <se...@roguewave.com>]

Anton Pevtsov wrote:
> The attached file contains my attempt to update lib.alg.unique tests and
> port them to new test driver.

Looks good, thanks! I committed it with just a few minor modifications
mostly to improve the readability of the code with this change:
http://svn.apache.org/viewcvs.cgi?rev=372633&view=rev

A few points on the changes I madet to your version:

*  It helps to separate function arguments one per line whenever there
    are more than two or three of them; it also help to line up their
    names.

*  It helps to line up like local variables and their initializers,
    such as the iterators, to immediately see the differences between
    them.

*  It's not necessary to cast the arguments to the iterator ctors
    to the target type since the type is explicitly provided in the
    name of the iterator (e.g., InputIter<X> iter (0, 0, 0) is good
    enough).

*  It's important to end every statement with a semicolon on the
    same line. Specifically, a macro definition should not end with
    a semicolon so that the the semicolon can and must be supplied
    when invoking the macro. (Otherwise Emacs formatting gets messed
    up.)

*  It helps to introduce helper variables for complicated-looking
    repeatedly used expressions (such as InputIter<T>(0, 0, 0)).

*  Please avoid gratuitous spaces in expressions such as (T*)0.
    I.e., do not write "(T*) 0."

Thanks again!
Martin