支持全对数时间操作的有序唯一元素列表对应哪种数据结构？

你需要的这类支持按序位、按值双向对数复杂度操作的有序集合，有非常成熟的简化实现方案，远没有你构思的逻辑复杂，以下是两种最常用的选项：

方案一：跳表+哈希映射（实现难度最低） #

跳表本身的实现逻辑远轻于自平衡二叉搜索树，不需要处理节点旋转、重平衡这类复杂操作，仅需额外维护指针跨度即可满足所有需求：

• 基础跳表每个节点存储元素值、多层级的后继指针，额外给每个后继指针加一个span属性，记录该指针跨过的节点数量
• 搭配一个哈希表存储「元素值→对应跳表节点」的映射，O(1)即可通过元素拿到节点引用
• 所有操作的时间复杂度均为O(log n)，完全满足你的要求：
  • 右端加元素：从跳表层首遍历到最右端插入，同步更新路径上的指针跨度和哈希表即可
  • 移除任意位置元素：按下标删除时通过跳表的跨度属性遍历定位到对应节点；按元素删除时直接通过哈希表拿节点，删除后同步更新路径上的指针跨度和哈希表即可
  • 获取长度：直接维护全局长度变量，O(1)复杂度
  • 按下标取元素：通过跳表跨度遍历定位第k个节点，O(log n)
  • 获取元素对应下标：通过哈希表拿到节点后，统计从表头到该节点的所有路径跨度和即可，O(log n)

方案二：顺序统计树+哈希映射（标准通用实现） #

这是算法领域的经典通用方案，是你最初构思方案的简化优化版，不需要额外维护插入计数：

• 底层用支持顺序统计的自平衡BST（红黑树、AVL树、Treap均可），每个节点除了存元素值，额外存储以自身为根的子树大小（这是顺序统计树的标准配置，所有算法教材都有现成模版，没有额外复杂逻辑）
• 搭配一个哈希表存储「元素值→对应BST节点」的映射
• 所有操作复杂度均为O(log n)，逻辑非常规整：
  • 右端加元素：作为最大值插入BST，同步更新路径上的子树大小和哈希表
  • 移除任意位置元素：按下标删除时调用BST的标准find_kth接口定位节点，按元素删除时通过哈希表拿节点，删除后同步更新子树大小和哈希表
  • 获取长度：直接读根节点的子树大小，O(1)复杂度
  • 按下标取元素：调用find_kth接口，O(log n)
  • 获取元素对应下标：通过哈希表拿到节点后，统计该节点左子树大小+所有祖先节点中该节点属于右子树的祖先的左子树大小之和即可，O(log n)

工程落地推荐 #

如果是实际业务开发，不需要手动实现上述结构，很多语言都有现成的封装：

• C++ 可以直接用GNU扩展的__gnu_pbds::tree（政策基树），本身内置顺序统计能力，搭配std::unordered_map存元素到迭代器的映射即可开箱即用
• Python 可以直接用第三方库sortedcontainers的SortedList，内部基于分段有序数组实现，你要求的5个操作全部原生支持，且都是O(log n)复杂度，甚至不需要额外维护哈希表，内置的index()方法就是对数复杂度。

目前不存在比上述方案复杂度更优的通用结构，所有操作已经达到理论下界。

内容的提问来源于stack exchange，提问作者Zachary Barbanell