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

### 1189. Awkward interface for changing the number of buckets in an unordered associative container

Section: 24.2.8 [unord.req], 24.5 [unord] Status: C++11 Submitter: Matt Austern Opened: 2009-08-10 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 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 to `size()`, 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): ]

> 1. 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.rehashreserve(n)` | `void` | Post: `a.bucket_count > max(a.size(), n) / a.max_load_factor()` and `a.bucket_count() >= n`. | Average 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].

> 2. 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)` | `void` | Post: `a.bucket_count > a.size() / a.max_load_factor()` and `a.bucket_count() >= n`. | Average case linear in `a.size()`, worst case quadratic.
>    > `a.reserve(n)` | `void` | Same 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);

[ 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)` provide `resize(n)`, with the semantics "make the container a good size for `n` elements".

> > 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.rehashresize(n)` | `void` | Post: `a.bucket_count > max(a.size(), n) / a.max_load_factor()` and `a.bucket_count() >= n`. | Average 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)` | `void` | Post: `a.bucket_count > a.size() / a.max_load_factor()` and `a.bucket_count() >= n`. | Average case linear in `a.size()`, worst case quadratic.
> `a.reserve(n)` | `void` | Same 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);