CODEWITHSUNDEEP
c#dictionarysortingsorteddictionary
OopsUser
OopsUser

Reputation: 4774

How to properly use SortedDictionary in c#?

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

Answers (3)

Peter
Peter

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

Linus Caldwell
Linus Caldwell

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

D Stanley
D Stanley

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

Related Questions