SortedSet.IsSubsetOf 未按预期工作

Question

我不相信

SortedSet.IsSubsetOf

能按预期工作。给出这段代码，

ss.IsSubsetOf(l)

不应该返回True吗？

我怀疑问题出在我的

CompareTo

函数中，但我看不到问题。

我还添加了一个单独的循环，认为必须在

other

IEnumerable 内找到该集合并进行排序。 。 。但这也行不通。

谁能解释为什么会发生这种行为？

List<Point> l = new();
SortedSet<Point> ss = new();
HashSet<Point> h = new();

for (int i = 0; i < 100; i++)
{
    var p = new Point(i, i);
    l.Add(p);
    l.Add(p);
    h.Add(p);
    h.Add(p);
    ss.Add(p);
    ss.Add(p);
}

// additional loop to get a sorted set.
for (int i = 0; i < 100; i++)
{
    l.Add(new Point(i, i));
}

Console.WriteLine(l.Count); // 300
Console.WriteLine(h.Count); // 100
Console.WriteLine(ss.Count); // 100
Console.WriteLine(h.IsSubsetOf(l));  // True (as expected)
Console.WriteLine(h.IsProperSubsetOf(l)); // False

// This is the line in question
Console.WriteLine(ss.IsSubsetOf(l)); // False ?????????

Console.WriteLine(ss.IsProperSubsetOf(l)); // False

readonly struct Point : IComparable<Point>, IEquatable<Point>
{
    public Point(double x, double y)
    {
        X = x;
        Y = y;
    }

    public double X { get; }
    public double Y { get; }

    public int CompareTo(Point other)
    {
        if (X == other.X)
        {
            return Y.CompareTo(other.Y);
        }
        else
        {
            return X.CompareTo(other.X);
        }
    }

    public bool Equals(Point other)
    {
        return X == other.X && Y == other.Y;
    }

    public override int GetHashCode()
    {
        return HashCode.Combine(X, Y);
    }
}

Answer 1

是的，这是一个错误。据我了解，错误的代码是确定集合大小的代码（似乎是一棵红黑树），稍后将用作一些位魔法的一部分：

int originalLastIndex = Count;

当前元素的索引是通过 以下代码确定的：

internal virtual int InternalIndexOf(T item)
{
    Node? current = root;
    int count = 0;
    while (current != null)
    {
        int order = comparer.Compare(item, current.Item);
        if (order == 0)
        {
            return count;
        }

        current = order < 0 ? current.Left : current.Right;
        count = order < 0 ? (2 * count + 1) : (2 * count + 2);
    }

    return -1;
}

稍后用于标记位表示遇到的索引：

int intArrayLength = BitHelper.ToIntArrayLength(originalLastIndex);

Span<int> span = stackalloc int[StackAllocThreshold];
BitHelper bitHelper = intArrayLength <= StackAllocThreshold ?
    new BitHelper(span.Slice(0, intArrayLength), clear: true) :
    new BitHelper(new int[intArrayLength], clear: false);

// ...

foreach (T item in other)
{
    int index = InternalIndexOf(item);
    if (index >= 0)
    {
        if (!bitHelper.IsMarked(index))
        {
            // item hasn't been seen yet
            bitHelper.MarkBit(index);
        }
    }
    // ...
}

和

BitHelper

实施。

问题是，对于不平衡的情况，

InternalIndexOf

计算的索引会“溢出”

BitHelper

的容量，导致不平衡的重复项丢失。

我的最小重现如下：

SortedSet<int> ss = new();
HashSet<int> h = new();

var num = 18;
for (int i = 0; i < num; i++)
{
    h.Add(i);
    ss.Add(i);
}

var data = Enumerable.Range(0, num).Append(17);
var hashSetEquals = h.SetEquals(data); // True
var sortedSetEquals = ss.SetEquals(data); // False 

请注意，如果您使用

SortedSet

的构造函数来生成平衡（基于实现）树，则代码将起作用：

HashSet<int> h = new();
var num = 18;
for (int i = 0; i < num; i++)
{
    h.Add(i);
}
SortedSet<int> ss = new(h); // will balance the tree
var data = Enumerable.Range(0, num).Append(17);
var hashSetEquals = h.SetEquals(data);
var sortedSetEquals = ss.SetEquals(data);

演示 @sharplab.io

附注

有人报告了该问题@github