Есть ли класс .SortedList <T>в .NET?

Question

Мне нужно отсортировать некоторые объекты по их содержанию (фактически по одному из их свойств, которое НЕ является ключом и может дублироваться между различными объектами).

.NET предоставляет два класса ( SortedDictionary и SortedList ), и оба они реализованы с использованием двоичного дерева. Единственные различия между ними

• SortedList использует меньше памяти, чем SortedDictionary.
• SortedDictionary имеет более быстрые операции вставки и удаления для несортированных данных, O (log n), в отличие от O (n) для SortedList.
• Если список заполняется сразу из отсортированных данных, SortedList работает быстрее, чем SortedDictionary.

Я мог бы добиться того, что хотел, используя List, , а затем с помощью его метода Sort () с пользовательской реализацией IComparer , но он не смог бы экономить время, так как я сортировал бы весь список каждый раз, когда я хочу вставить новый объект, тогда как хороший SortedList просто вставил бы элемент в правильную позицию.

Что мне нужно, так это класс SortedList с RefreshPosition (int index) для перемещения только измененного (или вставленного) объекта вместо того, чтобы перебирать весь список каждый раз, когда объект внутри изменяется.

Я что-то упускаю из виду?

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

Я в конце концов решил написать это:

class RealSortedList<T> : List<T>
    {
        public IComparer<T> comparer;

        public int SortItem(int index)
        {
            T item = this[index];
            this.RemoveAt(index);
            int goodposition=FindLocation(this[index], 0, this.Count);
            this.Insert(goodposition, item);
            return goodposition;
        }

        public int FindLocation(T item, int begin, int end)
        {
            if (begin==end)
                return begin;
            int middle = begin + end / 2;
            int comparisonvalue = comparer.Compare(item, this[middle]);
            if (comparisonvalue < 0)
                return FindLocation(item,begin, middle);
            else if (comparisonvalue > 0)
                return FindLocation(item,middle, end);
            else
                return middle;
        }
    }

Answer 3

Я задал похожий вопрос некоторое время назад, и там есть хороших ответов . Там хорошая коллекция коллекций , здесь .

Answer 4

Не забывайте, что вставка элемента в список, поддерживаемый массивом, может быть дорогостоящей операцией - вставка группы элементов и последующая сортировка могут выполняться быстрее, если только вам не нужно сортировать после каждой отдельной операции.

Кроме того, вы всегда можете обернуть список и заставить операцию добавления найти нужное место и вставить его туда.

Answer 5

Я решил эту проблему в прошлом, написав метод расширения, который выполняет бинарный поиск по IList, и другой метод, который выполняет вставку. Вы можете найти правильную реализацию в исходном коде CLR, потому что есть встроенная версия, которая работает только с массивами, а затем просто настроить ее как расширение для IList.

Одна из тех вещей, которые "должны быть уже в BCL".

Answer 6

Мне нужен класс SortedList с RefreshPosition (int index) для перемещения только измененный (или вставленный) объект вместо того, чтобы прибегать к полному списку каждый раз, когда объект внутри меняется.

Зачем обновлять, используя индекс , когда такие обновления делают индекс недействительным? Действительно, я думаю, что обновление по ссылке на объект будет более удобным. Вы можете сделать это с помощью 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; } }
}

Что-то в этом роде, наверное.