Scala支持重复排序键的有序数据结构选型问询

标准库最优方案：TreeSet + 自定义排序规则 #

Scala标准库中的TreeSet（包括可变版本scala.collection.mutable.TreeSet）基于红黑树实现，天生支持维护有序集合，且可以通过自定义Ordering解决「排序条件重复但元素不重复」的问题。

以人员按年龄排序为例，你可以为每个元素附加唯一标识（比如ID），将排序键设置为(年龄, 唯一ID)——这样既保证按年龄排序，又能区分同岁的不同人员，避免元素被错误去重。示例代码如下：

case class Person(id: Int, name: String, age: Int)

// 自定义排序逻辑：优先按年龄升序，年龄相同时按ID升序
val personOrdering: Ordering[Person] = Ordering.by(p => (p.age, p.id))
// 初始化可变TreeSet，传入自定义排序规则
val sortedPersonSet = scala.collection.mutable.TreeSet.empty[Person](personOrdering)

// 频繁增删操作示例
sortedPersonSet.add(Person(1, "Alice", 25))
sortedPersonSet.add(Person(2, "Bob", 23))
sortedPersonSet.add(Person(3, "Charlie", 25))
sortedPersonSet.remove(Person(1, "Alice", 25))

// 遍历输出始终是有序状态
sortedPersonSet.foreach(println)

该方案的增删改操作时间复杂度均为O(log n)，完全满足「频繁修改且始终有序」的要求。

关于PriorityQueue与旧提问的现状 #

Scala标准库的PriorityQueue基于堆结构实现，仅能保证头部元素为极值，无法支持全局遍历有序，这一点至今没有变化。你提到的旧提问场景，目前标准库层面依然没有新增专门的全局有序且支持重复排序键的集合类型，因此TreeSet配合自定义排序仍是最优解。

备选方案：第三方集合库 #

如果标准库方案无法覆盖特殊需求，可以考虑第三方库如Scalaz或Cats提供的增强型有序集合，不过这类库通常会引入额外依赖，多数情况下标准库方案已足够。

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