What is the point of Lookup<TKey, TElement>?

The MSDN explains Lookup like this:

> A Lookup<TKey, TElement> > resembles a Dictionary<TKey, > TValue>. The difference is that a > Dictionary<TKey, TValue> maps keys to single values, whereas a > Lookup<TKey, TElement> maps keys to collections of values.

I don't find that explanation particularly helpful. What is Lookup used for?

It's a cross between an IGrouping and a dictionary. It lets you group items together by a key, but then access them via that key in an efficient manner (rather than just iterating over them all, which is what GroupBy lets you do).

For example, you could take a load of .NET types and build a lookup by namespace... then get to all the types in a particular namespace very easily:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Xml;

public class Test
{
    static void Main()
    {
        // Just types covering some different assemblies
        Type[] sampleTypes = new[] { typeof(List<>), typeof(string), 
                                     typeof(Enumerable), typeof(XmlReader) };
        
        // All the types in those assemblies
        IEnumerable<Type> allTypes = sampleTypes.Select(t => t.Assembly)
                                               .SelectMany(a => a.GetTypes());
        
        // Grouped by namespace, but indexable
        ILookup<string, Type> lookup = allTypes.ToLookup(t => t.Namespace);
        
        foreach (Type type in lookup["System"])
        {
            Console.WriteLine("{0}: {1}", 
                              type.FullName, type.Assembly.GetName().Name);
        }
    }
}

(I'd normally use var for most of these declarations, in normal code.)

One way to think about it is this: Lookup<TKey, TElement> is similar to Dictionary<TKey, Collection<TElement>>. Basically a list of zero or more elements can be returned via the same key.

namespace LookupSample
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    class Program
    {
        static void Main(string[] args)
        {
            List<string> names = new List<string>();
            names.Add("Smith");
            names.Add("Stevenson");
            names.Add("Jones");

            ILookup<char, string> namesByInitial = names.ToLookup((n) => n[0]);

            // count the names
            Console.WriteLine("J's: {0}", namesByInitial['J'].Count()); // 1
            Console.WriteLine("S's: {0}", namesByInitial['S'].Count()); // 2
            Console.WriteLine("Z's: {0}", namesByInitial['Z'].Count()); // 0, does not throw
        }
    }
}

One use of Lookup could be to reverse a Dictionary.

Suppose you have a phonebook implemented as a Dictionary with a bunch of (unique) names as keys, each name associated with a phone number. But two people with different names might share the same phone number. This isn't a problem for a Dictionary, which doesn't care that two keys correspond to the same value.

Now you want a way of looking up who a given phone number belongs to. You build a Lookup, adding all the KeyValuePairs from your Dictionary, but backwards, with the value as the key and the key as the value. You can now query a phone number, and obtain a list of names of all the people whose phone number that is. Building a Dictionary with the same data would drop data (or fail, depending on how you did it), since doing

dictionary["555-6593"] = "Dr. Emmett Brown";
dictionary["555-6593"] = "Marty McFly";

means that the second entry overwrites the first - the Doc is no longer listed.

Trying to write the same data in a slightly different way:

dictionary.Add("555-6593", "Dr. Emmett Brown");
dictionary.Add("555-6593", "Marty McFly");

would throw an exception on the second line since you can't Add a key which is already in the Dictionary.

[Of course, you might want to use some other single data structure to do lookups in both directions, etc. This example means that you have to regenerate the Lookup from the Dictionary each time the latter changes. But for some data it could be the right solution.]

I haven't successfully used it before, but here is my go:

A Lookup<TKey, TElement> would behave pretty much like a (relational) database index on a table without a unique constraint. Use it in the same places you would use the other.

I guess you could argue it this way: imagine you're creating a data structure to hold the contents of a phone book. You want to key by lastName and then by firstName. Using a dictionary here would be dangerous because many people can have the same name. So a Dictionary will always, at most, map to a single value.

A Lookup will map to potentially several values.

Lookup["Smith"]["John"] will be a collection of size one billion.