Memory-efficient C++ strings (interning, ropes, copy-on-write, etc)

Question

My application is having memory problems, including copying lots of strings about, using the same strings as keys in lots of hashtables, etc. I'm looking for a base class for my strings that makes this very efficient.

I'm hoping for:

• String interning (multiple strings of the same value use the same memory),
• copy-on-write (I think this comes for free in nearly all std::string implementations),
• something with ropes would be a bonus (for O(1)-ish concatenation).

My platform is g++ on Linux (but that is unlikely to matter).

Do you know of such a library?

Answer 1

If most of your strings are immutable, the Boost Flyweight library might suit your needs.

It will do the string interning, but I don't believe it does copy-on-write.

Answer 2

copy-on-write (I think this comes for free in nearly all std::string implementations)

I don't believe this is the case any longer. Copy-on-write causes problems when you modify the strings through iterators: in particular, this either causes unwanted results (i.e. no copy, and both strings get modified) or an unnecessary overhead (since the iterators cannot be implemented purely in terms of pointers: they need to perform additional checks when being dereferenced).

Additionally, all modern C++ compilers perform NRVO and eliminate the need for copying return value strings in most cases. Since this has been one of the most common cases for copy-on-write semantics, it has been removed due to the aforementioned downsides.

Answer 3

One way is to create an invariant key class which contains a pointer to the string and comparison operators to string. Those string pointers will need to be managed in some kind of global map or reference counted map.

A less laborious but more opaque solution may be to key upon boost::shared_pointer, in this way on the pointers will be copied rather than the strings.

You will need to be able to map std::string -> boost::shared_pointer during lookup, so I would make that a function with a map, in simple terms

boost::shared_pointer<std::string> getsharedstring(std::string &s)
{
    typedef std::map<std::string, boost::shared_pointer<std::string>> ptrmap_t;
    static ptrmap_t m; // just for convenience for the example

    ptrmap_t::iterator it = m.find(s);

    if (it != m.end())
        return it->second;

    boost::shared_pointer<std::string> ptr(new std::string(s));
    m[s] = ptr;
    return ptr;
}

I haven't compiled this so forgive any typos.

Answer 4

Take a look at The Better String Library from legendary Paul Hsieh

Answer 5

Andrei Alexandrescu's 'Policy Based basic_string implementation' may help.