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.

Foresail

If you don't care about the duplicates why don't you just drop them? – Bolme

That's really awkward. If it makes no difference, why don't you just ignore if the key already exists? – Trull

When you say "behaves the same way" what are you looking for? One of the behaviors of the dictionary is that if you give it a key, it returns a single value. This is only possible because you cannot have duplicates. – Pebble

How about just a dictionary mapping keys to IEnumerable<T> or whatever collection you like? – Oeuvre

I means sorted dictionary, not dictionary. edited. – Foresail

You can use a DataTable. You can sort on whichever column and select based on criteria.. – Larder

What data structure are you using and where are you getting compilation errors? – Malines

Somebody started downvoting my answer on a misunderstanding. You are looking for the Lookup<> class. – Wheresoever

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?

Poignant

a sorted dictionary, not just a dictionary – Foresail

@SirYakalot: Yes, exactly. See the classes: SortedDictionary or SortedList. Updated answer. – Poignant

Answer 2

You could create your own class that derives from SortedSet:

public class SortedTupleBag<TKey, TValue> : SortedSet<Tuple<TKey, TValue>> 
    where TKey : IComparable
{
    private class TupleComparer : Comparer<Tuple<TKey, TValue>>
    {
        public override int Compare(Tuple<TKey, TValue> x, Tuple<TKey, TValue> y)
        {
            if (x == null || y == null) return 0;

            // If the keys are the same we don't care about the order.
            // Return 1 so that duplicates are not ignored.
            return x.Item1.Equals(y.Item1)
                ? 1
                : Comparer<TKey>.Default.Compare(x.Item1, y.Item1);
        }
    }

    public SortedTupleBag() : base(new TupleComparer()) { }

    public void Add(TKey key, TValue value)
    {
        Add(new Tuple<TKey, TValue>(key, value));
    }
}

Usage in a console app:

private static void Main(string[] args)
{
    var tuples = new SortedTupleBag<decimal, string>
    {
        {2.94M, "Item A"}, 
        {9.23M, "Item B"}, 
        {2.94M, "Item C"}, 
        {1.83M, "Item D"}
    };

    foreach (var tuple in tuples)
    {
        Console.WriteLine("{0} {1}", tuple.Item1, tuple.Item2);
    }

    Console.ReadKey();
}

produces this result:

 1.83 Item D
 2.94 Item A
 2.94 Item C
 9.23 Item B

Monolingual

Answer 3

I've hit this problem a number of times, and I always use the public license (i.e. free) Power Collections from Wintellect (http://powercollections.codeplex.com). They have an OrderedMultiDictionary that is exactly what you are looking for. It allows duplicate keys and it allows you to iterate through all of the duplicate key entries.

Bricky

Answer 4

You are looking for Lookup. Similarly to other dictionary based solutions proposed already, it stores an IEnumerable under each key to handle duplicates.

var registry = Items.ToLookup(item=>item.Price);
foreach(var item in registry[desiredPrice])
{
     //Here you handle items that all have Price == desiredPrice
}

Wheresoever

How is Lookup not a data structure? – Wheresoever

Sorry, my mistake. I thought you were talking about ToLookup. I removed my downvote – Survive

Ok. I edited the post for clarity, including a link to the type. – Wheresoever

Does Lookup preserve order? He seem to want it in some sorted order – Alaniz

Answer 5

You can do it by overriding CompareTo fucntion. When you add an aelement to a SortedDictionary, it uses CompareTo(), if the result is 0 trows an exception, but you can change the comparator behavior of your key class implementation to return only greather than or lower than (1 or -1)

        public int CompareTo(int key)
    {
        if (this.key.CompareTo(key) < 1)
            return 1;
        else
            return -1;
    }

Hereupon

This compare method never returns 0. However would you ever retrieve an item from the dictionary using a key? – Ruby

Answer 6

You could still use a dictionary. You would just need to change the type of the values to be collections rather than single items:

Dictionary<float, List<T>>

A dictionary be definition does not allow duplicate keys.

Anhydrous

Answer 7

What you're talking about is a bag. The difference between a bag and a set is that sets are unique whilst bags allow duplicates. {a,b,c} is a set; {a,b,c,a} is a bag.

Grab a copy of the C5 Collections Library. You want the classes HashBag<T> or TreeBag<T>. The difference is that the underlying data store in one is a hash and a red-black tree in the other. Externally, they behave the same. Either should give you what you want.

Hesitate

Answer 8

What you are looking for is called a heap or priority queue. I'm sure if you google you will find one for C#

Braziel

Unfortunately, C# doesn't provide an in-built heap data structure by default. – Reverberatory

@Reverberatory true, but the OP did not mention the requirement for it to be built in. – Braziel

Answer 9

You should be able to use a SortedDictionary with a custom implementation of IComparer to avoid collisions. For example:

private class NonCollidingFloatComparer : IComparer<float>
{
    public int Compare(float left, float right)
    {
        return (right > left) ? -1 : 1; // no zeroes 
    }
}

// silly method for the sake of demonstration
public void sortNodes(List<Node> nodesToSort)
{
    SortedDictionary<float, Node> nodesByWeight = new SortedDictionary<float, Node>(new NonCollidingFloatComparer());
    foreach (Node n in nodesToSort)
    {
        nodesByWeight.Add(n.FloatKey, n);
    }
    foreach (Node n in nodesByWeight.Values)
    {
        Console.WriteLine(n.FloatKey + " : " + n.UniqueID);
    }
}

Oran

unfortunately, you won't be able to lookup element by its key in the dictionary with such comparer. – Ilke

The poster requested a data structure that would keep elements in sorted order and would allow duplicates; he did not indicate a need to perform lookups by key. – Oran

Answer 10

private SortedList<Double,List<Result>> results = new();

public void Add(Double key, Result value) {
    if(results.ContainsKey(key)) results[key].Add(value);
    else results.Add(key, new List<Result> { value});
}

ForEach:

foreach(var i:results) foreach(var j:i.value) ....
    

Replacement