Section: 26.2.7 [unord.req] Status: C++17 Submitter: Daniel James Opened: 2012-05-07 Last modified: 2017-07-30
View other active issues in [unord.req].
View all other issues in [unord.req].
View all issues with C++17 status.
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 (26.2.7 [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
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]
This wording is relative to N3485.
In 26.2.7 [unord.req] Table 103 — Unordered associative container requirements, change the post-condition
in the row for
a.bucket_count() > a.size() / a.max_load_factor()and
a.bucket_count() >= n.
In 26.2.7 [unord.req]/p15 change
emplacemembers shall not affect the validity of iterators if
(N+n) < z * B, where
Nis the number of elements in the container prior to the insert operation,
nis the number of elements inserted,
Bis the container's bucket count, and
zis the container's maximum load factor.