Any existing .Net Ordered Set? [duplicate]

Question

I'm looking for .Net class, which will basically:

• Ensure that items are unique in it(like an HashSet)
• Ensure that when we enumerate, we get items in the same order than we inserted them(Like a List)

Is there an existing .Net class that does this?

I'm aware of the HashSet(which doesn't guarantee the order), the SortedSet(which order on the content), but they don't match my need. I don't have any other needs(like a Stack or a Queue).

My current alternative is to have a List<> and use the Contains(...) before Adding and Removing data.

Answer 1

You are right. HashSet do not preserve the insertion order.

Stackoverflow: HashSet that preserves ordering by achitaka-san It uses the Dictionary to look up items and the LinkedList to preserve order. All three insertion, removal and lookup work still in O(1).

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

Another implementation:

@Codeproject: HashSet that Preserves Insertion Order or .NET Implementation of LinkedHashSet

Answer 2

You can use an OrderedDictionary, documentation can be found here

You will use your values from your current List as keys in the dictionary and you can leave value as some randomness.

OrderedDictionary myOrderedDictionary = new OrderedDictionary();
myOrderedDictionary.Add(1, "smth");
myOrderedDictionary.Add(2, "smth");

foreach (DictionaryEntry v in myOrderedDictionary)
{
    int youValue = (int)v.Key;
}

The only downfall here is that this dictionary doesn't use generics and you have to cast from object yourself.