Как я могу получить предыдущий ключ от 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];      
}

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

---

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

Answer 2

Я также искал ответ на эту проблему, и я подумал, что лучшим решением, чем все ответы здесь, является использование 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);

Answer 3

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

Answer 4

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

Answer 5

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

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 6

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

РЕДАКТИРОВАТЬ: Извините, я прочитал только название LOL.

Если вам нужно , используйте LINQ:

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

Answer 7

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

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

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