What's a better way to store text for a word processor?

Question

The usual way is to store the characters in a string, but because while writing a text, a lot of times the user deletes or adds characters in the middle of the text, perhaps it is better to use std::list<char> to contains the characters, then adding characters in the middle of list is not costly operation.

Answer 1

The following paper summarizes the data structures used in word processors: http://www.cs.unm.edu/~crowley/papers/sds.pdf

Data Structures for Text Sequences. Charles Crowley, University of New Mexico, 1998

The data structure used to maintain the sequence of characters is an important part of a text editor. This paper investigates and evaluates the range of possible data structures for text sequences. The ADT interface to the text sequence component of a text editor is examined. Six common sequence data structures (array, gap, list, line pointers, fixed size buers and piece tables) are examined and then a general model of sequence data structures that encompasses all six structures is presented. The piece table method is explained in detail and its advantages are presented. The design space of sequence data structures is examined and several variations on the ones listed above are presented. These sequence data structures are compared experimentally and evaluated based on a number of criteria. The experimental comparison is done by implementing each data structure in an editing simulator and testing it using a synthetic load of many thousands of edits. We also report on experiments on the senstivity of the results to variations in the parameters used to generate the synthetic editing load.

Answer 2

SGI STL has a Rope class, you may want to check it out: http://www.sgi.com/tech/stl/Rope.html

Answer 3

Using std::list<char> would require about nine times more storage per character than using std::string. That's probably not a good tradeoff. My first inclination would be to use a std::vector<std::string>, where each string object holds the text of a paragraph. Insertions and deletions within a paragraph will be fast enough.

Answer 4

First word-processing do much more than string manipulation. You will need a rich-text data structure. If you need pagination you will also need some meta-data like page setup. Do some research on Word, you will have answer.

For the rich-text part, your data structure have to save two things: characters and attributes. In other words, you have to have some kind of markup language. HTML/DOM is a choice. But in most of time it's a overkill because of complexity.

There are many data structure can handle the character part: Rope, Gap Buffer, and Piece Table. But none of them provide attribute support directly. You have to build it by you self.

AbiWord using list based Piece Table before, but now using tree based Piece Table now. Go to the Wiki page of AbiWord you will find more.

OpenOffice use a different way. Basically, it keeps a list of paragraph, and inside the paragraph it keep a string (or other more effective data structure) and list of attributes. I prefer this way because Paragraph is a naturally small enough unit to edit, it's much easier than tree based piece table.