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)?
In C#, SortedDictionary is a generic collection which is used to store the key/value pairs in the sorted form and the sorting is done on the key. SortedDictionary is defined under System. Collection. Generic namespace.
Objects in a SortedList are accessible by using their keys or indexes. The keys in a SortedList must be unique and cannot be null. While a SortedDictionary is implemented using a red-black binary search tree, a SortedList is implemented using two internal arrays — one array for the keys and one for the values.
The SortedList class represents a collection of key-and-value pairs that are sorted by the keys and are accessible by key and by index. A sorted list is a combination of an array and a hash table. It contains a list of items that can be accessed using a key or an index.
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.
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());
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With