algorithm

I’ve always wondered what data structures are used by text editors to work with text so fast and smoothly, especially when the user is typing in the middle of a large document. I had already known about such data structures as ropes and gap buffers or splitting the document into smaller chunks (lines or paragraphs), but the implementation of a QTextDocument in Qt got my attention because it looked like the whole document content were stored in a huge continuous string:

class Q_GUI_EXPORT QTextDocumentPrivate : public QObjectPrivate
{
    // ...

private:
    QString text; // <-- the whole content, including tables and images, is indeed stored here :-)
};

The fact that this algorithm is absolutely undocumented and Google couldn’t find anything about it on the Internet, encouraged me to study the source code and write this blog post.