c# - 为类型 T 的复杂对象创建自定义比较器

Question

我正在用 C# 创建一个树结构，我有一些特定的目标:

• 当 Tree 的用户时创建 new Tree他们必须通过一种 ITreeComparer , 用户知道 T 的类型并且必须创建正确的比较器。
• Tree类创建 TreeNode 的所有实例调用者只添加 T 类型的值到 Tree类(class)。 TreeNode是私有(private)的并且是 Tree 的子类类 所以我需要一种方法将 IComparer 传递给 TreeNode所以我做了ITreeComparer静态。
• 我想使用我的习惯 ITreeComparer对于复杂类型的“T”，但我想让 ITReeComparer 从 IComparer 继承，这样就不需要 Tree 的用户不需要通过 ITreeComparer当类型 T 是基本类型时，例如 double 和 int。

我的问题:

1. 我希望有一种方法可以将 ITreeComparer 保留在 Tree 中类(class)尽管 Tree类处理自身的比较。我做了 ITreeComparision属性(property) TreeNode静态的，更好解决方案？

2. 我收到一条警告 TreeNode 定义 '==' 或 '!=' 但是不覆盖 'Object.Equals(object o) 和'Object.GetHasCode'，为什么我想使用 Object.Equals使用 _comparer.Compare(x.Value, y.Value) , _comparer是个已通过 ITreeComparer Tree 的实例创建者必须供应。

3. 如果 ITreeComparer将实现IComparer我会检查一下吗如果我的_comparer is null如果使用 IComparer默认比较，作为 Tree 的用户不必传入 ITreeComparison实现？

   public interface ITreeComparer<in T>
   {
       int Compare(T x, T y);
   }
   
   
   public class Tree<T>
   {
    private TreeNode _root = null;
    private ITreeComparer<T> _comparer = null;
   
   
   public Tree(ITreeComparer<T> comparer)
   {
       _comparer = comparer;
   }
   
   public Tree(T value, ITreeComparer<T> comparer)
   {
       _root =  new TreeNode(value,_comparer);
       _comparer = comparer;
   }
   
   public T Add(T value)
   {
       var newNode = new TreeNode(value, _comparer);
       if (_root == null)
       {
           _root = newNode;
           return _root.Value;
       }
       else
       {
           var startEdgeDirection = EdgeDirection.Left;
   
           if (_root > newNode) 
               startEdgeDirection = EdgeDirection.Right;
   
           var parent = FindItemNodeParent(value, _root, startEdgeDirection);
       }
   
       return value;
   }
   
   private TreeNode FindItemNodeParent(T value, TreeNode current , EdgeDirection direction)
   {
       throw new NotImplementedException();
   
       if (_comparer.Compare(current.Value, value) == 0)
           return null;
   
       if (direction == EdgeDirection.Left)
       {
   
       }
       else
       {
   
       }
   
   }
   
   private TreeNode Search(T value, TreeNode current, EdgeDirection direction )
   {
       throw new NotImplementedException();
   
       if (_comparer.Compare(current.Value, value) == 0)
           return null;
   
       if (direction == EdgeDirection.Left)
       {
   
       }
       else
       {
   
       }
   }
   
   private enum EdgeDirection
   {
       Left,
       Right
   }
   
   
   private class TreeNode
   {
       private static ITreeComparer<T> _comparer;
       public TreeNode LeftEdge { get; set; }
       public TreeNode RightEdge { get; set; }
       public T Value { get; set; }
   
       public TreeNode(ITreeComparer<T> comparer)
       {
           _comparer = comparer;
       }
   
       public TreeNode(T value, ITreeComparer<T> comparer)
       {
           Value = value;
           _comparer = comparer;
       }
   
       public static bool operator < (TreeNode x, TreeNode y)
       {
             if (x == null)
               return y == null;
           return _comparer.Compare(x.Value, y.Value) < 0;
   
       }
   
       public static bool operator > (TreeNode x, TreeNode y)
       {
             if (x == null)
               return y == null;
   
           return _comparer.Compare(x.Value, y.Value) > 0;
       }
   
       public static bool operator == (TreeNode x, TreeNode y)
       {
           if (x == null)
               return y == null;
   
           return _comparer.Compare(x.Value, y.Value) == 0;
       }
   
       public static bool operator != (TreeNode x, TreeNode y)
       {
            if (x == null)
               return y == null;
   
           return _comparer.Compare(x.Value, y.Value)  != 0;
       }
   }
   

更新

根据有用的 Stackoverflowers 的建议，我只使用 IComparable，我已经从 TreeNode 中删除了所有重载的比较运算符，并且我正在设置我的私有(private) IComparer<T> _comparer至 Comparer<T>.Default .这总是有效的，因为我添加了“where T: IComparable”，这意味着 Tree 的用户必须在他们的自定义 T 对象上实现 IComparable，对于 C# 原语，IComparable 已经实现，当 T 是 int 时，他们将不必实现 IComparable例如，他们将永远不需要传入 IComparer，因为必须始终为其类型 T 实现 IComparable。

    public partial class Tree<T> where T : IComparable<T>
{
    private TreeNode _root = null;
    private IComparer<T> _comparer = null;


    public Tree()
    {
        _comparer = Comparer<T>.Default;
    }

    public Tree(T value)
    {
        _root = new TreeNode(value);
        _comparer = Comparer<T>.Default;
    }

    public T Add(T value)
    {
        var newNode = new TreeNode(value);
        if (_root == null)
        {
            _root = newNode;
            return _root.Value;
        }

        var startEdgeDirection = EdgeDirection.Left;

        if (_comparer.Compare(_root.Value, value) > 0)
            startEdgeDirection = EdgeDirection.Right;

        var parent = FindItemNodeParent(value, _root, startEdgeDirection);

        if (parent != null)
        {
            if (_comparer.Compare(parent.Value, value) > 0)
            {
                parent.RightDescendant = newNode;
            }
            else
            {
                parent.LeftDescendant = newNode;
            }
        }


        return value;
    }

    private TreeNode FindItemNodeParent(T value, TreeNode current, EdgeDirection direction)
    {
        if (_comparer.Compare(current.Value, value) == 0)
            return null;

        if (direction == EdgeDirection.Left)
        {
            if (current.LeftDescendant == null)
                return current;

            if (_comparer.Compare(current.LeftDescendant.Value, value) > 0)
            {
                FindItemNodeParent(value, current.LeftDescendant, EdgeDirection.Right);
            }
            else
            {
                FindItemNodeParent(value, current.LeftDescendant, EdgeDirection.Left);
            }
        }
        else
        {
            if (current.RightDescendant == null)
                return current;

            if (_comparer.Compare(current.RightDescendant.Value, value) > 0)
            {
                FindItemNodeParent(value, current.RightDescendant, EdgeDirection.Right);
            }
            else
            {
                FindItemNodeParent(value, current.RightDescendant, EdgeDirection.Left);
            }

        }

        return null;

    }

    private TreeNode Search(T value, TreeNode current, EdgeDirection direction)
    {
        throw new NotImplementedException();

        if (_comparer.Compare(current.Value, value) == 0)
            return null;

        if (direction == EdgeDirection.Left)
        {

        }
        else
        {

        }
    }

    private enum EdgeDirection
    {
        Left,
        Right
    }

}

 public partial class Tree<T>
{
    private class TreeNode
    {
        public TreeNode LeftDescendant { get; set; }
        public TreeNode RightDescendant { get; set; }
        public T Value { get; set; }

        public TreeNode(T value)
        {
            Value = value;
        }
    }
}

Answer 1

正如我在上面的评论中提到的，我不明白为什么你有接口(interface) ITreeComparer .在我看来，它与 IComparer 完全一样, 所以你可以只使用 IComparer相反。

也就是说……

1. I wish there was a way to keep the ITreeComparer in the Tree class even though Tree class handles comparisons of itself. I made the ITreeComparision property in TreeNode static, any better solutions than this?

我同意制作它 static是个坏主意。一个明显的问题是，这意味着您只能使用一种 Tree<T>在一个过程中(即对于任何给定的 T ，只能有一种比较)。这意味着，例如，如果您有一个具有属性 Name 的类和 Id , 你只能拥有按 Name 排序的树，或按 Id 排序的树, 但不是同时出现这两种树。

的确，有了这个字段static在TreeNode<T>类，它是 Tree<T> 中的实例字段毫无意义, 因为所有 Tree<T>对象将使用相同的 TreeNode<T>类型。

在我看来，你甚至公开 ITreeComparer 的唯一原因到 TreeNode是为了允许重载比较运算符。如果你必须有那些运营商，我会继续做 _comparer TreeNode<T> 中的非静态字段，甚至只是将其更改为对父级的引用 Tree<T>对象(然后它可以从父级获取 _comparer)。

但实际上，我并不认为比较运算符有多大帮助。你不妨调用_comparer直接在 Tree<T>上课，不用费心 TreeNode<T>甚至懂得 self 比较。

2. I am getting a warning that TreeNode defines '==' or '!=' but does not override 'Object.Equals(object o) and 'Object.GetHasCode', why would I use Object.Equals when I want to use the _comparer.Compare(x.Value, y.Value), _comparer is the passed in ITreeComparer instance creator of Tree must supply.

无论好坏，对象在 C# 中进行 self 比较的方式有多种。任何时候这些方法的实现方式不一致，您都会为一些真正令人头疼的错误做好准备。

因此，当您重载与相等相关的运算符时 ==和 != , 但不是 Equals()方法，您会收到警告。同样，在不修复 GetHashCode() 的情况下实现自定义平等关系正确反射(reflect)这些相等关系是获得非常难以修复的错误的好方法。

如果您开始在类型本身内实现相等操作，确保您在该类型中执行并执行一致的所有相等相关操作，这一点非常重要。

3. If ITreeComparer were to implement IComparer would I just check if my _comparer is null and if is use the IComparer default Comparison, that way as user of Tree does not have to pass in an ITreeComparison implmentation?

正如我提到的，我认为您应该删除 ITreeComparer共。没有真正的“沙盒”在进行……事实上，如果用户愿意，他们可以让一个类实现这两个接口(interface)，在接口(interface)中使用完全相同的方法。当内置接口(interface)就足够了时，强制用户实现自定义接口(interface)只会让他们感到更加恼火。

只要我在写，我就会同意 the non-answer provided by ipavlu确实提供了一些有用的意见。特别是，您对空值的处理完全错误。另一篇文章指出了一些问题。另一个问题是如果x和 y都是空的，你的比较运算符都返回 true . IE。根据代码，x和 y如果它们都为空，则同时大于和小于彼此。

幸运的是，确实没有明显的理由表明比较需要处理空值。原始实现(由用户提供)按照约定已经需要容纳空值。您自己的代码不需要检查它们。此外，空值根本没有出现在树中的明显原因。空节点引用没有多大意义:任何时候您在树中到达空节点，这就是您要存储节点的位置；没有必要决定新节点是在那个 null 的左边还是右边……它在那个时候 null 的位置右边!