Как написать Equatable или Comparable тип

Не редко возникает необходимость добавить к типу данных, созданных вами, возможности для сравнения экземпляров друг с другом или с другими объектами. В C#, так уж повелось, это не самая простая операция, чреватая и ошибками и избыточным кодом. Связано это с тем, как мне кажется, что в различных источниках приведены самые разные "паттерны" реализации сравнения и люди, начитавшись (кто-то больше, кто-то меньше) иногда смешивают подходы в одном примере с подходами в другом да добавляют ещё и что-то от себя лично :) Таким образом "паттерны" размножаются, служа пищей для размышления и источником вдохновения для следующего поколения программистов, которые читают доставшийся им код, другие публикации и придумывают свои "паттерны".

Так же, свою руку к путанице, на первый взгляд, приложили и сами разработчики дотнета, описав "запутанные" правила, по которым должно быть реализовано сравнение (смотрите Notes to Implementers /* Даже адрес по ссылке заканчивается на "АК-47", даже на два :о) */). Но это только так кажется, на самом деле правила весьма просты и, наоборот, позволяют просто и безошибочно реализовать сравнения.

Большой вклад по привлечению к обозначенной проблеме широкой общественности внёс Чистяков Влад (VladD2) в своей статье "Багодром: Реализация операторов сравнения", наглядно продемонстрировав, на сколько неприятны могут быть последствия плохой реализации и предложив надёжный "паттерн" решения. Ниже я лишь где-то упрощу, а где-то усложню предложенный способ (обратите внимание, что предложенный в статье способ следует использовать только для reference-типов), а так же предложу способ, который следует применять с value-типами.

Тренироваться будем на следующих типах, к которым сначала добавим возможность сравнения на равенство, а затем на больше-меньше.

using System;

internal struct MyValue
{
 public MyValue(int first, int? second) : this() {
   First = first;
   Second = second;
 }

 public int First { get; private set; }
 public int? Second { get; private set; }
}

internal sealed class MyData
{
 public MyData(string name, MyValue value) {
   Name = name ?? String.Empty;
   Value = value;
 }

 public string Name { get; private set; }
 public MyValue Value { get; private set; }
}

Мы переопределим методы Equals(object) и GetHashCode(), добавим реализацию IEquatable<>, а так же переопределим операторы == и !=. Причём собственно реализация сравнения будет находиться лишь в двух методах: Object::GetHashCode() и IEquatable<T>::Equals(T) и всё остальные вызовы будут переадресованы туда и их реализация и будет "паттерном", не зависящим от логики сравнения.

internal struct MyValue : IEquatable<MyValue>
{
 public MyValue(int first, int? second) : this() {
   First = first;
   Second = second;
 }

 public int First { get; private set; }
 public int? Second { get; private set; }

 public override bool Equals(object obj) {
   return obj is MyValue && Equals((MyValue)obj);
 }

 public override int GetHashCode() {
   return First.GetHashCode() ^ Second.GetHashCode();
 }

 #region IEquatable<MyValue> Members

 public bool Equals(MyValue other) {
   return First == other.First && Second == other.Second;
 }

 #endregion IEquatable<MyValue> Members

 public static bool operator ==(MyValue left, MyValue right) {
   return left.Equals(right);
 }

 public static bool operator !=(MyValue left, MyValue right) {
   return !(left == right);
 }
}

internal sealed class MyData : IEquatable<MyData>
{
 public MyData(string name, MyValue value) {
   Name = name ?? String.Empty;
   Value = value;
 }

 public string Name { get; private set; }
 public MyValue Value { get; private set; }

 public override bool Equals(object obj) {
   return Equals(obj as MyData);
 }

 public override int GetHashCode() {
   return Name.GetHashCode() ^ Value.GetHashCode();
 }

 #region IEquatable<MyData> Members

 public bool Equals(MyData other) {
   return other != null
     && Name == other.Name
     && Value == other.Value;
 }

 #endregion IEquatable<MyData> Members

 public static bool operator ==(MyData left, MyData right) {
   return Equals(left, right);
 }

 public static bool operator !=(MyData left, MyData right) {
   return !(left == right);
 }
}

Разница между реализацией в значимом и ссылочном типах следующая:

• Проверка типа аргумента в значимом типе в реализации Object::Equals(object) "двойная" - сначала посредством is, а потом при приведении типа, но по-другому никак. С сылочным типом ситуация лучше - тут используется оператор as, который одновременно и проверяет тип и делает приведение типа. Причём, если тип аргумента не подходящий, as вернёт null, а эта ситуация рассматривается в следующем пункте.
• При реализации IEquatable<T>::Equals(T) в ссылочном типе всегда проверяйте аргумент на null и возвращайте false если проверка удалась, ибо "x.Equals(null) returns false" (Notes to Implementers).
• Реализация оператора "==" проста - в значимом типе мы просто вызываем экземплярный типизированный Equals, а в ссылочном - статический Object::Equals(object, object), который сначала проверит аргументы на null, а потом вызовет тот же самый экземплярный типизированный Equals (только если оба аргумента не пустые). Почему-то разработчики часто забывают об этом удобнейшем методе и самостоятельно выписывают велосипеды a-la
  if(ReferenceEquals(left, null)) {
    return ReferenceEquals(right, null);
  } else if(ReferenceEquals(right, null)) {
    return false;
  }//if
  
  или
  if((object)left == null) {
    return (object)right == null;
  } else if((object)right == null) {
    return false;
  }//if
  
  что совершенно не требуется.

Отдельно надо остановиться на следующем моменте: часто можно видеть при реализации равенства в ссылочном типе проверку, что мы сравниваем объект с самим собой. Виноват в этом, мне кажется, Джеффри Рихтер, начавший с этого соответствующую главу своей книги. Я этим обычно не пользуюсь, ибо 1) не часто приходится сравнивать объекты друг с другом и большого выигрыша не получается 2) на каплю, но усложняется логика сравнения, что, учитывая пункт первый, становится не нужным. Однако, если вы считаете, что такое сравнение добавит вам производительности, то реализация IEquatable<T>::Equals(T) может быть примерно такой:

public bool Equals(MyData other) {
  return RefenrenceEquals(other, this) || other != null
    && Name == other.Name
    && Value == other.Value;
}

Для завершения раздела о реализации равенства скажу, что сравнение незапечатанных (обратили внимание, что класс MyData обозначен как sealed?) ссылочных типов достойно отдельной статьи.

Наконец, для упрощения написания этих шаблонных методов я использую сниппеты. Первый добавляет реализацию для значимого типа:

<CodeSnippets xmlns="http://schemas.microsoft.com/VisualStudio/2005/CodeSnippet">
 <CodeSnippet Format="1.0.0">
   <Header>
     <Title>Implements IEquatable<> interface for a value type</Title>
     <Shortcut>eqstruct</Shortcut>
     <SnippetTypes>
       <SnippetType>Expansion</SnippetType>
     </SnippetTypes>
   </Header>
   <Snippet>
     <Declarations>
       <Literal Editable="false">
         <ID>TypeName</ID>
         <Function>ClassName()</Function>
       </Literal>
       <Literal Editable="false">
         <ID>NotImplementedException</ID>
         <Function>SimpleTypeName(global::System.NotImplementedException)</Function>
       </Literal>
     </Declarations>
     <Code Language="CSharp">
<![CDATA[public override bool Equals(object obj) {
  return obj is $TypeName$ && Equals(($TypeName$)obj);
}

public override int GetHashCode() {
  throw new $NotImplementedException$();
}

#region IEquatable<$TypeName$> Members

public bool Equals($TypeName$ other) {
  // Add you equals logic
  //return $end$;
  throw new $NotImplementedException$();
}

#endregion IEquatable<$TypeName$> Members

public static bool operator ==($TypeName$ left, $TypeName$ right) {
  return left.Equals(right);
}

public static bool operator !=($TypeName$ left, $TypeName$ right) {
  return !(left == right);
}]]>
     </Code>
   </Snippet>
 </CodeSnippet>
</CodeSnippets>

Второй - для ссылочного типа:

<CodeSnippets xmlns="http://schemas.microsoft.com/VisualStudio/2005/CodeSnippet">
 <CodeSnippet Format="1.0.0">
   <Header>
     <Title>Implements IEquatable<> interface for a reference type</Title>
     <Shortcut>eqclass</Shortcut>
     <SnippetTypes>
       <SnippetType>Expansion</SnippetType>
     </SnippetTypes>
   </Header>
   <Snippet>
     <Declarations>
       <Literal Editable="false">
         <ID>TypeName</ID>
         <Function>ClassName()</Function>
       </Literal>
       <Literal Editable="false">
         <ID>NotImplementedException</ID>
         <Function>SimpleTypeName(global::System.NotImplementedException)</Function>
       </Literal>
     </Declarations>
     <Code Language="CSharp">
<![CDATA[public override bool Equals(object obj) {
  return Equals(obj as $TypeName$);
}

public override int GetHashCode() {
  throw new $NotImplementedException$();
}

#region IEquatable<$TypeName$> Members

public bool Equals($TypeName$ other) {
  // Add you equals logic
  //return other != null && $end$;
  throw new $NotImplementedException$();
}

#endregion IEquatable<$TypeName$> Members

public static bool operator ==($TypeName$ left, $TypeName$ right) {
  return Equals(left, right);
}

public static bool operator !=($TypeName$ left, $TypeName$ right) {
  return !(left == right);
}]]>
     </Code>
   </Snippet>
 </CodeSnippet>
</CodeSnippets>

Реализация сравнения на больше-меньше будет заметно легче - в ней нет подводных камней, достаточно всё сделать аккуратно. Следующий пост постараюсь посвятить ей.

Компараторы для HashSet<>

Как я попробовал показать в предыдущем сообщении, стандартная реализация компаратора для HashSet<> содержит ошибку, которая состоит в том, что при сравнении элементов хешсета может использоваться внутренний компаратор хешсета, а при расчёте хешкода всегда используется стандартный (EqualityComparer<>.Default).

Настало время эту ошибку исправить. Вдаваясь в долгие и скучные объяснения с различными примерами можно показать, что одним методом без параметров для получения компаратора, как HashSet<>::CreateSetComparer(), нельзя вернуть универсальный компаратор на все случаи жизни. Поэтому придётся использовать два метода:

• Один (без параметров) возвращает компаратор, который для сравнения элементов и расчёта хешкода всегда использует внутренний компаратор хешсета. При этом, при сравнении двух хешсетов компаратор вернёт false в том случае, если компараторы в хешсетах не эквивалентны.
• Второй позволяет задать извне компаратор, который будет использоваться для сравнения элементов хешсета и расчёта хешкода.

Первый метод следует использовать тогда, когда вы заранее знаете, что будете сравнивать хешсеты, которые одинаково (одним и тем же компаратором) сравнивают свои собственные элементы. Второй метод позволит сравнивать произвольные хешсеты, но вы должны сами задать (с помощью компаратора) - как именно следует сравнивать элементы в этих хешсетах.

Вот эти методы (класс Comparers у меня содержит всякое безобразие для всевозможных компараторов, например, ещё это и это):

public static partial class Comparers
{
 public static EqualityComparer<HashSet<T>> HashSetComparer<T>() {
   return HashSetEqualityComparer<T>.Default;
 }

 public static EqualityComparer<HashSet<T>> HashSetCustomComparer<T>(IEqualityComparer<T> comparer = null) {
   return new HashSetCustomEqualityComparer<T>(comparer);
 }
}

Первый метод всегда возвращает один и тот же объект, так логика работы этого компаратора не зависит от каких либо внешних факторов. Второй метод возвращает компаратор, параметризованный другим компаратором, который будет использоваться для сравнения элементов хешсета, поэтому каждый раз создаётся новый объект. Рассмотрим устройство и особенности этих объектов.

Первый компаратор:

public static partial class Comparers
{
 [Serializable]
 private sealed class HashSetEqualityComparer<T> : EqualityComparer<HashSet<T>>
 {
   private const int MagicNumber = 13;

   static HashSetEqualityComparer() {
     Default = new HashSetEqualityComparer<T>();
   }

   public static new HashSetEqualityComparer<T> Default { get; private set; }

   public override bool Equals(HashSet<T> x, HashSet<T> y) {
     if(x == null) {
       return y == null;
     } else if(y == null) {
       return false;
     } else if(!Equals(x.Comparer, y.Comparer)) {
       return false;
     }//if

     return x.SetEquals(y);
   }

   public override int GetHashCode(HashSet<T> obj) {
     if(obj == null) {
       return 0;
     }//if

     return obj.Aggregate(0, (hash, item) =>
       hash ^ (obj.Comparer.GetHashCode(item) & 0x7FFFFFFF));
   }

   public override bool Equals(object obj) {
     return obj is HashSetEqualityComparer<T>;
   }

   public override int GetHashCode() {
     return MagicNumber;
   }
 }
}

Особенности:

• Данный компаратор умеет сравнивать только хешсеты с одинаковыми компараторами, зато достаточно оптимально.
• При вычислении хешкода для получения хешкода элемента хешсета используется внутренний компаратор хешсета.
• Любые два экземпляра этого компаратора всегда равны между собой (а экземпляров может быть несколько, так как конструктор открытый). Вообще, реализация сравнения в компараторах - отдельная тема. Обратите внимание, что для сравнения компараторов здесь используется метод Object::Equals(object, object), а не оператор сравнения (как, например, в родной реализации компаратора).
• MaficNumber, не равный нулю, используется из-за того, что равный нулю хешкод обычно возвращается для объектов, имеющих значение null.

Второй компаратор:

public static partial class Comparers
{
 [Serializable]
 private sealed class HashSetCustomEqualityComparer<T> : EqualityComparer<HashSet<T>>
 {
   public HashSetCustomEqualityComparer(IEqualityComparer<T> comparer = null) {
     Comparer = comparer ?? EqualityComparer<T>.Default;
   }

   private IEqualityComparer<T> Comparer { get; set; }

   public override bool Equals(HashSet<T> x, HashSet<T> y) {
     if(x == null) {
       return y == null;
     } else if(y == null) {
       return false;
     } else if(Equals(x.Comparer, y.Comparer) && Equals(x.Comparer, Comparer)) {
       return x.SetEquals(y);
     }//if

     var set = new HashSet<T>(x, Comparer);
     return set.SetEquals(y);
   }

   public override int GetHashCode(HashSet<T> obj) {
     if(obj == null) {
       return 0;
     }//if

     return obj.Aggregate(0, (hash, item) =>
       hash ^ (Comparer.GetHashCode(item) & 0x7FFFFFFF));
   }

   public override bool Equals(object obj) {
     var other = obj as HashSetCustomEqualityComparer<T>;
     return other != null && Equals(other.Comparer, Comparer);
   }

   public override int GetHashCode() {
     return Comparer.GetHashCode();
   }
 }
}

Особенности:

• Если компараторы сравниваемых хешсетов эквивалентны как между собой, так и с внутренним компаратором, будет использован более оптимальный способ сравнения.
• При вычислении хешкода для получения хешкода элемента хешсета используется собственный компаратор.

Конечно, можно было бы обойтись и одним методом и одним классом компаратора, но было бы больше проверок и ветвлений, поэтому я выбрал небольшое дублирование кода (реализация GetHashCode() у компараторов отличается только используемым внутри компаратором), но более простые классы.

В заключении надо сказать, что похожие проблемы есть и у компаратора, который стандартная библиотека предоставляет для SortedSet<>. Я, как мог, постарался описать их на форуме BCL (здесь) и узнал, что, оказывается, это всё by design, то есть "так и задумано". Хотя это может быть и ошибочным мнением. Отдельно на коннект сообщать об этой, второй, похожей проблеме нет желания - много писанины с заранее известным результатом. Буду надеяться, что справившись с опубликованной багой они просмотрят аналогичный код и приведут его в соответствие.

Баг в реализации HashSet<>::CreateSetComparer()

Не правильно работает компаратор, возвращаемый методом CreateSetComparer класса HashSet<>. Пример кода, демонстрирующий ошибку:

using System;
using System.Collections.Generic;
using System.Diagnostics;

internal sealed class MyItem
{
  public MyItem(int number, string text) {
    Number = number;
    Text = text ?? String.Empty;
  }

  public int Number { get; private set; }
  public string Text { get; private set; }
}

internal sealed class MyItemComparer : EqualityComparer<MyItem>
{
  public override bool Equals(MyItem x, MyItem y) {
    if(x == null) {
      return y == null;
    } else if(y == null) {
      return false;
    } else {
      return EqualityComparer<int>.Default.Equals(x.Number, y.Number);
    }//if
  }

  public override int GetHashCode(MyItem obj) {
    if(obj == null) {
      return 0;
    }//if

    return EqualityComparer<int>.Default.GetHashCode(obj.Number);
  }
}

internal static class Program
{
  private static void Main() {
    var itemComparer = new MyItemComparer();

    var set1 = new HashSet<MyItem>(itemComparer) { new MyItem(1, "One"), };
    var set2 = new HashSet<MyItem>(itemComparer) { new MyItem(1, "1"), };

    var test = set1.SetEquals(set2);
    Debug.Assert(test); // OK

    var setComparer = HashSet<MyItem>.CreateSetComparer();
    var equals = setComparer.Equals(set1, set2);
    Debug.Assert(equals); // OK

    var hash1 = setComparer.GetHashCode(set1);
    var hash2 = setComparer.GetHashCode(set2);
    Debug.Assert(hash1 == hash2, "hash1 == hash2"); // Failed
  }
}

Ошибка заключается в том, что для двух объектов, которые компаратор считает равными, он возвращает различные хеш-коды. Происходит это в рассмотренном случае из-за того, что при рассчёте равенства используется внутренний компаратор хеш-сета (потому что компараторы оказываются равными), а вот при подсчёте хеш-кода всегда используется дефолтовый компаратор.

Для решения моей проблемы будет достаточным написать свой аналог компаратора, в который можно будет передать кастомный компаратор элементов.

Update: Желающие могут проголосовать за этот баг на коннекте.