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
