The compiler states that there's no matching function for a call, even though there is one in the prototype

Question

I'm trying to implement a binary search tree class, but the compiler is throwing errors. The bstNode.h file is here:

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);
}

The .h file compiles fine with an empty main function, but when I try it with the following bit of code in bstNode.cxx, it crashes, giving an error. The code is:

    #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;
}

And the error is:

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]

The prototype is exactly the same as the function's implementation, sans the bstNode:: so I'm not sure what's going on. I'm using the g++ compiler. Any ideas? Much appreciated, thanks.

EDIT: I cut down on the code to try and highlight the problem.

It would help you (and us) if you could isolate the problem. Please reduce your program to the smallest complete program that still demonstrates the error. http://sscce.org/. — Robᵩ, May 01 '12 at 20:01
See [Why isn't it legal to convert pointer-to-pointer-to-non-const to pointer-to-pointer-to-const](http://stackoverflow.com/questions/2220916/why-isnt-it-legal-to-convert-pointer-to-pointer-to-non-const-to-a-pointer-to). Valid for reference to the pointers as well. — Bo Persson, May 01 '12 at 20:07

score 6 · Answer 1 · answered May 01 '12 at 20:05

6

The prototype isn't exactly the same, because there's a constness difference. The declaration is

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

(reference to const pointer) whereas you've called it as

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

so it's getting a reference to non-const pointer. And while you can pass a foo * to something that takes a const foo *, you can't pass a foo * by reference to something that takes a const foo * &.

answered May 01 '12 at 20:05

Gareth McCaughan

19,888
1
41
62

Ah, thanks, that must be it. I think I'll just take the reference out. It's unnecessary, only there because the teacher wanted it. I was very confused when he gave us the assignment, because if it was const and couldn't be modified, then what was the point of passing it as reference? I guess the compiler agreed. :D – vanchagreen May 01 '12 at 20:08
@vanchagreen: Note that in `const T * &` the pointer is *not* const, it is a mutable pointer to a `const T`. It might help if you rewrite the consts to the right: `const T*&` is equivalent to `T const *&`, and not to `T *const &` (*reference to a const pointer to a non-const T*) – David Rodríguez - dribeas May 01 '12 at 20:13
vanchagreen, if either David's answer or mine has solved the problem -- which it sounds like they have -- then you should accept one of them. (I think David's answer is a bit better even though mine currently has more upvotes, but you can accept mine instead if you happen to prefer it :-).) – Gareth McCaughan May 01 '12 at 20:41
Ah, sorry, I'm new to stack overflow. :D – vanchagreen May 01 '12 at 21:24
@GarethMcCaughan Unfortunately I'm not allowed modify my teacher's definitions. And I can't pass a const T*& into the function without making the function itself const, which I cannot do, since I can't modify the definition. Any advice? – vanchagreen May 01 '12 at 21:34
As to the last question: you could declare `root_ptr` to be `const bstNode *` instead of just `bstNode *`. Or make another variable that's `const bstNode *`, assign `root_ptr` to it, and call `tree_copy` on that. – Gareth McCaughan May 01 '12 at 21:39
@GarethMcCaughan I'll go back and do that then, thanks. As for the question, if I were to make bstNode a const, wouldn't I have to make the function itself const? – vanchagreen May 01 '12 at 22:10
`tree_copy` doesn't actually use the object it's being called on, so if you declare `root_ptr` non-const, make a const version of it, and call `root_ptr.tree_copy(const_root_ptr)`, I think that will work. It's ugly, but the real fault is in the weird way `tree_copy` is declared, and there's nothing you can do about that. – Gareth McCaughan May 01 '12 at 23:01

David Rodríguez - dribeas · Accepted Answer · 2012-05-01T20:11:07.960

The compiler (as in most cases) is right in rejecting the code. The problem is that there is no conversion from T*& to const T*&, so the existing function cannot be used.

Why is that conversion not present?

The reason for that conversion not to be present is that it would break const-correctness. Consider this example:

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
}

Now, a possible solution, since you do not need to modify the pointer passed to the function is to add even more consts to the signature:

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

In doing so, you are blocking the code from changing the pointer, which is the problem in the example above. But, if you really think about it,

Why do you pass a reference to a pointer in the first place?

Pointers are cheap to copy, so passing them by const& does not make much sense, and since you do not need the function to change the pointer that you are passing, passing by value will be both correct and potentially more efficient.

Unfortunately I'm not allowed modify my teacher's definitions. And I can't pass a const T*& into the function without making the function itself const, which I cannot do, since I can't modify the definition. Any advice? — vanchagreen, May 01 '12 at 21:27

The compiler states that there's no matching function for a call, even though there is one in the prototype

2 Answers2