«

Hi,

I'm working on writing a templated Binary Search Tree class in C++. In
regular C, I would have functions which traverse the tree take a pointer
to a user-defined function as an argument, which would then execute the
user-defined function for each node that is "visited". For example:

/* in the BST header file */
/* I actually don't remember if this is valid C or not */
typedef void (*fn)(void* tree_item);
void BST_inorder_traverse(const BST *tree, fn func);
/*...*/
void display_item(void* tree_item);
/*...*/
BST_inorder_traverse(tree, display); /* or something */

However, I'm not entierly certian how to do this in C++ if the BST is a
templated class. Is it possible to use typedef in conjunction with
templates? or is there some other 'correct' way of doing something like
this in C++?

Thanks,

Chris Schadl

Chris Schadl wrote:

> I'm working on writing a templated Binary Search Tree class in C++. In
> regular C, I would have functions which traverse the tree take a pointer
> to a user-defined function as an argument, which would then execute the
> user-defined function for each node that is "visited". For example:
>
> /* in the BST header file */
> /* I actually don't remember if this is valid C or not */
> typedef void (*fn)(void* tree_item);
> void BST_inorder_traverse(const BST *tree, fn func);
> /*...*/
> void display_item(void* tree_item);
> /*...*/
> BST_inorder_traverse(tree, display); /* or something */
>
> However, I'm not entierly certian how to do this in C++ if the BST is a
> templated class. Is it possible to use typedef in conjunction with
> templates? or is there some other 'correct' way of doing something like
> this in C++?

The standard library uses function objects. See for example the sort
template. You use templates to avoid specifying the type of a function
object. Here's a simple example.

#include <ostream>
#include <iostream>

template <typename Function>
void example (Function func)
{
for (int i = 0; i != 10; ++ i) func (i);
}

void f (int i)
{
std::cout << "Print " << i << " through pointer-to-function.\n";
}

struct g
{
void operator () (int i)
{
std::cout << "Print " << i << " through function object.\n";
}
};

int main ()
{
example (& f);
example (g ());
}

--
Regards,
Buster.

"Chris Schadl" <> wrote in message
news .uk...
> Hi,
>
> I'm working on writing a templated Binary Search Tree class in C++. In
> regular C, I would have functions which traverse the tree take a pointer
> to a user-defined function as an argument, which would then execute the
> user-defined function for each node that is "visited". For example:
>
> /* in the BST header file */
> /* I actually don't remember if this is valid C or not */
> typedef void (*fn)(void* tree_item);
> void BST_inorder_traverse(const BST *tree, fn func);
> /*...*/
> void display_item(void* tree_item);
> /*...*/
> BST_inorder_traverse(tree, display); /* or something */
>
> However, I'm not entierly certian how to do this in C++ if the BST is a
> templated class. Is it possible to use typedef in conjunction with
> templates?

Of course, assuming something like this, where NODE is the type of the node
data (and so the type of the parameter to your function pointer).

template <class NODE>
class BST
{
public:
typedef void (*node_visitor_func)(NODE*);
void inorder_traverse(node_visitor_func func);
};

john