Title
Unordered containers' reserve(n) reserves for n-1 elements
Status
c++17
Section
[unord.req]
Submitter
Daniel James

Created on 2012-05-07.00:00:00 last changed 80 months ago

Messages

Date: 2015-05-22.20:19:09

Proposed resolution:

This wording is relative to N3485.

  1. In [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 [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.
Date: 2015-05-22.20:19:09

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

Date: 2012-02-12.00:00:00

[ 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

Date: 2013-03-15.00:00:00

[ 2013-03-15 Issues Teleconference ]

Moved to Open.

Howard to provide rationale and potentally revised wording.

Date: 2013-03-16.00:00:00

[ 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
Date: 2012-05-07.00:00:00

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 ([unord.req] p15). But for this case the two sides of the equation are equal, so insert can affect the validity of iterators.

History
Date User Action Args
2017-07-30 20:15:43adminsetstatus: wp -> c++17
2015-10-27 16:52:45adminsetstatus: ready -> wp
2015-05-22 20:19:09adminsetmessages: + msg7453
2015-05-22 20:19:09adminsetstatus: open -> ready
2014-02-13 21:00:33adminsetmessages: + msg6846
2013-03-18 14:33:00adminsetmessages: + msg6410
2013-03-18 13:02:36adminsetstatus: new -> open
2013-03-16 17:15:26adminsetmessages: + msg6386
2013-03-16 17:15:26adminsetmessages: + msg6385
2012-05-07 00:00:00admincreate