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.
equal_range
on unordered containers should return a pair
of local_iterators
Section: 24.2.8 [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 (24.2.8 [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()) . |