BST with polymorphic data

Discussion in 'C++' started by Angelwings, Nov 17, 2007.

  1. Angelwings

    Angelwings Guest

    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.
    Angelwings, Nov 17, 2007
    #1
    1. Advertising

  2. Angelwings

    Kai-Uwe Bux Guest

    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
    Kai-Uwe Bux, Nov 17, 2007
    #2
    1. Advertising

  3. Angelwings

    Angelwings Guest

    > 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.
    Angelwings, Nov 18, 2007
    #3
  4. Angelwings

    Kai-Uwe Bux Guest

    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
    Kai-Uwe Bux, Nov 18, 2007
    #4
  5. Angelwings

    Angelwings Guest


    > 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!
    Angelwings, Nov 18, 2007
    #5
  6. Angelwings

    Kai-Uwe Bux Guest

    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
    Kai-Uwe Bux, Nov 18, 2007
    #6
  7. Angelwings

    Angelwings Guest

    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?
    Angelwings, Nov 19, 2007
    #7
  8. Angelwings

    Kai-Uwe Bux Guest

    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
    Kai-Uwe Bux, Nov 19, 2007
    #8
  9. Angelwings

    Angelwings Guest

    Thank you a lot, it works perfectly.
    Angelwings, Nov 20, 2007
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andrew Edwards

    BST & recursion

    Andrew Edwards, Jul 30, 2003, in forum: C++
    Replies:
    12
    Views:
    760
    Karl Heinz Buchegger
    Aug 4, 2003
  2. Rupert harrison

    BST

    Rupert harrison, Sep 15, 2003, in forum: C++
    Replies:
    2
    Views:
    544
    Karl Heinz Buchegger
    Sep 15, 2003
  3. Ridimz

    BST: remove less than

    Ridimz, Oct 4, 2003, in forum: C++
    Replies:
    8
    Views:
    521
    Josh Sebastian
    Oct 7, 2003
  4. Ice
    Replies:
    4
    Views:
    4,996
  5. puzzlecracker

    LL TO BST

    puzzlecracker, Jan 19, 2005, in forum: C++
    Replies:
    2
    Views:
    385
    Joseph Turian
    Jan 19, 2005
Loading...

Share This Page