使用可变长度编码作为内部形式的字符串，如何实现访问某个具体位置的字符？

[usamoi]

我在编写一个不可变 String 的轮子，面向处理中文文本较多的环境，希望能减少使用者的心智负担。目前计划使用 UTF-16 作为字符串的内部表示，由于 UTF-16 是变长编码，取得某个位置上的 Unicode Character 这个函数不易实现。单个 Unicode Character 可能占用 1 个 Unicode Code Unit，也可能占用 2 个 Unicode Code Unit，第 k 个 Unicode Code Unit 不一定对应第 k 个 Unicode Character 。

下面是我目前想到的几个解决方案：

• 避免问题。改换 UTF-32 作为内部表示。日常场景中只方便了 emoji 的处理，但是这也并不完全，因为一部分 emoji 又需要甚至 3 个 Unicode Character 才能表示出来，依然需要手工处理，所以尤其滑稽。

• 转移矛盾。和 String 配套的 Character，表示能力从 Unicode Character 缩小到 Unicode Code Unit 。要求使用者自行处理需要 2 个 Unicode Code Unit 表示的字符。这也是.NET 的方案。

• 加速顺序访问的一个策略。记录上一次访问的 Code Unit 位置和 Character 位置，用来加速下一次访问。为了对并行友好，还需要写一个 StringAccessor 来存储这两项，并且由它间接访问 String，以免不同线程访问同一字符串时这一加速失效。

• 加速随机访问的一个策略。将字符串均匀分为$O(\sqrt{n})$段，预处理每一段的 Character 数和每一段的 Code Unit 数目，随机访问的时间复杂度为$O(\sqrt{n})$，单个字符串需要$O(\sqrt{n})$的附加空间，代价依然很昂贵。

这个怎么整啊╮(╯▽╰)╭

[msg7086]

要自己扛的话可以考虑加索引。
比如每 128 字符记一个下标，这样每次寻址最多只需要检查 127 个字符，和你的#4 类似。
sqrt(n)是一个很不昂贵的操作了，额外的空间和时间基本可以忽略不计。
要便捷性总要有牺牲的。

[gyf304]

建议不要自己弄。用 ICU
http://site.icu-project.org/home

[agagega]

可以加速，但概念上 String 和 Bytes 就不是一个东西，String 可以当作一个无法随机访问的东西

[lxilu]

有 UTF-X Code Unit
没有 Unicode Code Unit