10

非常に単純なことをしようとしていますが、理解できないようSortedDictionaryです。

私がやろうとしているのは次のとおりです。
アイテムを浮動小数点数でソートするソート済み辞書を作成するため、次のような辞書を作成します

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

そして今、アイテムを追加した後、それらを 1 つずつ削除したいと思います (すべての削除は、最小から最大まで O(log(n)) の複雑さである必要があります。

どうすればいいのですか？単純allNodes[0]に最小になると思いましたが、そうではありません。

さらに、辞書は重複キーを処理できないようです。間違ったデータ構造を使用しているように感じます...
距離 (浮動小数点) で並べ替えたいノードがたくさんある場合は、別のものを使用する必要がありますか?

4

3 に答える 3

16

allNodes[0]辞書の最初の項目は表示されません。float キー値がの項目が表示されます0。

最初の項目が必要な場合は、allNodes.Values.First()代わりに試してください。または、最初のキーの用途を見つけるallNodes.Keys.First()

アイテムを1 つずつ削除するには、コレクションのコピーをループして呼び出します。KeysallNodes.Remove(key); 

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

あなたの質問への補遺に答えるために、はいSortedDictionary（それに関してはどんなフレーバーでDictionaryも）重複したキーを処理しません.既存のキーを持つアイテムを追加しようとすると、以前の値が上書きされます.

を使用することもできますが、コレクションとアイテムSortedDictionary<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>、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();

ノードを 1 つずつ削除するには、リストを繰り返しスローします。

while (list.Count > 0)
{
    list.RemoveAt(0);
}
于 2013-04-17T20:30:40.823 に答える