c# - 保持元素的排序列表，按该元素外部的属性排序

Question

我有一个维护对象列表的“管理器”类。每个对象都有一定的“位置”，但这对他们来说是不知道的，只有经理知道这一点。管理器必须为每个对象分配一个位置，并维护其根据此“外部属性”排序的对象列表。

请注意，对象的位置可以随时更改。理想情况下，我应该能够在任何时候立即获得位置 X 的元素或元素 X 的位置。

这是 C# 代码。我想知道这样做的一种干净或惯用的方式是什么。

我想过做一个这样的内部类:

class SortedElement {
    public Element Elem { get; set; }
    public int Position { get; set; }
}

然后维护一个 SortedElements 列表。我不知道，这对我来说似乎很笨拙。例如，两个 SortedElements 可能具有相同的 Position。我觉得我缺少一个明显的、干净的解决方案。我也可以使 Position 成为元素本身的一个属性，但这在语义上没有意义，这意味着除了让我的生活更轻松之外，他们没有理由知道这一点。

请让我去捂脸。

编辑:按照 Eric Lippert 列出我的要求和睡个好觉的建议，我意识到我应该选择 LinkedList<Element>并使用索引作为位置。事实上，这里最常见的操作是在容器的开头插入和从容器内的任何地方移除，这在基于数组的容器上是昂贵的。感谢所有回复。

Answer 1

让我们列出您的要求。我假设您想要一个具有以下操作的数据结构 S:

• ContainsElement:取一个元素，告诉你这个元素是否在S中
• IsValidPosition:取一个 Position，告诉你这个位置在 S 中是否可用
• GetElementAt:取得一个有效的 Position，返回一个 Element
• GetPositionOf:获取 S 中的一个元素，返回一个位置
• InsertElementAt:接受一个不在 S 中的元素和一个有效的位置。将元素放在该位置；该位置之后的所有元素“向上移动一个”。
• RemoveElementAt:取一个有效的 Position，删除该位置的元素，该位置之后的所有元素都“向下移动一个”。

这是您想要的操作的正确摘要吗？ (请注意，将元素移动到新位置与 RemoveElementAt 后跟 InsertElementAt 相同。)

如果这些不是对操作的正确总结，那么如果您准确列出您希望抽象数据类型支持的操作集将会很有帮助。

一旦我们有了明确的操作要求列表，那么下一个问题就是“渐近性能要求是什么？”

例如，您可以使用 List<T>作为你的数据结构 S；它支持所有这些操作。但是，如果列表很长，则在列表开头插入和删除的开销非常大，“包含”操作也是如此。

您可以使用更多奇特的数据结构，它们在建模插入和删除方面非常高效；我们使用这样的数据结构来模拟 C# IDE 中编辑器状态的变化。显然，每个标记、变量声明等都是一个具有“位置”的“元素”，并且当您在其周围键入时，该位置一直在变化；以有效的方式处理这些更改非常具有挑战性，但如果那是您所处的问题空间，那么请更清楚地描述它，我们可以为您提供有关数据结构的指导，您可以对其进行一些研究。