James Y Knight:
It would also be possible to use UTF-8 string storage, although this has the tradeoff that indexing an element takes linear time w.r.t. position instead of constant time.
At the cost of additional storage, indexing into UTF-8 by character rather than byte can be made better than linear. Two techniques are (1) maintain a list containing the byte index of some character index values (such as each line start) then use linear access from the closest known index and (2) to cache the most recent access due to the likelihood that the next access will be close. While I have thought about this problem, it has only once came up seriously for Scintilla (an editing component) and that was when someone was trying to provide a UCS2 facade that matched existing interfaces. Neil