Menu
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.
830
std::string has a huge number of string-related functions which make it easy to manipulate strings. 2. std::vector, on the other hand, is guaranteed to be contiguous in memory -- that is, &data[x + 1] = &data[x] + sizeof(data[x]). std::string has NO guarantee that it is contiguous in memory.
As mentioned above, std::vector is a templated class that represents dynamic arrays. std::vector typically allocates memory on the heap (unless you override this behavior with your own allocator). The std::vector class abstracts memory management, as it grows and shrinks automatically if elements are added or removed.
Yes, std::string (since C++11) is able to be moved i.e. it supports move semantics.
Vectors are assigned memory in blocks of contiguous locations. When the memory allocated for the vector falls short of storing new elements, a new memory block is allocated to vector and all elements are copied from the old location to the new location. This reallocation of elements helps vectors to grow when required.
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.
115
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
