How is stored a vector<string> in memory

Question

I am working on a project where I absolutly need to have data contiguous in memory. I want to store some (maximum 100) string (I don't know the actual size of each string). So I will create a vector of string of 100 elements.

std::vector<std::string> vect;
vect.reserve(100)

But a String can be of any size. So how does it work? Is my vector reallocated everytime I change a string? Or is a std::string simply like a pointer to the first character of the string like a char* would be for a C string?

Answer 1

1. Each string will be an instance of class string and that instance will contain a char*.
2. The string objects in the vector will be in contiguous memory.
3. The chars of each string will be in contiguous memory
4. All The chars of all the strings will not be in contiguous memory, unless you define a custom std::allocator for the strings
5. The location in memory of the strings may change when you increase the size of the vector or call shrink_to_fit
6. The location in memory of the chars of each string may change when you increase the size of the string
7. The vector will not be reallocated if you modify or remove one of the strings
8. There is something called Small String Optimization. If that comes into play the chars of each string will be stored within the string instead of another location pointed to by char*

Answer 2

The data in std::vector is laid out contiguosly. However std::strings implementation does not guarantee that the memory holding the character array is stored locally to the class itself. How could it? Like you said you don't know how large the string will be.

A lot of array like structures have a layout like follows:

class string
{
    T * begin; 
    T * end;
    T * capacity;
}

Which means that your vector of 100 strings will have 100 instances of a class layout that POINTS to the memory where the string is stored.

Now if you need to pack memory allocations as tightly as possible and still want to use std::string you can write a custom allocator.

Maybe you can write the string data into a char array and have a second container that stores the lengths of each individual string + NULL terminator.