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.openstd.org/jtc1/sc22/wg21/docs/lwgactive.html#384
You might want to doublecheck 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
