C#中是否有一种非唯一键排序列表的通用集合？

Question

我对System.Collections.Generic.SortedList有些惊讶，因为：

1. 它要求我使用<key, value>而不是<value>(比较器)
2. 每个值只允许一个条目

在我想要使用它的方式中，这些特点似乎有些古怪（尽管我相信它们对其他情况来说很正确）。有没有另一种集合不具备这两个特点？

- kdt

---

你想如何使用它？你对特定集合的要求是什么？ - Russ Cam

@Russ - 就我的需求而言，它类似于一个 List<KeyValuePair<K, V>>，但它支持按键进行二进制搜索。 - Jason Kleban

Answer 1

SortedList<,>其实是一个按键排序的映射表，而不是列表。也许命名不太好，但根据您的确切要求，有多种方法可以模拟您想要的功能。例如，您可以封装一个SortedList<T, int>，并添加/删除一些内容：

// add
int count;
if(list.TryGetValue(value, out count)) list[value] = count+1;
else list[value] = 1;

最终，您也可以使用简单的列表（List<>） - 这取决于您正在做什么。

部分原因在于，数据绑定等使得实现立即排序的常规列表变得困难 - 您需要实现许多界面才能使其工作，因为通常它期望添加的项留在末尾。

- Marc Gravell

Answer 2

我知道这是一个旧问题，但我刚刚发现另一个问题(C# Sortable collection which allows duplicate keys)，它提供了一种解决方案：使用自己的IComparer与SortedSet一起使用！

/// <summary>
/// Comparer for comparing two keys, handling equality as being greater
/// Use this Comparer e.g. with SortedSets, SortedLists or SortedDictionaries, that don't allow duplicate keys
/// </summary>
/// <typeparam name="TKey"></typeparam>
public class DuplicateKeyComparer<TKey> : IComparer<TKey> where TKey : IComparable
{
    #region IComparer<TKey> Members

    public int Compare(TKey x, TKey y)
    {
        int result = x.CompareTo(y);

        return result == 0 ? 1 : result; // Handle equality as being greater
    }

    #endregion
}

使用方法：

SortedSet<T> mySortedValues = new SortedSet<T>(new DuplicateKeyComparer<T>());

编辑：再次考虑后，这个想法可能不适用于除 SortedSet<T> 之外的其他情况，因为您可能无法使用除 foreach 循环以外的任何方式查找与重复键关联的不同值；而 SortedSet<T> 最好用 SortedList<TKey,TValue> 表示，其中 TKey 是有趣的值，TValue 是该对象重复次数的计数（例如 int）。

- Brett Ryland

Answer 3

我不确定这是否符合你的要求。但是你可以对普通列表进行排序。MSDN讨论了这个问题，但显然需要调用排序函数。

- Glenn

Answer 4

我尝试找到同样的东西：一个随着添加项目而保持有序的列表。到目前为止，我找到的最接近的是Goletas.Collections中的SortedSet，它使用AVL树实现：

http://www.goletas.com/solutions/collections/

但这个类仍然要求列表中的每个元素都是唯一的（因此为“Set”）。

也许可以修改这个类以支持非唯一项。

- Paul A Jungwirth

Answer 5

如果不是对性能要求很高的话，你可以使用以下两种方法之一：

1）Linq OrderBy()

2）List 方法 Sort()

请参考以下示例。

        var list = new List<int>();
        list.Add( 2);
        list.Add( 1);
        list.Add( 3);

        Console.WriteLine("Using Linq OrderBy");
        foreach (int i in list.OrderBy(i=>i))
            Console.WriteLine(i);

        Console.WriteLine("Using List.Sort()");
        list.Sort();
        foreach (int i in list)
            Console.WriteLine(i);

- Knasterbax

---

这个问题是关于排序数据结构的（即在插入时将元素放置到它们的排序位置），而不是对列表进行排序的方法。 - kdt