C# - 侵入式树结构，使用CRTP

Question

我目前正在研究一种在 C# 中实现侵入式树结构的简单方法。由于我主要是一名 C++ 程序员，所以我立刻就想使用 CRTP。这是我的代码：

public class TreeNode<T> where T : TreeNode<T>
{
    public void AddChild(T a_node)
    {
        a_node.SetParent((T)this); // This is the part I hate
    }

    void SetParent(T a_parent)
    {
        m_parent = a_parent;
    }

    T m_parent;
}

这有效，但是...我不明白为什么在调用 a_node.SetParent((T)this) 时必须进行强制转换，因为我正在使用泛型类型限制... C# 强制转换是有成本的，我不想在每个侵入式集合实现中传播此强制转换...

Answer 1

这至少是 TreeNode 类型。它可以是派生的，也可以是 TreeNode。 SetParent 需要一个 T。但 T 可以是与此不同的类型。我们知道 this 和 T 都派生自 TreeNode 但它们可以是不同的类型。

例子：

class A : TreeNode<A> { }
new TreeNode<A>() //'this' is of type 'TreeNode<A>' but required is type 'A'

Answer 2

没有人保证 T 和 this 的类型相同。它们甚至可以是 TreeNode 的不相关子类。

您希望在奇怪的重复模板模式中使用 T，但通用约束无法表达这一点。

愚蠢的实现可以定义为StupidNode:TreeNode。

Answer 3

问题出在这一行：

 TreeNode<T> where T : TreeNode<T>

T 作为 TreeNode 是一个递归定义，它无法在预编译时确定，甚至无法静态检查。不要使用模板，或者如果使用，则需要重构&将节点与有效负载分开（即节点数据与节点本身）。

 public class TreeNode<TPayload>
 {
     TPayload NodeStateInfo{get;set;}

     public void AddChild(TreeNode<TPayload> a_node)
     {
         a_node.SetParent(this); // This is the part I hate
     }

     void SetParent(TreeNode<TPayload> a_parent)
     {
     }
 }

此外，我不确定您为什么要调用 a_node.SetParent(this)。看来 AddChild 更适合命名为 SetParent，因为您将此实例设置为 a_node 的父级。可能是我不熟悉一些深奥的算法，否则看起来就不对劲。

Answer 4

考虑一下如果我们偏离 CRTP 约定，编写...

public class Foo : TreeNode<Foo>
{
}

public class Bar : TreeNode<Foo> // parting from convention
{
}

...然后按如下方式调用上面的代码，会发生什么：

var foo = new Foo();
var foobar = new Bar();
foobar.AddChild(foo);

AddChild 调用抛出一个 InvalidCastException 并表示 无法将“Bar”类型的对象强制转换为“Foo”类型。

关于 CRTP 习惯用法 - 这是单独的约定，要求泛型类型与声明类型相同。该语言必须支持不遵循 CRTP 约定的其他情况。 Eric Lippert 就这个主题写了一篇很棒的博客文章，他从另一个 crtp via c# 答案 链接到该文章。

综上所述，如果您将实现更改为这样...

public class TreeNode<T> where T : TreeNode<T>
{
    public void AddChild(T a_node)
    {
        a_node.SetParent(this);
    }

    void SetParent(TreeNode<T> a_parent)
    {
        m_parent = a_parent;
    }

    TreeNode<T> m_parent;
}

...之前引发 InvalidCastException 的上述代码现在可以工作。此更改使 m_Parent 成为 TreeNode 类型；使 this 要么是 Foo 类中的 T 类型，要么是 TreeNode 的子类Bar 类的情况，因为 Bar 继承自 TreeNode - 无论哪种方式都允许我们省略 SetParent 中的强制转换> 并通过该省略避免无效的强制转换例外，因为分配在所有情况下都是合法的。这样做的代价是不再能够像以前那样在所有地方自由使用 T，这牺牲了 CRTP 的大部分价值。

我的一位同事/朋友认为自己是某种语言/语言功能的新手，直到他可以诚实地说他“在愤怒中使用了它”；也就是说，他对这种语言足够熟悉，以至于他会因为无法实现他所需要的东西或者这样做很痛苦而感到沮丧。这很可能是其中一种情况，因为这里存在一些限制和差异，与以下事实相呼应：泛型不是模板。

Answer 5

当您使用引用类型时，并且您知道沿着类型层次结构进行的强制转换将会成功（此处没有自定义强制转换），则无需实际强制转换任何内容。引用整数的值在强制转换之前和之后是相同的，那么为什么不直接跳过强制转换呢？

这意味着你可以在CIL/MSIL中编写这个令人鄙视的AddChild方法。方法主体操作码如下：

ldarg.1
ldarg.0
stfld TreeNode<class T>::m_parent
ret

.NET 根本不会关心您是否没有转换该值。 The Jitter 似乎只关心商店的大小是否一致，它们始终仅供参考。

加载 Visual Studio 的 IL 支持扩展（可能必须打开 vsix 文件并修改支持的版本），并使用 MethodImpl.ForwardRef 属性将 C# 方法声明为 extern。然后只需在 .il 文件中重新声明该类并添加您需要的一种方法实现，其主体已在上面提供。

请注意，这还会手动将 SetParent 方法内联到 AddChild 中。