为类型 T 的复杂 object 创建自定义比较器

Question

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

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

我的问题：

我希望有一种方法可以将 ITreeComparer 保留在 Tree class 即使 Tree class 处理自身的比较。我做了 ITreeComparision 属性 in TreeNode static，更好解决方案比这个？
我收到警告说 TreeNode 定义了“==”或“!=”，但是不会覆盖 'Object.Equals(object o) 和 'Object.GetHasCode'，我为什么要用Object.Equals 使用 _comparer.Compare(x.Value, y.Value)，_comparer 是传入 ITreeComparer Tree 的实例创建者必须提供。

如果 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;
    }
}

}

更新

根据有用的 Whosebugers 的建议，我只使用 IComparable，我从 TreeNode 中删除了所有重载的比较运算符，并将我的私有 IComparer<T> _comparer 设置为 Comparer<T>.Default。这总是有效的，因为我添加了“where T: IComparable”，这意味着 Tree 的用户将必须在他们的自定义 T object 上实现 IComparable，对于 C# 基元，IComparable 已经实现并且他们将不必实现 IComparable 时例如，T 是 int，他们永远不需要传入 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

你的代码有很大问题：

public static bool operator == (TreeNode x, TreeNode y)
{
    if (x == null) return y == null;

    return _comparer.Compare(x.Value, y.Value) == 0;
}

x是树节点，y是树节点，所以：

      if (x == null) return y == null;

x == null 最终会调用 operator== 方法，因此该方法正在调用自身。

你必须这样做：

(object)x == null,

只要使用相同的类型，operator==就会调用自己。为了让它变得干净，这里 object.ReferenceEquals.

此外，您是否注意到您的代码不是 null 安全的？ x != null 和 y == null 是什么意思？然后 y.Value 将在行中抛出异常：

    return _comparer.Compare(x.Value, y.Value) == 0;

试试这样的方法：

public static bool operator == (TreeNode x, TreeNode y)
{
    var x_null = object.ReferenceEquals(x,null);
    var y_null = object.ReferenceEquals(y,null);
    if (x_null && y_null) return true;
    if (x_null || y_null) return false;

    //now is x.Value, y.Value is safe to call
    return _comparer.Compare(x.Value, y.Value) == 0;
}

Answer 2

正如我在上面的评论中提到的，我不明白你为什么有接口 ITreeComparer。在我看来，它与 IComparer 完全相同，因此您可以改用 IComparer。

也就是说……

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 属性的 class，您只能拥有按 Name 排序的树，或按 Id，但不是同时有两种树。

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

在我看来，你甚至将 ITreeComparer 暴露给 TreeNode 的唯一原因是为了允许重载比较运算符。如果你必须有这些运算符，我会继续在 TreeNode<T> 中使 _comparer 字段成为非静态字段，或者甚至只是将其更改为对父 Tree<T> 对象的引用（然后它可以从父级获得 _comparer）。

但实际上，我不觉得比较运算符有多大帮助。您不妨直接在 Tree<T> class 中调用 _comparer 而不必费心让 TreeNode<T> 甚至知道如何比较自己。

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# 中进行自我比较的方式有多种。任何时候这些方法的实现方式不一致，您都会为一些真正令人头疼的错误做好准备。

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

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

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。没有实际的 "sandboxing" 进行……事实上，用户可以根据需要使用接口中完全相同的方法使单个 class 实现两个接口。强制用户实现自定义界面，而内置界面就足够了，这只会让他们更加恼火。

只要我在写作，我就会同意 ipavlu 确实提供了一些有用的观察结果。特别是，您对空值的处理完全错误。另一个 post 指出了一些问题。另一个问题是如果 x 和 y 都是空的，你的比较运算符都是 return true。 IE。根据代码，如果 x 和 y 都为空，则它们同时大于和小于彼此。

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

为类型 T 的复杂 object 创建自定义比较器

Creating a custom comparer for a complex object of Type T

c#

tree

visual-studio