Как получить предыдущий ключ из SortedDictionary?

Question

У меня есть словарь, содержащий пары ключевых значений.

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

Я хочу получить предыдущую пару значений ключа из известного значения ключа. В приведенном выше случае, если у меня есть ключ 4, то как я могу получить <2,20>?

Answer 1

Это трудно эффективно реализовать это с SortedDictionary<TKey, TValue>, поскольку она реализуется в виде двоичного дерева поиска, не разоблачить предшественников или преемников.

Вы можете, конечно, просто перечислить каждый KeyValuePair, пока не найдете «известный» ключ. С немного LINQ, это будет выглядеть (предполагая, что ключ определенно существует, и не первый ключ):

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

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

Если эти предположения не выполняются, вы могли бы сделать:

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

(Убедитесь, что maybePreviousKvp != null чтобы убедиться, что предыдущий KeyValuePair был получен успешно.)

Но это не будет эффективным на всех.

---

Если это возможно, рассмотреть вопрос об использовании SortedList<TKey, TValue> вместо (очевидно, это не может быть возможным, если вы не можете взять его более медленные вставки и удаления). Эта коллекция поддерживает эффективный поиск ключей и значений на , заказанный индекс, поскольку он реализован как растущий массив. Тогда ваш запрос становится столь же просто, как:

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

запускает бинарный поиск по клавишам-списка, работает в O(log n) времени. Все остальное должно работать в постоянное время, то есть вся операция должна выполняться в логарифмическом времени.

---

В противном случае вам придется реализовать себя/найти коллекцию BST, которая будет показывать предшественников/преемников.

Answer 2

Dictionary<TKey,TValue> не отсортировано, поэтому нет предыдущий предмет для некоторых товаров. Вместо этого вы можете использовать SortedDictionary<TKey,TValue>.

EDIT: Извините, я прочитал название только LOL.

Если вы должны использования LINQ:

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

Answer 3

Вы можете цикл по словарю и следить за значениями, я думаю. Что-то вроде этого:

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

Однако это довольно сложная операция. Тот факт, что вам это нужно, может указывать на проблему с вашим дизайном.

Answer 4

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

Answer 5

Я бы предпочел использовать linq, если это так ...попробуйте это, безусловно, будет работать

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

Как насчет этого? Я не проверял его, но должен дать что-то, чтобы начать думать в этом направлении. Надеюсь, поможет.

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

тест на других условиях, как если (reqIndex! = -1) и т.д ..

Answer 7

Я также искал ответ на эту проблему, и я думал, что лучшее решение, чем все ответы здесь заключается в использовании TreeDictionary<K, V> от C5 Collections (GitHub/NuGet), который представляет собой реализацию красно-черного дерева.

имеет Predecessor/TryPredecessor и WeakPredessor/TryWeakPredecessor метода (а также эквивалентные методы для наследников), который делает именно то, что вы хотите.

Например:

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