c# - .NET中UniqueQueue和UniqueReplacementQueue集合的最高效实现

考虑到Enqueue和Dequeue操作的速度同等重要的事实，.NET中UniqueQueue和UniqueReplacementQueue集合的最有效的实现（就速度而言）。

UniqueQueue是一个队列，其中不可能重复。因此，如果我将元素推送到队列，仅在队列中尚不存在的情况下才添加该元素。

UniqueReplacementQueue是一个队列，其中也不能重复。不同之处在于，如果我推送队列中已经存在的元素，它将替换相同位置的现有元素。对于引用类型，这是有意义的。

我当前的UniqueQueue和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);
        }
    }
}

最佳答案

这已经很老了，但是具有内部HashSet和Queue的类又如何呢？ Enqueue first的自定义方法尝试将其添加到哈希集中。如果HashSet.Add调用返回false，则不将其加入队列。如果集合的大小足以容纳所有元素，则HashSet.Add（）是O（1）操作。

唯一的缺点是如果您担心这会占用内存。这是一个实现：

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

HashSet会尽可能使用，因为它通常更快。如果.NET的维护者将这些方法标记为虚拟方法，则可能会更好，但是，到此为止。