Space reallocated in vector::resize() when resized

问题:

According to Stroustrup : The C++ programming language :-

"When a vector is resized to accommodate more (or fewer) elements, all of its elements may be moved to new locations."

Is this holds true, even if the vector is re-sized to smaller size ?

回答1:

Case 1: If the new size being requested is greater than the current std::vector::capacity() then all elements will be relocated.
Case 2: If the new size being requested is lesser than the current std::vector::capacity() then there will be no relocation of elements.

---

Standerdese Evidence:

The standard defines effect of vector::resize() as:

C++11 Standard 23.3.6.3/12 vector capacity:

void resize(size_type sz, const T& c);

Effect:

if (sz > size())
     insert(end(), sz-size(), c);
else if (sz < size())
    erase(begin()+sz, end());
else
; // do nothing

As @DavidRodríguez-dribeas correctly points out, Iterator invalidation rules for std::vector::insert() operation are:

23.3.6.5 vector modifiers

1 [insert,push_back,emplace,emplace_back]

Remarks: 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.

Essentially this means: All iterators and references before the point of insertion will be unaffected, unless the new container size is greater than the previous capacity because in such a scenario all elements might be moved to new locations thus invalidating pointers/iterators to original location.Since resize() only erases/inserts elements at the end of the container^{[Note 1]}.The governing factor boils down to size being requested as against current capacity.

Hence the Case 1 result.

In Case 2 std::vector::erase() will be called and the invalidation rule in this case is:

23.3.6.5 vector modifiers

iterator erase(const_iterator position);

3 Effects: Invalidates iterators and references at or after the point of the erase.

Since ^{[Note 1]}, elements will be only removed at end and there is no need of relocation of all elements.

回答2:

...elements may be moved to new locations."

Notice how it says may be moved. So that would imply that it depends what what kind of a resize it is.

回答3:

Iterators in a vector are invalidated for two reasons. An element is inserted/removed before the location of the iterator (1) or the whole buffer is relocated (2) if the vector needs to grow it's capacity. The key here is a change to the capacity().

Because resize() only inserts/removes from the end of the container. When the vector shrinks only those iterators referring to the elements being removed become invalidated. When the vector grows no iterator will become invalid if the new size is smaller than capacity(), and all iterators will be invalidated if the new size is larger.

Since Als provided incorrect evidence¹, I am adding here the correct quotes:

23.3.6.5 vector modifiers

1 [insert,push_back,emplace,emplace_back]

Remarks: 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.

2 [erase]

Effects: Invalidates iterators and references at or after the point of the erase.

Similar quotes can be found in C++03.

---

¹ Avoiding to duplicate the quote that dictates the equivalence of resize to either insert or erase. Which is right.

回答4:

The answer in the body of the question ""When a vector is resized to accommodate more (or fewer) elements, all of its elements may be moved to new locations.""