Comparing two sets for new and missing keys

Question

When comparing two key-value dictionary sets in C#: set A and set B, what is the best way to enumerate keys present in set A but missing from set B and vice-versa?

For example:

A = { 1, 2, 5 }
B = { 2, 3, 5 }

Comparing B with A, missing keys = { 1 } and new keys = { 3 }.

Using Dictionary<...,...> objects, one can enumerating all values in B and test against set A using A.ContainsKey(key);, but it feels like there should be a better way that might involve a sorted set?

Answer 1

I'm aware of two built-in ways of doing set differences.

1) Enumerable.Except

Produces the set difference of two sequences by using the default equality comparer to compare values.

Example:

IEnumerable<int> a = new int[] { 1, 2, 5 };
IEnumerable<int> b = new int[] { 2, 3, 5 };

foreach (int x in a.Except(b))
{
    Console.WriteLine(x);  // prints "1"
}

2a) HashSet<T>.ExceptWith

Removes all elements in the specified collection from the current HashSet<T> object.

HashSet<int> a = new HashSet<int> { 1, 2, 5 };
HashSet<int> b = new HashSet<int> { 2, 3, 5 };

a.ExceptWith(b);

foreach (int x in a)
{
    Console.WriteLine(x);  // prints "1"
}

2b) HashSet<T>.SymmetricExceptWith

Modifies the current HashSet<T> object to contain only elements that are present either in that object or in the specified collection, but not both.

HashSet<int> a = new HashSet<int> { 1, 2, 5 };
HashSet<int> b = new HashSet<int> { 2, 3, 5 };

a.SymmetricExceptWith(b);

foreach (int x in a)
{
    Console.WriteLine(x);  // prints "1" and "3"
}

If you need something more performant, you'll probably need to roll your own collection type.

Answer 2

Use SortedDictionary : logic is A.Except(A.Intersect(B)).

Don't worry overmuch about performance until you've determined it is an issue to your datasets.