Каков самый быстрый (скорость вставки) способ получения приоритетного набора массивов в.Net?

Question

Я пишу определенную очередь приоритетов. Его структура должна быть такой:

Priority(<int>)    Data(List<Object>)
1                  a, b, g, h
3                  c, d, j
4                  k
10                 e, f, i

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

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

Я думал о словаре, но если я не ошибаюсь, у него нет простого способа сказать "если ключ __ существует, дайте мне значение, соответствующее ему, в противном случае дайте мне ноль". Или я что-то упустил?

РЕДАКТИРОВАТЬ

Моя текущая реализация должна иметь 32 фиксированных списка. Применимый список добавлен, а применимый бит установлен в 32-битном флаге. Я использую алгоритм де Брюина, чтобы получить младший бит. Это эффективно, но добавляет другую сложность, которую я хочу облегчить.

Answer 1

Может быть, вы должны использовать Dictionary<int,List<object>>

public void Add(int priority,object data)
{
    if(dictionary.ContainsKey(priority))
       dictionary[priority].Add(data);
    else
       dictionary.Add(priority,new List<object>{data});
}

Answer 2

SortedDictionary будет выполнять работу. Просто используйте TryGetValue(), чтобы условно найти список.

Answer 3

Хм, что не так с Dictionary в качестве основного контейнера? Вы получаете O(1) время доступа / вставки в среднем вместо O(log n) с rb-деревьями. Просто заверните Dictionary в соответствии с вашими потребностями, например:

internal public class PriorityQueue<TValue> 
{
    private Dictionary<int, List<TValue>> mDict;

    // only Add, TryGetValue shown...
    public void Add(int pPriority, TValue pInput) 
    {
        List<TValue> tTmp;
        if (mDict.TryGetValue(pPriority, tTmp)) 
        {
            tTmp.Add(pInput);
        } 
        else 
        {
            mDict.Add(pPriority, new List<TValue>{ pInput });
        }
    }

    public bool TryGetValue(int pPriority, out List<TValue>) 
    {
        // obvious...
    }
}