10

我正在尝试做一些非常简单的事情，但似乎我不明白SortedDictionary。

我想要做的是以下内容：
创建一个排序字典，按某个浮点数对我的项目进行排序，所以我创建一个看起来像这样的字典

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

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

我该怎么做？我以为这只allNodes[0]会给我最小的，但事实并非如此。

此外，字典似乎无法处理重复的键。我觉得我使用了错误的数据结构......
如果我有一堆节点想要按它们的距离（浮点数）排序，我应该使用其他东西吗？

4

3 回答 3

16

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

如果您想要第一个项目，请尝试allNodes.Values.First()。或者找到第一个键使用allNodes.Keys.First()

要逐个删除项目，请遍历集合的副本并调用KeysallNodes.Remove(key); 

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

要回答您对问题的补充，是SortedDictionary的（任何形式的Dictionary）都不会处理重复的键 - 如果您尝试使用现有键添加项目，它将覆盖以前的值。

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

于 2013-04-17T20:32:03.007 回答
2

是的，您对复杂性的看法是正确的。

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

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

您写道要删除项目。在使用 迭代期间禁止从集合中删除foreach，因此首先创建它的副本以执行此操作。

编辑：

是的，如果您有重复的密钥，则无法使用SortedDictionary. Node<T>用and创建一个结构节点float，然后编写一个比较器：

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

然后将所有内容简单List<Node> allNodes排序：

allNodes.Sort(new NodeComparer());
于 2013-04-17T20:32:25.750 回答
0

由于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);
}
于 2013-04-17T20:30:40.823 回答