384. equal_range has unimplementable runtime complexity

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.