是否有一个排序列表< T>类.NET？ [英] Is there a SortedList<T> class in .NET?

问题描述

我需要根据它们的内容的一些对象进行排序（事实上，根据它们的性质，这是不关键，并且可以不同的对象之间进行复制的一个）。

I need to sort some objects according to their contents (in fact according to one of their properties, which is NOT the key and may be duplicated between different objects).

.NET提供了两个类（ SortedDictionary 和排序列表），无一不是使用二进制树来实现。它们之间唯一的区别是

.NET provides two classes (SortedDictionary and SortedList), and both are implemented using a binary tree. The only differences between them are

• SortedList的使用比SortedDictionary较少的内存。


• SortedDictionary对未排序的数据更快的插入和删除操作，O（log n）的，而不是为O（n）的排序列表。


• 如果该列表中填充所有从排序的数据一次，SortedList的比SortedDictionary快。

我可以实现我想用什么名单， ，然后使用它排序（）法的IComparer ，但它不会是时间效率，我想我要插入一个新的对象，每次排序整个名单，而一个好的排序列表只会在合适的位置插入的项目。

I could achieve what I want using a List, and then using its Sort() method with a custom implementation of IComparer, but it would not be time-efficient as I would sort the whole List each time I want to insert a new object, whereas a good SortedList would just insert the item at the right position.

我需要的是一个排序列表类与RefreshPosition（INT指数）只移动改变（或插入）对象，而不是每次都诉诸整个名单的变化里面的对象。

What I need is a SortedList class with a RefreshPosition(int index) to move only the changed (or inserted) object rather than resorting the whole list each time an object inside changes.

我失去了一些东西明显？

Am I missing something obvious ?

推荐答案

也许我是缓慢的，但不的这个的最简单的实现前所未有

Maybe I'm slow, but isn't this the easiest implementation ever?

class SortedList<T> : List<T>
{
    public new void Add(T item)
    {
        Insert(~BinarySearch(item), item);
    }
}

的 http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

不幸的是，添加是不能覆写，所以我不得不新它时，你有没有那么好的列表< T>名单=新SortedList的< T> ;; 我真正需要做的....所以我说干就干，重建了整个事情...

Unfortunately, Add wasn't overrideable so I had to new it which isn't so nice when you have List<T> list = new SortedList<T>; which I actually needed to do.... so I went ahead and rebuilt the whole thing...

class SortedList<T> : IList<T>
{
    private List<T> list = new List<T>();

    public int IndexOf(T item)
    {
        var index = list.BinarySearch(item);
        return index < 0 ? -1 : index;
    }

    public void Insert(int index, T item)
    {
        throw new NotImplementedException("Cannot insert at index; must preserve order.");
    }

    public void RemoveAt(int index)
    {
        list.RemoveAt(index);
    }

    public T this[int index]
    {
        get
        {
            return list[index];
        }
        set
        {
            list.RemoveAt(index);
            this.Add(value);
        }
    }

    public void Add(T item)
    {
        list.Insert(~list.BinarySearch(item), item);
    }

    public void Clear()
    {
        list.Clear();
    }

    public bool Contains(T item)
    {
        return list.BinarySearch(item) >= 0;
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        list.CopyTo(array, arrayIndex);
    }

    public int Count
    {
        get { return list.Count; }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    public bool Remove(T item)
    {
        var index = list.BinarySearch(item);
        if (index < 0) return false;
        list.RemoveAt(index);
        return true;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return list.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return list.GetEnumerator();
    }
}

---

或许这样的事情是一个比较合适删除函数...

    public bool Remove(T item)
    {
        var index = list.BinarySearch(item);
        if (index < 0) return false;
        while (((IComparable)item).CompareTo((IComparable)list[index]) == 0)
        {
            if (item == list[index])
            {
                list.RemoveAt(index);
                return true;
            }
            index++;
        }
        return false;
    }

假设项目可以比较平等的，但不等于...

Assuming items can compare equal but not be equal...

这篇关于是否有一个排序列表< T>类.NET？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！