保留sorting的HashSet

我需要一个保留插入顺序的HashSet,在框架中是否有这样的实现?

标准的.NET HashSet不保留插入顺序。 对于简单的testing,插入顺序可能由于意外而被保留,但是不能保证,并且不总是以这种方式工作。 certificate在两者之间做一些清除就足够了。

看到这个问题的更多信息: HashSet是否保留插入顺序?

我简要地实现了一个保证插入顺序的HashSet 。 它使用Dictionary来查找项目和LinkedList以保持顺序。 所有三个插入,删除和查找工作仍然在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); } } 

您可以使用KeyedCollection<TKey,TItem>轻松获得此functionKeyedCollection<TKey,TItem>为TKey和TItem指定相同的types参数:

 public class OrderedHashSet<T> : KeyedCollection<T, T> { protected override T GetKeyForItem(T item) { return item; } } 

如果你需要不断的AddRemoveContains和命令保存的复杂性,那么在.NET Framework 4.5中没有这样的集合。

如果你对第三方代码还好,看看我的存储库(许可MIT许可证): https : //github.com/OndrejPetrzilka/Rock.Collections

OrderedHashSet<T>集合:

  • 基于经典的HashSet<T>源代码(来自.NET Core)
  • 保留插入顺序并允许手动重新sorting
  • function颠倒枚举
  • 具有 HashSet<T> 相同的操作复杂性
  • HashSet<T>相比, AddRemove操作速度降低了20%
  • 每个项目消耗8个字节的内存