使用SortedSet实现自定义排序队列时Remove移除Min元素失败问题

根因：比较器违反传递性导致SortedSet结构损坏 #

你遇到的Remove失败和排序异常问题，核心原因是自定义比较器不满足SortedSet要求的传递性规则，导致其内部平衡树结构被破坏，元素位置错乱，最终无法正确找到要删除的元素。

传递性违反的具体表现 #

你的排序规则会产生循环依赖的排序关系，例如：

• 元素A（路径P，index=1）和C（路径P，index=3）：同路径，A先于C（符合规则1）。
• 元素C和B（路径Q，index=2）：不同路径，C先于B（符合规则2，C的index更大）。
• 元素B和A：不同路径，B先于A（符合规则2，B的index更大）。

这就形成了A < C < B < A的循环，完全违反了排序的传递性（若A<C且C<B，则必须A<B）。SortedSet依赖严格的全序关系（自反、反对称、传递）来维护内部结构，这种循环会导致树结构混乱，元素无法被正确定位。

为什么SortedSet不适用 #

SortedSet要求比较器定义的排序必须是全序关系，而你的规则本质上无法形成全序——因为跨路径的优先级（高index优先）和同路径的FIFO（低index优先）会产生冲突的排序逻辑。因此，SortedSet并不是实现你需求的合适选择。

解决方案：组合数据结构实现需求 #

要满足你的规则（同路径FIFO，不同路径高index优先出队），可以采用路径队列字典+路径优先级排序集合的组合方案：

• 用字典存储每个路径对应的FIFO队列，保证同路径元素按入队顺序处理。
• 用SortedSet跟踪每个路径的最新元素index，确保每次出队时选择最新的路径。

实现代码示例 #

public class CustomSortingQueue<T>
{
    // 存储每个路径的FIFO队列
    private readonly Dictionary<string, Queue<(T Work, ulong Index)>> _pathQueues = new();
    // 按路径的最新元素index降序排序，优先选择最新的路径
    private readonly SortedSet<(ulong LatestIndex, string Path)> _sortedPaths = new(Comparer<(ulong LatestIndex, string Path)>.Create((x, y) =>
    {
        int indexCompare = y.LatestIndex.CompareTo(x.LatestIndex);
        if (indexCompare != 0)
            return indexCompare;
        // 避免同index的路径冲突（index唯一，实际不会触发）
        return x.Path.CompareTo(y.Path);
    }));

    private ulong _nextIndex = 0;

    public void Enqueue(T work, string fullPath)
    {
        if (!_pathQueues.TryGetValue(fullPath, out var queue))
        {
            queue = new Queue<(T Work, ulong Index)>();
            _pathQueues[fullPath] = queue;
        }

        var currentIndex = _nextIndex++;
        queue.Enqueue((work, currentIndex));

        // 更新路径的最新index记录
        _sortedPaths.RemoveWhere(item => item.Path == fullPath);
        _sortedPaths.Add((currentIndex, fullPath));
    }

    public (T Work, string FullPath) Dequeue()
    {
        if (_sortedPaths.Count == 0)
            throw new InvalidOperationException("队列为空");

        var highestPriorityPath = _sortedPaths.Min;
        var queue = _pathQueues[highestPriorityPath.Path];
        var item = queue.Dequeue();

        if (queue.Count == 0)
        {
            // 路径队列空了，移除该路径的所有记录
            _pathQueues.Remove(highestPriorityPath.Path);
            _sortedPaths.Remove(highestPriorityPath);
        }
        else
        {
            // 更新路径的最新index为队列最后一个元素的index
            _sortedPaths.Remove(highestPriorityPath);
            _sortedPaths.Add((queue.Last().Index, highestPriorityPath.Path));
        }

        return (item.Work, highestPriorityPath.Path);
    }
}

方案说明 #

1. 入队逻辑：将元素添加到对应路径的队列，并更新该路径在SortedSet中的最新index记录。
2. 出队逻辑：从SortedSet中获取最新的路径，取出该路径队列的第一个元素；若队列空则移除该路径的记录，否则更新路径的最新index。

这种方案完美满足你的需求：同路径元素按FIFO处理，不同路径优先处理最新入队的元素，且不会出现排序循环问题。

内容的提问来源于stack exchange，提问作者Loqaritm