14

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

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

编辑 - 我仍然需要重复，因为如果一个结果是死胡同，我抓住下一个（它们是 a* 搜索中的节点）

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

4

9 回答 9

12

你写：

相当于允许重复键的字典

我需要一个数据结构，可以通过与之关联的浮动键对对象进行排序，最低优先。

字典不会按键对项目进行排序，因此您要查找的结构实际上根本不等同于 a Dictionary。你想要的是类似于 a SortedListor的东西，SortedDictionary除了它应该允许重复的键。

.NET 中不存在这样的类。但是，您有几个选择：

  • 如果SortedDictionary<double, List<TValue>>您想要存储与键关联的所有值，即使您通常只需要第一个值，也可以使用。第一次插入键时，创建一个新列表并将值添加到列表中。插入已存在的键时，获取列表并将值附加到列表中。
  • 您的编辑意味着这种方法不适用于您的情况。 在插入之前使用SortedDictionary<double, TValue>并检查重复项。只会存储每个键的第一个值，因此与上述方法不同，您根本无法使用此方法访问第二个值。
  • 找到一个第三方收藏库，它的类可以满足您的需求。

有关的

于 2012-08-03T18:37:10.910 回答
7

您可以创建自己的类，该类派生自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
于 2013-03-15T18:54:27.477 回答
6

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

于 2013-05-08T22:04:37.997 回答
3

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

var registry = Items.ToLookup(item=>item.Price);
foreach(var item in registry[desiredPrice])
{
     //Here you handle items that all have Price == desiredPrice
}
于 2012-08-03T18:35:42.017 回答
2

您可以通过覆盖 CompareTo 函数来做到这一点。当您将 aelement 添加到 SortedDictionary 时，它使用 CompareTo()，如果结果为 0 则引发异常，但您可以更改键类实现的比较器行为以仅返回大于或小于（1 或 -1）

        public int CompareTo(int key)
    {
        if (this.key.CompareTo(key) < 1)
            return 1;
        else
            return -1;
    }
于 2016-03-06T19:51:07.773 回答
1

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

Dictionary<float, List<T>>

字典定义不允许重复键。

于 2012-08-03T18:35:13.107 回答
1

你说的是一个包。bag和set之间的区别在于，set 是唯一的，而 bag 允许重复。{a,b,c} 是一个集合；{a,b,c,a} 是一个包。

获取C5 Collections Library的副本。您想要课程HashBag<T>或TreeBag<T>. 不同之处在于，一个中的基础数据存储是散列，另一个中是红黑树。在外部，它们的行为相同。要么应该给你你想要的。

于 2012-08-03T18:46:59.897 回答
0

您要查找的内容称为 a heapor priority queue。我敢肯定，如果你用谷歌搜索，你会找到一个 C#

于 2012-08-03T18:33:08.820 回答
0

您应该能够将 SortedDictionary 与 IComparer 的自定义实现一起使用以避免冲突。例如：

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);
    }
}
于 2015-02-20T02:24:30.217 回答