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'"

and in your scenario what happens when you do vec[1].append("boom")? — bolov
– bolov, Commented Oct 9, 2019 at 9:33
this isnt really a vector, more like a concatenated string, and this already exitsts, it is std::string ;) — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Oct 9, 2019 at 9:39
In theory, sure. However, this requires too many assumptions about how compilers implement std::string. If you really need the memory layout you've specified, it's probably worth rolling your own class for it. GCC for example: stackoverflow.com/q/5058676/5343120 — Harrand
– Harrand, Commented Oct 9, 2019 at 9:40
It is possible in theory, yes. But what is your need really ? do you just need the strings to be lying around in the same memory segment or do you wan't to avoid 'the pointer deref' as well ? In the first case - appending to a string might then move to different memory segment. — darune
– darune, Commented Oct 9, 2019 at 9:42
Using STL/Boost would take a lot of assumptions about the underlying implementation of those classes. I would rather implement it myself. — khanh
– khanh, Commented Oct 9, 2019 at 9:57

Maxim Egorushkin · Accepted Answer · 2019-10-09 09:55:25Z

2

You can do that using boost interprocess allocators.

answered Oct 9, 2019 at 9:55

Maxim Egorushkin

138k19 gold badges201 silver badges293 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

nyarlathotep108 Over a year ago

Can you be more specific? Looks like there are many different types of facilities in the library, and different ways to compose them.

L. F. · Accepted Answer · 2019-10-09 09:55:34Z

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.

answered Oct 9, 2019 at 9:55

L. F.

20.9k9 gold badges57 silver badges85 bronze badges

1 Comment

nyarlathotep108 Over a year ago

I think I can be fine if between strings there are some small additional information. Cannot say the same about having the whole SSO block between them, but let's assume it is fine as well.

darune · Accepted Answer · 2019-10-09 10:13:40Z

0

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.

answered Oct 9, 2019 at 10:13

darune

11.5k2 gold badges32 silver badges81 bronze badges

Collectives™ on Stack Overflow

Memory efficient vector of strings

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related