如何从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>？

- PramodChoudhari

---

SortedDictionary<int, int> dictionary = new SortedDictionary<int, int>(); - PramodChoudhari

我认为这个问题的答案解释了如何实现你想要的功能。 - Cody Gray

有没有任何 Linq 查询可以给我前一个键。 - PramodChoudhari

user578083，我已经使用Linq查询给出了一个答案，请查看一下...好的 :) - Carls Jr.

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对key列表进行二分搜索，运行时间为O(log n)。其他所有操作都应该在常数时间内运行，这意味着整个操作应该在对数时间内运行。

---

否则，你将不得不自己实现/找到一种BST集合，它公开了前任/后继。

- Ani

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

- rikoe

---

如果有人不知道什么是前驱，那么它是第一个等于或小于传入值的项。而（严格的）前驱则是刚好比传入值小的项。后继同理。 - nawfal

C5集合很酷，但是它们的文档在最新版本上存在问题，所以为了节省时间，克隆源代码并查看源代码。 - Lev

Answer 3

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

- Amy B

---

+1. 我只想指出，OP的问题并不是很有意义。虽然这个答案会返回之前的一对，但是随着你向字典中添加项目，之前的一对将会不断变化。我认为需要更多关于OP试图做什么的澄清。 - Rob

我认为应该是.SkipWhile(kvp => kvp.Key != 4).Skip(1)。 - Gabe

Answer 4

你可以遍历字典并跟踪值，我猜。像这样：

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

然而，这是一个相当奇怪的操作需求。你需要它的事实可能指向你的设计存在问题。

- Adam Lear

Answer 5

Dictionary<TKey,TValue>是未排序的，因此某些项没有上一个。相反，您可以使用SortedDictionary<TKey,TValue>。

编辑：对不起，我只看了标题哈哈。

如果您必须使用LINQ：

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

- Cheng Chen

---

尝试在接受dict和givenKey作为我的字典和我要从中开始的键的函数中使用它，并返回previousItem作为字符串，因为我有一个<string，DateTime>的字典。我收到一个错误：Cannot implicitly convert type 'System.Collections.Generic.KeyValuePair<string, System.DateTime>' to 'string'。所以这不仅仅返回键 - 我确认它返回整个KeyValuePair。所以在我的情况下，我做了KeyValuePair<string, DateTime> tempKVP = MoveToPreviousKey(myDict, givenKey);然后string previousKey = tempKVP.Key;。效果很好。希望对某人有所帮助。 - vapcguy

Answer 6

如果可以的话，我更喜欢使用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();

- Carls Jr.

Answer 7

这个怎么样？虽然我还没有测试过，但应该可以给你一个开始思考的方向。希望能有所帮助。

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

测试其他条件，例如 if (reqIndex != -1) 等等..

- franklins