[Moderator's note: this defect report has been
 forwarded to the C++ committee. -moderator.]

section 25.3.3.3 [lib.equal.range]
states that at most 2 * log(last - first) + 1
comparisons are allowed for equal_range

It is not possible to implement equal_range with these constraints.

In a range of one element as in:
    int x = 1;
    equal_range(&x, &x + 1, 1)

it is easy to see that at least 2 comparison operations are needed.

For this case at most 2 * log(1) + 1 = 1 comparison is allowed.

I have checked a few libraries and they all use the same (nonconforming)
algorithm for equal_range that has a complexity of
     2* log(distance(first, last)) + 2.
I guess this is the algorithm that the standard assumes for equal_range.

It is easy to see that 2 * log(distance) + 2 comparisons are enough since
equal
range can be implemented with lower_bound and upper_bound (both
log(distance) + 1).

I think it is better to require something like 2log(distance) + O(1)  (or
even logarithmic as multiset::equal_range).
Then an implementation has more room to optimize for certain cases (e.g.
have log(distance) characteristics when at most match is found in the range
but 2log(distance) + 4 for the worst case).

Hans Bos.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]