Movatterモバイル変換

This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofC++17 status.

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

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

Priority:3

View otheractive issues in [unord.req].

View all otherissues in [unord.req].

View all issues withC++17 status.

Discussion:

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

For a container withmax_load_factor of1,reserve(n) is equivalent torehash(ceil(n/1)), ie.rehash(n).rehash(n) requires that the bucketcount is>= n, so it can ben (Table 103). The rule is thatinsertshall 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, soinsert 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/BS <= MLF * BB >= 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 fora.rehash(n) to:

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

2. In 23.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.