small string optimization for vector?

Question

I know several (all?) STL implementations implement a "small string" optimization where instead of storing the usual 3 pointers for begin, end and capacity a string will store the actual character data in the memory used for the pointers if sizeof(characters) <= sizeof(pointers). I am in a situation where I have lots of small vectors with an element size <= sizeof(pointer). I cannot use fixed size arrays, since the vectors need to be able to resize dynamically and may potentially grow quite large. However, the median (not mean) size of the vectors will only be 4-12 bytes. So a "small string" optimization adapted to vectors would be quite useful to me. Does such a thing exist?

I'm thinking about rolling my own by simply brute force converting a vector to a string, i.e. providing a vector interface to a string. Good idea?

Answer 1

It was discussed years ago (and a few of the names in that thread may look a bit familiar :-) ), but I don't know of an existing implementation. I don't think I'd try to adapt std::string to the task. The exact requirements on the type over which std::basic_string aren't well stated, but the standard is pretty clear that it's only intended for something that acts a lot like char. For types that are substantially different, it might still work, but it's hard to say what would happen -- it was never intended for, and probably hasn't been tested with many types other than small integers.

When you get down to it, implementing std::vector from scratch (even including a small vector optimization) won't be terribly difficult.

Answer 2

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

Answer 3

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