c# - .Net 有多重集的实现吗？

Question

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

（多重集或袋子是一个可以具有重复值的集合，您可以在其上进行集合操作：交集、差异等。例如，可以将购物车视为多重集，因为您可以多次出现相同的产品。）

Answer 1

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

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

Answer 2

任何自称为多集的 C# 实现的东西都不应该在内部基于 Dictionary。字典是哈希表，无序集合。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();
    }
}

Answer 3

public class Multiset<T>: ICollection<T>
{
    private readonly Dictionary<T, int> data;

    public Multiset() 
    {
        data = new Dictionary<T, int>();
    }

    private Multiset(Dictionary<T, int> data)
    {
        this.data = data;
    }

    public void Add(T item)
    {
        int count = 0;
        data.TryGetValue(item, out count);
        count++;
        data[item] = count;
    }

    public void Clear()
    {
        data.Clear();
    }

    public Multiset<T> Except(Multiset<T> another)
    {
        Multiset<T> copy = new Multiset<T>(new Dictionary<T, int>(data));
        foreach (KeyValuePair<T, int> kvp in another.data)
        {
            int count;
            if (copy.data.TryGetValue(kvp.Key, out count))
            {
                if (count > kvp.Value)
                {
                    copy.data[kvp.Key] = count - kvp.Value;
                }
                else
                {
                    copy.data.Remove(kvp.Key);
                }
            }
        }
        return copy;
    }

    public Multiset<T> Intersection(Multiset<T> another)
    {
        Dictionary<T, int> newData = new Dictionary<T, int>();
        foreach (T t in data.Keys.Intersect(another.data.Keys))
        {
            newData[t] = Math.Min(data[t], another.data[t]);
        }
        return new Multiset<T>(newData);
    }

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

    public void CopyTo(T[] array, int arrayIndex)
    {
        foreach (KeyValuePair<T, int> kvp in data)
        {
            for (int i = 0; i < kvp.Value; i++)
            {
                array[arrayIndex] = kvp.Key;
                arrayIndex++;
            }
        }
    }

    public IEnumerable<T> Mode()
    {
        if (!data.Any())
        {
            return Enumerable.Empty<T>();
        }
        int modalFrequency = data.Values.Max();
        return data.Where(kvp => kvp.Value == modalFrequency).Select(kvp => kvp.Key);
    }

    public int Count
    {
        get 
        {
            return data.Values.Sum();
        }
    }

    public bool IsReadOnly
    {
        get 
        { 
            return false; 
        }
    }

    public bool Remove(T item)
    {
        int count;
        if (!data.TryGetValue(item, out count))
        {
            return false;
        }
        count--;
        if (count == 0)
        {
            data.Remove(item);
        }
        else
        {
            data[item] = count;
        }
        return true;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new MultisetEnumerator<T>(this);
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return new MultisetEnumerator<T>(this);
    }

    private class MultisetEnumerator<T> : IEnumerator<T>
    {
        public MultisetEnumerator(Multiset<T> multiset)
        {
            this.multiset = multiset;
            baseEnumerator = multiset.data.GetEnumerator();
            index = 0;
        }

        private readonly Multiset<T> multiset;
        private readonly IEnumerator<KeyValuePair<T, int>> baseEnumerator;
        private int index;

        public T Current
        {
            get 
            {
                return baseEnumerator.Current.Key;
            }
        }

        public void Dispose()
        {
            baseEnumerator.Dispose();
        }

        object System.Collections.IEnumerator.Current
        {
            get 
            {
                return baseEnumerator.Current.Key;
            }
        }

        public bool MoveNext()
        {
            KeyValuePair<T, int> kvp = baseEnumerator.Current;
            if (index < (kvp.Value - 1))
            {
                index++;
                return true;
            }
            else
            {
                bool result = baseEnumerator.MoveNext();
                index = 0;
                return result;
            }
        }

        public void Reset()
        {
            baseEnumerator.Reset();
        }
    }
}