.NET中是否有SortedList <T>类？

Question

我需要根据它们的内容对某些对象进行排序(实际上根据它们的一个属性,这不是关键,可能在不同对象之间重复).

.NET提供了两个类(SortedDictionary和SortedList),并且都使用二叉树实现.它们之间的唯一区别是

• SortedList比SortedDictionary使用更少的内存.
• 对于未排序的数据,SortedDictionary具有更快的插入和删除操作,O(log n)而不是SortedList的O(n).
• 如果列表是从排序数据中一次性填充的,则SortedList比SortedDictionary快.

我可以使用List实现我想要的,然后将其Sort()方法与IComparer的自定义实现一起使用,但它不会节省时间,因为每次我想要插入一个新对象时我会对整个List进行排序,而一个好的SortedList只会将项目插入正确的位置.

我需要的是一个带有RefreshPosition(int索引)的SortedList类,它只移动已更改(或插入)的对象,而不是每次内部对象更改时都使用整个列表.

我错过了一些明显的东西吗

Answer 1

也许我是缓慢的,但不是这个最简单的实现过？

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

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

不幸的是,Add不能重写,所以我不得不new这样做,当你有List<T> list = new SortedList<T>;我真正需要做的时候不那么好....所以我继续重建整个事情......

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();
    }
}

或许这样的事情是更合适的Remove功能......

    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;
    }

假设项目可以比较相等但不相等......

Answer 2

我需要的是一个带有 RefreshPosition(int index) 的 SortedList 类，用于仅移动更改（或插入）的对象，而不是每次内部对象更改时都重新排序整个列表。

当此类更新使索引无效时，为什么要使用索引进行更新？确实，我认为通过对象引用更新会更方便。您可以使用 SortedList 来执行此操作 - 只需记住您的Key类型与从对象中提取可比较数据的函数的返回类型相同。

class UpdateableSortedList<K,V> {
    private SortedList<K,V> list = new SortedList<K,V>();
    public delegate K ExtractKeyFunc(V v);
    private ExtractKeyFunc func;

    public UpdateableSortedList(ExtractKeyFunc f) { func = f; }

    public void Add(V v) {
        list[func(v)] = v;
    }
    public void Update(V v) {
        int i = list.IndexOfValue(v);
        if (i >= 0) {
            list.RemoveAt(i);
        }
        list[func(v)] = v;
    }
    public IEnumerable<T> Values { get { return list.Values; } }
}

我猜是这样的。