Multimap is Lookup

Breaking the tradition of not giving developers even the most basic of data structures with which to work, Microsoft, in its magnanimous wisdom, chose to include a multimap implementation in the 3.5 version of .NET. This was the same time that it first gave developers a Set implementation too. Its amazing any developers tolerated not having these out of the box with .NET over the years, but I guess making them yourself is the norm for us old C/C++ types.

(I shouldn’t give MSFT such a hard time. Java doesn’t ship a multimap either, you are left to use Apache Commons or Google Collection Library. http://java.sun.com/docs/books/tutorial/collections/interfaces/map.html)

Not wanting to break all traditions, they screwed up on the naming. Calling it a multimap would have been too easy. After all, we don’t call our resizable arrays “vectors” do we? No, we call them Lists. But aren’t Linked Lists something else, well, yes they are, Lists aren’t Linked Lists, and Linked Lists aren’t Lists, at least not in the IList<> of the sense. Enough Ranting.

(http://java.sun.com/j2se/1.5.0/docs/api/java/util/List.html v. http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx)

In the System.Core assembly in the System.Linq namespace there is an Interface named ILookup`2. There is an implementation of it called Lookup`2, but you can’t construct it. Yes, as if poor naming weren’t enough, It seems that MSFT doesn’t actually want you to use a multimap. Taking a look at return types and interface definitions, it seems this type exists only to support the Groupby LINQ implementation. Being the lazy programmer that I am, I do not want to write a multimap. The existence of the ToLookup extension method on IEnumerable, tells me that maybe I can get at one of these things.

In this example, assume I have a grocery shopping list which I’ve named mmap so that you remember it is a multimap. I want to organize (key) things in my list according to where I will store it, the fridge or the freezer.

var mmap = (
    new [] {
        new {Key = “Freezer”, Item = “IceCream” },
        new {Key= “Freezer”, Item = “Blueberries”},
        new {Key= “Freezer”, Item=”FCOJ”},
        new {Key = “Fridge”, Item=”Milk”},
        new {Key=”Fridge”, Item=”Yogurt”},
        new {Key = “Fridge”, Item = “Eggs”}
    }
    ).ToLookup(a=>a.Key, b=>b.Item);
foreach(var map in mmap)
{
    Console.WriteLine(map.Key);
    foreach(var val in map)
    {
        Console.WriteLine(“\t”+val);
    }
}

//look’em up by index
Console.WriteLine(mmap[“Freezer”]);
//but that is just an IGrouping<>
foreach(var item in mmap[“Freezer”])
{ Console.Write(item);Console.Write(“\t”); }
Console.WriteLine();

Some things to note:

  • We are exploiting anonymous types, they are very useful here.
  • There is no reason that Key and Item have to be named as such, I just found this most readable.
  • There is no reason Key and Item have to be typed as String. They could be any type, but the key type should support equality comparison for the grouping to function.
  • ToLookup() returns an ILookup`2 and not a Lookup`2.
  • The resulting multimap is immutable, like most things LINQ.

An expert LINQer might say “this is no different than group by”, and at first glance, I’d agree. There is an important difference. Under the hood it is likely that this is implemented exactly the same as group by, but ToLookup returns an ILookup`2. ILookup`2 extends IEnumerable[IGrouping`2]. The latter is what Groupby returns. This is important because the ILookup`2 interface exposes the indexer so that you can get at your map by indexing by key.

I wish I could just new up a Lookup and add items rather than jumping through hoops (see a future post). But I’m happy to never write another multimap implementation again.