维护排序顺序C#的集合

Question

我有一个Foo包含对象列表的类:List<Bar>.每个Bar属性都有一个属性,可以对它们进行排序(类型TimeSpan,表示持续时间),并且Bar是一个不可变对象 - 也就是说,持续时间不会随着算法的运行而改变.目前,对于每一个Foo我也保持Bar在列表中的第一个如果它被订购(即Bar最短的持续时间).像这样的东西:

public class Foo
{
    public List<Bar> AllBars { get; set; }

    public Bar FirstBar { get; set; }

    public Foo (Bar bar)
    {
        FirstBar = bar;

        AllBars = new List<Bar>() { bar };
    }

    public AddBar(Bar bar)
    {
        if(bar.Duration < FirstBar.Duration)
        {
            FirstBar = bar;
        }

        AllBars.Add(bar);
    }
}

此类Foo用于处理性能(速度)至关重要的算法中.记忆很重要但不如速度快.有一个n Foo s 列表,每个都有m Bar s.直到这一刻,这门课一直很好.我现在希望为用户提供多种选择,这意味着我需要提供Bar对列表中前几个s的随机访问.

因此,我Bar希望按顺序存储我的s,以便我可以按顺序访问它们.在我的Bar课程中,我实现IComparable了允许Bars在持续时间上进行比较,但我坚持选择合适的数据类型.我看了System.Collections.SortedList但是(除非我错了)这似乎是在实现时按键引用元素IDictionary. 我可以使用哪些集合来维护我的对象,使它们保持排序状态,并且它们可以按索引顺序遍历？

Answer 1

我更喜欢使用SortedSet<T>，它是一个二叉树，其中键和值是同一个对象。这再次意味着添加/删除/查找是对数的 -O(log n)但您可以获得按顺序迭代项目的能力。为了使该集合有效，类型T必须实现IComparable<T>，或者您需要提供外部IComparer<T>.

Answer 2

（根据提问者的要求，从评论中升级）

如果您可以接受毫无意义的“值”，则只需在SortedList<Bar, object>不使用值部分的地方使用 a 即可。

在 O(n) 时间内添加yourSortedList.Add(yourBar, null)（列表必须将插入点之后的所有条目“向上”移动）。使用 检索iO(1) 时间内的第一个条目yourSortedList.Keys[i]。

请参阅SortedList<,>.Keys属性文档以获取上述描述正确的一些“证据”。请注意， aSortedList<,>实际上由一个“列表”组成（即长度为 的数组Capacity，必要时可以用更大的数组替换）。SortedDictionary<,>这与我认为的二叉搜索树不同。

但请注意：您的 中不能有重复项SortedList<,>，因此列表中的两个成员不允许CompareTo彼此返回值为零。