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

问题描述

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

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的位置或元素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设置为Elements本身的属性，但是从语义上讲没有任何意义，这意味着除了让我的生活更轻松之外，他们没有其他必要了解这些信息.

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<Element>并将索引用作位置.确实，这里最常见的操作是在容器的开始处插入和删除容器中的任何位置，这在基于数组的容器上很昂贵. 感谢您的所有答复.

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<T>作为数据结构S；它支持所有这些操作.但是，如果列表很长，那么在列表的开头进行插入和删除非常昂贵，"Contains"操作也是如此.

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屋！