Title
std::vector's reallocation policy still unclear
Status
open
Section
[vector.capacity]
Submitter
Daniel Krügler

Created on 2009-04-20.00:00:00 last changed 52 months ago

Messages

Date: 2020-07-17.22:37:26

[ This is a minimum version. I also suggest that the wording explaining the allocation strategy of std::vector in [vector.capacity]/3 and /6 is moved into a separate sub paragraph of [vector.capacity] before any of the prototype's are discussed, but I cannot provide reasonable wording changes now. ]

  1. Change [vector.capacity]/6 as follows:

    It is guaranteed that no reallocation takes place during insertions or erasures that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity().

  2. Change [vector.modifiers]/4 as follows:

    Effects: The capacity shall remain unchanged and no reallocation shall happen. Invalidates iterators and references at or after the point of the erase.

Date: 2020-07-15.00:00:00

[ 2020-07-17; Priority set to 3 in telecon ]

Date: 2020-05-15.00:00:00

[ 2020-05-08; Reopen after reflector discussions ]

"correct as written" has been disputed.

Date: 2010-10-21.18:28:33

[ 2009-10 Santa Cruz: ]

Mark as NAD. Rationale: there is no consensus to clarify the standard, general consensus that the standard is correct as written.

Date: 2010-10-21.18:28:33

[ Batavia (2009-05): ]

Bill believes paragraph 1 of the proposed resolution is unnecessary because it is already implied (even if tortuously) by the current wording.

Move to Review.

Date: 2009-04-20.00:00:00

I have the impression that even the wording of current draft N2857 does insufficiently express the intent of vector's reallocation strategy. This has produced not too old library implementations which release memory in the clear() function and even modern articles about C++ programming cultivate the belief that clear is allowed to do exactly this. A typical example is something like this:

const int buf_size = ...;
std::vector<T> buf(buf_size);
for (int i = 0; i < some_condition; ++i) {
  buf.resize(buf_size);
  write_or_read_data(buf.data());
  buf.clear(); // Ensure that the next round get's 'zeroed' elements
}

where still the myth is ubiquitous that buf might be allowed to reallocate it's memory inside the for loop.

IMO the problem is due to the fact, that

  1. the actual memory-reallocation stability of std::vector is explained in [vector.capacity]/3 and /6 which are describing just the effects of the reserve function, but in many examples (like above) there is no explicit call to reserve involved. Further-more [vector.capacity]/6 does only mention insertions and never mentions the consequences of erasing elements.
  2. the effects clause of std::vector's erase overloads in [vector.modifiers]/4 is silent about capacity changes. This easily causes a misunderstanding, because the counter parting insert functions described in [vector.modifiers]/2 explicitly say, that

    Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

    It requires a complex argumentation chain about four different places in the standard to provide the — possibly weak — proof that calling clear() also does never change the capacity of the std::vector container. Since std::vector is the de-facto replacement of C99's dynamic arrays this type is near to a built-in type and it's specification should be clear enough that usual programmers can trust their own reading.

History
Date User Action Args
2020-07-17 22:37:26adminsetmessages: + msg11380
2020-05-08 17:28:22adminsetmessages: + msg11272
2020-05-08 17:28:22adminsetstatus: nad -> open
2010-10-21 18:28:33adminsetmessages: + msg734
2010-10-21 18:28:33adminsetmessages: + msg733
2010-10-21 18:28:33adminsetmessages: + msg732
2009-04-20 00:00:00admincreate