Combine lists of key value pairs where keys match

I have a list of List<KeyvaluePair<DateTime, int>>, which I want to merge into one (union), and where there are pairs with the same key in more than one list, have their values summed.

Example:

input list 1:
date1, 1
date2, 2

input list 2:
date2, 3
date3, 4

input list 3:
date3, 5
date4, 6

desired output:
date1, 1
date2, 5
date3, 9
date4, 6

From what I've been reading about LINQ trickery this sort of thing is possible to do really neatly, but so far I've not been able to get my 开发者_运维知识库head around it. If there's a nice way to do this with LINQ I'd love to hear it, if not I'll be grateful for any other tidy looking answer too - my C++ brain can only think of long-winded procedural ways of doing this :)

Note that I'm using a List for a reason so please don't suggest using a dictionary or another datatype. Thanks.

var sums = list1.Concat(list2).Concat(list3)
            .GroupBy(pair => pair.Key, pair => pair.Value)
            .ToDictionary(g => g.Key, g => g.Sum());

sums here is a Dictionary<DateTime, int>, and you can easily access data using sums[date]. To keep your current data structure, you may replace ToDictionary with:

.Select(g => new KeyValuePair<DateTime, int>(g.Key, g.Sum())).ToList();

A bit more general LINQ way is to use an ILookup - this is similar to a dictionary of lists, so you get the individual numbers, if you need them (again, you can make a quick transformation to get to the list you want):

ILookup<DateTime,int> sums = list1.Concat(list2).Concat(list3)
    .ToLookup(pair=>pair.Key,pair=>pair.Value);
int number = sums[date].Sum();

ILookup<DateTime, int> lookup = source
  .SelectMany(list => list)
  .ToLookup(kvp => kvp.Key, kvp => kvp.Value);

Or

List<KeyValuePair<DateTime, int>> result = source
  .SelectMany(list => list)
  .GroupBy(kvp => kvp.Key, kvp => kvp.Value)
  .Select(g => new KeyValuePair<DateTime, int>(g.Key, g.Sum()))
  .ToList();

This is a great site for examples on LINQ: http://msdn.microsoft.com/en-us/vbasic/bb688085.aspx

I guess this one http://msdn.microsoft.com/en-us/vbasic/bb737926.aspx#grpbysum solves your problem