寻找一种数据结构，逻辑上表示由唯一标识符（为了简单起见，我们将其视为字符串或至少是可哈希对象） 键入的元素序列。每个元素只能出现一次，没有间隙，第一个位置为0。
应支持以下操作（用单字母字符串演示）：
- `insert(id, position)` - 在偏移量`position`处将键入`id`的元素添加到序列中。自然情况下，序列中稍后的每个元素的位置都会增加1。例如： `[S E L F].insert(H，1) -> [S H E L F]` - `remove(position)` - 移除偏移量`position`处的元素。将序列中稍后的每个元素的位置减1。例如： `[S H E L F].remove(2) -> [S H L F]` - `lookup(id)` - 查找由`id`键入的元素的位置。`[S H L F].lookup(H) -> 1`
朴素实现可以是链表或数组。两者都将提供O(n)`lookup`，`remove`和`insert`。
在实践中，`lookup`可能被使用得最多，而`insert`和`remove`足够频繁，以致于不要线性（哈希图+数组/列表的简单组合会让你获得这些功能）。
在完美的世界中，它将是O(1)`lookup`，O(log n)`insert` / `remove`，但我实际上怀疑这不会从纯信息论的角度起作用（尽管我还没有尝试），因此O(log n）`lookup`仍然很好。
应支持以下操作（用单字母字符串演示）：
- `insert(id, position)` - 在偏移量`position`处将键入`id`的元素添加到序列中。自然情况下，序列中稍后的每个元素的位置都会增加1。例如： `[S E L F].insert(H，1) -> [S H E L F]` - `remove(position)` - 移除偏移量`position`处的元素。将序列中稍后的每个元素的位置减1。例如： `[S H E L F].remove(2) -> [S H L F]` - `lookup(id)` - 查找由`id`键入的元素的位置。`[S H L F].lookup(H) -> 1`
朴素实现可以是链表或数组。两者都将提供O(n)`lookup`，`remove`和`insert`。
在实践中，`lookup`可能被使用得最多，而`insert`和`remove`足够频繁，以致于不要线性（哈希图+数组/列表的简单组合会让你获得这些功能）。
在完美的世界中，它将是O(1)`lookup`，O(log n)`insert` / `remove`，但我实际上怀疑这不会从纯信息论的角度起作用（尽管我还没有尝试），因此O(log n）`lookup`仍然很好。