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

Section: 26.2.7 [unord.req] Status: NAD Submitter: Joe Gottman Opened: 2007-11-29 Last modified: 2016-02-10

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 (26.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()).