equivalent to a sorted dictionary that allows duplicate keys

Question

I need a data structure that can sort objects by the float keys they're associated with, lowest first. The trouble is that the keys represent cost so there are often duplicates, I don't care about this because if two have the same cost I'll just grab the first as it makes no difference, the problem is that the compiler complains.

Is there a data structure that behaves in the same way but allows duplicate keys?

EDIT - I still need the duplicates though because if one turns out to be a dead-end, I grab the next (they're nodes in an a* search)

so just to be clear, it needs to allow duplicate keys that are sorted in order.

Answer 1

You write:

equivalent to a dictionary that allows duplicate keys

I need a data structure that can sort objects by the float keys they're associated with, lowest first.

A dictionary does not keep the items sorted by the keys, so the structure you are looking for is actually not equivalent to a Dictionary at all. What you want is something similar to a SortedList or SortedDictionary except that it should allow duplicate keys.

No such class exists in .NET. However you have a few options:

• Use SortedDictionary<double, List<TValue>> if you want to store all the values associated for a key, even though you usually only need the first. When inserting a key for the first time, create a new list and add the value to the list. When inserting a key that already exists, fetch the list and append the value to the list.
• _{Your edit means that this approach does not apply to your situation.}Use SortedDictionary<double, TValue> and check for duplicates before inserting. Only the first value for each key will be stored, so unlike the above approach, you can't access the second value at all with this method.
• Find a third party collections library that has a class that does what you want.

Related

• What's the difference between SortedList and SortedDictionary?