.Net的multiset是否有任何实现？
我正在寻找一个多集的.Net实现。 任何人都可以推荐一个好的吗？
（多集或包，是一个可以具有重复值的集合，您可以在其上设置操作：交集，差异等。例如，购物车可以被认为是多集，因为您可以多次出现相同的产品。）
任何称自己为多重集的C＃实现的东西都不应该基于内部的Dictionary。 字典是哈希表，无序集合。 C ++的集合，多重集合，映射和多重映射都是有序的。 在内部，每个都表示为自平衡二叉搜索树的某种风格。
在C＃中，我们应该使用SortedDictionary作为我们实现的基础，根据Microsoft自己的文档，SortedDictionary“ 是一个带有O（log n）检索的二叉搜索树 ”。 基本多集可以实现如下：
public class SortedMultiSet : IEnumerable { private SortedDictionary _dict; public SortedMultiSet() { _dict = new SortedDictionary(); } public SortedMultiSet(IEnumerable 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 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 GetEnumerator() { foreach(var kvp in _dict) for(int i = 0; i < kvp.Value; i++) yield return kvp.Key; } IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); } } 我不知道一个，但你可以使用一个Dictionary ，其中值是项目的数量。 当第二次添加项目时，您可以在字典中增加它的值。
另一种可能性是简单地使用项目List ，您可以在其中放置重复项。 这可能是购物车的更好方法。
public class Multiset: ICollection { private readonly Dictionary data; public Multiset() { data = new Dictionary(); } private Multiset(Dictionary 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 Except(Multiset another) { Multiset copy = new Multiset (new Dictionary(data)); foreach (KeyValuePair 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 Intersection(Multiset another) { Dictionary newData = new Dictionary(); foreach (T t in data.Keys.Intersect(another.data.Keys)) { newData[t] = Math.Min(data[t], another.data[t]); } return new Multiset (newData); } public bool Contains(T item) { return data.ContainsKey(item); } public void CopyTo(T[] array, int arrayIndex) { foreach (KeyValuePair kvp in data) { for (int i = 0; i < kvp.Value; i++) { array[arrayIndex] = kvp.Key; arrayIndex++; } } } public IEnumerable Mode() { if (!data.Any()) { return Enumerable.Empty (); } 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 GetEnumerator() { return new MultisetEnumerator (this); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return new MultisetEnumerator (this); } private class MultisetEnumerator : IEnumerator { public MultisetEnumerator(Multiset multiset) { this.multiset = multiset; baseEnumerator = multiset.data.GetEnumerator(); index = 0; } private readonly Multiset multiset; private readonly IEnumerator> 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 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(); } } }