是否存在现有的 .Net 有序集合？

Question

我正在寻找一个.Net类，它可以基本实现以下功能：

• 确保其中的项是唯一的（像HashSet一样）
• 确保我们枚举时按照插入顺序获取项目（就像List一样）

是否存在一个现有的.Net类可以实现这一点？

我知道 HashSet （不保证顺序）， SortedSet （按内容排序），但它们不符合我的需求。我没有其他需求（比如 Stack 或 Queue ）。

我的当前替代方案是拥有一个 List<> ，并在添加和删除数据之前使用 Contains(...) 。

- J4N

---

你尝试过使用Dictionary，特别是SortedDictionary吗？这可能有点取巧，但可以满足你的需求。 - Vsevolod Goloviznin

@VsevolodGoloviznin 是的，但我真的没有任何关键字可以指定（而且我不确定“字典”在枚举中是否保证任何顺序。 - J4N

你需要插入键（这些键将是列表中的值），而值可以是任意随机值。哦，我的意思不是SortedDictionary，而是OrderedDictionary。 - Vsevolod Goloviznin

Answer 1

您说得对。HashSet不保留插入顺序。

Stackoverflow: HashSet that preserves ordering by achitaka-san 它使用字典来查找项，并使用链表来保留顺序。插入、删除和查找仍然以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);
    }
}

另一种实现：

@Codeproject: HashSet that Preserves Insertion Order 或 .NET LinkedHashSet 的实现

- SteMa

---

是的，我可以想象出很多自定义实现方式来实现这种行为，我的问题更多的是想知道是否有现成的官方集合可以实现这一点。 - J4N

我不知道任何官方实现。 - SteMa

Answer 2

您可以使用一个 OrderedDictionary，文档可以在此处找到。

您将使用当前List中的值作为字典中的键，并且可以将值保留为一些随机值。

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

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

唯一的缺点是这个词典没有使用泛型，你需要自己从object进行类型转换。

- Vsevolod Goloviznin

---

链接：http://msdn.microsoft.com/zh-cn/library/system.collections.specialized.ordereddictionary(v=vs.110).aspx - Matthew Watson

@MatthewWatson 谢谢，链接已修复 :) - Vsevolod Goloviznin

哎呀，不是通用的 :( - nawfal