保留元素的排序列表，按該元素的外部屬性排序

我有一個維護對象列表的「管理器」類。每個對象都有一個特定的「職位」，但這是他們不知道的，只有經理知道這一點。管理員必須爲每個對象分配一個位置，並根據此「外部屬性」維護其對象列表。保留元素的排序列表，按該元素的外部屬性排序

請注意，對象的位置可以隨時更改。理想情況下，我應該能夠在任何時候立即獲得位置X處的元素或元素X的位置。

這是C＃代碼。我想知道這是乾淨的還是慣用的方式。

我想過做一個內部類是這樣的：

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

然後保持SortedElements的列表。我不知道，對我來說似乎很笨拙。例如，兩個SortedElements可以具有相同的位置。我覺得有一個明顯的，乾淨的解決方案，我錯過了。我也可以將「位置」作爲「元素」本身的屬性，但它在語義上沒有意義，這意味着除了讓我的生活更輕鬆之外，沒有理由讓他們知道這一點。

請讓我走facepalm。

編輯：按照Eric Lippert的建議列出我的要求和一個良好的睡眠，我意識到我應該選擇LinkedList<Element>並使用索引作爲位置。實際上，這裏最常見的操作將是在容器的開始處插入和移除，這在基於陣列的容器上是昂貴的。感謝您的回覆。

來源

2010-01-12 Asik

你是說任何時候對象的位置都可以改變，因爲如果引入了另一個對象，它可能會基於該外部屬性插入到現有元素之間？ – 2010-01-12 04:24:29

這將是一個可能的情況。另一個是經理決定交換兩個對象的位置。 – Asik 2010-01-12 04:29:20

讓我們列出您的要求。我假設你想擁有它具有以下操作的數據結構S：

ContainsElement：需要一個元素，告訴您該元素是否屬於S
IsValidPosition：需要一個位置，告訴你是否該位置屬於S
GetElementAt可供選擇：需要一個有效的位置，返回一個Element
GetPositionOf：需要一個元件，它在S，返回一個位置
InsertElementAt：需要一個元素不屬於S和有效的位置。將元素放置在該位置;所有元素後該位置移動「向上」。
RemoveElementAt：取一個有效的位置，移除該位置上的元素，該位置後面的所有元素都「向下移動」。

這是您想要的操作的正確總結嗎？（請注意，將元素移動到新位置與RemoveElementAt相同，後跟InsertElementAt。）

如果這些操作不是正確的操作摘要，那麼如果您準確列出操作集合會很有幫助你想要你的抽象數據類型支持。

一旦我們有明確的操作要求清單，那麼下一個問題是「什麼是漸近性能要求？」

例如，您可以使用List<T>作爲您的數據結構S;它支持所有這些操作。但是，如果列表很長，那麼在列表開始處插入和刪除代碼非常昂貴，而「Contains」操作也是如此。

您可以使用更多異國情調的數據結構，這些數據結構在插入和移除建模時非常高效;我們使用這些數據結構來模擬C＃IDE中編輯器狀態的變化。很顯然，每個標記，變量聲明等等都是一個「元素」，它有一個「位置」，並且該位置隨着您鍵入而始終改變;以有效的方式處理這些變化是相當具有挑戰性的，但如果這是您所處的問題空間，那麼將其更清楚地描述一下，我們可以爲您提供關於數據結構的指示，您可以對其進行一些研究。

來源

2010-01-12 04:37:57

您似乎在努力避免將集合描述爲一個簡單的元素序列，因此我將假設一個List<T>並將該索引用作位置是不可能的。那Dictionary<int, Element>呢？它強制實施獨特性，並假設您提到的這個「職位」是有序的，保持適當的排序。

來源

2010-01-12 04:17:09

與那個問題是不能輕易改變的位置。我向帖子添加了這項要求，感謝您的意見。 – Asik 2010-01-12 04:19:06

另外，使用索引作爲位置的列表的問題是，儘管找到知道其位置的元素是立即的，但找到知道該元素的位置需要搜索。但也許這是不可避免的。 TBH我不知道我在找什麼，我只是有一個糟糕的例子，「我知道有一個明顯的完美解決方案」。 – Asik 2010-01-12 04:27:01

您可以使用通用列表（List<Element>）在內部維護「管理器」類的元素列表。然後，您可以使用List<T>類的Sort()方法對列表進行排序。例如：

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

在這個例子中，元素由「名稱」屬性來分類的，但你可以在比較中使用的所有內容，包括「外部屬性」。

來源

2010-01-12 04:27:00 WayneC

恐怕你不明白我說的話。問題在於，我不能做你的建議，因爲手頭的「財產」不是要素的一部分;它不是這些元素的屬性，而是隻有經理才知道的外部屬性。所以你不能做elem1.Name，因爲Elem沒有名字，只有經理知道這個名字。 – Asik 2010-01-12 04:31:07

我認爲你應該真的使用SortedDictionary。

來源

2010-01-12 13:42:37

保留元素的排序列表，按該元素的外部屬性排序

回答

相關問題