This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of NAD status.

### 764. `equal_range` on unordered containers should return a `pair` of `local_iterators`

Section: 22.2.7 [unord.req] Status: NAD Submitter: Joe Gottman Opened: 2007-11-29 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with NAD status.

Discussion:

A major attribute of the unordered containers is that iterating though them inside a bucket is very fast while iterating between buckets can be much slower. If an unordered container has a low load factor, iterating between the last iterator in one bucket and the next iterator, which is in another bucket, is `O(bucket_count())` which may be much larger than `O(size())`.

If `b` is an non-const unordered container of type `B` and `k` is an object of it's `key_type`, then `b.equal_range(k)` currently returns `pair<B::iterator, B::iterator>`. Consider the following code:

>     B::iterator lb, ub;
>     tie(lb, ub) = b.equal_range(k);
>     for (B::iterator it = lb; it != ub; ++it) {
>             // Do something with *it
>     }

If `b.equal_range(k)` returns a non-empty range (i.e. `b` contains at least on element whose key is equivalent to `k`), then every iterator in the half-open range `[lb, ub)` will be in the same bucket, but `ub` will likely either be in a different bucket or be equal to `b.end()`. In either case, iterating between `ub - 1` and `ub` could take a much longer time than iterating through the rest of the range.

If instead of returning `pair<iterator, iterator>`, `equal_range` were to return `pair<local_iterator, local_iterator>`, then `ub` (which, like `lb`, would now be a `local_iterator`) could be guaranteed to always be in the same bucket as `lb`. In the cases where currently `ub` is equal to `b.end()` or is in a different bucket, `ub` would be equal to `b.end(b.bucket(key))`. This would make iterating between `lb` and `ub` much faster, as every iteration would be constant time.

[ Bellevue: ]

> The proposed resolution breaks consistency with other container types for dubious benefit, and iterators are already constant time.

Proposed resolution:

Change the entry for `equal_range` in Table 93 (22.2.7 [unord.req]) as follows:

expression | return type | assertion/note pre/post-condition | complexity
--- | --- | --- | ---
`b.equal_range(k)` | `pair<local_iterator,local_iterator>; pair<const_local_iterator,const_local_iterator>` for `const b`. | Returns a range containing all elements with keys equivalent to `k`. Returns `make_pair(b.end(b.bucket(key)),b.end(b.bucket(key)))` if no such elements exist. | Average case Θ`(b.count(k))`. Worst case Θ`(b.size())`.