CODEWITHSUNDEEP
c++stl
updogliu
updogliu

Reputation: 6255

When will the capacity of a vector reduce?

(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?

Upvotes: 4

Views: 2324

Answers (4)

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272457

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

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

Upvotes: 9

Alok Save
Alok Save

Reputation: 206508

The C++ Standard doesn't need std::vector to reduce the capacity() at any point of time during its existence. This is strictly implementation dependent So Implementations might on their own but you shouldn't rely on that behavior.

Upvotes: 0

nullpotent
nullpotent

Reputation: 9260

Nope, pop_back() doesn't do it. Others certainly don't. The only way is the way you mentioned. 

template< typename T, class Allocator >
void shrink_capacity(std::vector<T,Allocator>& v)
{
   std::vector<T,Allocator>(v.begin(),v.end()).swap(v);
}

And shrink_to_fit() in c++11

Upvotes: 5

Greg
Greg

Reputation: 1660

It could be reduced when usage is below 1/4 of capacity (this will give amortized constant cost of reallocation). But STL implementation is not obligated to reduce vector anytime, when you use only methods you have listed.

Upvotes: 0

Related Questions