保持元素的排序列表，按该元素外部的属性排序 [英] Keeping a sorted list of elements, sorted by an attribute external to that element

问题描述

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

I have a "manager" class maintaining a list of objects. Each Object has a certain "position", but this is not known to them, only the manager knows about this. The manager must assign each Object a position and maintain its list of Objects sorted according to this "external attribute".

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

Note that an Object's position can change at any time. Ideally I should be able to immediately get either Element at position X or the position of Element X at any time.

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

This is C# code. I am wondering what would be a clean or idiomatic way of doing this.

我想过像这样创建一个内部类:

I thought about making an internal class like this:

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

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

And then maintain a list of SortedElements. I don't know, it seems clumsy to me. Two SortedElements could have the same Position for instance. I feel like there's an obvious, clean solution which I'm missing. I could also make the Position a property of the Elements themselves, but it doesn't make sense semantically, meaning there's no reason for them to know about that except making my life easier.

请让我去facepalm.

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

Following Eric Lippert's advice of listing my requirements, and a good night's sleep, I realized I should opt for a LinkedList<Element> and use the index as position. Indeed, the most common operations here will be insertion at the beginning and removal anywhere within the container, which are expensive on an array-based container. Thanks for all replies.

推荐答案

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

Let's list your requirements. I assume you want to have a data structure S which has the following operations:

• ContainsElement:取一个元素，告诉你该元素是否在S中
• IsValidPosition:获取一个位置，告诉您该位置在 S 中是否可用
• GetElementAt:取一个有效的位置，返回一个元素
• GetPositionOf:获取 S 中的一个元素，返回一个位置
• InsertElementAt:采用不在 S 中的元素和有效的位置.将元素放在那个位置；该位置之后的所有元素向上移动".
• RemoveElementAt:取一个有效的位置，移除该位置的元素，该位置之后的所有元素向下移动一个".

• ContainsElement: takes an element, tells you whether the element is in S
• IsValidPosition: takes a Position, tells you whether that position is available in S
• GetElementAt: takes a valid Position, returns an Element
• GetPositionOf: takes an Element which is in S, returns a Position
• InsertElementAt: takes an Element not in S and a valid Position. Puts the element at that position; all elements after that position move "up by one".
• RemoveElementAt: takes a valid Position, removes the element at that position, all elements after that position move "down one".

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

Is that a correct summary of the operations you want? (Note that moving an element to a new position is the same as RemoveElementAt followed by InsertElementAt.)

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

If those are not a correct summary of the operations, then it would be helpful if you'd list exactly the set of operations you want your abstract data type to support.

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

Once we have a clear list of requirements for operations then the next question is "what are the asymptotic performance requirements?"

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

For example, you could use a List<T> as your data structure S; it supports all of those operations. However, if the list is very long then inserting and removing at the beginning of the list is very expensive, as is the "Contains" operation.

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

There are more exotic data structures you can use that are highly efficient at modeling insertions and removals; we use such data structures to model changes to the state of the editor in the C# IDE. Obviously each token, variable declaration, and so on, is an "element" that has a "position" and that position changes all the time as you type around it; handling those changes in an efficient manner is quite challenging, but if that's the sort of problem space you're in, then describe it more clearly and we can give you pointers on data structures you can do some research on.

这篇关于保持元素的排序列表，按该元素外部的属性排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！