什么.NET字典支持"查找最近的键"操作？

Question

我正在将一些C++代码转换为C#,并调用std :: map :: lower_bound(k)来查找映射中的键,该键的大小等于或大于k.但是,我没有看到任何方法与.NET的SortedDictionary做同样的事情.我怀疑我可以使用SortedList实现变通方法,但遗憾的是SortedList太慢(O(n)用于插入和删除键).我能做什么？

注意:我发现使用的解决方法利用了我的特定场景...具体来说,我的键是一个密集的整数,从0开始,所以我使用List <TValue>作为我的字典,列表索引作为密钥和搜索等于或大于k的密钥只能在几次循环迭代中完成.但是看到原来的问题得到解答仍然会很好.

Answer 1

我创建了几种为任何数据类型提供此功能的数据结构：（BList<T>排序列表）、BDictionary<K,V>（其项目按键排序的字典）和BMultiMap<K,V>（其中多个值可以与键关联的字典）。有关详细信息，请参阅这篇文章。这些数据结构中的每一个都提供了FindLowerBound()与FindUpperBound()C++lower_bound和upper_bound. 从内部来看，这些集合类似于B+树，因此具有良好的性能和较低的内存占用；BDictionary<,>通常比标准使用的内存少约 44% SortedDictionary<,>（而标准使用的内存平均比标准略少）Dictionary<,>假设 64 位密钥和 64 位值，

我还制作了一个“稀疏”集合，SparseAList<T>它与 类似BDictionary<int,T>，只是您可以在集合中的任何位置插入和删除“空白空间”（空白空间不消耗任何内存）。有关详细信息，请参阅这篇文章。

所有这些集合都位于Loyc.Collections NuGet 包中。