Memory efficient vector of strings

Question

Is it possible in theory to have a memory efficient STL (and/or Boost) vector of strings using some allocators such that:

using String = std::basic_string<char, std::char_traits<char>, SomeAllocMaybe;
using Vector = std::vector<String, SomeOtherAllocMaybe>;

Vector vec( /* an allocator eventually */ );
vec.emplace_back("first string longer than SSO");
vec.emplace_back("second string");
vec.emplace_back("third string longer than SSO");

Will result in having in memory only one compact contiguous block of data like this:

"first string longer than SSO'\0'second string'\0'third string longer than SSO'\0'"

Answer 1

You can do that using boost interprocess allocators.

Answer 2

No, this is not possible with a std::vector and a std::basic_string. A std::vector holds a contiguous sequence of elements (std::basic_strings), and std::basic_string is not going to be laid out in memory in this particular way. It stores the size information, or at least the tag bit to differentiate long strings and short strings.

If you want the contiguous memory, directly use one std::basic_string instead. Appending one character to strings is of amortized constant time complexity, and thus concatenating strings will be efficient.