The Most Efficient Implementation of UniqueQueue and UniqueReplacementQueue Collections in .NET

Question

What is the most efficient (in terms of speed) implementation of UniqueQueue and UniqueReplacementQueue collections in .NET considering the fact that the speed of Enqueue and Dequeue operations is equally important.

UniqueQueue is a queue where duplicates are not possible. So if I push an element to the queue it is added in only case it doesn't already exist in the queue.

UniqueReplacementQueue is a queue where duplicates are not possible either. The difference is that if I push an element which already exists in the queue, it replaces the existing element at the same position. It makes sense for reference types.

My current implementation of UniqueQueue and UniqueReplacementQueue:

sealed class UniqueQueue<T> : IQueue<T>
{
    readonly LinkedList<T> list;
    readonly IDictionary<T, int> dictionary;

    public UniqueQueue(LinkedList<T> list, IDictionary<T, int> dictionary)
    {
        this.list = list;
        this.dictionary = dictionary;
    }

    public int Length
    {
        get { return list.Count; }
    }

    public T Dequeue()
    {
        if (list.Count == 0)
        {
            throw new InvalidOperationException("The queue is empty");
        }

        var element = list.First.Value;
        dictionary.Remove(element);
        list.RemoveFirst();

        return element;
    }

    public void Enqueue(T element)
    {
        dictionary[element] = 0;

        if (dictionary.Count > list.Count)
        {
            list.AddLast(element);
        }
    }
}

sealed class UniqueReplacementQueue<T> : IQueue<T>
{
    readonly LinkedList<T> list;
    readonly IDictionary<T, T> dictionary;

    public UniqueReplacementQueue(LinkedList<T> list, IDictionary<T, T> dictionary)
    {
        this.list = list;
        this.dictionary = dictionary;
    }

    public int Length
    {
        get { return list.Count; }
    }

    public T Dequeue()
    {
        if (list.Count == 0)
        {
            throw new InvalidOperationException("The queue is empty");
        }

        var element = dictionary[list.First.Value];
        dictionary.Remove(element);
        list.RemoveFirst();

        return element;
    }

    public void Enqueue(T element)
    {
        dictionary[element] = element;

        if (dictionary.Count > list.Count)
        {
            list.AddLast(element);
        }
    }
}

Answer 1

This is pretty old, but how about a class that has an internal HashSet, and Queue. A custom method for Enqueue firsts tries to add it to the hashset. if the HashSet.Add call returns false, we do not enqueue it. HashSet.Add() is an O(1) operation if the set is of a size large enough to hold all elements.

The only drawback to this is memory usage if this is a concern for you. Here is an implementation:

public class UniqueQueue<T> : IEnumerable<T> {
    private HashSet<T> hashSet;
    private Queue<T> queue;


    public UniqueQueue() {
        hashSet = new HashSet<T>();
        queue = new Queue<T>();
    }


    public int Count {
        get {
            return hashSet.Count;
        }
    }

    public void Clear() {
        hashSet.Clear();
        queue.Clear();
    }


    public bool Contains(T item) {
        return hashSet.Contains(item);
    }


    public void Enqueue(T item) {
        if (hashSet.Add(item)) {
            queue.Enqueue(item);
        }
    }

    public T Dequeue() {
        T item = queue.Dequeue();
        hashSet.Remove(item);
        return item;
    }


    public T Peek() {
        return queue.Peek();
    }


    public IEnumerator<T> GetEnumerator() {
        return queue.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
        return queue.GetEnumerator();
    }
}

The HashSet is used whenever it can because it is typically faster. This could be nicer if the maintainers of .NET marked these methods as virtual, but alas here we are.

Answer 2

How about this?

//the UniqueQueueItem has the key in itself,
//and implements the IUniqueQueueItemable to copy the other values.
//For example:
class TestUniqueQueueItem : IUniqueQueueItemable<TestUniqueQueueItem>
{
    //Key
    public int Id { get; set; }
    public string Name { get; set; }
    public override int GetHashCode()
    {
        return Id;
    }

    //To copy the other values.
    public void CopyWith(TestUniqueQueueItem item)
    {
        this.Name = item.Name;
    }

    public override bool Equals(object obj)
    {
        return this.Id == ((TestUniqueQueueItem)obj).Id;
    }
}

internal interface IUniqueQueueItemable<in T>
{
    void CopyWith(T item);
}

class UniqueQueue<T> where T: IUniqueQueueItemable<T>
{
    private readonly bool _isReplacementQueue;
    private readonly Queue<T> _queue;
    private readonly Dictionary<T, T> _dictionary;

    public UniqueQueue(): this(false)
    {
    }

    public UniqueQueue(bool isReplacementQueue)
    {
        _isReplacementQueue = isReplacementQueue;
        _queue = new Queue<T>();
        _dictionary = new Dictionary<T, T>();
    }

    public void Enqueue(T item)
    {
        if(!_dictionary.Keys.Contains(item))
        {
            _dictionary.Add(item, item);
           _queue.Enqueue(item);
        }
        else
        {
            if(_isReplacementQueue)
            {
                //it will return the existedItem, which is the same key with the item 
                //but has different values with it.
                var existedItem = _dictionary[item];

                //copy the item to the existedItem. 
                existedItem.CopyWith(item);
            }
        }
    }

    public T Dequeue()
    {
        var item = _queue.Dequeue();
        _dictionary.Remove(item);
        return item;
    }
}