When will the capacity of a vector reduce?

Question

(This question is not about the shrink_to_fit tricks (using swap() or shrink_to_fit() in C++11).)

If I use a vector only through insert(), erase(), push_back(), pop_back(), clear(), when the capacity is not enough, it will increase and reallocation for the vector will occur. But under what circumstances will the capacity reduce? And will capacity reduction necessarily cause reallocation?

Answer 1

The standard guarantees that no references/iterators will be invalidated during e.g. pop_back. From [container.requirements.general]:

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

And there is no specification otherwise for e.g. pop_back.

So that implies that reallocation cannot occur.¹

---

1. It has been suggested in comments to another answer that perhaps the memory corresponding to a popped element could be freed, which wouldn't invalidate any references to "live" elements.

But then that would prevent the array from regrowing, as the standard specifically says that insertions cannot provoke a reallocation until the size exceeds the capacity. From [vector.capacity]:

It is guaranteed that no reallocation takes place during insertions 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().