sortedset从首次add()起即以红黑树维护有序、去重结构,所有操作o(log n);需构造时传icomparer指定规则,修改已添加对象排序字段会导致查找失败,unionwith等批量操作实为逐个执行。

SortedSet<t></t> 不是“先加完再排序”的容器,它从第一次 Add() 开始就维持红黑树结构——插入、查找、删除全在 O(log n) 完成,且天然去重、遍历即有序。别把它当 List<t></t> 配 OrderBy() 用,否则每次插入都触发树重建,白耗性能。
怎么创建并指定排序规则
构造时传入 IComparer<t></t> 是唯一可控入口;不传则默认走 T 是否实现 IComparable<t></t>。内置类型(如 int、string)自带升序逻辑,但要注意:StringComparer.Ordinal ≠ 按长度排,StringComparer.OrdinalIgnoreCase 也不等于“忽略空格”。
- 降序整数:
new SortedSet<int>(Comparer<int>.Create((x, y) => y.CompareTo(x)))</int></int> - 按字符串长度升序:
new SortedSet<string>(Comparer<string>.Create((a, b) => a.Length.CompareTo(b.Length)))</string></string> - 自定义类必须显式提供比较器,不能只靠
ToString()或字段直读——否则运行时抛ArgumentException
为什么修改已添加对象的排序字段会出问题
SortedSet 的节点位置由插入时的比较结果决定,后续修改影响排序的字段(如用于 Compare() 的属性),不会触发树结构调整。这时 Contains() 可能返回 false,Remove() 找不到节点,甚至遍历时跳项。
- 常见错误:把
Person对象加入SortedSet<person></person>后改Person.Age,而比较器正依赖Age - 安全做法:把参与排序的字段设为
readonly,或改用不可变对象(record) - 若必须可变,插入后禁止修改排序字段;或改用
SortedList<k></k>+ 外部重排逻辑
哪些操作看似高效实则暗藏开销
UnionWith()、IntersectWith()、RemoveWhere() 看似批量,实际仍是逐个调用 Add() 或 Remove(),每步都触发树平衡。没有“一次性建树”优化。
-
RemoveWhere(x => x > 100)是O(n log n),不是O(n) - 从大数组初始化:
new SortedSet<int>(array)</int>内部仍是一个个Add(),不如先array.Distinct().OrderBy().ToList()再转——仅当后续需频繁增删时才值得用SortedSet -
First()和Last()是O(1),但ElementAt(5)不存在——没索引支持,强行用会编译失败
最易被忽略的是:SortedSet 的“有序”是静态快照式保证,不是响应式监听。一旦你绕过 API 直接改内部状态(比如反射篡改节点),或让比较逻辑随外部状态漂移(比如比较器里读取了全局变量),整个结构就不可信了。










