What .NET dictionary supports a "find nearest key" operation?
.net, dictionary, key, lower-bound
Solution
I created several data structures that provide this functionality for any data type: `BList<T>` (a sorted list), `BDictionary<K,V>` (a dictionary whose items are sorted by key), and `BMultiMap<K,V>` (a dictionary in which more than one value can be associated with a key). See this article for details. Each of these data structures provide `FindLowerBound()` and `FindUpperBound()` methods that work like C++'s `lower_bound` and `upper_bound`. Internally, these collections are similar to B+ trees, so they have good performance and low memory usage; `BDictionary<,>` typically uses about 44% less memory than a standard `SortedDictionary<,>` (which in turn uses, on average, slightly less memory than `Dictionary<,>`), assuming 64-bit keys and 64-bit values.
I also made a "sparse" collection, `SparseAList<T>`, which is similar to `BDictionary<int,T>` except that you can insert and remove "empty space" anywhere in the collection (empty space does not consume any memory). See this article for details.
All of these collections are in the Loyc.Collections NuGet package.
Problem
I'm converting some C++ code to C# and it calls std::map::lower_bound(k) to find an entry in the map whose key is equal to or greater than k. However, I don't see any way to do the same thing with .NET's SortedDictionary. I suspect I could implement a workaround using SortedList, but unfortunately SortedList is too slow (O(n) for inserting and deleting keys). What can I do? Note: I found a workaround using that takes advantage of my particular scenario... Specifically, my keys are a dense population of integers starting at just over 0, so I used a List<TValue> as my dictionary with the list index serving as the key, and searching for a key equal or greater than k can be done in only a few loop iterations. But it would still be nice to see the original question answered.