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.
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): ]
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].
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);