我如何从SortedDictionary previous关键？

问题描述

我有一个包含键值对的字典。

I have dictionary containing key value pairs.

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

我想获得previous键值对从已知的密钥值。在上述情况下，如果我有4键，那么我怎样才能＆LT; 2,20＆GT;

推荐答案

这是很难用 SortedDictionary＆LT有效地实现这一点; TKEY的，TValue＆GT; ，因为它是作为一个二叉搜索树不暴露predecessors或接班人。

It's hard to implement this efficiently with a SortedDictionary<TKey, TValue> since it is implemented as a binary search tree that does not expose predecessors or successors.

您当然可以只列举每个KeyValuePair，直到找到已知的关键。随着LINQ的一点点，这样会看起来像（假设的关键肯定存在，已经不是第一次密钥）：

You could of course just enumerate each KeyValuePair until you find the "known" key. With a little bit of LINQ, this would look like (assuming the key definitely exists and isn't the first key):

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

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

如果这些假设不成立，你可以这样做：

If those assumptions don't hold, you could do:

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

（检查也许previousKvp！= NULL ，以确定该previous KeyValuePair被检索成功。）

(Check that maybePreviousKvp != null to ascertain that the previous KeyValuePair was retrieved successfully.)

但是，这不会是有效的。

But this isn't going to be efficient at all.

如果可行，可以考虑使用 排序列表＆LT ; TKEY的，TValue＆GT; 而不是（显然，这是不可能的，如果你不能把它较慢的插入和删除）。这个系列支持高效键和值检索用的订购的指数，因为它是作为一个可增长的阵列。然后你的查询变得简单：

If feasible, consider using a SortedList<TKey, TValue> instead (obviously, this may not be possible if you can't take its slower inserts and deletes). This collection supports efficient key and value-retrieval by ordered index since it is implemented as a growable array. Then your query becomes as simple as:

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）的时间运行。一切应在固定时间内运行，这意味着整个操作应该以对数时间运行。

IndexOfKey runs a binary search on the keys-list, running in O(log n) time. Everything else should run in constant time, meaning the entire operation should run in logarithmic time.

否则，你就必须自己实现/找到一个BST集合，确实暴露predecessors /接班人。

Otherwise, you'll have to implement yourself / find a BST collection that does expose predecessors / successors.

这篇关于我如何从SortedDictionary previous关键？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！