如何从/扩展递归类 [英] How to derive from/extend a recursive class

问题描述

我有一个递归类，一种树，其自身的实例作为成员变量。例如：

I have a recursive class, a kind of tree, that has instances of itself as member variables. For example:

template<class T>
class Tree {
public: 
  /* Constructors, etc. */
protected:
  T m_value;
  Tree<T> *leftChild;
  Tree<T> *rightChild;
};

如果我想添加一种使用有序遍历打印所有值的方法，则可以为此：

If I want to add a method that prints all the values using an in-order traversal, I could do this:

template <class T>
void Tree<T>::printInOrder()
{
   leftChild->printInOrder();
   std::cout << m_value << std::endl;
   rightChild->printInOrder();
}

但是，由于种种原因，我不能或不可以怎么办想更改Tree的实现？如果该类不是递归的，即不包含其自身的实例，则可以从Tree派生并在派生类中实现一个新方法。

But what if, for various reasons, I couldn't or didn't want to change Tree's implementation? If the class wasn't recursive, i.e. didn't contain instances of itself, I could just derive from Tree and implement a new method in the derived class. But this approach doesn't work for Tree.

template <class T>
class DerivedClass : public Tree<T> {
public:
  void printInOrder();
}

template <class T>
void DerivedClass<T>::
printInOrder()
{
   this->leftChild->printInOrder();
   std::cout << this->m_value << std::endl;
   this->rightChild->printInOrder();
}

leftChild和rightChild是Tree的实例，因此没有printInOrder（ ） 方法。

leftChild and rightChild are instances of Tree and thus don't have a printInOrder() method.

任何人都可以提出一种无需更改Tree的实现即可以模块化方式实现此目标的方法。只要您不需要在班级中进行扩展/派生，就不必更改它的总体实现方式。我可以通过使模板类T具有执行我想做的事情的方法来看到一种可能的方法，但这看起来很丑。必须有更好的方法。

Can anyone suggest a way to do this in a modular way without changing Tree's implementation. It's ok to change how it is implemented in general, as long as you don't have to change it whenever you want to extend/derive from the class. I can see a possible way to do it by making the template class T have methods to do the things I want, but that just seems ugly. There must be a better way.

我很高兴有人指出我如何忽略了明显的事情。

I'm perfectly happy for someone to point out how I've overlooked something obvious. It certainly feels like I have.

编辑：重点不是如何实现printInOrder（）。那只是一个例子。关键是如何派生一个类，以便子级也是派生类。

The point is not how to implement printInOrder(). That was just an example. The point is how to derive a class so that the children are also the derived class.

推荐答案

节点类型上的模板。 / p>

Template on the node type.

template<typename T, typename NodeType = void> class Tree {
    NodeType node;
    T m_data;
};
template<typename T> class Tree<void> {
    struct Node {
        Tree<T, void>* left;
        Tree<T, void>* right;
    };
    Node node;
    T m_data;
};
template<typename T> struct DerivedNode {
     DerivedTree<T>* left;
     DerivedTree<T>* right;
};
template<typename T> class DerivedTree : public Tree<T, DerivedNode<T>> {
     // now left and right are of type DerivedTree<T>*.
};

这基于两个不变量-即 Tree< T，NodeT> 为所有 NodeT 提供相同的接口，并且 DerivedTree< T> 继承自 Tree< T，...> 。

This works based on two invariants- that Tree<T, NodeT> offers the same interface for all NodeT, and that DerivedTree<T> inherits from Tree<T, ...>.

编辑：该死，为了防止递归实例化，这花了很多功夫 Tree< T，NodeType> 的数量。

Damn, that took a lot of effort to prevent recursive instantiation of Tree<T, NodeType>.

这篇关于如何从/扩展递归类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！