如何从SortedDictionary获取以前的密钥?

我有包含键值对的字典。

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

我想从已知的键值获取先前的键值对。 在上面的例子中,如果我有键4,那我怎么能得到

使用SortedDictionary很难有效地实现它SortedDictionary因为它是作为二进制搜索树实现的,不会公开前任或后继者。

您当然可以枚举每个KeyValuePair,直到找到“已知”密钥。 使用一点LINQ,这看起来像(假设密钥肯定存在并且不是第一个密钥):

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

如果这些假设不成立,你可以这样做:

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

(检查maybePreviousKvp != null以确定先前的KeyValuePair已成功检索。)

但这根本不会有效。


如果可行的话,考虑使用SortedList (显然,如果你不能采用较慢的插入和删除,这可能是不可能的)。 此集合支持通过有序索引进行有效的键和值检索,因为它是作为可增长的数组实现的。 然后您的查询变得如此简单:

 SortedList 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在keys-list上运行二进制搜索,在O(log n)时间内运行。 其他所有东西都应该在恒定的时间内运行,这意味着整个操作应该以对数时间运行。


否则,你将不得不实现自己/找到一个确实暴露前辈/后继者的BST集合。

我也在寻找这个问题的答案,我认为比这里的所有答案更好的解决方案是使用来自C5集合 ( GitHub / NuGet )的TreeDictionary ,这是一个红色的实现 – 黑树。

它具有Predecessor / TryPredecessorWeakPredessor / TryWeakPredecessor方法(以及后继的等效方法),它可以完全满足您的需求。

例如:

 TreeDictionary dictionary = new TreeDictionary(); dictionary.Add(1,33); dictionary.Add(2,20); dictionary.Add(4,35); // applied to the dictionary itself, returns KeyValuePair 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); 
 KeyValuePair lookingForThis = dictionary .Reverse() .SkipWhile(kvp => kvp.Key != 4) .Skip(1) .FirstOrDefault(); 

我猜你可以遍历字典并跟踪值。 像这样的东西:

 public int GetPreviousKey(int currentKey, SortedDictionary dictionary) { int previousKey = int.MinValue; foreach(KeyValuePair 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; } } } 

但是,这是一个非常奇怪的操作要求。 您需要它的事实可能指向您的设计的问题。

Dictionary是未排序的,因此某些项目没有先前的内容。 相反,您可以使用SortedDictionary

编辑:对不起,我只阅读标题LOL。

如果你必须使用LINQ:

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

我更愿意使用linq,如果是这样的话……试试这肯定会有用

 SortedDictionary dictionary = new SortedDictionary(); 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(); 

这个怎么样? 我没有测试过它,但是应该给这个方向开始思考。 希望能帮助到你。

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

测试其他条件,如if(reqIndex!= -1)等。