C++ Vector Memory Usage - Is it ever freed?

I know that vectors double in size whenever their capacity() is exceeded. This operation takes some time which is why vectors are supposed to hav开发者_Python百科e amortized constant time for addition of elements with push_back().

1. What I'm wondering is... what happens when a vector shrinks so that its size() is less than half of the capacity().

2. Do vectors ever relinquish the memory which they use, or is it just gone until the vector is destroyed?

It could be a lot of wasted memory if they don't shrink in size ever, but I've never heard of them having that feature.

---

No, it is never freed (i.e. capacity is never reduced) until destruction. A common idiom for freeing up some memory is to create a new vector of the correct size, and use that instead:

std::vector<type>(originalVector).swap(originalVector);

(inspired by "More Exceptional C++", Item #7)

---

If you want to make sure your vector uses as little space as possible, you can say:

std::vector<Foo>(my_vector).swap(my_vector);

You could also call the shrink_to_fit() member function, but that is just a non-binding request.

---

Erasing elements from a vector or even clearing the vector entirely does not necessarily free any of the memory associated with that element. This is because the maximum size of a vector since its creation is a good estimate of the future size of the vector.

To use the shrink to fit idiom:

std::vector<int> v;
//v is swapped with its temporary copy, which is capacity optimal
std::vector<int>(v).swap(v);

Solution in C++0x

In C++0x some containers declare such idiom as function shrink_to_fit(), e.g. vector, deque, basic_string. shrink_to_fit() is a non-binding request to reduce capacity() to size().

---

They don't shrink in size.

It would not be generally useful to de-allocate the memory.

For example, a vector could shrink now but then grow again later. It would be a waste to deallocate the extra memory (and copy all the elements in the memory) only to reallocate it later.

If a vector is shrinking, there is also a good chance the vector will be shrunk to empty and then destroyed. In that case deallocating as it shrinks would be a waste of time as well.

It can also be a useful optimization to reuse a vector object so as to avoid allocating/dealocating the contents. That would be ruined by introducing deallocations as it shrinks.

Basically, most of the time deallocating the extra memory isn't worth it. In the few case where it is, you can specifically ask for dealocation.

---

The memory is gone until the vector is destroyed.