std::vector resize downward

Question

the C++ standard seems to make no statement regarding side-effects on capacity by either resize(n), with n < size(), or clear().

It does make a statement about amortized cost of push_back and pop_back - O(1)

I can envision an implementation that does the usual sort of capacity changes ala CLRS Algorithms (eg double when enlarging, halve when decreasing size to < capacity()/4). (Cormen Lieserson Rivest Stein)

Does anyone have a reference for any implementation restrictions?

Answer 1

Calling resize() with a smaller size has no effect on the capacity of a vector. It will not free memory.

The standard idiom for freeing memory from a vector is to swap() it with an empty temporary vector: std::vector<T>().swap(vec);. If you want to resize downwards you'd need to copy from your original vector into a new local temporary vector and then swap the resulting vector with your original.

Answer 2

Actually, the standard does specify what should happen:

This is from vector, but the theme is the same for all the containers (list, deque, etc...)

23.2.4.2 vector capacity [lib.vector.capacity]

void resize(size_type sz, T c = T());

6) Effects:

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

That is to say: If the size specified to resize is less than the number of elements, those elements will be erased from the container. Regarding capacity(), this depends on what erase() does to it.

I cannot locate it in the standard, but I'm pretty sure clear() is defined to be:

void clear()
{
    erase(begin(), end());
}

Therefore, the effects clear() has on capacity() is also tied to the effects erase() has on it. According to the standard:

23.2.4.3 vector modifiers [lib.vector.modifiers]

iterator erase(iterator position);
iterator erase(iterator first, iterator last);

4) Complexity: The destructor of T is called the number of times equal to the number of the elements erased....

This means that the elements will be destructed, but the memory will remain intact. erase() has no effect on capacity, therefore resize() and clear() also have no effect.

Answer 3

The capacity will never decrease. I'm not sure if the standard states this explicitly, but it is implied: iterators and references to vector's elements must not be invalidated by resize(n) if n < capacity().

Answer 4

Thank you, but I know very well how to "shrink to fit." Had I been interested in that I would have asked explicitly about that.

The question was actually a performance question - I needed a guarantee that capacity() was monotonically increasing under operations push_pack, pop_back, clear, and resize. (ie no reallocation was for done for clear resize downward).

I knew that Dinkumware GCC and SGI stl did not "recapacitize" downward but did not quite find in the standard a statement to that effect. As Gman stated "I cannot locate it in the standard, but I'm pretty sure clear() is defined to be: ..."

I think the behaviour of clear is to be ascertained from table 67 in the sequences section on page 469

avakar's "iterators and references to vector's elements must not be invalidated by resize(n) if n < capacity()." ["and the iterator points to an element not destroyed by the resize" as the iterator while not made memory inaccessable is certainly invalidated when the element is destroyed] and Gmans "4) Complexity: The destructor of T is called the number of times equal to the number of the elements erased...." have answered the question.

My concern was that was that the requirement was O(n) versus exactly n.

Thank you all for the extra sets of eyes on the standard.