.Net的multiset是否有任何实现？

Question

我正在寻找一个多集的.Net实现.谁能推荐一个好的？

(多集或包,是一个可以具有重复值的集合,您可以在其上设置操作:交集,差异等.例如购物车可以被认为是多集,因为您可以多次出现相同的产品.)

Answer 1

我不知道一个，但是你可以使用 a Dictionary，其中的值是项目的数量。当第二次添加该项目时，您将在字典中增加它的值。

另一种可能性是简单地使用 a Listof items，您可以在其中放置重复项。对于购物车，这可能是更好的方法。

Answer 2

任何自称为多重集的 C# 实现的东西都不应该在内部基于字典。字典是哈希表，无序集合。C++ 的集合、多重集合、映射和多重映射是有序的。在内部，每个都被表示为某种形式的自平衡二叉搜索树。

在 C# 中，我们应该使用 SortedDictionary 作为我们实现的基础，因为根据 Microsoft 自己的文档，SortedDictionary “是一个具有 O(log n) 检索能力的二叉搜索树”。基本多重集可以按如下方式实现：

public class SortedMultiSet<T> : IEnumerable<T>
{
    private SortedDictionary<T, int> _dict; 

    public SortedMultiSet()
    {
        _dict = new SortedDictionary<T, int>();
    }

    public SortedMultiSet(IEnumerable<T> items) : this()
    {
        Add(items);
    }

    public bool Contains(T item)
    {
        return _dict.ContainsKey(item);
    }

    public void Add(T item)
    {
        if (_dict.ContainsKey(item))
            _dict[item]++;
        else
            _dict[item] = 1;
    }

    public void Add(IEnumerable<T> items)
    {
        foreach (var item in items)
            Add(item);
    }

    public void Remove(T item)
    {
        if (!_dict.ContainsKey(item))
            throw new ArgumentException();
        if (--_dict[item] == 0)
            _dict.Remove(item);
    }

    // Return the last value in the multiset
    public T Peek()
    {
        if (!_dict.Any())
            throw new NullReferenceException();
        return _dict.Last().Key;
    }

    // Return the last value in the multiset and remove it.
    public T Pop()
    {
        T item = Peek();
        Remove(item);
        return item;
    }

    public IEnumerator<T> GetEnumerator()
    {
        foreach(var kvp in _dict)
            for(int i = 0; i < kvp.Value; i++)
                yield return kvp.Key;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}