Set collection preserving insertion order

Question

I need a collection that behaves as Set and preserves order of element insertion.

Is there one or I'll have to implement it myself?

What would the best implementation be?

Answer 1

It doesn't exist in .NET, but you can emulate it using a List and the Distinct LINQ extension method, which should preserve the order of the underlying List.

Answer 2

Will an OrderedDictionary do what you want?

Although it is not generic (meaning everything it returns has to be cast or unboxed) and is a dictionary (not a set), it will behave the way you want. You could easily just use some arbitrary value like null or true as values and let the keys be the members of your set.

Here's a possible implementation:

public class OrderedSet : ICollection, IEnumerable
{
    OrderedDictionary dict = new OrderedDictionary();
    public void Add(object member)
    {
        dict.Add(member, null);
    }
    public void Clear()
    {
        dict.Clear();
    }
    public void CopyTo(Array array, int index)
    {
        for (int i = 0; i < Count; i++)
            array[i + index] = dict[i];
    }
    public bool Contains(object member)
    {
        return dict.Contains(member);
    }
    public void Insert(int index, object member)
    {
        dict.Insert(index, member, null);
    }
    public void Remove(object member)
    {
        dict.Remove(member);
    }
    public void RemoveAt(int index)
    {
        dict.RemoveAt(index);
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return dict.Keys.GetEnumerator();
    }

    public int Count { get { return dict.Count; } }
    public ICollection Members { get { return dict.Keys; } }
    bool ICollection.IsSynchronized { get { return dict.IsSynchronized; } }
    object ICollection.SyncRoot { get { return dict.SyncRoot; } }
}