Is there a C# Data structure to map keys to multiple values?

Question

Is there a C# data structure to map keys to multiple values? I have a collection of items that I want to key by name; however, the name is not unique. Hashtable and Dictionary only allow unique keys. Lookup seems close to what I want; however, it is not mutable.

Is there a built in data structure that I'm missing or do I need to build one myself?

How will you get the values out if the name is not unique and that's what you're hoping to do your lookup on? — Mike M., Jul 07 '10 at 18:43
I would assume it would return an IEnumerable or equivalent. — user171197, Jul 07 '10 at 18:49

score 8 · Accepted Answer · edited May 23 '17 at 12:06

What you're looking for is a multimap.

You may want to take a look at the answer to this question.

You may also want to look into the C5 Generic Collection library, which is free and has an implementation of a multimap.

If you feel like rolling your own, a simple place to start is a dictionary of lists:

Dictionary<TKey,List<TValue>>

However, you can't add to such a dictionary the normal way. You have to first check if the key already exists, and if so, fetch the value (list) and add to it. Otherwise, you need to create the list and populate it with a value.

If you are so inclined, I would suggest you consider using a set of extension methods to simplify the Add/Remove operations:

public static class MultimapExt
{
    public static void Add<TKey,TValue>( 
        this Dictionary<TKey,List<TValue>> dictionary, TKey key, TValue value )
    {
        List<TValue> valueList;
        if( !dictionary.TryGetValue( key, out valueList )
        {
            valueList = new List<TValue>();
            dictionary.Add( key, valueList );
        }
        valueList.Add( value );
    }

    public static void Remove<TKey,TValue>(
        this Dictionary<TKey,List<TValue>> dictionary, TKey key, TValue value )
    {
        List<TValue> valueList;
        if( dictionary.TryGetValue( key, out valueList ) )
        {
            valueList.Remove( value );
            if( valueList.Count == 0 )
               dictionary.Remove( key ); 
        }
    }
}

This looks what I'm looking for. Thanks! I just wish it was built into the framework. — user171197, Jul 07 '10 at 18:50
You need to add the valueList to your dictionary in your Add method. — Robert Davis, Jul 07 '10 at 19:43
I'd go with something a little more flexible: `Add(this IDictionary, TKey key, TValue value) where TCollection : ICollection`. This way you don't restrict yourself to an internal store of type `List` only (or of only `Dictionary` either, for that matter). — Dan Tao, Jul 07 '10 at 20:08

score 2 · Answer 2 · edited May 23 '17 at 12:12

LBushkin's answer is a good one. You can make it a bit more flexible, though, by removing the unnecessary restriction to use Dictionary<TKey, List<TValue>> (this way you could also use, say, a SortedDictionary<TKey, LinkedList<TValue>>) via some carefully chosen generic constraints:

public static class MultimapExt
{
    public static void Add<TKey, TValue, TCollection>( 
        this IDictionary<TKey, TCollection> dictionary,
        TKey key,
        TValue value
    ) where TCollection : ICollection<TValue>, new()
    {
        TCollection collection;
        if(!dictionary.TryGetValue(key, out collection)
        {
            collection = new TCollection();
            dictionary.Add(key, collection);
        }

        collection.Add(value);
    }

    public static bool Remove<TKey, TValue, TCollection>(
        this IDictionary<TKey, TCollection> dictionary,
        TKey key,
        TValue value
    ) where TCollection : ICollection<TValue>
    {
        TCollection collection;
        if(dictionary.TryGetValue(key, out collection))
        {
            bool removed = collection.Remove(value);

            if(collection.Count == 0)
               dictionary.Remove(key);

            return removed;
        }

        return false;
    }
}

Your enhancement is definitely a good one - it's useful to be able to decouple the collection management behavior. In practice though - it may make sense for both of our solutions to migrate into an actual `IDictionary<>` implementation rather than living as just extension methods. :D — LBushkin, Jul 07 '10 at 20:29
@LBushkin: I couldn't agree more. But they're good for illustrative purposes, I think. — Dan Tao, Jul 07 '10 at 20:52

score 0 · Answer 3 · answered Jul 07 '10 at 18:43

0

What about using a dictionary to IList<YOUR_VALUE_TYPE> ?

answered Jul 07 '10 at 18:43

jdehaan

19,700
6
57
97

This is what I would probably do if I was implementing it myself. I was just wondering if there was something built in. – user171197 Jul 07 '10 at 18:50

Is there a C# Data structure to map keys to multiple values?

3 Answers3