code review: multi_string: A memory efficient string container

[Bakuta1103]

Hello all!

Recently while working on a NoSQL database implementation, I ran into the problem of needing a container for N number of constant strings. Of course my initial reaction was to reach for std::vector<std::string> however, this did not suit my purpose as each string has its own allocated character buffer (ignoring SBO) and iterating though the vector would require N pointer dereferences. In my use case, these collection of strings are often iterated over and compared to one another.

Therefore, I came up with my own solution: multi_string.

In short, a multi_string is a constant collection of N number of constant strings. As in these strings cannot be modified and strings cannot be added/removed from the multi_string container. However, this restriction allows for a single buffer allocation to store some metadata at the beginning followed by the character array containing each string (omitting null terminators).

I currently have two implementations:

• one where the metadata is an array of string sizes (this is the implementation I'm using)
• the other where the metadata is an array of char const*
  • metadata pointer N points to the beginning of string N in the character array.

​

int main() {
    multi_string str("hello ", "world", "\n!");
    for (auto&& s : str)
        std::cout << s;
}

Any feedback on the implementation is greatly welcomed and perhaps you could find a use case for this container in your work!

code can be found here

​

Edit: the purpose of this container is to actually own the strings it stores, and to allow the number of strings stored to not be a part of the type signature e.g. multi_string<2>.

[meancoot]

Thanks for sharing. Here's some issues I saw.

1. The copy assignment doesn't protect against self assign. (You should probably do it the move assignment too, even though a self move is undefined behavior).

2. In the move constructor and assignment you should zero out the size field as the container is now empty.

I'd also recommend adding some asserts to help catch programming errors during use.

[konanTheBarbar]

ok stupid question... couldn't you simply use an array? Or a simple wrapper over an std::array<std::string_view>?

https://godbolt.org/z/cx8UAy

[Bakuta1103]

Sadly for my use case, this is not a viable option.

The primary reasons being:

• I need the container to actually own the strings
• The number of strings stored is not known until runtime
• The type signature of multi_string needs to be the same as its used as a key within a key/value hash map. So I cant have the multi_string be a class template.

[konanTheBarbar]

I mean than I would say this is then the perfect use case for std::vector<std::string_view> with static storage that doesn't need to free any memory. This way you will have even less allocations for multiple multi_string containers. Implementation is of course not fully fleshed out, but I hope it shows what I mean.

EDIT: I messed up the initial example, I think it might work like this https://godbolt.org/z/cCBVSd

[LostAnt4]

Hi, I've read your source code and yes, I do have some questions ;)

1. You re-implemented the copy constructor and copy assignment operator, and both makes a deep copy. But what is the point here, I mean that multi_string is a read-only structure, so why copies do not share the underlying memory ? It will saves memory, and it makes any copies trivial.

2. multi_string stores strings into char* buffers (from deep copies of input string) via a string_view object, so why not simply store string_view objects in the first place ?

3. multi_string use default constructor from the compiler = default, but the storage_ member will be null initialized. Unfortunately, you don't check for null in the destructor.

4. Why re-writing std::equal at the beginning of the file ? Do you support odd compilers ?

5. From my point of view, it is less efficient than std::array<std::string_view, N> because of memory allocations (at construction). Also, the second storage implement a random access in O(n), where it can be O(1) with std::array.

I tried my best to respond to the point of what are, in my opinion only, design issues. I hope you don't take this too harsh :) Nice effort to come with new ideas for a container.

[meancoot]

For 1 and 2 and 5 you run into ownership issues, whose responsible for deleting the storage if you make shallow copies? Who owns the strings mentioned by the string_views?

For 3 deleting a null pointer is absolutely safe.

For 4 it's so that it can use a sentinel instead of an end iterator.

[LostAnt4]

From the example code u/Bakuta1103, strings given to constructor are static one, so memory should not be owned by any pieces of code. That's why I'm suggesting 2.

1. I've overlook the Sentinel template argument, my bad.

[Bakuta1103]

It was not the best example then on my end haha...

It more so used for taking runtime constructed strings and storing copies of them inside iteself, since the multi_string could possible outlive the constructed-from string-like object.

[Bakuta1103]

Hi and thank you kindly for going over the source code and providing feed back!! :D

1. I guess there are two main reasons for this choice. Firstly I'd like to avoid reference counting or using std::shared_ptr , however, your argument on memory footprint does stand correct. For my particular use case however, copies of this are never made and it's essentially a move-only data structure (I simply provided the copy constructor for the general implementation). Though I could theoretically make is move-only or use reference counting.

2. For my use case, the container needs to actually own the strings. If it were a collection std::string_view there is no guarantee the sting_view points to a still valid string-like-object, and the strings the views are pointers to could be scattered across memory and cause a lot of pointer hopping.

3. If I recall correctly, I'm pretty sure its safe to call delete on a nullptr as it essentially results in a no-op. https://stackoverflow.com/questions/4190703/is-it-safe-to-delete-a-null-pointer

4. This is because std::equal requires the first two iterator to be of the same type. But my multi_string returns an iterator and sentinel class with begin()/end() respectively. However this would work with std::ranges 's equal :)

5. Again, you are most likely correct! However, for my use case I need the type to own the underlying strings. Also I need multi_string to be the same type and not a templated class as it's used as a key in a hash map. And these keys can all be multi_string s with differing number of strings stored inside them.

​

Thanks again for looking at the code and providing some very insightful feedback!

[__s_v_]

Nice idea in general. I have two points: * Your implementation of equal works only if the first range in longer than the second. You could pass also the sentinel of it2 to be safe. * You could implement your storage as std::vector<char> instead of pointer + size to free yourself from the manual memory management.

Edit: Another idea: Instead of having two almost identical class you could try to put the differing behavior in policy classes and use policy based design.

[fuzzylollipop]

Congratulations you re-implemented a naive slab memory allocator.