2156. Unordered containers' reserve(n) reserves for n-1 elements

Section: 23.2.8 [unord.req] Status: C++17 Submitter: Daniel James Opened: 2012-05-07 Last modified: 2017-07-30

Priority: 3

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with C++17 status.

Discussion:

I think that unordered containers' reserve doesn't quite do what it should. I'd expect after calling x.reserve(n) to be able to insert n elements without invalidating iterators. But as the standard is written (I'm looking at n3376), I think the guarantee only holds for n-1 elements.

For a container with max_load_factor of 1, reserve(n) is equivalent to rehash(ceil(n/1)), ie. rehash(n). rehash(n) requires that the bucket count is >= n, so it can be n (Table 103). The rule is that insert shall not affect the validity of iterators if (N + n) < z * B (23.2.8 [unord.req] p15). But for this case the two sides of the equation are equal, so insert can affect the validity of iterators.

[2013-03-16 Howard comments and provides wording]

Given the following: 

LF := load_factor()
MLF := max_load_factor()
S := size()
B := bucket_count()

LF == S/B

The container has an invariant: 

LF <= MLF

Therefore: 

MLF >= S/B
S <= MLF * B
B >= S/MLF

[2013-03-15 Issues Teleconference]

Moved to Open.

Howard to provide rationale and potentally revised wording.

[2012-02-12 Issaquah : recategorize as P3]

Jonathan Wakely: submitter is Boost.Hash maintainer. Think it's right.

Marshall Clow: even if wrong it's more right than what we have now

Geoffrey Romer: issue is saying rehash should not leave container in such a state that a notional insertion of zero elements should not trigger a rehash

AJM: e.g. if you do a range insert from an empty range

AJM: we don't have enough brainpower to do this now, so not priority zero

Recategorised as P3

[Lenexa 2015-05-06: Move to Ready]

Proposed resolution:

This wording is relative to N3485.

  1. In 23.2.8 [unord.req] Table 103 — Unordered associative container requirements, change the post-condition in the row for a.rehash(n) to:

    Post: a.bucket_count() >= a.size() / a.max_load_factor() and a.bucket_count() >= n.

  2. In 23.2.8 [unord.req]/p15 change

    The insert and emplace members shall not affect the validity of iterators if (N+n) <= z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container's bucket count, and z is the container's maximum load factor.