stdcxx-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Martin Sebor <se...@roguewave.com>
Subject Re: test for lib.equal.range
Date Sun, 05 Feb 2006 23:29:22 GMT
Anton Pevtsov wrote:
> There were a couple of typo errors in the version I sent yesterday.
> The attach contains corrected version of the test.

Thanks! Committed thusly:
http://svn.apache.org/viewcvs.cgi?rev=375132&view=rev

[...]
> I have one small question about the complexity of this algorithm: The
> standard talks that it should be at most 2 * log (last - first) + 1.
> 
> But for some small sequences I got 2 * log (last - first) + 2 (this is
> the sum of lower.bound and upper.bound "complexities").
> 
> I am not sure that this may be considered as a bug, so the test consider
> 2 * log (last - first) + 2 as a correct value.

In general the log complexities are approximations, not exact values,
so a positive difference by a small constant shouldn't matter. What
tends to be confusing is that in some cases (such as in this one) the
standard gives an exact value instead of simply saying the complexity
is logarithmic in N. Here's an issue that explains what the intent is
for equal_range and clarifies the complexity requirement of not just
it but also of the lower_bound and upper_bound algorithms:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#384

You might want to double-check that the tests for the other two
algorithms verify these requirements as well.

> 
> I'll check this on other stl implementations (at first glance there will
> be the same result).

Good idea! If our implementation fails to conform to the clarified
requirements from issue 384 please put together a small test case
and open an issue.

Martin

Mime
View raw message