在这种情况下，应该使用哪个？IComparable 泛型还是非泛型？

Question

我有一个通用的二叉搜索树和一个数据项类，作为树节点的值。

public class BinarySearchTree<T> : ICollection<T>  where T : IComparable
{

}

public class EnglishDictionaryWord
    : IComparer<EnglishDictionaryWord>, IComparable<EnglishDictionaryWord>
{
    public EnglishDictionaryWord(string word, WordCompareType type)
    {
        Word = word;
        Length = Word.Length;
        _compareType = type;
    }

    public int Compare(EnglishDictionaryWord x, EnglishDictionaryWord y)
    {
        if (_compareType == WordCompareType.Length)
            return new WordLengthComparer().Compare(x, y);
        else if (_compareType == WordCompareType.Lexical)
            return new WordLexicalComparer().Compare(x, y);
        else
            throw new InvalidOperationException("Unsupported Comparison type");
    }

    public int CompareTo(EnglishDictionaryWord obj)
    {
        return Compare(this, obj);
    }
} 

public class WordLengthComparer : IComparer<EnglishDictionaryWord>
{
    public WordLengthComparer()
    {

    }
    public int Compare(EnglishDictionaryWord x, EnglishDictionaryWord y)
    {
        return x.Length - y.Length;
    }
}

and similar Lexical comparer class.

现在当我尝试使用时：

BinarySearchTree<EnglishDictionaryWord> _tree = 
    new BinarySearchTree<EnglishDictionaryWord>();

我遇到了编译错误：

在泛型类型或方法“DsLib.BinarySearchTree”中，无法将类型“DsLib.EnglishDictionaryWord”用作类型参数“T”。从“DsLib.EnglishDictionaryWord”到“System.IComparable”的隐式引用转换不存在。

如果我尝试进行

public class BinarySearchTree<T> : ICollection<T>  where T : IComparable<T>

然后我遇到了这个编译错误，关于装箱转换不可用。

类型“T”无法用作泛型类型或方法“DsLib.BinaryTreeNode”的类型参数。从“T”到“System.IComparable”没有装箱转换或类型参数转换。

我有两个问题：

(1) 我对泛型实现感到困惑。有人能详细说明如何进行更正吗？以及避免将来出现此类错误的一般模式。何时使用，何时使用。

(2) 这个比较器模式是否正确，将比较器放在数据项类中？因为用户将提供要插入树中的新EnglishWord。他可能会为每个单词使用不同的比较器。那么它就会破坏树。

编辑：添加了BSTNode类代码

public class BinaryTreeNode<T> where T : IComparable
{
    public BinaryTreeNode(T value)
    {
        Value = value;
    }

    public T Value { get; protected internal set; }
    public BinaryTreeNode<T> Right { get; protected internal set; }
    public BinaryTreeNode<T> Left { get; protected internal set; }
    public BinaryTreeNode<T> Parent { get; protected internal set; }

    public int Height { get; protected internal set; }
}

- Munish Goyal

---

我没有在任何地方看到 DsLib.BinaryTreeNode ... - Daniel Hilgarth

@Kamarey 我的问题是关于 IComparable 和 IComparable<T>，而不是 IComparer<T> 和 IComparable<T>。 - Munish Goyal

Answer 1

您需要更改BinaryTreeNode：

public class BinaryTreeNode<T> where T : IComparable<T>

- Daniel Hilgarth

---

我也试过了，还是出现了同样的错误。问题仍然是为什么？需要对所提出的问题进行一些解释。 - Munish Goyal

Answer 2

我使用了以下定义来尝试您的代码：

  public class BinarySearchTree<T>
      : ICollection<T>
      where T : IComparable<T>

  public class EnglishDictionaryWord
      : IComparer<EnglishDictionaryWord>,
        IComparable<EnglishDictionaryWord>

  public class WordLengthComparer
      : IComparer<EnglishDictionaryWord>

它运行得非常好 - 它可以编译、执行等等...（.NET 4.0，c#）：

 BinarySearchTree<EnglishDictionaryWord> _tree = 
     new BinarySearchTree<EnglishDictionaryWord>();

回答你的其他问题：

1. 你应该始终优先使用 IComparable<T> 而不是 IComparable。它更快，更不容易出错（没有转换/装箱/拆箱）等等... 至于你的问题：为什么需要？ 简单来说 - IComparable<T> 和 IComparable 是不同的类型（它们有相似的名称，但不要让这使你困惑 - 这些类型是不同的）。所以，你只需要在引用处放置相同的类型。

2. 插入树中的数据应该具有比较逻辑。当你定义树时，你指定它将使用哪些类型的项 - 因此只要该对象存在，你就不能将某些完全不同的类型添加到其中。例如，如果你定义了：

   BinarySearchTree<EnglishDictionaryWord> _tree;

你不能向_tree添加其他东西，比如SpanglishDictionaryWord，因为只有EnglishDictionaryWord的项目被添加，它们具有定义的结构和一致的比较逻辑，所以树会保持正确的结构。

编辑我刚刚看到你有一个“Has”比较器逻辑，而不是纯粹的“Is”可比较。这应该被修复（从数据项中删除对比较器的引用）-如果没有，你是对的-树可能会被破坏...

编辑2如果您需要数据项具有灵活的比较逻辑（即更改它们的比较方式，这很奇怪，所以请考虑一下），那么BST必须引用您打算与之一起使用的比较器的实例：将包装比较器和实际项目的项目放入其中，或将项目的比较器作为BST的属性放置，并在决定要进入哪个分支时对每个数据项使用它。

- veljkoz

---

@Daniel 是的，谢谢。如果我在与树相关的类/方法中到处更改为IComparable<T>，它就可以编译了。这很好。你能回答一下为什么需要这样做以及第二个问题吗？主要是我想了解原因，而不是在将来进行试错 :) - Munish Goyal

+1 for "Has".."Is"。请参阅我对@David B答案的评论，并在该部分递增您的答案。谢谢。 - Munish Goyal

Answer 3

如果我在与树有关的类/方法中到处更改为 IComparable<T>，它就可以编译。为什么需要这样做？ IComparable<T> 未继承自 IComparable。

而第二个问题呢？

你说得对 - 如果不同的项具有不同的排序类型，列表将会出现故障。更好的模式是使类型拥有单一的默认排序行为，然后允许集合接受和使用替代的 IComparers。要查看此操作，请检查 Enumerable.OrderBy 的重载。

- Amy B

---

那么你的意思是，TreeOfEnglishWords.OrderBy(new WordLengthComparer()) 就像这样？我的树在 Add/Contains 操作期间需要比较器。那么树在构造函数中应该接受一个默认的比较器吗？ - Munish Goyal

是的，构造函数。类似于通用字典可以在其构造函数中接受IEqualityComparer<T>。http://msdn.microsoft.com/en-us/library/6918612z.aspx - Amy B