How to use SortedDictionary in C # correctly?

Question

I am trying to make something very simple, but it seems that I do not understand SortedDictionary .

I am trying to do the following:
Create a sorted dictionary that sorts my objects using some floating point number, so I am creating a dictionary that looks like

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

And now, after adding the elements, I want to delete them one by one (each removal should be difficult with O (log (n)) from the smallest to the largest.

How can I do it? I thought that just allNodes[0] would give me the smallest, but it is not.

Moreover, it seems that the dictionary cannot handle duplicate keys. I feel like using the wrong data structure ...
Should I use something else if I have a bunch of nodes that I want to sort by their distance (floating point)?

Answer 1

allNodes[0] will not give you the first element in the dictionary - it will give you an element with a key value of float 0 .

If you want the first element to try using allNodes.Values.First() . Or to find the first key, use allNodes.Keys.First()

To delete items one at a time, loop a copy of the Keys collection and call allNodes.Remove(key);

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

To answer your addition to your question, yes SortedDictionary (any flavor of the Dictionary , for that matter) will not handle duplicate keys - if you try to add an item with an existing key, it will overwrite the previous value.

You can use SortedDictionary<float, List<Node<T>>> , but then you have the difficulty of retrieving collections compared to elements that need to initialize each list, and not just add an element, etc. This is all possible and may be the fastest structure to add and receive, but it adds a bit of complexity.

Answer 2

Yes, you are right in complexity.

In SortedDictionary all keys are sorted. If you want to iterate from smallest to largest, foreach will be enough:

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

You wrote that you want to delete items. It is forbidden to delete from collections during iteration using foreach , so first create a copy for this.

EDIT:

Yes, if you have duplicate keys, you cannot use SortedDictionary . Create a structural Node with Node<T> and float , then write a comparator:

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

And then put everything in a simple List<Node> allNodes and do a sort:

 allNodes.Sort(new NodeComparer()); 

Answer 3

Since Dictionary<TKey, TValue> must have unique keys, I would use List<Node<T>> instead. For example, 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 delete nodes one by one, just go to the list:

 while (list.Count > 0) { list.RemoveAt(0); }