Memory efficient vector of strings

user_3074280 0
Viewed 220

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'"
allocator vector c++ string
3 Answers
user_4120800

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.

user_97165970

Yes, that is definately possible - that being said, you probably do not wan't the same allocator/memory segment for both as it complicates things - mainly that when the vector needs reallocation you would have to move plus possible reallocate everything. Therefore you would need to take special care which again you would need to tailer into your specific need. So it's a lot simpler to just consider the strings heap alone and then you do not need to worry about the configure to your needs part. Im assuming the strings needs to be worked with with and aren't just const - because that is special case that could be handled very differently.

user_22615380
Related