How is stored a vector 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?

http://stackoverflow.com/questions/1986966/does-s0-point-to-contiguous-characters-in-a-stdstring — fatihk, Oct 14 '15 at 17:32
`std::string` behaves like a pointer in your example. There is small string optimization where small strings (small means ~20-40 characters) are inside the `std::string` itself. If you require all characters to be in contiguous memory you will have to use a `vector` and do it manually. — nwp, Oct 14 '15 at 17:35
thank you, that kind of information are precious, because string could do background thing, that's why I asked this. And what you say is that it does some optimization that could make it not contiguous ? — FreeYourSoul, Oct 14 '15 at 17:37
A `std::string` is dynamically allocated, and is guaranteed to have *local* contiguous memory at all times (meaning the individual string will have contiguous memory). However, this says nothing about it's contiguity within your `vect` of `string`s. I'm not aware of a way to guarantee contiguity in this way. — Colin Basnett, Oct 14 '15 at 17:38
@cmbasnett the constructor of `std::string` has an optional template argument for an `std::allocator`. You can define a memory pool and each time you create a `string` it will be allocated in there. You can make sure that all string are in a contiguous memory block. — Manos Nikolaidis, Oct 14 '15 at 17:40

Manos Nikolaidis · Accepted Answer · 2015-10-14T17:50:10.500

10

Each string will be an instance of class string and that instance will contain a char*.
The string objects in the vector will be in contiguous memory.
The chars of each string will be in contiguous memory
All The chars of all the strings will not be in contiguous memory, unless you define a custom std::allocator for the strings
The location in memory of the strings may change when you increase the size of the vector or call shrink_to_fit
The location in memory of the chars of each string may change when you increase the size of the string
The vector will not be reallocated if you modify or remove one of the strings
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*

edited Oct 14 '15 at 17:50

answered Oct 14 '15 at 17:33

Manos Nikolaidis

21,608
12
74
82

So a string is actually just an encapsulation of a char* – FreeYourSoul Oct 14 '15 at 17:35
It's templated but if you are using just default std::string then yes. – Connor Hollis Oct 14 '15 at 17:36
2

@FreeYourSoul It has more stuff like capacity and size, not just the `char *`. – nwp Oct 14 '15 at 17:37

score 3 · Answer 2 · answered Oct 14 '15 at 17:35

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.

score 3 · Answer 3 · answered Oct 14 '15 at 18:15

The implementation of string is implementation defined and has actually changed between different versions of certain compilers (for example from gcc 4.9 to 5.0). The is absolutely no guarantee that the chars in consecutive strings are contiguous in memory, even if you use a custom allocator.

So if you really need the chars to be contiguous in memory, you must use just a vector<char>.

How is stored a vector in memory

3 Answers3