保留元素的排序列表，按该元素外部的属性排序
我有一个“管理器”类维护对象列表。每个对象都有一定的“位置”，但是他们不知道这一点，只有管理者知道这一点。管理器必须为每个对象分配一个位置，并维护根据此“外部属性”排序的对象列表。
请注意，对象的位置可以随时更改。理想情况下，我应该能够立即获取位置 X 处的元素或随时获取元素 X 的位置。
这是 C# 代码。我想知道什么是一种干净或惯用的方法来做到这一点。
我考虑过创建一个像这样的内部类：
class SortedElement {
public Element Elem { get; set; }
public int Position { get; set; }
}
然后维护一个 SortedElements 列表。我不知道，这对我来说似乎很笨拙。例如，两个 SortedElements 可以具有相同的 Position。我觉得我缺少一个明显、干净的解决方案。我还可以将位置设置为元素本身的属性，但这在语义上没有意义，这意味着除了让我的生活更轻松之外，他们没有理由知道这一点。
请让我捂脸。
编辑：按照 Eric Lippert 列出我的要求的建议，并睡个好觉，我意识到我应该选择 LinkedList 并使用索引作为位置。事实上，这里最常见的操作是在容器内的开头插入和删除，这对于基于数组的容器来说是昂贵的。 感谢您的所有回复。
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".
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.
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; }
}
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.
Please make me go facepalm.
EDIT: 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
让我们列出您的要求。我假设您想要一个具有以下操作的数据结构 S：
这是您想要的操作的正确摘要吗？ （请注意，将元素移动到新位置与 RemoveElementAt 后跟 InsertElementAt 相同。）
如果这些不是操作的正确摘要，那么如果您准确地列出您想要抽象的操作集，将会很有帮助支持的数据类型。
一旦我们有了明确的操作要求列表，那么下一个问题就是“渐近性能要求是什么？”
例如，您可以使用
List作为数据结构 S；它支持所有这些操作。但是，如果列表很长，那么在列表开头插入和删除的成本非常高，“包含”操作也是如此。您可以使用更多奇特的数据结构，它们在建模插入和删除方面非常高效；我们使用此类数据结构对 C# IDE 中编辑器状态的更改进行建模。显然，每个标记、变量声明等都是一个具有“位置”的“元素”，并且当您在其周围键入时，该位置始终会发生变化；以有效的方式处理这些变化是相当具有挑战性的，但如果这就是您所处的问题空间，那么请更清楚地描述它，我们可以为您提供有关数据结构的指导，您可以对其进行一些研究。
Let's list your requirements. I assume you want to have a data structure S which has the following operations:
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?"
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.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.
您似乎煞费苦心地避免将集合描述为简单的元素序列，因此我假设使用
List并使用索引作为位置是不可能的。Dictionary怎么样？它强制执行唯一性，并假设您引用的这个“位置”是有序的，保持正确的排序。You seem to be taking pains to avoid describing the collection as a simple sequence of elements, so I'll assume a
List<T>and using the index as position is out of the question. What about aDictionary<int, Element>? It enforces uniqueness and assuming this "position" you refer to is ordinal, maintains proper sorting.您可以使用通用列表 (
List) 在“manager”类内部维护元素列表。然后，您可以使用List类的Sort()方法对列表进行排序。例如：在此示例中，元素按属性“名称”排序，但您可以在比较中使用任何内容，包括“外部属性”。
You could maintain the list of elements internally to the "manager" class using a generic list (
List<Element>). You could then sort the list however you wanted using theSort()method of theList<T>class. For example:In this example the elements are sorted by the property "Name", but you could use anything in the comparison, including your "external attribute".
我认为你真的应该使用 SortedDictionary。
I think you should really use a SortedDictionary.