Is there an alternative to Dictionary/SortedList that allows duplicates? [duplicate]

Question

Possible Duplicate:
C# Sortable collection which allows duplicate keys

Basically I'd like to make a Dictionary work with duplicate keys without going into custom comparer implementations. There is an idea of:

  Dictionary<key, List<value>>

but it still has some overhead. I wish Dictionary had "AllowDuplicates".

Anisole

Didn't find that in my searches. Voted for close, thanks. – Anisole

Also related: #5716923 – Organometallic

Answer 1

If you're using .NET 3.5 then Lookup is probably what you're after.

Madeleinemadelena

It's a pity that such a potentially useful class has a few limitations. Such as no public constructor or ability to add/remove items. – Bestrew

@Ray, Agree completely. Although I guess that's why it's called Lookup rather than something like MultiDictionary, to hint that it's an immutable lookup of some sort rather than a collection to be manipulated. The OP's suggestion of a Dictionary<key, List<value>> would be much more flexible. – Madeleinemadelena

@Ray: The best constructor is, and i quote MSDN: "You can create an instance of a Lookup<TKey, TElement> by calling ToLookup on an object that implements IEnumerable<T>. " – Hawley

Answer 2

.NET 2.0: PowerCollections contains the OrderedMultiDictionary.

Arrogant

Answer 3

You still can use SortedList and try to make a unique key by combining your value and a Guid into a class. In this case, you must implement the IComparer<NewKey> for your new key, something like:

class MyKey
{
    public Guid Guid { get; set; }
    public float Value { get; set; }
}

class MyComparer : IComparer<MyKey>
{

    public int Compare(MyKey x, MyKey y)
    {
        if (x == null || y == null)
            throw new InvalidOperationException("both of parameters must be not null");
        if (x.Value < y.Value) return -1;
        if (x.Value > y.Value) return 1;
        return 0;
    }
}

and then

var mySortedList = new SortedList<MyKey, MyValue>(new MyComparer());

Jowett

Answer 4

Not in the Fx < 3.5.. You can implement one, obviously, with a Dictionary of IList objects. But then you have the encapsulation issue/responsibility.

If you're using .NET 3.5, use the Lookup class.

Sher

It's only a replacement for Dictionary, but not for SortedList. – Cribbs

Answer 5

That does not work. As soon as you return 0 from the comparer, it will throw "duplicate" exception.

You don't need classes encapsulation or anything, just make a comparer that does not return 0 (equal) result. Here is an example for int type of key

class MyComparer : IComparer<int>
{

  public int Compare(int x, int y)
  {
    if (x < y)
      return -1;
    else return 1;
  }
}

Eucalyptus

Keep in mind that this trick will break the indexer. If you try to get a value using the indexer you will get an exception because the key could not be found. – Villous

Answer 6

By definition, a Dictionary contains unique keys. Your example above is effectively a sort of two-dimensional keyed array, a structure I've used many times. Why would you want to have duplicate keys? If you did, how would the Dictionary uniquely address its members?

Thorner

Consider a real-world dictionary listing different meanings for the same word. Multiple entries with a common key. Nothing contradictory about that. Members could be addressed by a lookup returning a collection or Enumerable. C++ has had a multimap for ages. It's not an impossible problem. :) – Geraldina

Answer 7

I came across with same issue.. I needed a sortedList which can allow Duplicate Keys..

var sortList = new SortedList<string, IDictionary<string, object>>();

but this didnt work.. so i used

var list = new List<KeyValuePair<string, IDictionary<string, object>>>();

add new data to it as ..

list.Add(new KeyValuePair<string, IDictionary<string, object>>>(value, Dictionary));

with linq i sorted it with no problem..

Try List<KeyValuePair<TKey, List<TValue>>>();

Hygrometric

Don't forget that this has O(N) lookup cost by key unlike an hashtable (or a dictionary), which is O(1) mostly. – Anisole