相当于允许重复键的排序字典

Question

我需要一个数据结构,可以通过与它们关联的浮动键对对象进行排序,最先降低.问题是密钥代表成本所以经常有重复,我不关心这个,因为如果两个具有相同的成本,我只会抓住第一个,因为它没有区别,问题是编译器抱怨.

是否存在行为方式相同但允许重复键的数据结构？

编辑 - 我仍然需要重复项,因为如果一个结果是一个死胡同,我抓住下一个(他们是一个*搜索中的节点)

所以为了清楚起见,它需要允许按顺序排序的重复键.

Answer 1

你写:

相当于允许重复键的字典

我需要一个数据结构,可以通过与它们关联的浮动键对对象进行排序,最先降低.

字典不会保留按键排序的项目,因此您要查找的结构实际上并不等同于a Dictionary.你想要的是类似于a SortedList或者SortedDictionary它应该允许重复键的东西.

.NET中不存在这样的类.但是你有几个选择:

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

有关

• SortedList和SortedDictionary有什么区别？

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

Answer 3

我已多次遇到此问题,并且我总是使用Wintellect(http://powercollections.codeplex.com)的公共许可证(即免费)Power Collections .他们有一个OrderedMultiDictionary,正是您正在寻找的.它允许重复键,它允许您遍历所有重复的键条目.

Answer 4

您正在寻找的称为heap或priority queue。我确信如果你用 google 搜索你会找到一个 C# 的