Come usare correttamente SortedDictionary in C#?

Question

Sto provando a fare qualcosa di molto semplice ma sembra che non capisco SortedDictionary.

Quello che sto cercando di fare è la seguente:
creare un dizionario ordinato che ordina i miei oggetti da qualche numero virtuale, in modo da creare un dizionario che assomiglia a questo

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

Ed ora dopo ho aggiungere elementi, voglio rimuoverli uno per uno (ogni rimozione dovrebbe essere a una complessità di O (log (n)) dal più piccolo al più grande

Come faccio? Ho pensato che semplicemente allNodes[0] sarà dammi il più piccolo, ma non lo è.

Inoltre, sembra che il dizionario non possa gestire chiavi duplicate. Mi sembra di utilizzare la struttura dati errata ...
Devo usare qualcos'altro se ho un mucchio di nodi che voglio essere ordinato in base alla loro distanza (virgola mobile)?

Answer 1

allNodes[0] non vi darà la prima voce nel dizionario - che vi darà la voce con un floatvalore chiave di 0.

Se si desidera il primo elemento, provare invece allNodes.Values.First(). O per trovare il primo chiave uso allNodes.Keys.First()

Per rimuovere gli articoli uno per uno, loop su una copia della collezione Keys e chiamare allNodes.Remove(key);

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

Per rispondere alla tua addendum al vostro domanda, sì SortedDictionary (qualsiasi sapore di Dictionary per quella materia) non gestirà chiavi duplicate - se provi ad aggiungere un elemento con una chiave esistente, lo sovrascriverà valore vizioso.

si potrebbe usare un SortedDictionary<float, List<Node<T>>> ma poi si deve la complessità di estrarre collezioni contro gli elementi, la necessità di inizializzare ciascuna lista, piuttosto che solo l'aggiunta di un elemento, ecc Tutto questo è possibile e può ancora essere la struttura più veloce per aggiunge e ottiene, ma aggiunge un po 'di complessità.

Answer 2

Poiché uno Dictionary<TKey, TValue> deve avere chiavi univoche, utilizzarei invece List<Node<T>>. Per esempio, se la classe Node<T> ha un Value proprietà

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

e si desidera ordinare da questa proprietà, usare LINQ:

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

// populate list 

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

Per rimuovere i nodi uno per uno, basta scorrere gettato la lista :

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

Answer 3

Sì, hai ragione riguardo alla complessità.

In SortedDictionary tutte le chiavi sono ordinate.Se si desidera iterare dal più piccolo al più grande, foreach sarà sufficiente:

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

Lei ha scritto che si desidera rimuovere gli elementi. È vietato rimuovere dalle raccolte durante l'iterazione con foreach, quindi in primo luogo creare una copia di esso per farlo.

EDIT:

Sì, se si è duplicato le chiavi non è possibile utilizzare SortedDictionary. Creare un nodo strutturale con Node<T> e float, quindi scrivere un operatore di confronto:

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

e poi mettere tutto in semplici List<Node> allNodes e scegli:

allNodes.Sort(new NodeComparer());