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

Section: 23.2.8 [unord.req], 23.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 (23.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 23.5.3 [unord.map], 23.5.4 [unord.multimap], 23.5.6 [unord.set], and 23.5.7 [unord.multiset].

2. In 23.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 23.5.3 [unord.map]/3 in the definition of class template unordered_map, in 23.5.4 [unord.multimap]/3 in the definition of class template unordered_multimap, in 23.5.6 [unord.set]/3 in the definition of class template unordered_set and in 23.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 (23.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 23.5.3 [unord.map], 23.5.4 [unord.multimap], 23.5.6 [unord.set], and 23.5.7 [unord.multiset].

Proposed resolution:

In 23.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 23.5.3 [unord.map]/3 in the definition of class template unordered_map, in 23.5.4 [unord.multimap]/3 in the definition of class template unordered_multimap, in 23.5.6 [unord.set]/3 in the definition of class template unordered_set and in 23.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);