1

我现在正在用 C++ 为数据结构类开发一个模板化的二叉搜索树。到目前为止，一切都进展顺利。这个问题涉及一些我不熟悉的细节 C++ 东西，我需要帮助。

我之前定义了遍历树并以不同顺序访问每个节点的函数。这里所讨论的定义如下。

树节点.h

public:
  static void PostOrderVisit(TreeNode<T>* node, void visit(const T& v));

树节点.cpp 

template <class T> void TreeNode<T>::PostOrderVisit(TreeNode* node, void visit(const T& v)) {
  if (node->leftChild != NULL)
    PostOrderVisit(node->leftChild, visit);
  if (node->rightChild != NULL)
    PostOrderVisit(node->rightChild, visit);
  visit(node->value);
}

这在制作节点并静态调用 PostOrderVisit 的测试程序中运行良好。

在一个朋友类（BinSTree.h/cpp）中，我正在实现一个删除树中每个节点的方法，所以我认为使用这个访问者并在每个节点上调用我的 Delete() 函数是个好主意（ Delete() 函数在 BinSTree 的测试程序中也可以正常工作）。

该函数定义如下。

template <class T> void BinSTree<T>::ClearTree() {
  TreeNode<T>::PostOrderVisit(this->root(), &BinSTree<T>::Delete);
}

这就是问题所在。g++ 说……

BinSTree.cpp:156: error: no matching function for call to ‘TreeNode<int>::PostOrderVisit(TreeNode<int>*, void (BinSTree<int>::*)(const int&))’
TreeNode.cpp:56: note: candidates are: static void TreeNode<T>::PostOrderVisit(TreeNode<T>*, void (*)(const T&)) [with T = int]

在这种情况下，我认为那void (BinSTree<T>::*)(const T&)将是 的一个实例void (*)(const T&)，但事实并非如此。我可以让函数定义识别调用的唯一方法是像这样转换函数指针：

TreeNode<T>::PostOrderVisit(this->root(), (void (*)(const T& v)) &BinSTree<T>::Delete);

这可以识别函数并适当地调用它，但是（这需要进行一些重要的研究......），C++ 成员函数有一个隐式参数，允许从内部访问“this”关键字。将成员函数指针转换为普通函数指针会完全删除“this”引用，导致我的 Delete() 方法出现段错误（它使用了很多“this”）。

这太麻烦了，我花了很多时间在这个项目的一小部分上。谁能告诉我一种方法：A：在没有强制转换的情况下识别函数，或者 B：如何在整个强制转换中保持“this”引用。ClearTree() 和 Delete() 方法都在同一个类中。

提前致谢。

4

2 回答 2

3

首先，PostOrderVisit应该将函数参数作为指针，即PostOrderVisit(TreeNode<T>* node, void (*visit)(const T& v)).

但是，这不会解决您的问题，因为您正在向它传递一个非静态成员函数。您传递给它的函数必须static在类中，或者您可以使用类似的东西std::function而不是函数指针参数，即PostOrderVisit(TreeNode<T>* node, std::function<void(const T&)> visit).

编辑 在那种情况下，我认为你有两种方法可以做到这一点：一种是改变你的设计以适应参数，这意味着你不能使用成员方法作为参数。二是修改代码以适应你的设计，向老师解释由于它的限制你必须改变界面，并解释那些限制。

使用普通函数指针作为参数的问题在于，成员函数this对于类的实例有一个隐式和隐藏的参数 。普通函数没有这个隐藏参数，所以编译器禁止你使用成员函数。解决方案是使用普通函数，这不是很 C++-ish，另一种是使用static成员函数（因为它们没有this指针），或者使用类似std::function.

至于如何使用std::function，你在PostOrderVisit我展示的声明和定义中使用它。当您调用它时，您会执行以下操作：

template <class T> void BinSTree<T>::ClearTree() {
    TreeNode<T>::PostOrderVisit(this->root(), std::mem_fn(&BinSTree<T>::Delete));
}
于 2012-04-10T07:02:27.933 回答
1

非静态方法采用“this”的隐式参数。例如对于一个方法 C::f(int i)，你可以把它想象成 f(C* this, int i)。你所做的任何铸造并搞砸了这个签名，你都可以预料到坏事会发生。您已经经历过崩溃，但更险恶的伪影可能会使程序行为异常或在其他看似随机的地方崩溃。

您可以像这样使用指向成员函数的指针：

在.h

template <class C>
static void PostOrderVisit(C* node, void (C::* visit)(const T& v));

在 .cpp 中（实际上，如果它是一个模板，它必须全部在 h 中，否则链接错误）

template <class T>
template <class C>
void TreeNode<T>::PostOrderVisit(C* node, void (C::* visit)(const T& v))
{
    // ...
    T value;
    (node->*visit)(value);
    // ...
}

您可以将指针传递给派生类（如此处的 C）或指向基类的指针（如原始的 TreeNode）。在某些时候，您可能需要投射。

当您将普通函数作为访问者传递时，您也可以保留原始函数。函数重载会引起注意。

更通用的方法是使用 std::function。尽管它可能会对性能造成一些轻微的影响，但它是最通用的。

例如（未编译可能有一些小的语法错误）：

static void PostOrderVisit(TreeNode<T>* node, std::function<void (const T& v)> visit);

在 PostOrderVisit 中，您只需执行访问（值），例如像普通函数一样调用。

当您调用 PostOrderVisit 时，您可以使用 std::bind 或 boost::bind 的所有功能来携带尽可能多的额外信息。例如

PostOrderVisit(this->root(), std::bind(&BinSTree::Delete, this));

于 2012-04-10T07:31:01.213 回答