如何从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已成功检索.)

但这根本不会有效.

如果可行,请考虑使用a 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集合(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);