Elegant way to create a nested Dictionary in C#

Question

I realized that I didn't give enough information for most people to read my mind and understand all my needs, so I changed this somewhat from the original.

Say I've got a list of items of a class like this:

public class Thing
{
    int Foo;
    int Bar;
    string Baz;
}

And I want to categorize the Baz string based on the values of Foo, then Bar. There will be at most one Thing for each possible combination of Foo and Bar values, but I'm not guaranteed to have a value for each one. It may help to conceptualize it as cell information for a table: Foo is the row number, Bar is the column number, and Baz is the value to be found there, but there won't necessarily be a value present for every cell.

IEnumerable<Thing> things = GetThings();
List<int> foos = GetAllFoos();
List<int> bars = GetAllBars();
Dictionary<int, Dictionary<int, string>> dict = // what do I put here?
foreach(int foo in foos)
{
    // I may have code here to do something for each foo...
    foreach(int bar in bars)
    {
        // I may have code here to do something for each bar...
        if (dict.ContainsKey(foo) && dict[foo].ContainsKey(bar))
        {
            // I want to have O(1) lookups
            string baz = dict[foo][bar];
            // I may have code here to do something with the baz.
        }
    }
}

What's an easy, elegant way to generate the nested dictionary? I've been using C# long enough that I'm getting used to finding simple, one-line solutions for all of the common stuff like this, but this one has me stumped.

Answer 1

Dictionary<int, Dictionary<string, int>> nestedDictionary = 
            new Dictionary<int, Dictionary<string, int>>();

Answer 2

Define your own custom generic NestedDictionary class

public class NestedDictionary<K1, K2, V>: 
     Dictionary<K1, Dictionary<K2, V>> {}

then in your code you write

NestedDictionary<int, int, string> dict = 
       new NestedDictionary<int, int, string> ();

if you use the int, int, string one a lot, define a custom class for that too..

   public class NestedIntStringDictionary: 
        NestedDictionary<int, int, string> {}

and then write:

  NestedIntStringDictionary dict = 
          new NestedIntStringDictionary();

EDIT: To add capability to construct specific instance from provided List of items:

   public class NestedIntStringDictionary: 
        NestedDictionary<int, int, string> 
   {
        public NestedIntStringDictionary(IEnumerable<> items)
        {
            foreach(Thing t in items)
            {
                Dictionary<int, string> innrDict = 
                       ContainsKey(t.Foo)? this[t.Foo]: 
                           new Dictionary<int, string> (); 
                if (innrDict.ContainsKey(t.Bar))
                   throw new ArgumentException(
                        string.Format(
                          "key value: {0} is already in dictionary", t.Bar));
                else innrDict.Add(t.Bar, t.Baz);
            }
        }
   }

and then write:

  NestedIntStringDictionary dict = 
       new NestedIntStringDictionary(GetThings());

Answer 3

You may be able to use a KeyedCollection where you define:

class ThingCollection
    : KeyedCollection<Dictionary<int,int>,Employee>
{
    ...
}

Answer 4

Here's a solution using Linq:

Dictionary<int, Dictionary<int, string>> dict = things
    .GroupBy(thing => thing.Foo)
    .ToDictionary(fooGroup => fooGroup.Key,
                  fooGroup => fooGroup.ToDictionary(thing => thing.Bar,
                                                    thing => thing.Baz));

Answer 5

An elegant way would be to not create the dictionaries yourself but use LINQ GroupBy and ToDictionary to generate it for you.

var things = new[] {
    new Thing { Foo = 1, Bar = 2, Baz = "ONETWO!" },
    new Thing { Foo = 1, Bar = 3, Baz = "ONETHREE!" },
    new Thing { Foo = 1, Bar = 2, Baz = "ONETWO!" }
}.ToList();

var bazGroups = things
    .GroupBy(t => t.Foo)
    .ToDictionary(gFoo => gFoo.Key, gFoo => gFoo
        .GroupBy(t => t.Bar)
        .ToDictionary(gBar => gBar.Key, gBar => gBar.First().Baz));

Debug.Fail("Inspect the bazGroups variable.");

I assume that by categorizing Baz using Foo and Bar you mean that if two things have both Foo and Bar equals then their Baz value also be the same as well. Please correct me if I'm wrong.

You're basically group by the Foo property first...
then for each resulting group, you group on the Bar property...
then for each resulting group you take the first Baz value as the dictionary value.

If you noticed, the method names matched exactly what you are trying to do. :-)

---

EDIT: Here's another way using query comprehensions, they are longer but are quiet easier to read and grok:

var bazGroups =
    (from t1 in things
     group t1 by t1.Foo into gFoo
     select new
     {
         Key = gFoo.Key,
         Value = (from t2 in gFoo
                  group t2 by t2.Bar into gBar
                  select gBar)
                  .ToDictionary(g => g.Key, g => g.First().Baz)
     })
     .ToDictionary(g => g.Key, g => g.Value);

Unfortunately, there are no query comprehension counterpart for ToDictionary so it's not as elegant as the lambda expressions.

...

Hope this helps.

Answer 6

Another approach would be to key your dictionary using an anonymous type based on both the Foo and Bar values.

var things = new List<Thing>
                 {
                     new Thing {Foo = 3, Bar = 4, Baz = "quick"},
                     new Thing {Foo = 3, Bar = 8, Baz = "brown"},
                     new Thing {Foo = 6, Bar = 4, Baz = "fox"},
                     new Thing {Foo = 6, Bar = 8, Baz = "jumps"}
                 };
var dict = things.ToDictionary(thing => new {thing.Foo, thing.Bar},
                               thing => thing.Baz);
var baz = dict[new {Foo = 3, Bar = 4}];

This effectively flattens your hierarchy into a single dictionary. Note that this dictionary cannot be exposed externally since it is based on an anonymous type.

If the Foo and Bar value combination isn't unique in your original collection, then you would need to group them first.

var dict = things
    .GroupBy(thing => new {thing.Foo, thing.Bar})
    .ToDictionary(group => group.Key,
                  group => group.Select(thing => thing.Baz));
var bazes = dict[new {Foo = 3, Bar = 4}];
foreach (var baz in bazes)
{
    //...
}

Answer 7

I think the simplest approach would be to use the LINQ extension methods. Obviously I haven't tested this code for performace.

var items = new[] {
  new Thing { Foo = 1, Bar = 3, Baz = "a" },
  new Thing { Foo = 1, Bar = 3, Baz = "b" },
  new Thing { Foo = 1, Bar = 4, Baz = "c" },
  new Thing { Foo = 2, Bar = 4, Baz = "d" },
  new Thing { Foo = 2, Bar = 5, Baz = "e" },
  new Thing { Foo = 2, Bar = 5, Baz = "f" }
};

var q = items
  .ToLookup(i => i.Foo) // first key
  .ToDictionary(
    i => i.Key, 
    i => i.ToLookup(
      j => j.Bar,       // second key
      j => j.Baz));     // value

foreach (var foo in q) {
  Console.WriteLine("{0}: ", foo.Key);
  foreach (var bar in foo.Value) {
    Console.WriteLine("  {0}: ", bar.Key);
    foreach (var baz in bar) {
      Console.WriteLine("    {0}", baz.ToUpper());
    }
  }
}

Console.ReadLine();

Output:

1:
  3:
    A
    B
  4:
    C
2:
  4:
    D
  5:
    E
    F