Коллекция, которая поддерживает порядок сортировки C#

Question

У меня есть класс Foo, который содержит список объектов: List<Bar>. Каждый из Bar имеет свойство, которое можно упорядочить (тип TimeSpan, представляющий продолжительность), а Bar - неизменный объект, то есть продолжительность не изменяется при работе алгоритма. На данный момент для каждого Foo я также поддерживаю Bar, который будет первым в списке, если он должен быть заказан (т. Е. Bar кратчайшей продолжительности). Что-то вроде этого:

public class Foo 
{ 
    public List<Bar> AllBars { get; set; } 

    public Bar FirstBar { get; set; } 

    public Foo (Bar bar) 
    { 
     FirstBar = bar; 

     AllBars = new List<Bar>() { bar }; 
    } 

    public AddBar(Bar bar) 
    { 
     if(bar.Duration < FirstBar.Duration) 
     { 
      FirstBar = bar; 
     } 

     AllBars.Add(bar); 
    } 
} 

Этот класс Foo используется в алгоритме, где производительность обработки (скорость) имеет решающее значение. Память важна, но не так сильно, как скорость. Существует список nFoo s, каждый из которых имеет до mBar s. Этот класс довел меня до этого момента. Теперь я хочу предложить пользователю несколько вариантов, то есть мне нужно будет предоставить произвольный доступ к первым немногим Bar s в списке.

Я хотел бы сохранить мои Bar s для того, чтобы я мог получить к ним доступ по индексу по порядку. В моем Bar классе I реализовано IComparable, чтобы можно было сравнивать Bar s, но я застреваю при выборе подходящего типа данных. Я посмотрел на System.Collections.SortedList, но (если я не ошибаюсь) это похоже на ссылку элементов по ключу, поскольку оно реализует IDictionary. Какую коллекцию я мог использовать, чтобы поддерживать мои объекты таким образом, чтобы они оставались отсортированными и чтобы они проходили по порядку индекса?

Answer 1

(пропагандируется комментарий, в соответствии с просьбой Аскер)

Если вы можете жить с наличием «ценности», которые ничего не значат, просто использовать SortedList<Bar, object>, где вы не используете значение части.

Добавить с yourSortedList.Add(yourBar, null) в O (n) раз (список должен будет перемещать «вверх» все записи после точки, в которую вы вставляете). Получите i-й элемент в O (1) раз с yourSortedList.Keys[i].

См. SortedList<,>.Keys property documentation для некоторых «доказательств», что приведенное выше описание верное. Обратите внимание, что SortedList<,> фактически состоит из «списка» (т. Е. Массива длины Capacity, подлежащего замене большим массивом, когда это необходимо). Это отличается от SortedDictionary<,>, который, я считаю, является двоичным деревом поиска.

Однако обратите внимание: Вы не сможете иметь дубликаты в SortedList<,>, так что два члена в списке не допускается CompareTo друг друга с возвращаемым значением нуля.

Answer 2

Я предпочитаю использовать SortedSet<T>, который является двоичным деревом, где ключ и значение являются одним и тем же объектом. Это еще раз означает, что добавление/удаление/поиск являются логарифмическими - O(log n) - но вы получаете возможность перебирать элементы по порядку. Для того чтобы этот сборник был эффективным, введите T, необходимо выполнить IComparable<T> или вам необходимо поставить внешний IComparer<T>.

Answer 3

Почему бы не просто использовать List.Insert?
Вставка - O (n) и позволяет вставлять определенный индекс.
п + п остается O (п)

public AddBar(Bar bar) 
{ 
    int index = 0;  
    foreach (bar b in AllBar) 
    { 
     if(bar.Duration < b.Duration) 
     break; 
     index++; 
    } 
    AllBars.Insert(index, bar); 
} 

Итак, вы вроде и O (1) индекс
Цены О (п) Добавить
Ток Добавить в также O (п)

SortedList в NlogN, и тогда вы не имеют индекс, как ключ продолжительность и ключ в не уникальный

SortedSet вставки является LogN но ToList О (п), так что вы все еще O (n)

Вызов метода Рода на список NlogN

Это отвечает на заявленный вопрос: Что коллекции я мог бы использовать, что бы сохранить свои объекты таким образом, что они остаются отсортированы, и таким образом, чтобы они проходимые в порядке индекс?

Я не думаю, что вы сделаете это лучше, чем O (n) Добавить.
Кто когда-нибудь давал ему голос, тогда лучшее решение?