维护排序顺序的集合 C#

Question

我有一个 class 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);
    }
}

此class Foo 用于处理性能（速度）至关重要的算法。内存很重要，但不如速度重要。有一个nFoo个列表，每个列表最多有mBar个。到目前为止，这个 class 对我很有帮助。我现在希望为用户提供多种选择，这意味着我需要提供对列表中前几个 Bar 的随机访问。

因此，我想按顺序存储我的 Bar，以便我可以按顺序按索引访问它们。在我的 Bar class 中，我实现了 IComparable 以允许 Bars 在持续时间上进行比较，但我坚持选择合适的数据类型。我查看了 System.Collections.SortedList，但是（除非我错了）这似乎是在实现 IDictionary 时按键引用元素。 我可以使用什么集合来维护我的对象，以便它们保持排序，并且可以按索引顺序遍历？

Answer 1

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

Answer 2

为什么不直接使用 List.Insert？
插入是 O(n) 并允许您在特定索引处插入。
n + n 仍然是 O(n)

public AddBar(Bar bar)
{
    int index = 0;    
    foreach (bar b in AllBar)
    {
       if(bar.Duration < b.Duration)
         break;
       index++;
    }
    AllBars.Insert(index, bar);
}

所以你有排序和 O(1) 索引
以 O(n) Add
为代价当前Add in也是O(n)

NlogN 中的 SortedList 然后你没有索引，因为键是 Duration 并且键不是唯一的

SortedSet 插入是 LogN 但 ToList 是 O(n) 所以你仍然是 O(n)

调用列表的Sort方法是NlogN

这回答了以下问题： 我可以使用什么集合来维护我的对象，以便它们保持排序，并且可以按索引顺序遍历？

我认为你不会用比 O(n) 加法更好的方法来做到这一点。
谁曾否决过它，那么什么是更好的解决方案？

Answer 3

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

如果您可以接受没有任何意义的 "values"，请在不使用值部分的地方使用 SortedList<Bar, object>。

在 O(n) 时间内添加 yourSortedList.Add(yourBar, null)（列表必须将 "up" 所有条目移动到您插入的点之后）。使用 yourSortedList.Keys[i].

在 O(1) 时间内检索第 i 个条目

看到SortedList<,>.Keys property documentation一些"proof"认为上面的描述是正确的。请注意，SortedList<,> 实际上由 "list" 组成（即长度为 Capacity 的数组，必要时可替换为更大的数组）。这与我认为是二叉搜索树的 SortedDictionary<,> 不同。

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

维护排序顺序的集合 C#

Collection that maintains sort order C#

.net

c#

sorting

performance

icomparable