Optimizing small strings for a vector?

Question

I know that several (all?) STL implementations implement the "small string" optimization, where instead of storing the usual 3 pointers for start, end and capacity, the string will store the actual character data in the memory used for pointers if sizeof (characters) <= sizeof (pointers). I am in a situation where I have many small vectors with the element size <= sizeof (pointer). I cannot use arrays with a fixed size, since vectors must be able to dynamically resize and can potentially grow quite large. However, the average (not average) size of the vectors will be only 4-12 bytes. Therefore, the optimization of the "small line", adapted to the vectors, would be useful to me. Is there such a thing?

I am thinking about flipping my own just brute force by converting a vector to a string, i.e. providing a vector interface for the string. A good idea?

Answer 1

You can take SmallVector from LLVM. (only the header located in LLVM \ include \ llvm \ ADT)

Answer 2

Boost 1.58 has just been released, and the Container library has a small_vector class based on LLVM SmallVector .

There is also a static_vector that cannot exceed the originally specified size. Both containers have only a header.

The facebook folly library also contains some amazing containers.

It has a small_vector that can be customized using a template parameter to act like boost static or small . It can also be configured to use small integer types for its internal bookkeeping, which, provided that they are facebook, is not surprising :)

Work has been done on creating a cross-platform library, so Windows / MSVC support should land someday ...

Answer 3

If T is a POD type, why not basic_string instead of vector ??

Answer 4

This was discussed a few years ago (and a few names in this thread may look a little familiar :-)), but I am not aware of the existing implementation. I do not think that I will try to adapt std :: string to the task. The exact type requirements over which std :: basic_string are not stated, but the standard is pretty clear that it is intended only for something that is very similar to char . For types that differ significantly from each other, it can still work, but it's hard to say what will happen - it was never intended and probably has not been tested with many types other than small integers.

When you get started, implementing std::vector from scratch (even including a little vector optimization) won't be terribly difficult.