.Net 是否有 multiset 的实现？

Question

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

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

Answer 1

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

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

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();
    }
}

Answer 3

另一种选择是仅包装 SortedSet，但不是在其中存储类型 T，而是存储值元组 (T value, int counter) 其中，每插入一个新的 value 实例，counter 就会增加 1。本质上你是在强迫价值观是不同的。您可以有效地使用 GetViewBetween() 查找特定值的 counter 最大值，然后递增它以获取新添加值的计数器。与计数字典解决方案不同，您可以使用 GetViewBetween() 复制功能 equal_range、lower_bound 和 upper_bound > 以 C++ 形式给出。下面是一些代码，显示了我的意思：

public class SortedMultiSet<T> : IEnumerable<T>
{
    public void Add(T value)
    {
        var view = set.GetViewBetween((value, 0), (value, int.MaxValue));
        int nextCounter = view.Count > 0 ? view.Max.counter + 1 : 0;
        set.Add((value, nextCounter));
    }

    public bool RemoveOne(T value)
    {
        var view = set.GetViewBetween((value, 0), (value, int.MaxValue));
        if (view.Count == 0) return false;
        set.Remove(view.Max);
        return true;
    }

    public bool RemoveAll(T value)
    {
        var view = set.GetViewBetween((value, 0), (value, int.MaxValue));
        bool result = view.Count > 0;
        view.Clear();
        return result;
    }

    public SortedMultiSet<T> GetViewBetween(T min, T max)
    {
        var result = new SortedMultiSet<T>();
        result.set = set.GetViewBetween((min, 0), (max, int.MaxValue));
        return result;
    }

    public IEnumerator<T> GetEnumerator() =>
        set.Select(x => x.value).GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() =>
        set.Select(x => x.value).GetEnumerator();

    private SortedSet<(T value, int counter)> set =
        new SortedSet<(T value, int counter)>();
}

现在您可以编写如下内容：

var multiset = new SortedMultiSet<int>();
foreach (int i in new int[] { 1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 8 })
{
    multiset.Add(i);
}
foreach (int i in multiset.GetViewBetween(2, 7))
{
    Console.Write(i + " "); // Output: 2 2 3 4 5 5 6 7 7
}

在过去，存在一些问题，其中 GetViewBetween() 在时间 O(输出大小) 中运行，而不是在时间 O( log n)，但我认为这些已经解决了。当时它会对节点进行计数以缓存计数，现在它使用分层计数来有效地执行计数操作。请参阅此 StackOverflow 帖子和此库代码。

Answer 4

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();
        }
    }
}

Answer 5

您可以使用排序多重集的此实现： SortedMultiSet.cs