**Section:** 27.8.4.4 [equal.range] **Status:** CD1
**Submitter:** Hans Bos **Opened:** 2002-10-18 **Last modified:** 2016-01-28 10:19:27 UTC

**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 `log _{2}(last - first) + O(1)`.

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

In 27.8.4.4 [equal.range]/4, change `2*log(last - first) + 1`
to `2*log _{2}(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.