modo più efficace per trovare l'indice di un elemento in un SortedDictionary

Question

sto usando un dizionario ordinato di mantenere un elenco di elementi, di cui ho regolarmente necessità di monitorare lo stato dei migliori x elementi. Ogni volta che aggiorno un oggetto, mi piacerebbe un modo rapido di capire ciò che indice l'oggetto a cui mi riferisco sta usando. Capisco che posso enumerare l'intera lista e contare la mia posizione, ma cerco qualcosa con O (log n), o meglio, dopo tutto il dizionario ordinato è su un albero RedBlack. Ogni nodo dovrebbe essere in grado di tenere traccia dei suoi figli, e questo dovrebbe essere un rapido calcolo.

Answer 1

Si può semplicemente cambiare la vostra SortedDictionary<TKey, TValue> in un SortedList<TKey, TValue> e quindi utilizzare IndexOfKey(key):

var s = new SortedList<string, string>
    { { "a", "Ay" }, { "b", "Bee" }, { "c", "Cee" } };

// Outputs 1
Console.WriteLine(s.IndexOfKey("b"));

IndexOfKey utilizza internamente Array.BinarySearch<TKey>(), quindi sarà O (log n ), che è più veloce di O ( n ) (che sarebbe se hai cercato dalla parte anteriore a indietro di iterazione attraverso di esso).

Answer 2

Una struttura ad albero potrebbe essere costruito a elementi di accesso in base all'indice o per segnalare l'indice di un elemento esistente in tempo LGN, che richiede molto leggera tempo supplementare per inserti ed eliminazioni. Un modo per farlo sarebbe quello di tenere traccia di quanti articoli sono nei rami destro e sinistro di ciascun nodo (su un inserto o cancellare, modificare il conteggio di nodo di nodi padre quando si cambia il conteggio dei figli). Se una struttura ad albero non offre tale impianto una, però, non conosco nessun modo semplice per il retrofit di esso.