IEqualityComparer for sequences (T[], Memory<T>, IEnumerable<T>)

Problem:

Sometimes, it is useful to use arrays as keys in a map such as Dictionary. A motivating use case would be blockchain applications. Here, we often need to map a hash to some piece of data. For example, we might want to map a 32 byte block hash (byte[]) to block metadata.

Proposal:

There should be built-in equality comparers for sequences. By default, each element is default-compared. It should be possible to use a custom nested comparer.

I propose this API surface:

public static class EqualityComparer
{
    public static IEqualityComparer<T[]> Array<T>(IEqualityComparer<T> elementComparer = null);
    public static IEqualityComparer<Memory<T>> Memory<T>(IEqualityComparer<T> elementComparer = null);
    public static IEqualityComparer<IEnumerable<T>> Sequence<T>(IEqualityComparer<T> elementComparer = null);
}

Example usage:

var dict = new Dictionary<byte[], BlockHeader>(EqualityComparer.Array<byte>());

These factory methods can internally pick an optimal comparer for the given arguments. For example, for arrays of primitive types, we can use memcmp-style algorithms internally. If a custom comparer is provided, an element-by-element comparison algorithm must be used. A cached instance can be used if no custom comparer is provided.

Possible extension: The same thing could be done for IComparer<T[]> (see #33873).

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

I don't think adding excessive overloads for matrix of current collections and operations is a good idea.

I'm looking forward to improvement of type system (HKT, Type Classes). Then they can be written once for all kind of certain abstraction.

I think the request seems reasonable. The API design should probably be made in unison with #33873.

Should we be also supporting ReadOnlyMemory<T> comparers?

Should we be also supporting ReadOnlyMemory<T> comparers?

Is there a case that Memory<T> needs to be treated differently from ReadOnlyMemory<T>? If no, then I'd say to only have ReadOnlyMemory<T> comparers, since converting from the writable version to ReadOnly is implicit.

Agreed, so perhaps something like this?

namespace System.Collections.Generic
{
+    public static class EqualityComparer
+    {
+        public static IEqualityComparer<T[]> Array<T>(IEqualityComparer<T>? elementComparer = null);
+        public static IEqualityComparer<ReadOnlyMemory<T>> ReadOnlyMemory<T>(IEqualityComparer<T>? elementComparer = null);
+        public static IEqualityComparer<IEnumerable<T>> Sequence<T>(IEqualityComparer<T>? elementComparer = null);
+    }
}

Any annotation to clarify it's sequence equality instead of set equality?

Any annotation to clarify it's sequence equality instead of set equality?

Hmm, I can't think of a reason why this could be assumed to use set equality (or why would ever want to introduce set equality for these types to require some form of disambiguation). But perhaps you're right that we should be explicit about the semantics in the combinator names. But I can't think of a naming convention better than this:

namespace System.Collections.Generic
{
+    public static class EqualityComparer
+    {
+        public static IEqualityComparer<T[]> ArraySequenceEquality<T>(IEqualityComparer<T>? elementComparer = null);
+        public static IEqualityComparer<ReadOnlyMemory<T>> MemorySequenceEquality<T>(IEqualityComparer<T>? elementComparer = null);
+        public static IEqualityComparer<IEnumerable<T>> EnumerableSequenceEquality<T>(IEqualityComparer<T>? elementComparer = null);
+    }
}

Related to #48304.

@Joe4evr

@Joe4evr A Dictionary with Memory<T> keys would need a Memory<T> equality comparer, since implicit coersion to ReadOnlyMemory doesn't work inside generic code. Arguably one should not use Memory<T> keys, though.

@qwertie

@qwertie If you absolutely need that for some ungodly reason, you can make a wrapper easily enough:

internal sealed class MemoryComparerWrapper<T> : IEqualityComparer<Memory<T>>
{
    private readonly IEqualityComparer<ReadOnlyMemory<T>> _wrappedComparer;

    public MemoryComparerWrapper(IEqualityComparer<T>? elementComparer = null)
        => _wrappedComparer = EqualityComparer.MemorySequenceEquality(elementComparer);

    public bool Equals(Memory<T> x, Memory<T> y) => _wrappedComparer.Equals(x, y);
    public int GetHashCode(Memory<T> obj) => _wrappedComparer.GetHashCode(obj);
}

That would double the number of interface calls per comparison, reducing performance. Keep in mind: performance is what motivates the use of Memory<T> in the first place.

Related to #27039.

Due to lack of recent activity, this issue has been marked as a candidate for backlog cleanup. It will be closed if no further activity occurs within 14 more days. Any new comment (by anyone, not necessarily the author) will undo this process.

This process is part of our issue cleanup automation.

Due to lack of recent activity, this issue has been marked as a candidate for backlog cleanup. It will be closed if no further activity occurs within 14 more days. Any new comment (by anyone, not necessarily the author) will undo this process.

This process is part of our issue cleanup automation.

Navigation Menu

Repository navigation

IEqualityComparer for sequences (T[], Memory<T>, IEnumerable<T>) #44796

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

IEqualityComparer for sequences (T[], Memory<T>, IEnumerable<T>) #44796

Description

Activity

Dotnet-GitSync-Bot commented on Nov 17, 2020

huoyaoyuan commented on Nov 17, 2020

eiriktsarpalis commented on Nov 25, 2020

eiriktsarpalis commented on Nov 25, 2020

Joe4evr commented on Nov 26, 2020

eiriktsarpalis commented on Nov 26, 2020

huoyaoyuan commented on Nov 26, 2020

eiriktsarpalis commented on Nov 26, 2020

eiriktsarpalis commented on Apr 19, 2021

qwertie commented on Jul 25, 2021

Joe4evr commented on Jul 26, 2021

qwertie commented on Jul 26, 2021

eiriktsarpalis commented on Oct 29, 2021

dotnet-policy-service commented on Oct 19, 2026

dotnet-policy-service commented on Oct 19, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions