相當於一個允許重複鍵的排序字典

Question

我需要一個數據結構，它可以通過它們關聯的浮點鍵排序對象，最低優先。麻煩的是，鍵代表成本，所以經常重複，我不關心這個，因爲如果兩個有相同的成本，我會搶第一，因爲它沒有區別，問題是，編譯器抱怨。

是否有一個數據結構的行爲方式相同，但允許重複鍵？

編輯 - 我還需要重複的，但因爲如果一個人原來是一條死衚衕，我抓住下一個（他們在A *搜索節點）

所以僅僅是明確的，它需要允許按順序排序的重複鍵。

Answer 1

你在找什麼叫做heap或priority queue。我敢肯定，如果你谷歌，你會發現一個用於C＃

Answer 2

你仍然可以使用字典。您只需要將值的類型更改爲集合而不是單個項目：

Dictionary<float, List<T>> 

字典定義不允許重複鍵。

Answer 3

您正在尋找Lookup。 與其他基於字典的解決方案類似，它已在每個密鑰下存儲IEnumerable以處理重複。

var registry = Items.ToLookup(item=>item.Price); 
foreach(var item in registry[desiredPrice]) 
{ 
    //Here you handle items that all have Price == desiredPrice 
} 

Answer 4

你寫：相當於一本字典，允許重複鍵

我需要一個數據結構，可以按他們正在與相關聯的浮動鍵，第一個最低目標

。

字典不保留按鍵排序的項目，所以你正在尋找的結構實際上不等同於Dictionary。你需要的是類似於SortedList或SortedDictionary的東西，除了它應該允許重複鍵。

.NET中不存在這樣的類。然而，你有幾種選擇：

• 使用SortedDictionary<double, List<TValue>>如果要存儲一個鍵相關聯的所有值，即使你通常只需要第一。首次插入密鑰時，創建一個新列表並將該值添加到列表中。插入已存在的密鑰時，請取出列表並將該值附加到列表中。
• _{您的編輯意味着此方法不適用於您的情況。} 使用 SortedDictionary<double, TValue>並在插入前檢查重複項。只有每個鍵的第一個值纔會被存儲，因此與上面的方法不同，您不能使用此方法訪問第二個值。
• 找到一個第三方的集合庫，它有一個你想要的類。

相關

• What's the difference between SortedList and SortedDictionary?

Answer 5

什麼你所談論的是一個袋。 包包和集合之間的差異在於，包是獨特的，而包允許重複。 {a，b，c}是一個集合; {a，b，c，a}是一個包。

拿一份C5 Collections Library的副本。你想要的類HashBag<T>或TreeBag<T>。不同之處在於，其中一個基礎數據存儲是另一個散列，另一個是紅黑樹。在外部，他們的行爲是一樣的。要麼給你想要的東西。

Answer 6

從SortedSet派生你可以創建自己的類：在一個控制檯應用程序

public class SortedTupleBag<TKey, TValue> : SortedSet<Tuple<TKey, TValue>> 
    where TKey : IComparable 
{ 
    private class TupleComparer : Comparer<Tuple<TKey, TValue>> 
    { 
     public override int Compare(Tuple<TKey, TValue> x, Tuple<TKey, TValue> y) 
     { 
      if (x == null || y == null) return 0; 

      // If the keys are the same we don't care about the order. 
      // Return 1 so that duplicates are not ignored. 
      return x.Item1.Equals(y.Item1) 
       ? 1 
       : Comparer<TKey>.Default.Compare(x.Item1, y.Item1); 
     } 
    } 

    public SortedTupleBag() : base(new TupleComparer()) { } 

    public void Add(TKey key, TValue value) 
    { 
     Add(new Tuple<TKey, TValue>(key, value)); 
    } 
} 

用法：

private static void Main(string[] args) 
{ 
    var tuples = new SortedTupleBag<decimal, string> 
    { 
     {2.94M, "Item A"}, 
     {9.23M, "Item B"}, 
     {2.94M, "Item C"}, 
     {1.83M, "Item D"} 
    }; 

    foreach (var tuple in tuples) 
    { 
     Console.WriteLine("{0} {1}", tuple.Item1, tuple.Item2); 
    } 

    Console.ReadKey(); 
} 

會產生這樣的結果：

1.83 Item D 
2.94 Item A 
2.94 Item C 
9.23 Item B 

Answer 7

我已經打這個問題有好幾次了，我總是使用Win的公共許可證（即免費）Power Collections電話（http://powercollections.codeplex.com）。他們有一個OrderedMultiDictionary，正是你正在尋找的。它允許重複的鍵，它允許你迭代所有重複的鍵入口。

Answer 8

您應該能夠使用SortedDictionary和IComparer的自定義實現來避免衝突。例如：

private class NonCollidingFloatComparer : IComparer<float> 
{ 
    public int Compare(float left, float right) 
    { 
     return (right > left) ? -1 : 1; // no zeroes 
    } 
} 

// silly method for the sake of demonstration 
public void sortNodes(List<Node> nodesToSort) 
{ 
    SortedDictionary<float, Node> nodesByWeight = new SortedDictionary<float, Node>(new NonCollidingFloatComparer()); 
    foreach (Node n in nodesToSort) 
    { 
     nodesByWeight.Add(n.FloatKey, n); 
    } 
    foreach (Node n in nodesByWeight.Values) 
    { 
     Console.WriteLine(n.FloatKey + " : " + n.UniqueID); 
    } 
} 

Answer 9

您可以通過重寫CompareTo函數來實現。如果將一個元素添加到SortedDictionary中，它將使用CompareTo（），如果結果爲0，則會拋出一個異常，但您可以將鍵類實現的比較器行爲更改爲僅返回大於或小於（1或-1）

 public int CompareTo(int key) 
    { 
     if (this.key.CompareTo(key) < 1) 
      return 1; 
     else 
      return -1; 
    }