I was looking for a data structure (under .NET) which will do all tree basic operations (add, contains and remove) in constant-time O(1) and at the same time allow to retrieve elements exactly in the same order as they where added.
Some facts I’ve discovered after some googling:
- There is no such data structure natively available as of .NET 4.5
- Many people naively assume an ordinary .NET HashSet preserves insertion order
- Indeed HashSet accidentally preserves insertion order until you remove and re-add some elements
- There is such a data structure in Java – LinkedHashSet
- No I did not find a (working) corresponding implementation in .NET
So I’ve implemented one. Some notes before you go ahead and copy & paste the code:
- The example below implements only ICollection<T> generic interface which should be good enough for most cases.
- Inside this Gist you will find full ISet<T> generic implementation which is fully interchangeable with HashSet (after .NET 4.0, a HashSet had no dedicated interface before 4.0).
- The implementation uses linked list in combination with dictionary to define the iteration ordering and at the same time allow O(1) removal.
- The order is not affected if an element is re-inserted into the set it retains it’s old position.
Download OrderedSet c# Project
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 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); } 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; } }