如何在c＃中正確使用SortedDictionary？

我正在嘗試做一些非常簡單的事情，但似乎我不明白SortedDictionary。如何在c＃中正確使用SortedDictionary？

我試圖做的是以下幾點：
創建一些浮數排序我的項目排序的字典，所以我創建了一個字典，看起來像這樣

SortedDictionary<float, Node<T>> allNodes = new SortedDictionary<float, Node<T>>();

現在經過我添加項目，我想逐一刪除它們（每次刪除的複雜度應該是從最小到最大的O（log（n））。

我該怎麼做？我以爲只需要allNodes[0]給我最小的，但它沒有。

更重要的是，它似乎像字典無法處理重複鍵。我覺得我正在使用錯誤的數據結構...
如果我有一堆節點，我想按它們的距離（浮點）排序，我應該使用其他的東西嗎？

2013-04-17 OopsUser

字典鍵值必須是唯一的。我想你想使用列表>，因爲列表可以有重複的條目。然後使用LINQ將數據按照您希望它們的順序操作。 –

您是否想根據每個節點的某個值對一組節點進行排序，或者是否有某些特定原因需要使用「SortedDictionary」？如果是前者，只需在開始時收集的任何東西上使用LINQ'OrderBy'。 – Servy

我想插入和刪除O（日誌（n）），我的大部分工作是插入和刪除...哪個列表在O（N）中。和你的問題：排序是基於每個節點的一些價值。 – OopsUser

allNodes[0]不會給你在字典中的第一個項目 - 它會給你一個項目0 的關鍵值的0。

如果你想第一個項目嘗試allNodes.Values.First()來代替。或者找到的第關鍵使用allNodes.Keys.First()

要逐個刪除項目，循環在副本Keys收集和呼叫allNodes.Remove(key);

foreach (var key in allNodes.Keys.ToList()) 
{ 
    allNodes.Remove(key); 
}

要回答你編的你問題，是SortedDictionary（對於這個問題的任何味道Dictionary）將不會處理重複鍵 - 如果您嘗試添加一個項目與現有的密鑰它將覆蓋前真正的價值。

你可以使用一個SortedDictionary<float, List<Node<T>>>但你必須提取集合與項目的複雜性，需要對初始化每個列表，而不是僅僅增加一個項目，等等這一切都可能，並可能仍然是最快的結構增加並得到，但它確實增加了一點複雜性。

2013-04-17 20:32:03

由於Dictionary<TKey, TValue>必須有唯一的密鑰，我會使用List<Node<T>>來代替。舉例來說，如果你的Node<T>類有一個Value財產

class Node<T> 
{ 
    float Value { get; set; } 
    // other properties 
}

，並且希望通過這個屬性進行排序，使用LINQ：

var list = new List<Node<T>>(); 

// populate list 

var smallest = list.OrderBy(n => n.Value).FirstOrDefault();

要逐個刪除節點，只是想迭代扔列表：

while (list.Count > 0) 
{ 
    list.RemoveAt(0); 
}

2013-04-17 20:30:40

是的，你是對的複雜性。

在SortedDictionary所有的鍵都排序。如果你想從最小到最大的迭代，foreach也就足夠了：

foreach(KeyValuePair<float, Node<T>> kvp in allNodes) 
{ 
    // Do Something... 
}

你寫，你要刪除的項目。在foreach迭代過程中禁止從集合中刪除，因此請首先創建它的副本。

編輯：

是的，如果你有重複鍵不能使用SortedDictionary。創建Node<T>和float結構節點，然後寫一個比較器：

public class NodeComparer : IComparer<Node> 
{ 
    public int Compare(Node n1, Node n2) 
    { 
     return n2.dist.CompareTo(n1.dist); 
    } 
}

然後把一切簡單List<Node> allNodes和排序：

allNodes.Sort(new NodeComparer());

2013-04-17 20:32:25

回答