我正在将一些 C++ 代码转换为 C#，它调用 std::map::lower_bound(k) 在映射中查找其键等于或大于 k 的条目。但是，我看不到任何方法可以用 .NET 的 SortedDictionary 做同样的事情。我怀疑我可以使用 SortedList 实现一种解决方法，但不幸的是，SortedList 太慢（插入和删除键的 O(n)）。我能做些什么？
注意：我找到了一种利用我的特定场景的解决方法......具体来说，我的键是从 0 开始的密集整数，所以我使用 List<TValue> 作为我的字典，列表索引用作密钥，并且搜索等于或大于 k 的密钥只需几个循环迭代即可完成。但是很高兴看到原始问题得到回答。
我开发了几个支持“查找下一个较高键”和“查找下一个较低键”操作的集合类。
首先，我制作了一套Compact Patricia Trie系列。这些是旨在最小化内存使用的集合/字典；它们对于大量 URL 和某些其他类型的数据特别有效。它们只能部分解决问题，因为只支持某些类型的键，即byte[],string和所有原始整数类型 (Int8..UInt64)。此外，字符串排序区分大小写。NuGet 包：Loyc.Utilities
发布这个答案后，我制作了更多排序的数据结构来解决这个问题：BList<T>、BDictionary<K,V>和. 有关详细信息，请参阅我的第二个答案。BMultiMap<K,V>SparseAList<T>
问题是字典/哈希表旨在根据输入值到达唯一的内存位置，因此您需要一个数据结构，旨在容纳与您存储的每个值相关的范围，同时时间正确更新每个间隔
我认为跳过列表（或平衡二叉树）可以帮助你。尽管它们不能在 O(n) 中执行查找，但它们可以以对数方式执行，并且仍然比树快。
我知道这不是一个正确的答案，因为我不能说 .NET BCL 已经包含这样一个类，不幸的是你必须自己实现一个，或者找到一个支持它的第 3 方程序集。不过，这里的 CodeProject似乎有一个很好的例子。
你可以试试我下面写的代码。它使用二进制搜索，因此假设列表/数组是预先排序的。
public static class ListExtensions
{
public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer)
{
return GetAtMostIndex(list, value, comparer, 0, list.Count);
}
public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer)
{
return GetAtLeastIndex(list, value, comparer, 0, list.Count);
}
public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count)
{
if (count == 0)
{
return -1;
}
int startIndex = index;
int endIndex = index + count - 1;
int middleIndex = 0;
int compareResult = -1;
while (startIndex < endIndex)
{
middleIndex = (startIndex + endIndex) >> 1; // / 2
compareResult = comparer.Invoke(list[middleIndex], value);
if (compareResult > 0)
{
endIndex = middleIndex - 1;
}
else if (compareResult < 0)
{
startIndex = middleIndex + 1;
}
else
{
return middleIndex;
}
}
if (startIndex == endIndex)
{
compareResult = comparer.Invoke(list[startIndex], value);
if (compareResult <= 0)
{
return startIndex;
}
else
{
int returnIndex = startIndex - 1;
if (returnIndex < index)
{
return -1;
}
else
{
return returnIndex;
}
}
}
else
{
//todo: test
return startIndex - 1;
}
}
public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count)
{
if (count == 0)
{
return -1;
}
int startIndex = index;
int endIndex = index + count - 1;
int middleIndex = 0;
int compareResult = -1;
while (startIndex < endIndex)
{
middleIndex = (startIndex + endIndex) >> 1; // / 2
compareResult = comparer.Invoke(list[middleIndex], value);
if (compareResult > 0)
{
endIndex = middleIndex - 1;
}
else if (compareResult < 0)
{
startIndex = middleIndex + 1;
}
else
{
return middleIndex;
}
}
if (startIndex == endIndex)
{
compareResult = comparer.Invoke(list[startIndex], value);
if (compareResult >= 0)
{
return startIndex;
}
else
{
int returnIndex = startIndex + 1;
if (returnIndex >= index + count)
{
return -1;
}
else
{
return returnIndex;
}
}
}
else
{
return endIndex + 1;
}
}
}
我创建了几个为任何数据类型提供此功能的数据结构：（BList<T>排序列表）、BDictionary<K,V>（其项按键排序的字典）和BMultiMap<K,V>（其中多个值可以与键关联的字典）。有关详细信息，请参阅本文。这些数据结构中的每一个都提供FindLowerBound()与FindUpperBound()C++lower_bound和upper_bound. 在内部，这些集合类似于B+ 树，因此它们具有良好的性能和较低的内存使用率；假设使用 64 位键和 64 位值，BDictionary<,>通常使用的内存比标准少约 44% SortedDictionary<,>（而后者平均使用的内存略少于）。Dictionary<,>
我还做了一个“稀疏”集合，SparseAList<T>它类似于，BDictionary<int,T>除了您可以在集合中的任何位置插入和删除“空白空间”（空白空间不消耗任何内存）。有关详细信息，请参阅本文。
所有这些集合都在Loyc.Collections NuGet 包中。
找到最接近 K：
dict.Keys.Where(i => i >= K).OrderBy(i => i).First();
或者更快：
public int? GetNearestKey(dict, K)
{
int? lowerK = null;
foreach (int key in dict.Keys)
{
if (key == K)
{
lowerK = K;
break;
}
else if (key >= K && (!lowerK.HasValue || key < lowerK))
{
lowerK = key;
}
}
return lowerK;
}
基本框架中没有二叉搜索树集合实现，因此您必须构建一个或找到一个实现。正如您所指出的，SortedList 在搜索方面最接近，但插入/删除速度较慢（由于其底层数组实现）。
我认为关于SortedList复杂性的问题存在错误。
SortedList具有 O(log(n)) 用于插入新项目的摊销复杂度。如果您事先知道容量，在最坏的情况下可以在 O(Log(n)) 中完成。
您可以SortedSet<T>使用以下扩展方法执行此操作：
public static class SortedSetExtensions
{
public static bool FindLowerOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
{
if(set.Count == 0)
{
first = default(T);
return false;
}
var minimum = set.Min;
if(set.Comparer.Compare(minimum, value) > 0)
{
first = default(T);
return false;
}
first = set.GetViewBetween(minimum, value).Max;
return true;
}
public static bool FindGreaterOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
{
if (set.Count == 0)
{
first = default(T);
return false;
}
var maximum = set.Max;
if (set.Comparer.Compare(maximum, value) < 0)
{
first = default(T);
return false;
}
first = set.GetViewBetween(value, maximum).Min;
return true;
}
}