Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://cplusplus.github.io/LWG/issue1189 below:

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

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: 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. rehash reserve(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. rehash resize(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);

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4