为什么IList 没有排序？！？！ （编辑）的

I was pretty surprised when I discovered that there is no direct way to sort or perform a binary search on an IList< T >. Just like there are static methods to sort and perform a binary search on an Array, I think that it would be awfully helpful to have similar static methods that take an IList< T >.

当我发现没有直接的方法对IList 进行排序或执行二进制搜索时,我感到非常惊讶。就像有一些静态方法来对数组进行排序和执行二进制搜索一样,我认为使用类似于IList 的静态方法会非常有用。

Currently:

class Array
{
    static Sort<T>(T[] array);
    static int BinarySearch<T>(T[] array, T item);
}

I wish they would add:

我希望他们会补充:

class List
{
    static Sort<T>(IList<T> list);
    static int BinarySearch<T>(IList<T> list, T item);
}

I glanced at the .NET Framework 4.0 Beta SDK and there still doesn't appear to be a solution to this problem.

我瞥了一眼.NET Framework 4.0 Beta SDK,但似乎仍然没有解决这个问题的方法。

I know that I could work around this by creating an extension method that checks if it is a List< T > and then sort/search using the List< T > instance; however, if it is not an instance of a List< T >, then I have to perform a copy (which stinks for very large lists). I know I could do all of this, but why? Is there some reason they have intentionally omitted this feature?

我知道我可以通过创建一个扩展方法来解决这个问题,该方法检查它是否是List 然后使用List 实例进行排序/搜索;但是,如果它不是List 的实例,那么我必须执行一个副本(对于非常大的列表很臭)。我知道我可以做到这一切,但为什么呢?他们故意遗漏这个功能有什么理由吗?

To try to get this in the .NET 4.0 Framework, I have created a suggestion via Microsoft's Connect program. If you are frustrated like me about this issue, vote on it and maybe it will get added.

为了尝试在.NET 4.0 Framework中实现这一点,我通过Microsoft的Connect程序创建了一个建议。如果你像我这样对这个问题感到沮丧,那就投票吧,也许它会被添加。

https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=474201

5 个解决方案

#1

LINQ has a OrderBy method that works on all IEnumerable<T>, including IList<T>. You can accomplish the same thing using OrderBy.

LINQ有一个OrderBy方法,适用于所有IEnumerable ,包括IList 。你可以使用OrderBy完成同样的事情。

// Order a list of addresses:
IList<string> list = ...
var orderedList = list.OrderBy(input => input);

#2

I think there's a pretty good case for not including a sort method for IList<T>. First, it would create added complexity for those that want to implement an IList and second it would make it harder for the IList interface to conform to the Interface Segregation Principle.

我认为不包括IList 的排序方法是一个很好的例子。首先,它会为那些想要实现IList的人带来额外的复杂性,其次会使IList接口更难以符合接口隔离原则。

Generally what I do if I need to perform a sort on an IList<T> is create a new List<T> and pass in the IList<T> as a parameter

一般来说,如果我需要对IList 执行排序,我会创建一个新的List 并传入IList 作为参数

so for example:

例如:

        public IList<Address> SortAddresses(IList<Address> addresses)
        {
            var sortedAddresses = new List<Address>(addresses);
            sortedAddresses.Sort();
            return sortedAddresses;
        }

#3

The good news is that you can write such methods fairly easily; and thanks to C# 3.0 extension methods, you can make this work on the interface:

好消息是你可以很容易地写出这样的方法;并且由于C#3.0扩展方法,您可以在界面上进行此操作:

public static class ListExt
{
    public static void AddRange<T>(this IList<T> list, IEnumerable<T> items) {
        foreach(T item in items) list.Add(item);
    }
    public static void Sort<T>(this IList<T> list) {
        Sort<T>(list,Comparer<T>.Default); // ordinal sort by default
    }
    public static void Sort<T>(this IList<T> list, IComparer<T> comparer)
    { // very poor implementation!
        List<T> concreteList = new List<T>(list);
        concreteList.Sort(comparer); // cheat!
        list.Clear();
        list.AddRange(concreteList);
    }
    public static int BinarySearch<T>(this IList<T> list, T item) {
        return BinarySearch<T>(list, item, Comparer<T>.Default);
    }
    public static int BinarySearch<T>(this IList<T> list, T item,
        IComparer<T> comparer)
    {...} // TODO
}

Now all that remains is the TODO code itself (and probaby re-write Sort ;-p); but after that:

现在剩下的就是TODO代码本身(和probaby重写Sort ;-p);但在那之后:

IList<T> list = ...
list.Sort();
T huntFor = ...
int i = list.BinarySearch(huntFor);

Importantly, IList<T> has a read/write indexer, so it is certainly possible to do both the sort and binary-search without the hack above.

重要的是,IList 有一个读/写索引器,所以当然可以在没有上面的hack的情况下进行排序和二进制搜索。

#4

You do have ArrayList.Adapter that allows the use of ArrayList's sorting routines, but it would cause a huge performance impact for generic lists of unboxed value types, plus both virtual call and interface dispatch overhead.

您确实拥有允许使用ArrayList的排序例程的ArrayList.Adapter,但它会对未装箱值类型的通用列表以及虚拟调用和接口调度开销产生巨大的性能影响。

For both reference and value types, the interface dispatch could be expensive, meaning a call to ICollection<T>.CopyTo an array T[] followed by separate sort could be the fastest general purpose option, including a custom extension to directly sort on the IList<T> object.

对于引用和值类型,接口调度可能很昂贵,这意味着调用ICollection .CopyTo数组T []后跟单独的排序可能是最快的通用选项,包括直接排序的自定义扩展IList 对象。

List<T> has a Sort method because it can very efficiently operate on the underlying array of type T[]. There is simply no way to do this for an arbitrary IList<T>.

List 有一个Sort方法,因为它可以非常有效地对T []类型的底层数组进行操作。对于任意IList ,根本无法做到这一点。

#5

I'm not a C# expert, but very few List implementations support sorting, binary search, or even indexed retrieval. Lists are generally based on linked lists which don't usually offer an O(1) way of retrieving an item by its index. If you want to locate an element quickly, then use something that keeps the elements in sorted order like a tree or an array as suggested by others.

我不是C#专家,但很少有List实现支持排序,二进制搜索甚至索引检索。列表通常基于链表,这些链表通常不提供通过其索引检索项的O(1)方式。如果要快速定位元素,则使用按照其他人的建议将元素按照排序顺序保存的内容,如树或数组。

I do find the fact that IList includes an indexed retrieval method interesting. You might want to consider using SortedList instead of List since it looks like it should support lookups by index or key in O(1) time. In general, if you need something that supports fast lookup, then look for a data structure that keeps its elements in order instead of sorting them explicitly. If nothing else, C# has quite the litany of data structures already.

我确实发现IList包含一个有趣的索引检索方法。您可能想要考虑使用SortedList而不是List,因为它看起来应该支持在O(1)时间内通过索引或键进行查找。通常,如果您需要支持快速查找的内容,那么请查找保持其元素顺序而不是显式排序的数据结构。如果不出意外,C#已经有了很多数据结构。