entspricht einem sortierten Wörterbuch, das doppelte Schlüssel erlaubt

Question

Ich brauche eine Datenstruktur, die Objekte nach den Float-Keys sortieren kann, denen sie zugeordnet sind, niedrigste zuerst. Das Problem ist, dass die Schlüssel Kosten darstellen, also gibt es oft Duplikate, das ist mir egal, denn wenn zwei die gleichen Kosten haben, nehme ich nur die erste, da es keinen Unterschied macht, das Problem ist, dass der Compiler sich beschwert.

Gibt es eine Datenstruktur, die sich auf die gleiche Weise verhält, aber doppelte Schlüssel erlaubt?

EDIT - ich muss noch die Duplikate aber, weil, wenn man eine Sackgasse erweist, ich das nächste greifen (sie Knoten in einer a * Suche sind)

so einfach klar zu sein, es muss doppelte Schlüssel zulassen, die in der richtigen Reihenfolge sortiert sind.

Answer 1

Was Sie suchen, heißt heap oder priority queue. Ich bin mir sicher, wenn Sie googlen, finden Sie eine für C#

Answer 2

Sie könnten immer noch ein Wörterbuch verwenden. Sie würden nur die Art des Wertes ändern müssen Sammlungen sein, anstatt einzelne Elemente:

Dictionary<float, List<T>> 

Ein Wörterbuch seiner Definition erlaubt keinen doppelten Schlüssel.

Answer 3

Sie suchen nach Lookup. Ähnlich wie bei anderen bereits vorgeschlagenen wörterbuchbasierten Lösungen wird ein IEnumerable unter jedem Schlüssel gespeichert, um Duplikate zu verarbeiten.

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

Answer 4

Sie schreiben:

zu einem Wörterbuch äquivalent, die doppelten Schlüssel

erlaubt Ich brauche eine Datenstruktur, die mit Objekten von dem Schwimmerschlüssel sie zugeordnet sortieren kann, niedrigster zuerst.

Ein Wörterbuch halten nicht die durch die Tasten sortiert Elemente, so dass die Struktur die Sie suchen, ist überhaupt zu einem eigentlich nicht gleichwertig Dictionary. Was Sie wollen, ist etwas Ähnliches wie eine SortedList oder SortedDictionary, außer dass es doppelte Schlüssel erlauben sollte.

Keine solche Klasse existiert in .NET. Jedoch Sie ein paar Optionen:

• Verwenden SortedDictionary<double, List<TValue>>, wenn Sie alle Werte für einen Schlüssel zugeordnet gespeichert werden soll, auch wenn Sie in der Regel nur die erste benötigen. Wenn Sie einen Schlüssel zum ersten Mal einfügen, erstellen Sie eine neue Liste und fügen Sie den Wert zur Liste hinzu. Wenn Sie einen bereits vorhandenen Schlüssel einfügen, rufen Sie die Liste ab und hängen Sie den Wert an die Liste an.
• _{Ihre Bearbeitung bedeutet, dass dieser Ansatz nicht auf Ihre Situation zutrifft.} Verwenden Sie SortedDictionary<double, TValue> und prüfen Sie vor dem Einfügen auf Duplikate. Es wird nur der erste Wert für jeden Schlüssel gespeichert. Im Gegensatz zu dem obigen Ansatz können Sie mit dieser Methode nicht auf den zweiten Wert zugreifen.
• Suchen Sie nach einer Bibliothek für Third Party Collections, die eine Klasse enthält, die Ihre Anforderungen erfüllt.

Verwandte

• What's the difference between SortedList and SortedDictionary?

Answer 5

Was du redest ist ein Tasche. Der Unterschied zwischen einem Beutel und einem Satz ist, dass Sets einzigartig sind, während Taschen Duplikate erlauben. {a, b, c} ist eine Menge; {a, b, c, a} ist eine Tasche.

Besorgen Sie sich eine Kopie der C5 Collections Library. Sie möchten die Klassen HashBag<T> oder TreeBag<T>. Der Unterschied besteht darin, dass der zugrunde liegende Datenspeicher in einem Fall ein Hash- und ein Rot-Schwarz-Baum in dem anderen ist. Äußerlich verhalten sie sich gleich. Entweder sollte man dir geben was du willst.

Answer 6

Sie könnten Ihre eigene Klasse erstellen, die von SortedSet ableitet:

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)); 
    } 
} 

Verwendung in einer Konsole App:

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(); 
} 

produziert dieses Ergebnis:

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

Answer 7

Ich habe getroffen Dieses Problem ein paar Mal, und ich verwende immer die öffentliche Lizenz (dh kostenlos) Power Collections von Win Telefon (http://powercollections.codeplex.com). Sie haben ein OrderedMultiDictionary, das genau das ist, wonach Sie suchen. Es ermöglicht doppelte Schlüssel und ermöglicht Ihnen, alle doppelten Schlüsseleinträge zu durchlaufen.

Answer 8

Sie sollten in der Lage sein, ein SortedDictionary mit einer benutzerdefinierten Implementierung von IComparer zu verwenden, um Kollisionen zu vermeiden. Zum Beispiel:

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

Sie können dies tun, indem Sie CompareTo function überschreiben. Wenn Sie einem SortedDictionary ein Element hinzufügen, verwendet es CompareTo(), wenn das Ergebnis 0 eine Exception trogt. Sie können jedoch das Verhalten des Komparators Ihrer Schlüsselklassenimplementierung so ändern, dass es nur größer als oder kleiner als (1 oder -1) zurückgibt.