How would I implement a QueueDictionary, a combination of Queue and Dictionary in C#?

Question

Basically the data structure I want would mirror a MSMQ but would be in memory, because it is being used in the one process. By mirroring MSMQ I mean you would enqueue objects, then you could either dequeue objects or retrieve them using a key. Here is me initial attempt. My main problem with this attempt is that the Get by id would be used frequently and therefore the queue would end up having a lot of "dead" objects in it.

public class QueueDictionary<TKey, TValue>
{
    private readonly Queue _queue = new Queue();
    private readonly Dictionary<TKey, TValue> _dictionary = new Dictionary<TKey, TValue>();
    private readonly object _syncRoot = new object();

    public TValue Dequeue()
    {
        lock (_syncRoot)
        {
            TKey key = (TKey)_queue.Dequeue();
            while (!_dictionary.ContainsKey(key))
                key = (TKey)_queue.Dequeue();
            return _dictionary[key];
        }
    }

    public TValue Get(TKey key)
    {
        lock (_syncRoot)
        {
            TValue result = _dictionary[key];
            _dictionary.Remove(key);
            return result;
        }
    }

    public void Enqueue(TKey key, TValue value)
    {
        lock (_syncRoot)
        {
            _dictionary.Add(key, value);
            _queue.Enqueue(key);
        }
    }
}

Answer 1

Rather than using a Queue internally, you could use a LinkedList. Then in the Dictionary you can store the Key and the LinkedListNode. Then when you remove the item from the Dictionary, you can unlink the LinkedListNode from the linked list. Of course you loose the locality of the Queue, but gain the performance of the random access.

Here is a quick and dirty example, not tested so excuse any errors and no error checking. For example you should check if the queue is empty, make sure an item with the same key is not already in the dictionary etc.

public class QueueDictionary<TKey, TValue>
{
  private readonly LinkedList<Tuple<TKey, TValue>> _queue =
    new LinkedList<Tuple<TKey, TValue>>();

  private readonly Dictionary<TKey, LinkedListNode<Tuple<TKey, TValue>>> 
    _dictionary = new Dictionary<TKey, LinkedListNode<Tuple<TKey, TValue>>>();

  private readonly object _syncRoot = new object();

  public TValue Dequeue()
  {
    lock (_syncRoot)
    {
      Tuple<TKey, TValue> item = _queue.First();
      _queue.RemoveFirst();
      _dictionary.Remove(item.Item1);
      return item.Item2;
    }
  }

  public TValue Dequeue(TKey key)
  {
    lock (_syncRoot)
    {
      LinkedListNode<Tuple<TKey, TValue>> node = _dictionary[key];
      _dictionary.Remove(key);
      _queue.Remove(node);
      return node.Value.Item2;
    }
  }

  public void Enqueue(TKey key, TValue value)
  {
    lock (_syncRoot)
    {
      LinkedListNode<Tuple<TKey, TValue>> node = 
        _queue.AddLast(new Tuple<TKey, TValue>(key, value));
      _dictionary.Add(key, node);
    }
  }
}

Answer 2

What if you used a double-linked list to act as the Queue and that way you can have full control of the Enqueue, Dequeue, and specially the Get method. So in the Get method you can simply remove the key from the double-linked list.

Answer 3

Well your object can act like a queue without actually using the Queue class as its internal storage. Depending on how many items you plan on keeping, it might be easier just to maintain a single LinkedList(T) instead of storing the item in both a LinkedList(T) and a Dictionary(K,V).

But basically, instead of using a Queue internally, you could use a LinkedList(T) and just add new items to the end of the list and dequeue from the front of the list. When you need to find one by key, you can just scan the list for the matching key or if the number of items makes this perform poorly, you could double up your storage with a Dictionary(K, LinkedListNode(T)) and use the dictionary for your key lookups.