等同于允许重复键的排序字典

Question

我需要一种数据结构，可以按与它们相关联的浮点键进行排序，最低的排在前面。问题在于这些键表示成本，因此通常会出现重复值，但我并不在意这一点，因为如果两个对象具有相同的成本，我只需取第一个，因为这没有任何影响，问题是编译器会抱怨。

是否有一种数据结构行为相同但允许重复键呢？

编辑 - 我仍然需要这些重复项，因为如果其中一个变成死胡同，我会选择下一个（它们是a *搜索中的节点）

所以，清楚了吗，它需要允许按顺序排序的重复键。

- Dollarslice

---

如果您不关心重复项，为什么不直接将它们删除？ - Jesse

当你说“表现相同”时，你在寻找什么？字典的行为之一是，如果你给它一个键，它会返回一个单一的值。这只有在没有重复项的情况下才可能。 - Kyeotic

要不就用一个字典将键映射到 IEnumerable<T> 或者你喜欢的任何集合类型？ - ceyko

我指的是有序字典，而不是普通字典。已编辑。 - Dollarslice

您可以使用 DataTable。您可以根据任何列进行排序，并根据条件进行选择。 - banging

Answer 1

你写道:

相当于允许重复键的字典

我需要一种数据结构，可以按它们关联的浮点键进行排序对象，最低的优先。

字典不会按键排序项，因此你想要的结构实际上根本不等同于 Dictionary 。你想要的是类似于 SortedList 或 SortedDictionary 的东西，只是它应该允许重复键。

.NET 中没有这样的类。但是你有几个选择:

• 如果您想存储与键相关联的所有值（即使通常只需要第一个值），请使用 SortedDictionary<double，List<TValue>>。 插入首次键时，请创建新列表并将值添加到列表中。插入已经存在的键时，请获取列表并将值附加到列表中。
• _{您的编辑意味着此方法不适用于您的情况。} 使用SortedDictionary<double, TValue> 并在插入之前检查重复项。每个键仅存储第一个值，因此与上述方法不同，使用此方法无法访问第二个值。
• 查找具有所需功能的类的第三方集合库。

相关的

• SortedList 和 SortedDictionary 有什么区别？

- Mark Byers

---

一个已排序的字典，而不仅仅是一个字典。 - Dollarslice

@SirYakalot: 是的，没错。可以看一下这些类：SortedDictionary或者SortedList。已经更新了回答。 - Mark Byers

Answer 2

您可以创建一个从SortedSet派生的自定义类：

public class SortedTupleBag<TKey, TValue> : SortedSet<Tuple<TKey, TValue>> 
    where TKey : IComparable
{
    private class TupleComparer : Comparer<Tuple<TKey, TValue>>
    {
        public override int Compare(Tuple<TKey, TValue> x, Tuple<TKey, TValue> y)
        {
            if (x == null || y == null) return 0;

            // If the keys are the same we don't care about the order.
            // Return 1 so that duplicates are not ignored.
            return x.Item1.Equals(y.Item1)
                ? 1
                : Comparer<TKey>.Default.Compare(x.Item1, y.Item1);
        }
    }

    public SortedTupleBag() : base(new TupleComparer()) { }

    public void Add(TKey key, TValue value)
    {
        Add(new Tuple<TKey, TValue>(key, value));
    }
}

在控制台应用程序中的使用方法：

private static void Main(string[] args)
{
    var tuples = new SortedTupleBag<decimal, string>
    {
        {2.94M, "Item A"}, 
        {9.23M, "Item B"}, 
        {2.94M, "Item C"}, 
        {1.83M, "Item D"}
    };

    foreach (var tuple in tuples)
    {
        Console.WriteLine("{0} {1}", tuple.Item1, tuple.Item2);
    }

    Console.ReadKey();
}

生成这个结果:

 1.83 Item D
 2.94 Item A
 2.94 Item C
 9.23 Item B

- Kevin Aenmey

Answer 3

我遇到过很多次这个问题，我总是使用来自Wintellect的公共许可证（即免费）Power Collections(http://powercollections.codeplex.com)。他们有一个OrderedMultiDictionary，正是你需要的。它允许重复的键，并且允许您迭代所有重复的键条目。

- CoinTrader

Answer 4

您正在寻找Lookup。与其他基于字典的解决方案类似，它在每个键下存储一个IEnumerable来处理重复项。

var registry = Items.ToLookup(item=>item.Price);
foreach(var item in registry[desiredPrice])
{
     //Here you handle items that all have Price == desiredPrice
}

- Tormod

---

查找（Lookup）怎么不是数据结构？ - Tormod

抱歉，我的错误。我以为你在谈论 ToLookup。我撤销了我的负评。 - Marlon

好的。我为了更清晰地表达，编辑了这篇文章，并包含了类型的链接。 - Tormod

查找功能是否保留顺序？他似乎希望按某种排序顺序进行查找。 - nawfal

Answer 5

您可以通过覆盖CompareTo函数来实现。当您向SortedDictionary添加元素时，它会使用CompareTo()，如果结果为0，则会抛出异常，但是您可以更改键类实现的比较器行为，仅返回大于或小于（1或-1）。

        public int CompareTo(int key)
    {
        if (this.key.CompareTo(key) < 1)
            return 1;
        else
            return -1;
    }

- Omar

---

这个比较方法永远不会返回0。但是你是否曾经使用过一个键从字典中检索项目？ - user1559897

Answer 6

您仍然可以使用字典。您只需要将值的类型更改为集合而不是单个项：

Dictionary<float, List<T>>

字典的定义不允许有重复的键。

- Dan

Answer 7

你所说的是一个“袋子”。 “袋子”和“集合”的区别在于，集合是唯一的，而袋子允许重复。{a，b，c}是一个集合; {a，b，c，a}是一个袋子。

获取C5 Collections Library的副本。您需要HashBag<T>或TreeBag<T>类。它们之间的区别在于一个的底层数据存储是哈希，另一个是红黑树。从外部看，它们的行为相同。任何一个都应该能给你想要的东西。

- Nicholas Carey

Answer 8

你要找的是叫做“堆”或“优先队列”的数据结构。我相信如果你在谷歌上搜索，一定能找到C#的实现。

- idz

---

不幸的是，C#默认情况下不提供内置堆数据结构。 - dev27

@dev27 没错，但是原帖并没有提到它需要被内置。 - idz

Answer 9

你可以使用一个自定义的IComparer实现来避免哈希碰撞，进而使用SortedDictionary。例如：

private class NonCollidingFloatComparer : IComparer<float>
{
    public int Compare(float left, float right)
    {
        return (right > left) ? -1 : 1; // no zeroes 
    }
}

// silly method for the sake of demonstration
public void sortNodes(List<Node> nodesToSort)
{
    SortedDictionary<float, Node> nodesByWeight = new SortedDictionary<float, Node>(new NonCollidingFloatComparer());
    foreach (Node n in nodesToSort)
    {
        nodesByWeight.Add(n.FloatKey, n);
    }
    foreach (Node n in nodesByWeight.Values)
    {
        Console.WriteLine(n.FloatKey + " : " + n.UniqueID);
    }
}

- user3324937

---

很遗憾，您将无法使用此比较器按其键查找字典中的元素。 - Boris

海报要求一个数据结构，它可以保持元素的排序顺序并允许重复；他没有表明需要通过键执行查找的需求。 - user3324937