std::vector resize downward

问题:

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 (e.g. double when enlarging, halve when decreasing size to < capacity()/4). (Cormen Lieserson Rivest Stein)

Does anyone have a reference for any implementation restrictions?

回答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.

Updated: C++11 added a member function shrink_to_fit() for this purpose, it's a non-binding request to reduce capacity() to size().

回答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.

回答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().

回答4:

As i checked for gcc (mingw) the only way to free vector capacity is what mattnewport says. Swaping it with other teporary vector. This code makes it for gcc.

template<typename C> void shrinkContainer(C &container) {
    if (container.size() != container.capacity()) {
        C tmp = container;
        swap(container, tmp);
    }
    //container.size() == container.capacity()
}