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.

### 384. equal_range has unimplementable runtime complexity

Section: 27.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 27.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 27.8.4.2 [lower.bound]/4, change `log(last - first) + 1` to `log2(last - first) + O(1)`.

In 27.8.4.3 [upper.bound]/4, change `log(last - first) + 1` to `log2(last - first) + O(1)`.

In 27.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.