寻找符合C++ std::set核心特性需求的JavaScript有序集合容器

已调研候选的能力缺口对比 #

• sorted-btree：覆盖自定义比较器、自动排序、下界位置查找3项能力，但原生未提供迭代器双向移动的支持，要实现前后元素移动需要手动维护元素与索引的映射关系，额外开发成本不低。
• collectionsjs 提供的sorted-array-set：支持自定义比较器、双向迭代器遍历、自动排序，但没有内置插入位置查找接口，要实现C++ lower_bound对应的能力只能自行实现二分查找，动态插入场景下很容易出现索引不同步的问题。

全需求覆盖的可选实现 #

1. 伸展树（SplayTree）实现的有序集合 #

完全匹配4项核心需求，操作复杂度与C++ std::set保持一致：

• 支持传入任意自定义比较函数，排序规则完全由用户传入的逻辑决定，不依赖JS原生默认的排序逻辑
• 每次插入节点时自动按照比较器规则调整树结构，始终维持全局有序
• 内置lowerBound查找方法，传入目标值后可直接返回第一个满足“大于等于目标值”的节点引用；目标值不存在时，会直接返回对应插入位置的后续节点，完全对齐C++的行为
• 每个节点自带prev()和next()方法，可直接实现迭代器自增、自减，在相邻元素间移动时不需要额外计算索引

2. 红黑树实现的SortedSet #

同样可以完整覆盖全部需求：

• 支持自定义比较器注入
• 插入时自动维护红黑树的平衡与有序性
• 内置下界查找能力，可直接返回目标值对应的插入位置元素
• 每个节点存储前后相邻元素的指针，支持双向迭代器的前后移动操作

零依赖简易实现方案 #

如果不想引入第三方库，可基于有序数组+二分查找快速搭出最小可用版本：

• 用普通数组存储元素，每次插入时通过二分查找定位插入位置，插入后自然保持全局有序
• 将自定义比较器作为排序、查找的统一逻辑入口
• 基于二分查找实现lower_bound逻辑，直接拿到目标值的插入索引
• 迭代器仅需维护当前数组索引，自增操作对应索引值加1，自减操作对应索引值减1
  注意：这种实现的插入操作是O(n)复杂度，仅适合小数据量场景，元素规模超过千级后会出现明显的性能下降。

内容的提问来源于stack exchange，提问作者Takatoshi Kondo