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.

Suggested Resolution:

Change the entry for equal_range in Table 93 as follows:

Return type:
pair<local_iterator,local_iterator>; pair<const_local_iterator,
const_local_iterator> for const b.

assertion/note pre/post-condition:
Returns a range contained completely in one bucket 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.


Joe Gottman

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]