Q:

Algorithm and data structure for text comments

Which data structure are used for commenting text and which algorithms take care for updating the comment position? A commenting feature is present in every good word processor such as Microsoft Word, Google Docs etc.
I can imagine two approaches: One would be surrounding the commented text with some sort of markup (e.g. XML tags), which implicitly stores the position of the comment inside of the commented text. The user doesn't get to see the the XML tags, since it gets parsed beforehand by the word processor.
The other approach could be storing an array of all comments and their positions and updating the positions as the commented text changes.
Are there other possible approaches? What could be the caveats of a specific implementation?

A:

I would do it with a simple collection of tuples containing the position and length of text to be annotated, and the annotation text.
For example
public class Annotation {
    public int Position;
    public int Length;
    public string Text;
}

In C#, the most favorable collection appears to be an OrderedDictionary.  An OrderedDictionary allows you to lookup annotation by position, but you can also iterate the annotations in the order that they appear in the text.  You can even hold a pointer to the nearest annotation as the user navigates through the text.
var dictionary = new OrderedDictionary<int, Annotation>();

