std::string implementation

[musicfreak]

Just out of curiosity, how is the std::string type implemented? In other words, what are the internals? Is it an immutable C string? Is it an over-allocated char[]? How does it work? Any insight would be appreciated.

(If you were wondering, I'm building an interpreter/runtime, and I need efficient strings for what I'm doing, and so I need to know whether I need to use my own implementation or not.)

Thanks in advance.

[weaknessforcats]

To quote P.J.Plaugher fo Dinkumware who provides STL templates for many major compilers such as Visual Studio.NET: "The templates are optimized for speed. If you think you can do it faster, then think three times."

That said, with the templates optimized for speed with footprint secondary, the string only has to support the methods defined by the ANS/ISO C++ Standard.

That said, the internal implementation can vary by whoever provides your STL templates.

One implementation looks like this:

class basic_string
{
    T str[19];
    T* pstr;
    //etc...
};

Here memory allocation takes a lot of time so this implementation did a study and found that most strings are 19 elements or less so better to allocate that much right off when the string is created. Later, if more is needed, a heap allocation can be made and the 19 elements copied to it. From then on the 19 element array is not used.

Addtionally, if a string occupies, say 100 elements and is reduced to 50 elements, the allocation is not re-done to 50. Instead it stays at 100 in case you change your mind and need more later. Again, by not re-allocating the speed increases at the expense of more memory, speed increases.

In every analysis I have seen than compares the STL string to the C string library functions, the STL string is markedly faster.

[musicfreak]

Very in-depth analysis, thank you. I never knew strings were that fast. (Actually, my implementation would have been very similar, but now I know not to bother.)

Thanks again!