I'm designing a language that I intend to be implemented on the .NET platform. To my understanding, the native string representation uses UTF-16, by storing an array of
char (an unsigned 16-bit type) and offering an API that treats each 16-bit code unit as an element.
This isn't the indexing behaviour I want for strings in my language. At the very least, I want to index character-by-character, returning the nth code point from the data - which is different from the nth code unit, because of surrogate pairs.
Given an unknown amount and position of surrogate pairs in the underlying data, it seems that a naive algorithm to index by character would be forced into O(N) performance (i.e., iterating over the code units until there are enough to make N code points). Is it possible to do better than this, perhaps by recording auxiliary data or using a more complex data structure? Or is resorting to UCS-32 or another such "flat" encoding the only viable option?
Is it possible to support better-than-O(N) indexing for grapheme clusters (notwithstanding the work required to identify the clusters)?
What approaches are taken by real-world languages to store and use such string data?
This is not a duplicate of How have modern language designs dealt with Unicode strings? or Prior art on modeling characters of variable lengths in that I am specifically interested in the implementation of indexing operators, the performance characteristics afforded by various designs, and any relevant optimization techniques.