Merging Dictionary containing a List in C#

This is kind-of related to this question, on how to merge two dictionaries in C#. An elegant Linq solution is presented, which is cool.

However, that question relates to Dictionary<Object1, Object2>, whereas I have a dictionary where the value is a List<Object2>.

I am looking for a solution for merging a Dictionary<Object1, List<Object2>>, with the following requirements:

• If Dictionary1 contains the same key as Dictionary2, then their List<Object2> lists should be combined. You would end up with a new key-value-pair with the shared key, and the combined lists from the two dictionaries.
• If Dictionary1 contains a key that Dictionary2 doesn't then the List<Object2> list from Dictionary1 should become the value, and vice versa.

This may not be possible in Linq, or it may be worth writing it out longhand with for loops and the like, but it would be nice to have an elegant solution.

I would suggest creating your own extension method. It will be more efficient and easier to modify.

public static void MergeDictionaries<OBJ1, OBJ2>(this IDictionary<OBJ1, List<OBJ2>> dict1, IDictionary<OBJ1, List<OBJ2>> dict2)
    {
        foreach (var kvp2 in dict2)
        {
            // If the dictionary already contains the key then merge them
            if (dict1.ContainsKey(kvp2.Key))
            {
                dict1[kvp2.Key].AddRange(kvp2.Value);
                continue;
            }
            dict1.Add(kvp2);
        }
    }

The difficulty is dealing with the merging of key conflicts.

If we start by flattening all the input dictionaries using SelectMany, we can group together the elements by their key.

var result = dictionaries
    .SelectMany(dict => dict)
    .GroupBy(kvp => kvp.Key)

The result set contains groups where each group's key is a key from the original dictionaries, and the contents of the group are an IEnumerable<List<T>> of the lists with the same key. From these groups, we can merge all List<T> into a single IEnumerable<T> using a Select transformation with SelectMany.

var result = dictionaries
    .SelectMany(dict => dict)
    .GroupBy(kvp => kvp.Key)
    .Select(grp => new { Key = grp.Key, Items = grp.SelectMany(list => list)})

We can then get a dictionary from this using a ToDictionary transformation, converting the IEnumerable<T> back to a List<T>.

var result = dictionaries
    .SelectMany(dict => dict)
    .GroupBy(kvp => kvp.Key)
    .Select(grp => new { Key = grp.Key, Items = grp.SelectMany(list => list)})
    .ToDictionary(kip => kip.Key, kip => new List<T>(kip.Items));

Updated in response to comment

You can populate dictionaries however you like. I have assumed it is a type which implements IEnumerable<IDictionary<TKey, List<T>>> for a TKey and T of your choosing.

The simplest way would be using a List<T> as follows:

List<IDictionary<TKey, List<T>>> dictionaries 
    = new List<IDictionary<TKey, List<T>>>();

dictionaries.Add(dictionary1); // Your variable
dictionaries.Add(dictionary2); // Your variable

// Add any other dictionaries here.

// Code as above!

You just need to change item merging part in solution to the previous problem. For object we have this:

.ToDictionary(group => group.Key, group => group.First())

i.e. for duplicated items, just take the first one.

But we could use this:

.ToDictionary(group => group.Key, group => group.SelectMany(list => list).ToList());

to concatenate lists.

So, the final expression would be

var result = dictionaries.SelectMany(dict => dict)
            .ToLookup(pair => pair.Key, pair => pair.Value)
            .ToDictionary(group => group.Key, 
                          group => group.SelectMany(list => list).ToList());

You could try a different merging expression if you need some extra list merging logic (e.g. only merge distinct items)

I'll be the first to admit that this is not all that pretty but this works for me.

var d1 = new Dictionary<string, List<string>>();
var d2 = new Dictionary<string, List<string>>();

d1["test"] = new List<string>() { "Stockholm", "Motala" };
d1["more"] = new List<string>() { "numerous", "populous", "bigger", "plentiful" };
d2["test"] = new List<string>() { "Washington", "Charlottesville" };
d2["less"] = new List<string>() { "insufficient", "small", "imperceptible" };

var intersect = (from key in d1.Keys.Intersect(d2.Keys) select new { Key = key, Value = new List<string>(d1[key].Concat(d2[key])) }).ToDictionary(d => d.Key, d => d.Value);
var merged = d1.Concat(d2).Where(d => !intersect.Keys.Contains(d.Key)).Concat(intersect).ToDictionary(d => d.Key, d => d.Value);