collection without duplicates but with order, with fast containment check and adding/removing

user_5333340 0
Viewed 97

I am looking for a collection that has fast containment check and adding/removing methods (like HashSet<T>, approaching O(1) if T is implemented well), but that also has an order. That does not mean indexed access - it merely means that if I iterate over it, the order of elements is the same as the order in which I added them.

Is there something like that in C#? Does HashSet<T> even do the trick? (I couldn't find that info on MSDN, I checked HashSet<T> and HashSet<T>.GetEnumerator.)

If not, I was thinking of implementing it with a class that contains an internal HashSet<T> and an internal LinkedList<T>. The HashSet<T> would expose the adding, removing and containment check while the LinkedList<T> would expose the enumerator.

collections c#
1 Answers

It seems that you are looking for the OrderedDictionary.

The only downside is that it doesn't support generics, but you can easily make a wrapper around it or just cast the values to the type you need.

EDIT: as @Blorgbeard refered to in the comments, you can find an implementation of an "OrderedSet" in another answer that meets your exact requirements (and implements this exactly with a LinkedList<T> and HashSet<T>), that might be useful to you.

Here is their implementation (credits go to the original author, not me)

public class OrderedSet<T> : ICollection<T>
{
    private readonly IDictionary<T, LinkedListNode<T>> m_Dictionary;
    private readonly LinkedList<T> m_LinkedList;

    public OrderedSet()
        : this(EqualityComparer<T>.Default)
    {
    }

    public OrderedSet(IEqualityComparer<T> comparer)
    {
        m_Dictionary = new Dictionary<T, LinkedListNode<T>>(comparer);
        m_LinkedList = new LinkedList<T>();
    }

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

    public virtual bool IsReadOnly
    {
        get { return m_Dictionary.IsReadOnly; }
    }

    void ICollection<T>.Add(T item)
    {
        Add(item);
    }

    public bool Add(T item)
    {
        if (m_Dictionary.ContainsKey(item)) return false;
        LinkedListNode<T> node = m_LinkedList.AddLast(item);
        m_Dictionary.Add(item, node);
        return true;
    }

    public void Clear()
    {
        m_LinkedList.Clear();
        m_Dictionary.Clear();
    }

    public bool Remove(T item)
    {
        LinkedListNode<T> node;
        bool found = m_Dictionary.TryGetValue(item, out node);
        if (!found) return false;
        m_Dictionary.Remove(item);
        m_LinkedList.Remove(node);
        return true;
    }

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

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

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

    public void CopyTo(T[] array, int arrayIndex)
    {
        m_LinkedList.CopyTo(array, arrayIndex);
    }
}
user_39635610
Related