SetComparers: A variety of comparers for collections of objects in C#

• Download SetComparers.zip - 4.7 KB

Introduction

When implementing a mathematical algorithm in code there are many situations where you need to compare sets or collections for equality. One example is the powerset construction algorithm used to convert NFA state machines into DFA state machines. Yet another example is in building LALR(1) parsing tables.

Using this Mess

Using this is just a matter of dropping SetComparers.cs into your project and then using SetComparers:

using SetComparers;
...
var x = new int[] { 1, 2, 3 };
var y = new int[] { 3, 2, 1 };
Console.WriteLine("OrderedSetComparer<int>.Default.Compare(x, y) = {0}", 
    OrderedSetComparer<int>.Default.Compare(x, y));
Console.WriteLine("OrderedSetComparer<int>.Default.Compare(y, x) = {0}", 
    OrderedSetComparer<int>.Default.Compare(y, x));
Console.WriteLine();

Console.WriteLine("OrderedSetEqualityComparer<int>.Default.Equals(x, y) = {0}", 
    OrderedSetEqualityComparer<int>.Default.Equals(x, y));
Console.WriteLine();

Console.WriteLine("UniqueUnorderedSetEqualityComparer<int>.Default.Equals(x, y) = {0}", 
    UniqueUnorderedSetEqualityComparer<int>.Default.Equals(x, y));

You can also use the equality comparers with Dictionary<> and HashSet<> classes so that you can use collections as keys:

var d = new Dictionary<ICollection<int>, string>(
    OrderedSetEqualityComparer<int>.Default);
d.Add(new int[] { 1, 2, 3 }, "foo");
d.Add(new int[] { 3, 2, 1 }, "bar");
Console.WriteLine("d[new int[] { 1, 2, 3 }] = " 
    + d[new int[] { 1, 2, 3 }].ToString());
Console.WriteLine("d[new int[] { 3, 2, 1 }] = " 
    + d[new int[] { 3, 2, 1 }].ToString());

Performance

This is not nearly as performant as it could be if you were using dedicated sets that were intended for this, although it will use the optimized set comparisons on ISet<> instances. If you want better throughput you should use something like my optimized comparable collections.

History

• 23^rd November, 2021 - Initial submission