C++ function pointer casting

Question

I'm developing a templated binary search tree in C++ for a data structures class right now. Everything has been going well until now. This issue deals with some nitty gritty C++ stuff that I'm not to familiar with, and I need help.

I've previously defined functions that traverse the tree and visit each node in different orders. The one in question here is defined as follows.

TreeNode.h

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

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

This works fine in a test program that makes nodes and statically calls PostOrderVisit.

In a friend class (BinSTree.h/cpp), I am implementing a method that deletes every node in the tree, so I thought it would be a good idea to use this visitor and call my Delete() function on each node (the Delete() function also works fine in test programs for the BinSTree).

This function is defined as follows.

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

And here lies the problem. g++ says...

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]

In this case, I thought that void (BinSTree<T>::*)(const T&) would be an instance of void (*)(const T&), but it is not. The only way I can get the call to be recognized by the function definition is by casting the function pointer like this:

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

This recognizes the function and calls it appropriately, however (this took some significant research...), C++ member functions have an implicit parameter that allows the 'this' keyword to be accessed from within. Casting a member function pointer to a plain function pointer drops the 'this' reference altogether, causing my Delete() method to seg fault (it uses 'this' quite a bit).

This has been a HELL of a hassle, and I have spent quite a bit of time on such a small bit of this project. Can anyone show me a way to either A: make the function be recognized without the casting, or B: how to maintain the 'this' reference throughout the cast. The ClearTree() and Delete() methods are both within the same class.

Thanks in advance.

If you're already using templates, skip function pointers and go directly to functors. Non-virtual, non-function pointer calls can be inlined. Make visit a template that can overload operator () (). — asveikau
– asveikau, Commented Apr 10, 2012 at 7:09

Some programmer dude · Accepted Answer · 2012-04-10 07:28:33Z

3

First of all, PostOrderVisit should take the function argument as a pointer, i.e. PostOrderVisit(TreeNode<T>* node, void (*visit)(const T& v)).

However, that wont solve your problem because you are passing it a non-static member function. Either the function you pass to it has to be static in the class, or you can use something like std::function instead of a function pointer argument, i.e. PostOrderVisit(TreeNode<T>* node, std::function<void(const T&)> visit).

Edit In that case I think you have two ways you can do this: One is to change your design to fit the parameter, that means you can not use member methods as a parameter. The second is to change the code to fit your design, and explain to the teacher that you had to change the interface due to its limitations, and explain those limitations.

The problem with using a normal function pointer as argument is that member functions have an implicit and hidden argument, this, for the instance of the class. Normal functions do not have this hidden parameter, and so the compiler prohibits you from using a member function. The solution is to either use normal functions, which is not very C++-ish, another is to use static member functions (as they don't have a this pointer), or use something like std::function.

As for how to use std::function, you use it in the declaration and definition of PostOrderVisit like I've shown. When you call it you do something like this:

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

edited Apr 10, 2012 at 7:28

answered Apr 10, 2012 at 7:02

Some programmer dude

411k36 gold badges420 silver badges655 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jay Elrod Over a year ago

Not sure how much leadway I have to change the parameters PostOrderVisit takes, since it's a school project (a very terribly outlined one). Can I use std::function where the function is called? Or must it be in the declaration of PostOrderVisit? Sorry, I'm still a bit new to C++.

Some programmer dude Over a year ago

@JayElrod Added some explanations to my answer.

dpiskyulev · Accepted Answer · 2012-04-10 07:31:01Z

Non-static methods take an implicit parameter for "this". E.g. for a method C::f(int i), you can think of it like f(C* this, int i). Any casting that you do and screws up this signature you can expect badness to happen. You have already experienced crashes but more sinister artifacts could make the program misbehave or crash at other seemingly random places.

You can use pointer to member function like this:

in .h

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

in .cpp (actually if it is a template it has all to be in h, otherwise link error)

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

You either pass pointer to your derived class (C as in here) or pointer to base class (TreeNode as in original). At some point you may need to cast.

You can also leave original function for when you pass a normal function as visitor. Function overload would take care.

A more generic way can be to use std::function. Although it may have some minor performance hit it would be most generic.

e.g. (have not compiled may have some minor syntax errors):

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

Inside PostOrderVisit you just do visit(value), e.g. call like normal function.

When you call PostOrderVisit you can use all the power of std::bind or boost::bind to carry as much extra info as you wish. E.g.

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

Collectives™ on Stack Overflow

C++ function pointer casting

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related