std::vector and std::string reallocation strategy

Question

What is the reallocation strategy used for std::string and std::vector in GCC's implementations?

I'm interested in the specific strategy employed: When I append items to a vector (or chars to a string) it may exceed the reserved size and then a reallocation will occur, but what will be the new size as a function of the old one? In case of deleting elements, what is the threshold to actually reallocate and free memory (and again what will be the new size)?

Answers for other compilers will be appreciated as well.

Answer 1

Look at the function _M_check_len in bits/stl_vector.h. It contains:

const size_type __len = size() + std::max(size(), __n);

So the basic strategy when you append n elements is either double the size or increase by n, whichever is largest. pop_back never deallocates. libc++ (LLVM) does exactly the same.

Reading the code is the only way you'll find out the strategies for string, deallocation, etc.