2

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

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

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

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

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

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

请让我捂脸。

编辑：遵循 Eric Lippert 列出我的要求和睡个好觉的建议，我意识到我应该选择 aLinkedList<Element>并将索引用作位置。实际上，这里最常见的操作将是在容器内的开头插入和删除，这在基于数组的容器上是昂贵的。感谢所有回复。

4

4 回答 4

2

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

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

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

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

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

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

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

于 2010-01-12T04:37:57.513 回答
1

您似乎在努力避免将集合描述为简单的元素序列，因此我假设 aList<T>并使用索引作为位置是不可能的。一个Dictionary<int, Element>呢？它强制执行唯一性并假设您所指的这个“位置”是序数，保持正确的排序。

于 2010-01-12T04:17:09.867 回答
0

您可以使用通用列表 ( ) 在“管理器”类内部维护元素列表List<Element>。然后，您可以使用类的Sort()方法对列表进行排序List<T>。例如：

myList.Sort((elem1, elem2) => elem1.Name.CompareTo(elem2.Name));

在此示例中，元素按属性“名称”排序，但您可以在比较中使用任何内容，包括您的“外部属性”。

于 2010-01-12T04:27:00.810 回答
0

我认为你真的应该使用SortedDictionary。

于 2010-01-12T13:42:37.627 回答