.net - 什么 .NET 字典支持 "find nearest key"操作？

Question

我正在将一些 C++ 代码转换为 C#，它调用 std::map::lower_bound(k) 在映射中查找其键等于或大于 k 的条目。但是，我看不出有任何方法可以用 .NET 的 SortedDictionary 做同样的事情。我怀疑我可以使用 SortedList 实现一种解决方法，但不幸的是 SortedList 太慢(插入和删除键的 O(n))。我能做什么？

注意:我找到了一种利用我的特定场景的解决方法......具体来说，我的键是从刚超过 0 开始的密集整数群，所以我使用 List 作为我的字典，列表索引用作键，并且搜索等于或大于 k 的键只能在几次循环迭代中完成。但是看到原始问题得到回答仍然很高兴。

Answer 1

我开发了几个支持“查找下一个更高键”和“查找下一个更低键”操作的集合类。
首先我做了一套Compact Patricia Trie集合。这些是旨在最小化内存使用量的集合/字典；它们对于大量 URL 和某些其他类型的数据特别有效。它们只能部分解决问题，因为只支持某些类型的 key ，即 byte[] , string , 以及所有原始整数类型 (Int8..UInt64)。此外，字符串排序区分大小写。 NuGet 包:Loyc.Utilities
发布这个答案后，我做了更多排序的数据结构，一般可以解决这个问题:BList<T> , BDictionary<K,V> , BMultiMap<K,V>和 SparseAList<T> .有关详细信息，请参阅我的第二个答案。