1

我正在尝试实现二叉搜索树类，但编译器抛出错误。bstNode.h 文件在这里：

template <class Item, class Key>
class bstNode
{
public:
    bstNode();
    bstNode(const Item& init_data, const Key& init_key, bstNode<Item, Key> *init_left, bstNode<Item, Key> *init_right);
    ~bstNode();
    bstNode<Item, Key>* tree_copy(const bstNode<Item, Key>*& root);
private:
    Item data;
    Key key;
    bstNode* left;
    bstNode* right;
};

    template <class Item, class Key>
    //line 83 in the original code is below
bstNode<Item, Key>* bstNode<Item, Key>::tree_copy(const bstNode<Item, Key>*& root)
{
    bstNode<Item, Key>* l_ptr;
    bstNode<Item, Key>* r_ptr;
    if (root == NULL) return NULL;
    l_ptr = tree_copy(root -> left());
    r_ptr = tree_copy(root -> right());
    return new bstNode<Item, Key> (root -> data(), l_ptr, r_ptr);
}

.h 文件可以使用空的 main 函数正常编译，但是当我使用 bstNode.cxx 中的以下代码尝试它时，它会崩溃，并给出错误。代码是：

    #include <cstddef>
#include <algorithm>
#include <math.h>
#include <iostream>
#include "bstNode.h"

using namespace std;

int main()
{
    bstNode<int, size_t>* root_ptr = NULL;
    bstNode<int, size_t>* copy_root_ptr = root_ptr -> tree_copy(root_ptr);
    return 0;
}

错误是：

bstNode.cxx: In function ‘int main()’:
bstNode.cxx:14: error: no matching function for call to ‘bstNode<int, long unsigned int>::tree_copy(bstNode<int, long unsigned int>*&)’
bstNode.h:83: note: candidates are: bstNode<Item, Key>* bstNode<Item, Key>::tree_copy(const bstNode<Item, Key>*&) [with Item = int, Key = long unsigned int]

原型与函数的实现完全相同，没有 bstNode:: 所以我不确定发生了什么。我正在使用 g++ 编译器。有任何想法吗？非常感谢，谢谢。

编辑：我减少了代码以尝试突出问题。

4

2 回答 2

6

原型并不完全相同，因为存在质量const差异。声明是

 bstNode<Item, Key>* tree_copy(const bstNode<Item, Key>*& root);

（引用 const 指针）而您将其称为

 bstNode<int, size_t>* root_ptr;
 tree_copy(root_ptr);

所以它得到了对非常量指针的引用。虽然你可以将 a 传递foo *给需要 a 的东西，const foo *但你不能通过foo *引用来传递 a 到需要 a 的东西const foo * &。

于 2012-05-01T20:05:00.373 回答
6

编译器（在大多数情况下）拒绝代码是正确的。问题是没有从T*&to的转换const T*&，所以不能使用现有的函数。

为什么这种转换不存在？

不存在该转换的原因是它会破坏 const 正确性。考虑这个例子：

const int k = 10;
void f( const int*& kp ) {
   kp = &k;                 // Fine, the pointer promises not to change the object
}
int main() {
   int *p; 
   f( p );                 // Does not compile, but assume it would
                           // after the call, p points to k
   *p = 20;                // Modifying a constant!!!!
                           //    p never promised not to change the pointee
}

现在，一个可能的解决方案是，因为您不需要修改传递给函数的指针，所以const在签名中添加更多 s：

bstNode<Item, Key>* tree_copy(const bstNode<Item, Key>* const & root);

这样做会阻止代码更改指针，这是上面示例中的问题。但是，如果你真的想一想，

为什么首先要传递对指针的引用？

指针复制起来很便宜，因此传递它们const&没有多大意义，而且由于您不需要函数来更改要传递的指针，因此按值传递既正确又可能更有效。

于 2012-05-01T20:05:45.420 回答