C# SortedList<K ,V> 上有下界函数吗？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/594518/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is there a Lower Bound function on a SortedList<K ,V>?
提问by agsamek
Is there a Lower Bound function on a SortedList<K ,V>? The function should return the first element equal to or greater than the specified key. Is there some other class that supports this?
上有下界函数SortedList<K ,V>吗？该函数应返回等于或大于指定键的第一个元素。是否有其他一些类支持这一点？
Guys - please read the question once again. I do not need a function that returns the key if it is present. I'm interested in scenario when there is no exact key matching.
伙计们 - 请再次阅读这个问题。如果键存在，我不需要返回键的函数。我对没有精确键匹配的场景感兴趣。
I'm interested in O(log n) time. It means that I do not have a problem with foreach loop, but rather would like to have an efficient way of doing this.
我对 O(log n) 时间感兴趣。这意味着我对 foreach 循环没有问题，而是希望有一种有效的方法来做到这一点。
I have done some tests on this.
我对此做了一些测试。
Linq statements are not optimized by neither the compiler nor runtime machine, so they walk through all collection elements and are slow O(n). Based on Mehrdad Afshari answer, here is a Binary Search that works in O(log n) on the Keys collection:
Linq 语句既没有被编译器也没有被运行时机器优化，所以它们遍历所有集合元素并且慢 O(n)。根据 Mehrdad Afshari 的回答，这里是一个二进制搜索，它在 Keys 集合上以 O(log n) 运行：
public static int FindFirstIndexGreaterThanOrEqualTo<T>(
this IList<T> sortedCollection, T key
) where T : IComparable<T> {
int begin = 0;
int end = sortedCollection.Count;
while (end > begin) {
int index = (begin + end) / 2;
T el = sortedCollection[index];
if (el.CompareTo(key) >= 0)
end = index;
else
begin = index + 1;
}
return end;
}
采纳答案by Mehrdad Afshari
Binary search the SortedList.Keyscollection.
二进制搜索SortedList.Keys集合。
Here we go. This is O(log n):
开始了。这是 O(log n)：
private static int BinarySearch<T>(IList<T> list, T value)
{
if (list == null)
throw new ArgumentNullException("list");
var comp = Comparer<T>.Default;
int lo = 0, hi = list.Count - 1;
while (lo < hi) {
int m = (hi + lo) / 2; // this might overflow; be careful.
if (comp.Compare(list[m], value) < 0) lo = m + 1;
else hi = m - 1;
}
if (comp.Compare(list[lo], value) < 0) lo++;
return lo;
}
public static int FindFirstIndexGreaterThanOrEqualTo<T,U>
(this SortedList<T,U> sortedList, T key)
{
return BinarySearch(sortedList.Keys, key);
}
回答by Garry Shutler
Not aware of one, but it's a simple LINQ statement:
不知道，但这是一个简单的 LINQ 语句：
first = sortedList.Where(x => x >= theObjectForComparison).FirstOrDefault();
firstwill either be the first object that passes the comparison or default(T)(which is normally null).
first要么是第一个通过比较的对象，要么default(T)（通常是null）。
Edit
编辑
DaveW's version:
DaveW 的版本：
first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);
does the same job but could potentially be faster, you'd have to test it though.
做同样的工作，但可能会更快，但你必须测试它。
回答by Dave W
I'd go with LINQ (presuming you're using C#3), but using the overload of FirstOrDefault that takes a predicate:
我会使用 LINQ（假设您使用的是 C#3），但是使用带有谓词的 FirstOrDefault 的重载：
first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);
(a lot of the other Enumerable methods can also take predicates which is a nice shortcut)
（许多其他 Enumerable 方法也可以使用谓词，这是一个很好的捷径）
回答by Migol
Or you can write own extension method to do this. Note that all those functions are NOT guaranteed to go in a sequesce.
或者您可以编写自己的扩展方法来执行此操作。请注意，不能保证所有这些功能都会按顺序进行。
回答by Shannon Monasco
Hopefully this should be faster, depending on SortedList's implementation.
希望这应该更快，这取决于 SortedList 的实现。
public static int FindFirstIndexGreaterThanOrEqualTo<K, V>(
this SortedList<K, V> sortedCollection, K key
) where V : new()
{
if (sortedCollection.ContainsKey(key))
{
return sortedCollection.IndexOfKey(key);
}
sortedCollection[key] = new V();
int retval = sortedCollection.IndexOfKey(key);
sortedCollection.Remove(key);
return retval;
}
