destructor of binary tree

[xz]

I am writing some codes to implement a binary tree, which basically
looks like:

class BTree {
BTree(BTree &); // prevent copy-construction
BTree * pRight;
BTree * pLeft;
double value;

public:
BTree(double value): value(value), pRight(0), pLeft(0) {};

void setRightBranch(BTree * pbt) {
pRight = pbt;
}

void setLeftBranch(BTree * pbt) {
pLeft = pbt;
}
// and the rest code
}

I might create instances of BTree both statically or dynamically, i.e.
both of the following two ways will be used:

BTree bTree(1.0);
or
BTree * pBTree = new BTree(1.0);

To manage the memory allocation in the dynamic creation of the
instances, I need a recursive destructor, which I would like to
implement as follows:

~BTree() {
if(pRight != 0) // not the end
delete pRight;
if(pLeft != 0) // not the end
delete pLeft;
}

This destrucotr works fine for a tree whose nodes are all created by
the new-operator, e.g.

BTree * pbt1= new BTree(1.0);
BTree * pbt2= new BTree(2.0);
BTree * pbt3= new BTree(3.0);
pbt3->setLeftBranch(pbt1);
pbt3->setRightBranch(pbt2);

delete pbt3;


However, if I have statically created tree in my program, e.g.

BTree bt1(1.0);
BTree bt2(2.0);
BTree bt3(3.0);
bt3.setLeftBranch(bt1);
bt3.setRightBranch(bt2);

At the end of the scope, the destructor of bt3 will be called and the
line "delete pRight;" and "delete pLeft;" will be carried out to the
instances, bt1and bt2, which are not created by new-operator.

I wonder how should I implement this destructor so it works for both
statically created instances and dynamically created instances.
Thanks!

 

[xz]

bt3.setLeftBranch(bt1);
bt3.setRightBranch(bt2);

Actually, I meant

bt3.setLeftBranch(&bt1);
bt3.setRightBranch(&bt2);

Sorry about the typo.

 

[xz]

Is this question too stupid to answer?

 

[Erik Wikström]

I am writing some codes to implement a binary tree, which basically
looks like:

class BTree {
BTree(BTree &); // prevent copy-construction
BTree * pRight;
BTree * pLeft;
double value;

public:
BTree(double value): value(value), pRight(0), pLeft(0) {};

void setRightBranch(BTree * pbt) {
pRight = pbt;
}

void setLeftBranch(BTree * pbt) {
pLeft = pbt;
}
// and the rest code
}

I might create instances of BTree both statically or dynamically, i.e.
both of the following two ways will be used:

BTree bTree(1.0);
or
BTree * pBTree = new BTree(1.0);

To manage the memory allocation in the dynamic creation of the
instances, I need a recursive destructor, which I would like to
implement as follows:

~BTree() {
if(pRight != 0) // not the end
delete pRight;
if(pLeft != 0) // not the end
delete pLeft;
}

This destrucotr works fine for a tree whose nodes are all created by
the new-operator, e.g.

BTree * pbt1= new BTree(1.0);
BTree * pbt2= new BTree(2.0);
BTree * pbt3= new BTree(3.0);
pbt3->setLeftBranch(pbt1);
pbt3->setRightBranch(pbt2);

delete pbt3;


However, if I have statically created tree in my program, e.g.

BTree bt1(1.0);
BTree bt2(2.0);
BTree bt3(3.0);
bt3.setLeftBranch(bt1);
bt3.setRightBranch(bt2);

At the end of the scope, the destructor of bt3 will be called and the
line "delete pRight;" and "delete pLeft;" will be carried out to the
instances, bt1and bt2, which are not created by new-operator.

I wonder how should I implement this destructor so it works for both
statically created instances and dynamically created instances.

I think you have a problem with your design, the BTree class should
probably only have an interface for operations on the whole tree.
Internally it will use some kind of node-class to build up the tree,
these nodes should be created and managed by the BTree class an
allocated on the heap (or, preferably using an allocator like the STL
containers).

 

[Charles]

I am writing some codes to implement a binary tree...
I wonder how should I implement this destructor so it works for both
statically created instances and dynamically created instances.

I'm using a binary tree in one of my programs. It may not be the best design
but each node of the tree holds a Boost shared_ptr to the terminal or
function object. That smart pointer takes care of the destruction
automatically. I don't trust myself to correctly destruct anything.

You should also investigate the Boost pointer containers.

 

[Rolf Magnus]

Is this question too stupid to answer?

Nah. You're just too impatient to wait for an answer.

 

[James Kanze]

On 2008-01-26 21:19, xz wrote:

[...]

I think you have a problem with your design, the BTree class should
probably only have an interface for operations on the whole tree.

Which doesn't necessarily solve the problem.

Internally it will use some kind of node-class to build up the tree,
these nodes should be created and managed by the BTree class an
allocated on the heap (or, preferably using an allocator like the STL
containers).

That's fine in theory, but I have a case in practice (a trie,
rather than a tree, but the problem is the same) where in some
cases, order of initialization issues mean that I need a
complete static initialization. The only solution I've found to
date is inheritance: the static instances are instances of
StaticSetOfCharacter, which also defines the const functions
(lookup, etc.). The user uses a derived class SetOfCharacter,
which adds the non-const functions and a destructor which
deletes all of the internal data. This still doesn't support
mixing of static nodes with non-static nodes, but in my case, at
least, that's almost an advantage. What's not pretty, of
course, is that the user has to be aware of the two types---if
he's not modifying data, it's not SetOfCharacter const&, it's
StaticSetOfCharacter const&. But as I said, I haven't found a
better solution.

 

[kwikius]

Is this question too stupid to answer?

No , the question of the different nature of objects on the stack and
the heap is extremely interesting and even difficult.

The fundamental difference in semantics is, of course, that stack
objects are garbage collected, but heap objects arent.

One option that would work is to query the pointer:
void f (T * p)
{
if (is_on_heap(p)){
delete p;
}
else {
/* do nothing */
}
}

One slight problem... C++ has no obvious way to define the function
is_on_heap(p). IMO it should.

Therefore IMO it is a very interesting question

regards
Andy Little

 

[Jerry Coffin]

No , the question of the different nature of objects on the stack and
the heap is extremely interesting and even difficult.

The fundamental difference in semantics is, of course, that stack
objects are garbage collected, but heap objects arent.

One option that would work is to query the pointer:
void f (T * p)
{
if (is_on_heap(p)){
delete p;
}
else {
/* do nothing */
}
}

One slight problem... C++ has no obvious way to define the function
is_on_heap(p). IMO it should.

Therefore IMO it is a very interesting question

While the standard library doesn't support it directly, the standard
allows you to replace ::new and ::delete, so you can write your own that
support them. The obvious way would be to create a set of the addresses
your ::new has returned. is_on_heap() would then look something like:

template <class T>
bool is_on_heap(T *p) {
return heap_map.find((void *)p) != heap_map.end();
}

At least at first glance, there are only two things that look tricky to
me. The first is the simple situation that even though replacing ::new
and ::delete is officially supported, it's sufficiently unusual that you
might find your code doesn't work with it. The second is that you have
to ensure heap_map doesn't use your replacement ::new to allocate its
own memory, or you'll run into infinite recursion.

 

[kwikius]

While the standard library doesn't support it directly, the standard
allows you to replace ::new and ::delete, so you can write your own that
support them. The obvious way would be to create a set of the addresses
your ::new has returned. is_on_heap() would then look something like:

template <class T>
bool is_on_heap(T *p) {
        return heap_map.find((void *)p) != heap_map.end();

}

At least at first glance, there are only two things that look tricky to
me.

Another problem is that the pointer you are looking for may be an ABC
with virtual dtor. Hence will not be found, because your allocated
pointer will be to some derived class.

There are other problems too once you get into this. p may be a
pointer to some member of a class allocated on the heap. Technically
it is on the heap but is "owned" by the class its a member of."

Its an interesting problem domain but once solved is very useful for
the internal workings of smart pointers for example ;-)

regards
Andy Little

 

[James Kanze]

While the standard library doesn't support it directly, the
standard allows you to replace ::new and ::delete, so you can
write your own that support them. The obvious way would be to
create a set of the addresses your ::new has returned.
is_on_heap() would then look something like:

template <class T>
bool is_on_heap(T *p) {
return heap_map.find((void *)p) != heap_map.end();
}

At least at first glance, there are only two things that look
tricky to me. The first is the simple situation that even
though replacing ::new and ::delete is officially supported,
it's sufficiently unusual that you might find your code
doesn't work with it. The second is that you have to ensure
heap_map doesn't use your replacement ::new to allocate its
own memory, or you'll run into infinite recursion.

The trickiest part takes place when you start dealing with
inheritance, particularly multiple or virtual inheritance. In
such cases, it's likely that the Base* given to is_on_heap
doesn't compare equal to an address :perator new() returned.
(This can be solved, of course---operator new() has to save a
range in the heap_map---, but it's not quite as simple as is
avoiding infinite recursion.)

And of course, there will always be the un-co-operative user,
who dynamically allocates an array of nodes, or placement new's
them in dynamically allocated memory, expecting to use an
explicit delete later.

 

[xz]

I'm using a binary tree in one of my programs. It may not be the best design
but each node of the tree holds a Boost shared_ptr to the terminal or
function object. That smart pointer takes care of the destruction
automatically. I don't trust myself to correctly destruct anything.

You should also investigate the Boost pointer containers.

Hi,
That's very interesting. But I have not figured out how it is
implemented.
Could you give me more details on that?
Thanks!

 

[Charles]

That's very interesting. But I have not figured out how it is
implemented.
Could you give me more details on that?

Briefly ptr_containers mimic the STL containers owning pointers to clones of
objects.

It might be best to play with an example program provided in the Boost
ptr_container library. The \boost\boost_1_34_1\libs\ptr_container\tut1.cpp
source code file is identical to the large example given in section 9 of
\boost\boost_1_34_1\libs\ptr_container\doc\examples.html. Recent
enhancements are found in the Boost SVN files.