I remember reading that there are no existing data structures which allow for random-access into a variable length encoding, like UTF-8, without requiring additional lookup tables.
The main question I have is, is this even a useful property? I mean, to look up and replace random single codepoints in O(1) time.
Best Answer
I would give the traditional, and really quite boring answer of it depends.
Is random access to individual characters (glyphs) in a string a useful property? Yes, definitely.
Do you need access to individual code points? I guess that could be useful in certain situations that aren't too contrived if you are doing extensive handling of text data, such as in for example word processing or text rendering. Data (text encoding) normalization is another possible use-case that I can think of. I'm sure there are other good uses as well.
Does it need to be in O(1) time? Really, with a few exceptions that are unlikely to apply in the general case, not necessarily. If O(1) time access is a requirement, it's probably easier to just use a fixed-length encoding such as UTF-32. (And you will still be dealing with cache misses and swap space fetches, so for sufficiently long strings it won't be O(1) anyway... :))