What problem does IStructuralEquatable and IStructuralComparable solve?

I've noticed these two interfaces, and several associated classes, have been added in .NET 4. They seem a bit superfluous to me; I've read several blogs about them, but I still can't figure out what problem they solve that was tricky before .NET 4.

What use are IStructuralEquatable and IStructuralComparable?

Solution 1:

All types in .NET support the Object.Equals() method which, by default, compares two types for reference equality. However, sometimes, it also desirable to be able to compare two types for structural equality.

The best example of this is arrays, which with .NET 4 now implement the IStructuralEquatable interface. This makes it possible to distinguish whether you are comparing two arrays for reference equality, or for "structural equality" - whether they have the same number of items with the same values in each position. Here's an example:

int[] array1 = new int[] { 1, 5, 9 };
int[] array2 = new int[] { 1, 5, 9 };

// using reference comparison...
Console.WriteLine( array1.Equals( array2 ) ); // outputs false

// now using the System.Array implementation of IStructuralEquatable
Console.WriteLine(
    StructuralComparisons.StructuralEqualityComparer.Equals( array1, array2 )
); // outputs true

Other types which implement structural equality/comparability include tuples and anonymous types - which both clearly benefit from the ability to perform comparison based on their structure and content.

A question you didn't ask is:

Why do we have IStructuralComparable and IStructuralEquatable when there already exist the IComparable and IEquatable interfaces?

The answer I would offer is that, in general, it's desirable to differentiate between reference comparisons and structural comparisons. It's normally expected that if you implement IEquatable<T>.Equals you will also override Object.Equals to be consistent. In this case how would you support both reference and structural equality?

Solution 2:

I had the same question. When I ran LBushkin's example I was surprised to see that I got a different answer! Even though that answer has 8 upvotes, it is wrong. After a lot of 'reflector'ing, here is my take on things.

Certain containers (arrays, tuples, anonymous types) support IStructuralComparable and IStructuralEquatable.

• IStructuralComparable supports deep, default sorting.
• IStructuralEquatable supports deep, default hashing.

{Note that EqualityComparer<T> supports shallow (only 1 container level), default hashing.}

As far as I see this is only exposed through the StructuralComparisons class. The only way I can figure out to make this useful is to make a StructuralEqualityComparer<T> helper class as follow:

    public class StructuralEqualityComparer<T> : IEqualityComparer<T>
    {
        public bool Equals(T x, T y)
        {
            return StructuralComparisons.StructuralEqualityComparer.Equals(x,y);
        }

        public int GetHashCode(T obj)
        {
            return StructuralComparisons.StructuralEqualityComparer.GetHashCode(obj);
        }

        private static StructuralEqualityComparer<T> defaultComparer;
        public static StructuralEqualityComparer<T> Default
        {
            get
            {
                StructuralEqualityComparer<T> comparer = defaultComparer;
                if (comparer == null)
                {
                    comparer = new StructuralEqualityComparer<T>();
                    defaultComparer = comparer;
                }
                return comparer;
            }
        }
    }

Now we can make a HashSet with items having containers within containers within containers.

        var item1 = Tuple.Create(1, new int[][] { new int[] { 1, 2 }, new int[] { 3 } });
        var item1Clone = Tuple.Create(1, new int[][] { new int[] { 1, 2 }, new int[] { 3 } });
        var item2 = Tuple.Create(1, new int[][] { new int[] { 1, 3 }, new int[] { 3 } });

        var set = new HashSet<Tuple<int, int[][]>>(StructuralEqualityComparer<Tuple<int, int[][]>>.Default);
        Console.WriteLine(set.Add(item1));      //true
        Console.WriteLine(set.Add(item1Clone)); //false
        Console.WriteLine(set.Add(item2));      //true

We can also make our own container play well with these other containers by implementing these interfaces.

public class StructuralLinkedList<T> : LinkedList<T>, IStructuralEquatable
    {
        public bool Equals(object other, IEqualityComparer comparer)
        {
            if (other == null)
                return false;

            StructuralLinkedList<T> otherList = other as StructuralLinkedList<T>;
            if (otherList == null)
                return false;

            using( var thisItem = this.GetEnumerator() )
            using (var otherItem = otherList.GetEnumerator())
            {
                while (true)
                {
                    bool thisDone = !thisItem.MoveNext();
                    bool otherDone = !otherItem.MoveNext();

                    if (thisDone && otherDone)
                        break;

                    if (thisDone || otherDone)
                        return false;

                    if (!comparer.Equals(thisItem.Current, otherItem.Current))
                        return false;
                }
            }

            return true;
        }

        public int GetHashCode(IEqualityComparer comparer)
        {
            var result = 0;
            foreach (var item in this)
                result = result * 31 + comparer.GetHashCode(item);

            return result;
        }

        public void Add(T item)
        {
            this.AddLast(item);
        }
    }

Now we can make a HashSet with items having containers within custom containers within containers.

        var item1 = Tuple.Create(1, new StructuralLinkedList<int[]> { new int[] { 1, 2 }, new int[] { 3 } });
        var item1Clone = Tuple.Create(1, new StructuralLinkedList<int[]> { new int[] { 1, 2 }, new int[] { 3 } });
        var item2 = Tuple.Create(1, new StructuralLinkedList<int[]> { new int[] { 1, 3 }, new int[] { 3 } });

        var set = new HashSet<Tuple<int, StructuralLinkedList<int[]>>>(StructuralEqualityComparer<Tuple<int, StructuralLinkedList<int[]>>>.Default);
        Console.WriteLine(set.Add(item1));      //true
        Console.WriteLine(set.Add(item1Clone)); //false
        Console.WriteLine(set.Add(item2));      //true

Solution 3:

Here is another example that illustrates a possible usage of the two interfaces:

var a1 = new[] { 1, 33, 376, 4};
var a2 = new[] { 1, 33, 376, 4 };
var a3 = new[] { 2, 366, 12, 12};

Debug.WriteLine(a1.Equals(a2)); // False
Debug.WriteLine(StructuralComparisons.StructuralEqualityComparer.Equals(a1, a2)); // True

Debug.WriteLine(StructuralComparisons.StructuralComparer.Compare(a1, a2)); // 0
Debug.WriteLine(StructuralComparisons.StructuralComparer.Compare(a1, a3)); // -1

Solution 4:

The description of the IStructuralEquatable Interface says (in the "Remarks" section):

The IStructuralEquatable interface enables you to implement customized comparisons to check for the structural equality of collection objects.

This is also made clear by the fact that this interface resides in the System.Collections namespace.