This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++17 status.
reserve(n)
reserves for n-1
elementsSection: 24.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.
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
(24.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.
In 24.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()
anda.bucket_count() >= n
.
In 24.2.8 [unord.req]/p15 change
Theinsert
andemplace
members shall not affect the validity of iterators if(N+n) <= z * B
, whereN
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, andz
is the container's maximum load factor.