This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of CD1 status.
Section: 26.8.4.4 [equal.range] Status: CD1 Submitter: Hans Bos Opened: 2002-10-18 Last modified: 2016-01-28
Priority: Not Prioritized
View all other issues in [equal.range].
View all issues with CD1 status.
Discussion:
Section 26.8.4.4 [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).
Proposed resolution:
In 26.8.4.2 [lower.bound]/4, change log(last - first) + 1
to log2(last - first) + O(1).
In 26.8.4.3 [upper.bound]/4, change log(last - first) + 1
to log2(last - first) + O(1).
In 26.8.4.4 [equal.range]/4, change 2*log(last - first) + 1
to 2*log2(last - first) + O(1).
[Matt provided wording]
Rationale:
The LWG considered just saying O(log n) for all three, but
decided that threw away too much valuable information. The fact
that lower_bound is twice as fast as equal_range is important.
However, it's better to allow an arbitrary additive constant than to
specify an exact count. An exact count would have to
involve floor or ceil. It would be too easy to
get this wrong, and don't provide any substantial value for users.