Reputation: 4774
I'm trying to do something very simple but it seems that I don't understand SortedDictionary
.
What I'm trying to do is the following:
Create a sorted dictionary that sorts my items by some floating number, so I create a dictionary that looks like this
SortedDictionary<float, Node<T>> allNodes = new SortedDictionary<float, Node<T>>();
And now after I add items, I want to remove them one by one (every removal should be at a complexity of O(log(n)) from the smallest to the largest.
How do I do it? I thought that simply allNodes[0]
will give me the the smallest, but it doesn't.
More over, it seems like the dictionary can't handle duplicate keys. I feel like I'm using the wrong data structure...
Should I use something else if I have bunch of nodes that I want to be sorted by their distance (floating point)?
Upvotes: 12
Views: 26135
Reputation: 962
Yes, you're right about complexity.
In SortedDictionary
all the keys are sorted. If you want to iterate from the smallest to the largest, foreach
will be enough:
foreach(KeyValuePair<float, Node<T>> kvp in allNodes)
{
// Do Something...
}
You wrote that you want to remove items. It's forbidden to remove from collections during iteratation with foreach
, so firstly create a copy of it to do so.
EDIT:
Yes, if you have duplicated keys you can't use SortedDictionary
. Create a structural Node with Node<T>
and float
, then write a comparer:
public class NodeComparer : IComparer<Node>
{
public int Compare(Node n1, Node n2)
{
return n2.dist.CompareTo(n1.dist);
}
}
And then put everything in simple List<Node> allNodes
and sort:
allNodes.Sort(new NodeComparer());
Upvotes: 3
Reputation: 11088
As a Dictionary<TKey, TValue>
must have unique keys, I'd use List<Node<T>>
instead. For instance, if your Node<T>
class has a Value
property
class Node<T>
{
float Value { get; set; }
// other properties
}
and you want to sort by this property, use LINQ:
var list = new List<Node<T>>();
// populate list
var smallest = list.OrderBy(n => n.Value).FirstOrDefault();
To remove the nodes one by one, just iterate threw the list:
while (list.Count > 0)
{
list.RemoveAt(0);
}
Upvotes: 0
Reputation: 152654
allNodes[0]
will not give you the first item in the dictionary - it will give you the item with a float
key value of 0
.
If you want the first item try allNodes.Values.First()
instead. Or to find the first key use allNodes.Keys.First()
To remove the items one by one, loop over a copy of the Keys
collection and call allNodes.Remove(key);
foreach (var key in allNodes.Keys.ToList())
{
allNodes.Remove(key);
}
To answer your addendum to your question, yes SortedDictionary
(any flavor of Dictionary
for that matter) will not handle duplicate keys - if you try and add an item with an existing key it will overwrite the previous value.
You could use a SortedDictionary<float, List<Node<T>>>
but then you have the complexity of extracting collections versus items, needing to initialize each list rather than just adding an item, etc. It's all possible and may still be the fastest structure for adds and gets, but it does add a bit of complexity.
Upvotes: 17