BST with polymorphic data

[Angelwings]

Hi everyone,
I've to write my own definition of a BST with polymorphic data, as an
university course project.
I have troubles about comparing data when it's defined as polymorphic
pointer.
In my situation I've something like:
class A {}
class B : public A {}
class C : public A {}

and a BST allocated as bst<A*>

how should I discern when i've to compare pointers (as the example) or
objects (as bst<B> for example)?
Thanks in advance and sorry for my english.

 

[Kai-Uwe Bux]

Hi everyone,
I've to write my own definition of a BST with polymorphic data, as an
university course project.
I have troubles about comparing data when it's defined as polymorphic
pointer.
In my situation I've something like:
class A {}
class B : public A {}
class C : public A {}

and a BST allocated as bst<A*>

Since we have no idea what the bst<> template looks like, the last piece of
information is by and large useless.

how should I discern when i've to compare pointers (as the example) or
objects (as bst<B> for example)?

Huh? How would a bst<B> come up if you have a bst<A*>?



Anyway, here is a suggestion on how to separate concerns: first implement a
basic_bst<T> template that does not support polymorphism at all. Instead it
presupposes the existence of a binary predicate

bool less_than ( T lhs, T rhs )

or

bool less_than ( T const & lhs, T const & rhs )

and does all comparison through that predicate. (Of course, you would be
reinventing the wheel at this point, since the associative standard
containers implement exactly this.)

Then, define a forwarding comparison predicate:

bool less_than ( A const * lhs, A const * rhs ) {
assert ( lhs != 0 );
assert ( rhs != 0 );
return ( polymorphic_less( *lhs, *rhs ) );
}

And finally define

bool polymorphic_less ( A const & lhs, A const & rhs )

in a way appropriate for comparing objects of types derived from A. Note
that the const-reference parameters preserve the dynamic type.

Now, you can use basic_bst<A*> to store non-null A* which will be compared
through comparison of pointees. Finally, you can write your polymophic
bst<A> as a wrapper around basic_bst<A*> essentially changing the interface
from using non-null A* to A&.

Note: There is one major issue that you will have to deal with, namely
whether objects shall be copied into the search tree or whether the search
tree just holds pointers to the original objects (this ought to be
mentioned somewhere in the specs). In the first case, you would need to
clone the objects as you populate the tree and you would need to dispose of
them when they are removed.


Best

Kai-Uwe Bux

 

[Angelwings]

Huh? How would a bst<B> come up if you have a bst<A*>?
the binary search tree has to work with every type. I'm going to write
with more details the exercise.
Premise: I know it's exactly what an stl tree does, but since it's a
didactic exercise we have to implement it by ourself, without using
stl library.

The exercise consists to define a template of a container, with
minimal operations of insertion, search and erasing.
Then we have to define a class hierarchy that use the container. So I
defined something like i wrote before:

class A {}
class B : public A {}
class C : public A {}

Since every object A, B, C, could be inside the container at runtime,
I have to allocate the bst as bst<A*>. But this is a *particular*
allocation for the exercise. The bst should keep his generalization.

The problem comes when I've to compare objects inside a method of the
bst. If they are allocated as objects there's no problem; they are
compared by their operators. But if they are pointers, they are
compared with their address. I want to dereference them in that case
to use comparing operators of the objects they point.

Here's an example:

template <class T>
void BinarySearchTree<T>::recInsert(Node<T>* root, const T& value) {
if (value < root->info)
if (root->left == 0)
root->left = new Node<T>(value, root);
else
recInsert(root->left, value);
else
if (root->right == 0)
root->right = new Node<T>(value, root);
else
recInsert(root->right, value);
}// recInsert

if the value is a pointer, the addresses are compared instead of
objects.
I've read I could use a functor in the bst template, to define a
custom comparison function. Is that a correct way? Where could I find
a good example to know how I could use a functor in my case? (I
googled it a few yesterday but I didn't find a good explanation)

thanks.

 

[Kai-Uwe Bux]

Huh? How would a bst<B> come up if you have a bst<A*>?

the binary search tree has to work with every type. I'm going to write
with more details the exercise.
Premise: I know it's exactly what an stl tree does, but since it's a
didactic exercise we have to implement it by ourself, without using
stl library.

The exercise consists to define a template of a container, with
minimal operations of insertion, search and erasing.
Then we have to define a class hierarchy that use the container. So I
defined something like i wrote before:

class A {}
class B : public A {}
class C : public A {}

Since every object A, B, C, could be inside the container at runtime,
I have to allocate the bst as bst<A*>. But this is a *particular*
allocation for the exercise. The bst should keep his generalization.

The problem comes when I've to compare objects inside a method of the
bst. If they are allocated as objects there's no problem; they are
compared by their operators. But if they are pointers, they are
compared with their address. I want to dereference them in that case
to use comparing operators of the objects they point. [snip]
I've read I could use a functor in the bst template, to define a
custom comparison function. Is that a correct way?

It is the way that is used in the STL. It has proven to be feasible.

Where could I find
a good example to know how I could use a functor in my case? (I
googled it a few yesterday but I didn't find a good explanation)

What do you mean by "use a functor"? That can refer to two things (at
least):

a) How to implement bst<> so that it allows for customization of the
comparison by a user-provided functor.

b) How to write a functor that will forward comparison to pointees.


Best

Kai-Uwe Bux

 

[Angelwings]

What do you mean by "use a functor"? That can refer to two things (at
least):

Sorry I know nothing about functors

a) How to implement bst<> so that it allows for customization of the
comparison by a user-provided functor.

this one. I've seen it's the standard way in the stl library. I've
seen some examples and I've seen they overload the operator(). But I
don't want to just copy 'n' paste. I want to understand what I'm
doing. I'd like to read a complete explanation on how they work. I'll
look more on google but if you know a good place to learn them you'll
make to me a great favor to link me the site thanks!

 

[Kai-Uwe Bux]

Sorry I know nothing about functors
this one.
Ok.

I've seen it's the standard way in the stl library. I've
seen some examples and I've seen they overload the operator(). But I
don't want to just copy 'n' paste. I want to understand what I'm
doing. I'd like to read a complete explanation on how they work. I'll
look more on google but if you know a good place to learn them you'll
make to me a great favor to link me the site thanks!

The basic idea is to no hard-code the comparison. For instance, consider the
function you posted:

template <class T>
void BinarySearchTree<T>::recInsert(Node<T>* root, const T& value) {
if (value < root->info)
if (root->left == 0)
root->left = new Node<T>(value, root);
else
recInsert(root->left, value);
else
if (root->right == 0)
root->right = new Node<T>(value, root);
else
recInsert(root->right, value);
}// recInsert


In the line

if ( value < root->info )

you have hard-coded the comparison. Instead, consider this:

if ( this->is_less( value, root->info ) )

This uses a member object (is_less) to do the comparison. Naturally, for
this syntax to work, the member object is_less will need an overloaded
operator()( T const & lhs, T const & rhs ). However, done this way, the
semantics of the comparison will depend on the _value_ of is_less.


Now, the question arises, what the type of is_less will be. There are two
main alternatives:

a) is_less could be a function pointer

bool (*) ( T const &, T const & )

b) the type is_less could be passed to bst as a template parameter.

The second is more flexible. It is usually done like this:


template < typename T, typename Comp = std::less<T> >
class bst {

...
Comp is_less;

public:

bst ( Comp pred = Comp() )
: is_less ( pred )
{}

...

};

Note the default-type for Comp and the default value for pred. Taken
together, they ensure that writing

bst<T> tree;

creates a tree that does comparison like the first version.


Best

Kai-Uwe Bux

 

[Angelwings]

Thanks a lot for the complete and clear example.

Seeing I'll need to search datas within the tree I thought to define a
compare functor that returns a value < 0 if a < b, a value > 0 if a >
b and 0 otherwise. Is it a standard way? Or it's better to use a
second argument in the template for the equality?

 

[Kai-Uwe Bux]

Thanks a lot for the complete and clear example.

Seeing I'll need to search datas within the tree I thought to define a
compare functor that returns a value < 0 if a < b, a value > 0 if a >
b and 0 otherwise. Is it a standard way? Or it's better to use a
second argument in the template for the equality?

The standard associative containers only use one comparison predicate and
operate on the premise that


either a < b
or b < a
or a == b

That is, if neither a < b nor b < a, the two elements will be treated as
equivalent (e.g. std::set will not insert b if a is already in the set).

One nice thing about this approach is that it will let the container operate
on elements of type vector<T>, list<T>, ... provided T has a comparison
predicate: all standard containers define a comparison predicate in terms
of comparison of their elements.


On the other hand, a three-way comparison function with values in {-1,0,1}
is clearly a viable alternative. You can even provide a default defined in
terms of "<" and overloads for std::string and standard containers.


Best

Kai-Uwe Bux

 

[Angelwings]

Thank you a lot, it works perfectly.