Single Key Multiple Values Data Structure for one to many mapping

For updated version of the article please visit www.agnosticdevs.com

Dictionaries are good, they are great to store Key / Value pairs but what if you want to store multiple values for a single key?

Dictionaries would not allow duplicate keys. You can obviously create a Dictionary like Dictionary<int, List<string>>, but ToLookup extension method saves you time in a way that you just have to tell it how keys are calculated and it'd make the DS for you. Additionally it' gives you functionality to iterate over the groupings etc.

Given an IEnumerable<T>, you can easily convert it to a  ILookup<TKey, TElement> without any hassles.

I came across a nice way to represent such a Data Structure using one of the Extension Method (ToLookup) present in System.Linq Namespace which converts an IEnumerable<T> to an ILookup<TKey, TElement>.

 

Now, there are two parameters this method expects (The other overload expects 3 parameters):

  • IEnumerable<TSource> - This list would contain the actual data.
  • Func<TSource, TKey> keySelector - The Delegate which which computes the keys

 

The method returns the following:

ILookup<TKey, TElement>

 

This DS would store Keys and multiple values along those keys.

 

Let's see a small example:

 

 

   12  using System;

   13     using System.Collections.Generic;

   14     using System.Linq;

   15 

   16     /// <summary>

   17     /// </summary>

   18     internal class Program

   19     {

   20         #region Methods

   21 

   22         /// <summary>

   23         /// </summary>

   24         /// <param name="args">

   25         /// The args.

   26         /// </param>

   27         private static void Main(string[] args)

   28         {

   29             // Create an array of strings.

   30             var list = new List<string> { "IceCream1", "Chocolate Moose", "IceCream2" };

   31 

   32             // Generate a lookup Data Structure

   33             ILookup<int, string> lookupDs = list.ToLookup(item => item.Length);

   34 

   35           // Enumerate groupings.

   36             foreach (var group in lookupDs)

   37             {

   38                 foreach (string element in group)

   39                 {

   40                     Console.WriteLine(element);

   41                 }

   42             }

   43         }


Published Tuesday, October 30, 2012 7:58 PM by nijhawan.saurabh
Filed under: , ,

Comments

# re: Single Key Multiple Values Data Structure for one to many mapping

Wednesday, October 31, 2012 5:31 PM by MBR

What's wrong witht the more explict and easier to use:

Dictionary<int, List<string>> lookup;

# re: Single Key Multiple Values Data Structure for one to many mapping

Thursday, November 1, 2012 2:19 AM by nijhawan.saurabh

@MBR. Given an IEnumerable,if you want to convert it to a one to many mapping DS, ToLookUp saves you a lot of time. You don't have to look through and write the logic to build the DS and additionally it gives you ways to display the groups etc. Creating a LookUp on the fly in a lambda expression is kind of cool.

# re: Single Key Multiple Values Data Structure for one to many mapping

Thursday, November 1, 2012 2:13 PM by MBR

Sorry - that's what I get for speed-reading.

I think the disoverability/symetry of the collections to be a little lacking -- the Lookup does not have a .Groups property, but only access though its enumerator, and the group itself has a Key property, but no .Values property, but only access though its enumerator.

The docs also don't say what the implementation of the Lookup is -- is it a Dictionary<>, or as it's read-only after creation it could be some kind of functional data-struct like a red-black tree.

# re: Single Key Multiple Values Data Structure for one to many mapping

Thursday, November 1, 2012 2:20 PM by MBR

It would be interesting to see whether they made the decsision to optimize to creation-time of the lookup, or to optimize the lookup-time itself - e.g., is the typical use case to only "query" the lookup after it's built or enumerate though all the groups/elements - I assume the latter. The value Func could also be lazily rather than eagerly called only when the lookup for a key is accessed.

Leave a Comment

(required) 
(required) 
(optional)
(required)