C# with .NET - Dictionary with Multiple Keys

Dictionary with Multiple Keys

The dictionaries available with the .NET Framework only support one value per key. You cannot add multiple values to the same key. However, you can create a custom dictionary that is based on Dictionary<TKey, TValue> and uses a list as value.

The class MultiDictionary <TKey, TValue> implements the interface IDictionary<TKey, TValue>. Contained in this class is the generic Dictionary class that has the same key TKey from the outer class, but the value is defined as type List<TValue>. Every key maps to a value of type List<TValue>.


using System;
using System.Collections.Generic;

namespace Wrox.ProCSharp.Collections
{
   public class MultiDictionary<TKey, TValue> : IDictionary<TKey, TValue>
   {
      private Dictionary<TKey, List<TValue>> dict =
         new Dictionary<TKey, List<TValue>>();
   //...

MultiDictionary<TKey, TValue> requires the implementation of the interface IDictionary<TKey, TValue> methods Add(), ContainsKey(), Remove(), TryGetValue(); the properties Keys and Values; and the indexer.

The implementation of the Add() method first determines if the key has already been added to the dictionary with TryGetValue(). If the key is already in the dictionary, the new value is added to the list that is returned from TryGetValue(). Otherwise, a new list is created, the value is added to the list, and the key together with the list is added to the dictionary.


public void Add(TKey key, TValue value)
{
   List<TValue> list;
   if (dict.TryGetValue(key, out list))
   {
      list.Add(value);
   }
   else
   {
      list = new List<TValue>();
      newList.Add(value);
      dict.Add(key, list);
   }
}
//...

The methods ContainsKey(), Remove(), and the property Keys can be implemented by forwarding the request to the contained dictionary:


public bool ContainsKey(TKey key)
{
   return dict.ContainsKey(key);
}

public ICollection<TKey> Keys
{
   get
   {
      return dict.Keys;
   }
}

public bool Remove(TKey key)
{
   return dict.Remove(key);
}
//...

The property Values must convert the internal values of type List<TValue> to type TValue. After the while loop is completed, the list named values contains all values from all the lists that are stored as values in the contained dictionary. The while loop uses the enumerator from the variable dict to iterate through all keys to add all items to the list that is returned.


public ICollection<TValue> Values
{
   get
   {
      List<TValue> values = new List<TValue>();

      Dictionary<TKey, List<TValue>>.Enumerator enumerator = dict.GetEnumerator();
      while (enumerator.MoveNext())
      {
         values.AddRange(enumerator.Current.Value);
      }
      return values;
   }
}
//...

The indexer and the TryGetValue method are not supported with MultiDictionary, because a key can be associated with more than one value, so a single value cannot be returned:


bool IDictionary<TKey, TValue>.TryGetValue(TKey key, out TValue value)
{
   throw new NotSupportedException("TryGetValue is not supported");
}

TValue IDictionary<TKey, TValue>.this[TKey key]
{
   get
   {
      throw new NotSupportedException(
            "accessing elements by key is not supported");
   }
   set
   {
      throw new NotSupportedException(
            "accessing elements by key is not supported");
   }
}
//...

With this class, it’s not useful to have an indexer of type TValue, but it’s useful to have an indexer of type IList<TValue>:


public IList<TValue> this[TKey key]
{
   get
   {
      return dict[key];
   }
}
//...

The interface IDictionary<TKey, TValue> is derived from ICollection<KeyValuePair<TKey, TValue>>, so the methods Add(), Clear(), Contains(), CopyTo(), and Remove(), and the properties Count and IsReadOnly must be implemented as well.

The Add() method with the argument of type KeyValuePair<TKey, TValue> just needs to invoke the Add() method, where TKey and TValue are passed separately. The Clear() method invokes the Clear() on the contained dictionary. Contains() returns false if the key specified does not exist. If the key exists, list.Contains() determines if the value is in the list and returns the result. CopyTo() copies all items to an array. The property Count returns the number of all values.


public void Add(KeyValuePair<TKey, TValue> item)
{
   Add(item.Key, item.Value);
}

public void Clear()
{
   dict.Clear();
}

public bool Contains(KeyValuePair<TKey, TValue> item)
{
   List<TValue> list;
   if (!dict.TryGetValue(item.Key, out list))
   {
      return false;
   }
   else
   {
      return list.Contains(item.Value);
   }
}

public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{

   if (array == null)
      throw new ArgumentNullException("array");
   if (arrayIndex < 0 || arrayIndex > array.Length)
      throw new ArgumentOutOfRangeException("array index out of range");
   if (array.Length - arrayIndex < this.Count)
      throw new ArgumentException("Array too small");

   Dictionary<TKey, List<TValue>>.Enumerator enumerator = dict.GetEnumerator();
   while (enumerator.MoveNext())
   {
      KeyValuePair<TKey, List<TValue>> mapPair = enumerator.Current;
      foreach (TValue val in mapPair.Value)
        {
         array[arrayIndex++] = new KeyValuePair<TKey,TValue>(mapPair.Key, val);
        }
   }
}
public int Count
{
   get
   {
      int count = 0;

      Dictionary<TKey, List<TValue>>.Enumerator enumerator = dict.GetEnumerator(); 
      while (enumerator.MoveNext())
      {

         KeyValuePair<TKey, List<TValue>> pair = enumerator.Current;
         count += pair.Value.Count;
      }
      return count;
   }
}

public bool IsReadOnly
{
   get { return false; }
}

public bool Remove(KeyValuePair<TKey, TValue> item)
{
   List<TValue> list;
   if (dict.TryGetValue(item.Key, out list))
   {
      return list.Remove(item.Value);
   }
   else
   {
      return false;
   }
}
//...

IDictionary<TKey, TValue> is also derived from IEnumerable<KeyValuePair<TKey, TValue>>, so the method GetEnumerator() must be implemented. Here, the yield return statement is of practical use.

Tip

The yield return statement is explained in Chapter 5, “Arrays.”


     public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
     {
        Dictionary<TKey, List<TValue>>.Enumerator enumerateKeys = dict.GetEnumerator();
        while (enumerateKeys.MoveNext())
        {
           foreach (TValue val in enumerateKeys.Current.Value)
           {
              KeyValuePair<TKey, TValue> pair = new KeyValuePair<TKey, TValue>(
                 enumerateKeys.Current.Key, val);
              yield return pair;
            }
         }
      }
      System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
      {
         return GetEnumerator();
      }
   }
}

The MultiDictionary<TKey, TValue> can be created like a normal dictionary, but here it’s possible to use the same key multiple times. In this case, the country is used as the key and Racer as value. Two racers from Australia and two racers from the United Kingdom are added to the dictionary. The indexer of this dictionary returns a list that is iterated through with a foreach loop.


MultiDictionary<string, Racer> racers = new MultiDictionary<string, Racer>();

racers.Add("Canada", new Racer("Jacqes", "Villeneuve", "Canada", 11));
racers.Add("Australia", new Racer("Alan", "Jones", "Australia", 12));
racers.Add("United Kingdom", new Racer("Jackie", "Stewart",
      "United Kingdom", 27));
racers.Add("United Kingdom", new Racer("James", "Hunt",
      "United Kingdom", 10));
racers.Add("Australia", new Racer("Jack", "Brabham", "Australia", 14));

foreach (Racer r in racers["Australia"])
{
   Console.WriteLine(r);
}

The output shows the racers from Australia:

Alan Jones
Jack Brabham