如何在c#中正确使用SortedDictionary

本文关键字：SortedDictionary | 更新日期: 2023-09-27 18:09:48

我想做一些非常简单的事情，但似乎我不理解SortedDictionary。

我想做的是:
创建一个排序字典，按某个浮点数对条目进行排序，因此我创建了一个如下所示的字典

SortedDictionary<float, Node<T>> allNodes = new SortedDictionary<float, Node<T>>();

现在在我添加项之后，我想一个一个地移除它们(每次移除的复杂度应该是O(log(n)))从最小到最大

我该怎么做?我以为简单的allNodes[0]会给我最小的，但它不是。

而且，字典似乎不能处理重复的键。我觉得我使用了错误的数据结构…
如果我有一堆节点，我想按它们的距离(浮点数)排序，我应该用别的东西吗?

如何在c#中正确使用SortedDictionary

allNodes[0]不会给你字典中的第一个项目-它会给你float 键值为0的项目。

如果你想要第一项，试试allNodes.Values.First()代替。或者使用allNodes.Keys.First()

查找第一个键

要逐个删除项，循环Keys集合的副本，并调用allNodes.Remove(key); 

foreach (var key in allNodes.Keys.ToList())
{
    allNodes.Remove(key);
}

回答你的问题的附录，是的，SortedDictionary (Dictionary的任何版本)不会处理重复的键-如果你尝试用现有的键添加一个项，它将覆盖先前的值。

您可以使用SortedDictionary<float, List<Node<T>>>，但这样您就有了提取集合和项的复杂性，需要初始化每个列表，而不仅仅是添加一个项，等等。这一切都是可能的，并且可能仍然是最快的添加和获取结构，但它确实增加了一些复杂性。

是的，关于复杂性你是对的。

在SortedDictionary中所有的键都是排序的。如果你想从最小的到最大的迭代，foreach就足够了:

foreach(KeyValuePair<float, Node<T>> kvp in allNodes)
{
    // Do Something...
}

您写了要删除项。在foreach的迭代过程中，禁止从集合中删除，所以首先创建它的副本来执行此操作。

编辑:

是的，如果你有重复的密钥，你不能使用SortedDictionary。用Node<T>和float创建一个结构节点，然后编写一个比较器:

public class NodeComparer : IComparer<Node>
{
    public int Compare(Node n1, Node n2)
    {
        return n2.dist.CompareTo(n1.dist);
    }
}

然后把所有的东西放在简单的List<Node> allNodes和sort:

allNodes.Sort(new NodeComparer());

由于Dictionary<TKey, TValue>必须具有唯一的密钥，我将使用List<Node<T>>代替。例如，如果你的Node<T>类有一个Value属性

class Node<T>
{
    float Value { get; set; }
    // other properties
}

如果你想按这个属性排序，使用LINQ:

var list = new List<Node<T>>();
// populate list
var smallest = list.OrderBy(n => n.Value).FirstOrDefault();

要逐个删除节点，只需迭代抛出列表:

while (list.Count > 0)
{
    list.RemoveAt(0);
}
相关文章：