Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

1 Answer 1

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

Your Answer

 
discard

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.
{"cc_re__cc_re__cc_by_sa_3_0": ["sites in the Stack Exchange network\">Area 51</a></li>\r\n                        <li><a href=\"//careers.stackoverflow.com?utm_source=stackoverflow.com&amp;utm_medium=site-ui&amp;utm_campaign=footerlink\">Stack Overflow Careers</a></li>\r\n                    \r\n                </ol>\r\n            </td>\r\n    </tr>\r\n</table>\r\n                </div>\r\n            </div>\r\n\r\n            <div id=\"copyright\">\r\n                site design / logo &#169; 2014 stack exchange inc; user contributions licensed under <a href=\"http://creativecommons.org/licenses/by-sa/3.0/\" rel=\"license\">cc by-sa 3.0</a>                   with <a href=\"http://blog.stackoverflow.com/2009/06/attribution-required/\" rel=\"license\">attribution required</a>\r\n            </div>\r\n            <div id=\"svnrev\">\r\n                rev 2014.12.19.2131\r\n            </div>\r\n            \r\n        </div>\r\n    </div>\r\n    <noscript>\r\n        <div id=\"noscript-warning\">Programmers Stack Exchange works best with JavaScript enabled<img src=\"http://pixel.quantserve.com/pixel/p-c1rF4kxgLUzNc.gif\" alt=\"\" class=\"dno\"></di"], "copyright__copyright__copyright": ["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... :))\n\nshare|improve this answer\n\nYour Answer\n\n\u00a0\ndiscard\n\nBy posting your answer, you agree to the privacy policy and terms of service.\n\nNot the answer you're looking for? Browse other questions tagged or ask your own question."]}