Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 4 down vote accepted

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... :))

share|improve this answer
Could you give an example situation where random access to glyphs is useful? – John Bartholomew Nov 11 '12 at 19:51
@JohnBartholomew I was just about to do that as you posted your comment. See my edit. I'm sure there are plenty more, but that's a fairly obvious one I can think of off the top of my head on a Sunday evening. – Michael Kjörling Nov 11 '12 at 19:52
Sorry, did you forget to push the change? I don't see any specific example of an operation that benefits from random access, only mention of the general areas of word processing and text rendering. – John Bartholomew Nov 11 '12 at 20:02
@JohnBartholomew I guess that depends on how specific an example you want. I'm not particularly familiar with the low-level details of translating (bytes into) code points into graphemes into characters into pixels on a rendering surface, but I can definitely see that at some point in that stack of operations, dealing with code points separately is useful. – Michael Kjörling Nov 11 '12 at 20:06
Ok, here is a specific example: if you're rendering with a monospace font, then being able to jump into the text by codepoint allows you to select a segment of the text to display a scrolling ticker/marquee, or place the cursor at the right codepoint boundary based on the position of a mouse click. (For the ticker, it's easier to store a byte-index directly, so it just turns into normal sequential iteration over the text which doesn't need random access. In either case it'll only work for a subset of Unicode -- combining marks, bi-di text, complex shaping rules et c. will break it) – John Bartholomew Nov 11 '12 at 21:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.