¿Cómo obtengo la clave anterior de SortedDictionary?

Question

Tengo un diccionario que contiene pares de valores clave.

SortedDictionary<int,int> dictionary=new SortedDictionary<int,int>(); 
dictionary.Add(1,33); 
dictionary.Add(2,20); 
dictionary.Add(4,35); 

Quiero obtener un par de valores clave previo de un valor de clave conocido. En el caso anterior, si tengo la clave 4, ¿cómo puedo obtener <2,20>?

Answer 1

Es difícil implementar esto de manera eficiente con un SortedDictionary<TKey, TValue> ya que se implementa como un árbol binario de búsqueda que no exponga predecesores o sucesores.

Por supuesto, puede simplemente enumerar cada KeyValuePair hasta que encuentre la clave "conocida". Con un poco de LINQ, esto se vería así (suponiendo que la clave sin duda existe y no es la primera clave):

SortedDictionary<int, int> dictionary = ... 
int knownKey = ... 

var previousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey) 
          .Last(); 

Si estos supuestos no se sostienen, se podría hacer:

var maybePreviousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey) 
           .Cast<KeyValuePair<int, int>?>() 
           .LastOrDefault(); 

(Compruebe que maybePreviousKvp != null comprobar que la KeyValuePair anterior fue recuperado satisfactoriamente.)

Pero esto no va a ser eficiente en absoluto.

---

Si es posible, considere el uso de un SortedList<TKey, TValue> lugar (obviamente, esto puede no ser posible si usted no puede tomar sus inserciones y eliminaciones más lentos). Esta colección admite claves eficientes y recuperación de valores por ordenado índice ya que se implementa como una matriz cultivable. A continuación, la consulta se vuelve tan simple como:

SortedList<int, int> dictionary = ... 
int knownKey = ... 

int indexOfPrevious = dictionary.IndexOfKey(knownKey) - 1; 

// if "known" key exists and isn't the first key 
if(indexOfPrevious >= 0) 
{ 
    // Wrap these in a KeyValuePair if necessary 
    int previousKey = dictionary.Keys[indexOfPrevious]; 
    int previousValue = dictionary.Values[indexOfPrevious];  
} 

ejecuta una búsqueda binaria sobre las teclas de vinos, lo que se ejecuta en O(log n) tiempo. Todo lo demás debería ejecutarse en tiempo constante, lo que significa que toda la operación debería ejecutarse en tiempo logarítmico.

---

De lo contrario, tendrá que aplicar a sí mismo/BST encontrar una colección que hace exponer predecesores/sucesores.

Answer 2

Dictionary<TKey,TValue> no está clasificado, por lo que no hay anterior cosa para algún artículo. En su lugar, puede usar SortedDictionary<TKey,TValue>.

EDIT: siento haber leído el título solo jajaja.

Si usted tiene que uso de LINQ:

int givenKey = 4; 
var previousItem = dict.Where((pair, index) => 
            index == dict.Count || 
            dict.ElementAt(index + 1).Key == givenKey) 
         .FirstOrDefault(); 

Answer 3

Se puede recorrer el diccionario y realizar un seguimiento de los valores, supongo. Algo como esto:

public int GetPreviousKey(int currentKey, SortedDictionary<int, int> dictionary) 
{ 
    int previousKey = int.MinValue; 
    foreach(KeyValuePair<int,int> pair in dictionary) 
    { 
     if(pair.Key == currentKey) 
     { 
      if(previousKey == int.MinValue) 
      { 
       throw new InvalidOperationException("There is no previous key."); 
      } 
      return previousKey; 
     } 
     else 
     { 
      previousKey = pair.Key; 
     } 
    } 
} 

Sin embargo, esta es una operación bastante extraña para requerir. El hecho de que lo necesite podría estar apuntando a un problema con su diseño.

Answer 4

KeyValuePair<int, int> lookingForThis = dictionary 
    .Reverse() 
    .SkipWhile(kvp => kvp.Key != 4) 
    .Skip(1) 
    .FirstOrDefault(); 

Answer 5

Preferiría usar linq si ese es el caso ...intente esto seguramente funcionará

SortedDictionary<int,int> dictionary = new SortedDictionary<int,int>(); 
dictionary.add(1, 33); 
dictionary.add(2, 20); 
dictionary.add(4, 35); 

int SelectedKey = 4; 

var ResutValue = (from n in dictionary  
       where n.Key < TheSelectedKey 
       select n.Value).Last(); 

this.txtResult.Text = ResultValue.ToString(); 

Answer 6

¿Qué le parece esto? No lo he probado, pero debería dar algo para empezar a pensar en esta dirección. Espero eso ayude.

 int input = 4; 
     List<int> lKeys = dictionary.Keys.ToList(); 
     int reqIndex = lKeys.IndexOf(input) - 1; 
     int reqAnswer = dictionary[reqIndex]; 

prueba para otras condiciones como si (reqIndex! = -1), etc ..

Answer 7

También estaba buscando una respuesta a este problema, y ​​pensé que una solución mejor que todas las respuestas aquí es usar el TreeDictionary<K, V> del C5 Collections (GitHub/NuGet), que es una implementación de un árbol rojo-negro.

Tiene Predecessor/TryPredecessor y WeakPredessor/TryWeakPredecessor métodos (así como métodos equivalentes para los sucesores) que hace exactamente lo que quiere.

Por ejemplo:

TreeDictionary<int,int> dictionary = new TreeDictionary<int,int>(); 
dictionary.Add(1,33); 
dictionary.Add(2,20); 
dictionary.Add(4,35); 

// applied to the dictionary itself, returns KeyValuePair<int,int> 
var previousValue = dictionary.Predecessor(4); 
Assert.Equals(previousValue.Key, 2); 
Assert.Equals(previousValue.Value, 20); 

// applied to the keys of the dictionary, returns key only 
var previousKey = dictionary.Keys.Predecessor(4); 
Assert.Equals(previousKey, 2); 

// it is also possible to specify keys not in the dictionary 
previousKey = dictionary.Keys.Predecessor(3); 
Assert.Equals(previousKey, 2);