c# - 适当的类似列表的排序数据结构

Question

我正在寻找具有以下属性的类列表数据结构:

1. 通用，即 DataStructure<T> , 其中T是通用的
2. T 的多个不同实例IComparable<T> 认为它们相等必须允许同时出现在列表中；它们的顺序可以是任意的(甚至可以改变)，但它们必须在 T 的“较小”实例之后。在 T 的“更大”实例之前
3. O(log(n))插入时间复杂度(或更快)
4. O(log(n))检索时间复杂度(或更快)
5. 可以使用 O(1) 访问第一个/最后一个元素时间复杂度
6. 可以使用 O(1) 访问元素的前导/后继时间复杂度
7. 无需使用额外的库即可使用

我不关心移除时间复杂度，因为元素很少需要被删除。我也不关心空间复杂度。

我知道没有满足所有属性的数据结构，但是来自 BCL 的数据结构(乍一看它们可以满足我的需要)似乎有太多缺点:

• SortedSet<T>不允许 IComparable<T> 认为相同的多个实例(2) 并且没有前任/后继职能 (6)
• SortedSet<T, List<T>> (只有 T 的一个“代表性”索引实例)将需要相当多的额外(丑陋)代码，并且仍然没有前置/后继函数 (6)
• SortedList<T, T>插入速度太慢 (3)
• SortedDictionary<T, T>不允许 IComparable<T> 认为相同的多个实例(2) 并且不允许直接访问第一个/最后一个元素 (5)，也没有前导/后继函数 (6)
• 继承自 List<T>并保持排序可能是一种选择，但由于实现工作和潜在的性能不佳，我宁愿使用内置的东西 (7)

我是不是忽略了什么？我的用例似乎没有其他相关数据结构(我查看了 here 和 here 等)。是否还有其他我没有考虑到的数据结构？

Answer 1

如果您愿意放宽 5 和 6，那么您可以使用 TreeMap