Существует ли отсортированная очередь в .NET?

Question

Мне нужна довольно специализированная коллекция .NET, и я не думаю, что BCL может мне помочь, но я подумал, что выкину ее там, если кто-нибудь узнает о чем-то подобном.

В основном мои требования таковы:

• У меня есть список пар значений, таких как: (3, 10), (5, 10), (3, 7), (5, 5)
• Порядок важен, т.е. (3, 10)! = (10, 3)
• Дубликаты отдельных значений хороши, но дублирующие пары должны быть отброшены (желательно без вывода сообщений).
• Кикер, мне нужен этот список, отсортированный все время. Меня интересует только первое значение в списке, определенное алгоритмом сортировки в любой момент времени.

Итак, пример кода того, что я хочу сделать (поскольку я предполагаю, что это, вероятно, будет реализовано, другие реализации, которые соответствуют вышеописанному, подойдут):

public class Pair
{
    public Pair(int first, int second)
    { First = first; Second = second; }
    public int First { get; set; }
    public int Second { get; set; }
}

SortedQueue<Pair> foo = new SortedQueue<Pair>((left, right) => {
    return right.First - left.First;
});

foo.Add(new Pair(10, 3));
foo.Add(new Pair(4, 6));
foo.Add(new Pair(6, 15));
foo.Add(new Pair(6, 13)); // This shouldn't cause a problem

Pair current = foo.Shift(); // current = (4, 6)

Answer 1

Цитирую:

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

Звучит так, как будто вы не хотите отсортированную очередь, а приоритетную очередь . Если производительность является проблемой, то PQ, безусловно, будет быстрее, O (log n) против O (n). Но проблема удаления дубликатов потребует от вас также параллельного HashSet <>.

Answer 2

Вы просматривали SortedDictionary или SortedList ?

Answer 3

Ознакомьтесь с C5 Generic Collections Library , которая уже имеет реализацию, как вы ищете, под названием IntervalHeap или Priority Queue. Вот некоторая документация об этом из Книги C5: IPriorityQueue<T>

Answer 4

В настоящее время в .NET нет ничего, что отвечало бы всем вашим требованиям. В .NET 4.0 есть класс SortedSet. Я понимаю, что это, вероятно, не приносит вам ничего хорошего.

SortedList подходит близко, если вы реализуете IComparable. Вы бы просто использовали пару в качестве ключа и значения. Вы сохраняете ссылку на свою пару только дважды, так что это не требует больших затрат памяти. Но это не позаботится о дубликатах.

Существует множество способов написать это самостоятельно, но нет ничего встроенного в том, что полностью соответствует вашим потребностям. Существует несколько реализаций SortedSet с открытым исходным кодом (например, в Spring.Net). Это может быть вашей лучшей ставкой прямо сейчас.

Answer 5

Скорее всего, вы должны использовать класс Lookup, как Skeet упоминает в его ответ . Затем вы создаете и получаете к нему доступ примерно так:

List<Lookup<int, int>> yourList = new List<Lookup<int, int>>();
yourList.Add(new Lookup(3,5));
//...
var list = from item in yourList
           orderby list.Key //or whatever sort criteria you want here
           select item;
//use list

Синтаксис может быть немного неправильным в 1 или 2 местах, но он должен работать.

Answer 6

SortedList был бы лучшим, все, что вам нужно сделать, это реализовать IComparable в вашем классе Pair, и он автоматически упорядочит их. Что касается удаления дубликатов, я не думаю, что отсортированный список обрабатывает это, но вы можете наследовать его и добавить эту функциональность.