.net 中有没有按添加顺序排序的不重复的集合? 类似 Java 中的 LinkedHashSet

[bthulu]

只找到一个 SortedSet, 想要他按添加顺序排序, 必须给元素包装一下, 添加一个添加序号, 然后再指定一个按此序号排序的比较器, 比如像下面这样, 为了构造一个按添加顺序排序的 string 集合, 写了一堆代码, 实在是太麻烦了

    public void SortedSetSortByAddOrder()
    {
        SortedSet<(int, string)> set = new(new AddComparer())
        {
            (1, "first"),
            (2, "second"),
            (3, "third"),
            (4, "forth"),
            (5, "fifth"),
            (6, "sixth")
        };
    }
    
    public class AddComparer : IComparer<(int, string)>
    {
        public int Compare((int, string) x, (int, string) y)
        {
            return x.Item1.CompareTo(y.Item1);
        }
    }

[sunmker]

貌似没有

[netnr]

声明 两个对象，HashSet List

[thinkershare]

这样的集合效率必然低下，原生肯定是没有的， 可以自己实现一个， 不过效率嘛， 再怎么优化也不会太高。

[geelaw]

没有自带的。Microsoft 目前的 Dictionary 实现是用数组作为节点存储、下标作为指针的链表，数组里的顺序是遍历顺序，删除的时候把节点放入空闲链表，加入的时候优先使用空闲链表，其次使用数组之后的空位，最后考虑扩容。因此，加入 1 、2 、3 ，删除 2 ，加入 4 ，此后遍历顺序是 1 、4 、3 。当然，现在的实现不一定是未来的实现。

你可以仿照这个实现一下自己的 Dictionary ，删除的时候不要放入空闲链表，但要考虑碎片整理（例如有 1/2 空间是碎片的时候整理），加入的时候先考虑数组之后的空位，再考虑碎片整理，最后考虑扩容，以数组顺序作为遍历顺序。删除的时候碎片整理是为了提高均摊效率，当然坏处是删除操作会令所有迭代器无效（最新版本的 Dictionary 里，删除操作不会令迭代器无效）。

[a33291]

https://github.com/maroontress/Oxbind.CSharp
https://github.com/NightOwl888/J2N/blob/main/src/J2N/Collections/Generic/LinkedHashSet.cs

[FungKao]

https://gist.github.com/gmamaladze/3d60c127025c991a087e

[huang119412]

@thinkershare 这样的集合效率必然低下？你是怎么得出这个结论的？从名字看也是 HashSet ，O(1)的查找，效率低？ LinkedHashSet 和 SortedSet 根本不是一个类型。SortedSet 和 Hash 比才是效率低下。

[thinkershare]

@huang119412 我没有义务告诉你为什么.

[zhady009]

@thinkershare enrty 加两个一前一后的属性 维护起来跟链表一样这也叫效率低下？

[zhady009]

@zhady009 entry 修正下

[bthulu]

@zhady009 可以写个测试对比下 java 的 LinkedHashMap 和.net 的 SortedSet 到底哪个快不就知道了

[bthulu]

@FungKao 这里面的 IntersectWith 方法实现是有问题的, 可以参考我下面这个
public void IntersectWith(IEnumerable<T> other)
{
HashSet<T> intersection = other.Where(Contains).ToHashSet();
T[] removed = this.Where(e => !intersection.Contains(e)).ToArray();
foreach (T item in removed)
{
Remove(item);
}
}

[INCerry]

如果我没理解错，这两个能解决你的问题？
https://learn.microsoft.com/zh-cn/dotnet/api/system.collections.generic.sortedset-1?view=net-6.0
https://learn.microsoft.com/zh-cn/dotnet/api/system.collections.generic.priorityqueue-2.-ctor?view=net-6.0

[zmal]

3L 的这位，不懂还爱装 X 。'我没有义务告诉你为什么'，很久没见过这么爱装 X 的人了。

[zmal]

.net 的 SortSet 用红黑树实现的，相当于 Java 里的 TreeMap 、TreeSet 。
LinkedHashSet 相比 HashSet 每个 entry 多维护了两个指针，开销不大。