**Section:** 24.2.8 [unord.req], 24.5 [unord] **Status:** C++11
**Submitter:** Matt Austern **Opened:** 2009-08-10 **Last modified:** 2016-01-28 10:19:27 UTC

**Priority: **Not Prioritized

**View other** active issues in [unord.req].

**View all other** issues in [unord.req].

**View all issues with** C++11 status.

**Discussion:**

Consider a typical use case: I create an `unordered_map` and then start
adding elements to it one at a time. I know that it will eventually need
to store a few million elements, so, for performance reasons, I would
like to reserve enough capacity that none of the calls to `insert` will
trigger a rehash.

Unfortunately, the existing interface makes this awkward. The user
naturally sees the problem in terms of the number of elements, but the
interface presents it as buckets. If `m` is the map and `n` is the expected
number of elements, this operation is written `m.rehash(n /
m.max_load_factor())` — not very novice friendly.

*[
2009-09-30 Daniel adds:
]*

I recommend to replace "

resize" by a different name like "reserve", because that would better match the intended use-case. Rational: Any existing resize function has the on-success post-condition that the provided size is equal tosize(), which is not satisfied for the proposal. Reserve seems to fit the purpose of the actual renaming suggestion.

*[
2009-10-28 Ganesh summarizes alternative resolutions and expresses a
strong preference for the second (and opposition to the first):
]*

In the unordered associative container requirements (24.2.8 [unord.req]), remove the row for rehash and replace it with:

Table 87 — Unordered associative container requirements (in addition to container) Expression Return type Assertion/note pre-/post-condition Complexity a.~~rehash~~reserve(n)voidPost: a.bucket_count > max(a.size(), n) / a.max_load_factor()~~and~~.a.bucket_count() >= nAverage case linear in a.size(), worst case quadratic.Make the corresponding change in the class synopses in 24.5.4 [unord.map], 24.5.5 [unord.multimap], 24.5.6 [unord.set], and 24.5.7 [unord.multiset].

In 24.2.8 [unord.req]/9, table 98, append a new row after the last one:

Table 87 — Unordered associative container requirements (in addition to container) Expression Return type Assertion/note pre-/post-condition Complexity a.rehash(n)voidPost: a.bucket_count > a.size() / a.max_load_factor()anda.bucket_count() >= n.Average case linear in a.size(), worst case quadratic.a.reserve(n)voidSame as a.rehash(ceil(n / a.max_load_factor()))Average case linear in a.size(), worst case quadratic.In 24.5.4 [unord.map]/3 in the definition of class template

unordered_map, in 24.5.5 [unord.multimap]/3 in the definition of class templateunordered_multimap, in 24.5.6 [unord.set]/3 in the definition of class templateunordered_setand in 24.5.7 [unord.multiset]/3 in the definition of class templateunordered_multiset, add the following line after member functionrehash():void reserve(size_type n);

*[
2009-10-28 Howard:
]*

Moved to Tentatively Ready after 5 votes in favor of Ganesh's option 2 above. The original proposed wording now appears here:

Informally: instead of providing

rehash(n)provideresize(n), with the semantics "make the container a good size fornelements".In the unordered associative container requirements (24.2.8 [unord.req]), remove the row for rehash and replace it with:

Table 87 — Unordered associative container requirements (in addition to container) Expression Return type Assertion/note pre-/post-condition Complexity a.~~rehash~~resize(n)voidPost: a.bucket_count > max(a.size(), n) / a.max_load_factor()~~and~~.a.bucket_count() >= nAverage case linear in a.size(), worst case quadratic.Make the corresponding change in the class synopses in 24.5.4 [unord.map], 24.5.5 [unord.multimap], 24.5.6 [unord.set], and 24.5.7 [unord.multiset].

**Proposed resolution:**

In 24.2.8 [unord.req]/9, table 98, append a new row after the last one:

Table 87 — Unordered associative container requirements (in addition to container) Expression Return type Assertion/note pre-/post-condition Complexity a.rehash(n)voidPost: a.bucket_count > a.size() / a.max_load_factor()anda.bucket_count() >= n.Average case linear in a.size(), worst case quadratic.a.reserve(n)voidSame as a.rehash(ceil(n / a.max_load_factor()))Average case linear in a.size(), worst case quadratic.

In 24.5.4 [unord.map]/3 in the definition of class template `unordered_map`, in
24.5.5 [unord.multimap]/3 in the definition of class template `unordered_multimap`, in
24.5.6 [unord.set]/3 in the definition of class template `unordered_set` and in
24.5.7 [unord.multiset]/3 in the definition of class template `unordered_multiset`, add the
following line after member function `rehash()`:

void reserve(size_type n);