Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > BST with polymorphic data

Reply
Thread Tools

BST with polymorphic data

 
 
Angelwings
Guest
Posts: n/a
 
      11-17-2007
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.
 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      11-17-2007
Angelwings wrote:

> 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
 
Reply With Quote
 
 
 
 
Angelwings
Guest
Posts: n/a
 
      11-18-2007
> 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.
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      11-18-2007
Angelwings wrote:

>> 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
 
Reply With Quote
 
Angelwings
Guest
Posts: n/a
 
      11-18-2007

> 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!
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      11-18-2007
Angelwings wrote:

>
>> 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.


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
 
Reply With Quote
 
Angelwings
Guest
Posts: n/a
 
      11-19-2007
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?
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      11-19-2007
Angelwings wrote:

> 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
 
Reply With Quote
 
Angelwings
Guest
Posts: n/a
 
      11-20-2007
Thank you a lot, it works perfectly.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
LL TO BST puzzlecracker C++ 2 01-19-2005 11:10 PM
Applications of stacks/queues/trees/heap/BST Ice C++ 4 12-19-2004 06:04 PM
BST: remove less than Ridimz C++ 8 10-07-2003 01:40 AM
BST Rupert harrison C++ 2 09-15-2003 08:38 AM
BST & recursion Andrew Edwards C++ 12 08-04-2003 10:54 AM



Advertisments