Q:

How to create a mutable string class that can be used as an actual string?

I want to create a python class that represents a string, but can be modified efficiently.
I thought about implementing a treelike data structure, but I don't know how to make it behave like a string, such that it can be used in all kind of string functions, for instance in regular expressions.
Of course one could construct a string from the data structure each time it is needed, but that isn't very efficient, and wastes the efficiency of the data structure.
Any ideas?

A:

I think one needs to implement both "sequence" and "buffer" Python protocols, which are only available from C. There is one library I know about which does this, though it's a bit dated:
https://code.google.com/p/gapbuffer/

