char_index

一个用于 ~O(1) 字符索引的字符串的 crate，而不需要像 Vec<char> 那样使用大量的内存。

基准测试

1000 个 "e"，3 个额外的非 ASCII 字符，随机排序

(使用 benches/char_index.rs 收集的数据)

no_std

此 crate 完全 no_std，但它依赖于 alloc。
将来可能添加 std 功能，但目前尚不清楚这将包括哪些内容。

许可证

此 crate 使用 MPL-2.0 许可证，这是一个弱版权许可，旨在保持对核心库的任何修改都是开源的，而不会对其他要求产生很大影响。这不是法律建议。

lib.rs:

char_index

一个提供空间效率和看似 O(1) 字符索引权衡的 crate。

要开始使用，请创建一个新的 IndexedChars 或 OwnedIndexedChars 实例。

工作原理

IndexedChars 通过在底层分配一个 Vec<u8> 来工作，该 Vec 存储从其自己的索引在 Vec 中的位置到字符在支持字符串中的位置的偏移量。这利用了 UTF-8 的最小大小至少为每个字符 1 字节的事实。

这里有一个权衡，在添加了255个字节的非单字节字符串数据后（或者，所有超出一个字节长度的字符的总和减去第一个字节），它就不能再存储数据，因为它会超出u8的范围。这就是回滚结构生效的地方，它是一个专门用来存储回滚发生位置的索引的Vec，这样就可以简单地通过二分搜索找到我们正在处理的当前索引，然后将该点的列表长度乘以u8::MAX，以找到字符的真实偏移。

通过这种方式，对于大多数字符串，我们实现了O(1)的字符查找（技术上最坏情况为O(log n)），同时节省了内存，比Vec（除了字符串仅由4字节字符组成的情况，这也会是时间复杂度的最坏情况）节省内存。

此外，作为一项专门的优化，如果字符串只包含ASCII字符（所有偏移量都是0），它将不会分配任何额外的内存，并获得完美的O(1)查找。