[ACCEPTED]-The Most Efficient Implementation of UniqueQueue and UniqueReplacementQueue Collections in .NET-unique

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

The only 6 drawback to this is memory usage if this 5 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 4 HashSet is used whenever it can because 3 it is typically faster. This could be nicer 2 if the maintainers of .NET marked these 1 methods as virtual, but alas here we are.

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;
    }
}

0