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

У меня есть класс 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 используется в алгоритме, в котором производительность обработки (скорость) имеет решающее значение. Память важна, но не так сильно, как скорость. Существует список n Foo s, каждый из которых имеет до m Bar s. Этот класс довел меня до этого момента. Теперь я хочу предложить пользователю несколько вариантов, то есть мне нужно будет предоставить произвольный доступ к первым нескольким Bar в списке.

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

Ответ 1

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

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

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

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

Обратите внимание, однако: у вас не будет дубликатов в SortedList<,>, поэтому двум членам в списке не разрешено CompareTo друг другу с возвратным значением 0.

Ответ 2

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

Ответ 3

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

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 (n) Добавить | Текущее добавление также O (n)

A SortedList в NlogN, а затем у вас нет индекса, так как ключ - это Duration, а ключ не уникален

Вставка SortedSet - это LogN, но ToList - O (n), так что вы все еще O (n)

Вызов метода сортировки в списке - NlogN

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

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