Automatically creating a collection in the Dictionary<Key, Collection<Value>>

Question

Lot of times I have to create a Dictionary<KeyType, List<ValueType>>

Before I can start using the dictionary I have to first verify that List has been created for that key.

//Can i remove these two lines?
if(!dict.ContainsKey(key)) 
    dict[key]= new List<ValueType>;

//now use the key
dict[key].Add(value);

I know its only "2 lines" of code but it annoys me and I think it can be removed.

I can extend dictionary in someway but before I do it, I want to know if someone has found a clever way to remove the above if statement.

Basically i want to create a Dictionary<KeyType, Collection<ValueType>> and start using it right away like dict[key].Add(value).

Answer 1

Have a look at the LookUp class introduced with Linq in .NET 3.5 - it might be just what you're looking for: a Dictionary like class that supports multiple items per key.

Perhaps the only significant downside is that you have to have all your elements available in one batch, as LookUp is immutable.

Answer 2

You could create something like Google Java Collection's Multimap... or you could just add an extension method like this:

public static void AddValue<TKey, TValue>
    (this IDictionary<TKey, List<TValue>> dictionary, TKey key, TValue value)
{
    List<TValue> values;
    if (!dictionary.TryGetValue(key, out values))
    {
        values = new List<TValue>();
        dictionary.Add(key, values);
    }
    values.Add(value);
}

As Bevan says, Lookup can help as well - but you can only create one with the ToLookup method, and you can't modify it afterwards. In many cases that's a thoroughly good thing, but if you need a mutable map then you'll ned something like the above.

Answer 3

To add to the answers, you can also add a more general extension which accepts a delegate for instantiation:

public static TValue GetOrCreate<TKey, TValue>
    (this IDictionary<TKey, TValue> dict, 
          TKey key, 
          Func<TKey, TValue> getValue)
{
    TValue value;
    if (!dict.TryGetValue(key, out value))
    {
        dict.Add(key, getValue(key));
    }
    return value;
}

and then you can provide whatever instantiation method you like:

Dictionary<int, string> dict = new Dictionary<int, string>();
string result = dict.GetOrCreate(5, i => i.ToString());

Answer 4

The ConcurrentDictionary<T,K>.GetOrAdd method is amazingly useful.

private ConcurrentDictionary<string, ICollection<int>> _dictionary;

private static ICollection<int> CreateEmptyList(string dummyKey)
{
    return new List<int>();
}

private void AddValue(string key, int value)
{
    ICollection<int> values = _dictionary.GetOrAdd(key, CreateEmptyList);
    values.Add(value);
}

Edit: Here's an example of how to implement the feature as an extension method for IDictionary<T,K> (C# 3):

Note that IDictionary<TKey, TValue> is generally not thread safe, so if you want thread safety with this extension method you'll have to manually implement it just as for other operations.

public static TValue GetOrAdd<TKey, TValue>(
    this IDictionary<TKey, TValue> dictionary,
    TKey key,
    Func<TKey, TValue> valueFactory)
{
    TValue value;
    if (!dictionary.TryGetValue(key, out value))
    {
        value = valueFactory(key);
        dictionary.Add(key, value);
    }

    return value;
}