Tree of pointers

[Travis]

I have a tree of pointers and I need the ability to search the tree
for a specific node. The problem is I can't provide that pointer for
the node I'm looking for as criteria. The only critieria I can provide
is a node that is the same and will == true.

So naturally this would work if my tree was not of pointers but of
objects. Since it's of pointers, it compares my node criteria against
every node in the tree and the memory addresses aren't the same so
it's not found.

If I force the tree to deference the node before comparing it works
but then what if my tree was of objects, not pointers, dereferencing
and object would blow up right?

Any suggestions, solutions?

 

[Victor Bazarov]

I have a tree

Did you write it yourself or did you use some third-party library?

of pointers and I need the ability to search the tree
for a specific node. The problem is I can't provide that pointer for
the node I'm looking for as criteria. The only critieria I can provide
is a node that is the same and will == true.

So naturally this would work if my tree was not of pointers but of
objects. Since it's of pointers, it compares my node criteria against
every node in the tree and the memory addresses aren't the same so
it's not found.

Pardon me... WHO compares?

If I force the tree to deference the node before comparing it works
but then what if my tree was of objects, not pointers, dereferencing
and object would blow up right?

Any suggestions, solutions?

I believe it's covered in FAQ 5.8.

V

 

[Marcus Kwok]

I have a tree of pointers and I need the ability to search the tree
for a specific node. The problem is I can't provide that pointer for
the node I'm looking for as criteria. The only critieria I can provide
is a node that is the same and will == true.

So naturally this would work if my tree was not of pointers but of
objects. Since it's of pointers, it compares my node criteria against
every node in the tree and the memory addresses aren't the same so
it's not found.

If I force the tree to deference the node before comparing it works
but then what if my tree was of objects, not pointers, dereferencing
and object would blow up right?

If you have a tree of pointers, then you should not be able to put
objects in it, so dereferencing in order to compare should be OK
(assuming you have appropriate checks for NULL, etc.).

If the tree is templated so that you can store either objects or
pointers in it (but not at the same time in the same tree), then perhaps
you could follow the way the Standard Library does and provide an
additional template parameter for the comparison function to use.

 

[Travis]

It's a tree that I wrote.

The tree is templated and can store anything of NODETYPE.

When I instantiate the tree, I make each node a pointer to my custom
class.

In my custom class I have == overloaded.

When I do a search for a node I provide it a NODETYPE to find.

It doesn't find it because even though the NODETYPE I provide as
search criteria is the same as a node in the tree, they aren't
occupying the same memory so the == operator never goes true. I have
to dereference int the NODETYPE and it works fine.

My concern is the reusabilty of the tree. If someone else comes along
and makes NODETYPE some object (not a pointer), then the dereferencing
in my find routine will bomb right?

Can you elaborate a little more on how the STL handles this?

 

[John Harrison]

It's a tree that I wrote.

The tree is templated and can store anything of NODETYPE.

When I instantiate the tree, I make each node a pointer to my custom
class.

In my custom class I have == overloaded.

When I do a search for a node I provide it a NODETYPE to find.

It doesn't find it because even though the NODETYPE I provide as
search criteria is the same as a node in the tree, they aren't
occupying the same memory so the == operator never goes true. I have
to dereference int the NODETYPE and it works fine.

My concern is the reusabilty of the tree. If someone else comes along
and makes NODETYPE some object (not a pointer), then the dereferencing
in my find routine will bomb right?

Can you elaborate a little more on how the STL handles this?

The moral is don't store pointers in your tree. Store NODETYPE objects
instead.

An STL container that stored pointers would have exactly the same issues.

john

 

[Fei Liu]

I have a tree of pointers and I need the ability to search the tree
for a specific node. The problem is I can't provide that pointer for
the node I'm looking for as criteria. The only critieria I can provide
is a node that is the same and will == true.

So naturally this would work if my tree was not of pointers but of
objects. Since it's of pointers, it compares my node criteria against
every node in the tree and the memory addresses aren't the same so
it's not found.

If I force the tree to deference the node before comparing it works
but then what if my tree was of objects, not pointers, dereferencing
and object would blow up right?

Any suggestions, solutions?

If you are implementing a binary search tree, then don't do it at all
because the STL set and map containers are tree based. Just use set or
map for your container needs.

If you are implementing arbitrary tree structure, I'd suggest you check
boost::graph because a tree is a graph with a root note and leaves...

If you insist on implementing a tree as an exercise, do some research
how STL implements set and map. It'll help a lot.

Fei

 

[Obnoxious User]

It's a tree that I wrote.

The tree is templated and can store anything of NODETYPE.

When I instantiate the tree, I make each node a pointer to my custom
class.

In my custom class I have == overloaded.

When I do a search for a node I provide it a NODETYPE to find.

It doesn't find it because even though the NODETYPE I provide as
search criteria is the same as a node in the tree, they aren't
occupying the same memory so the == operator never goes true. I have
to dereference int the NODETYPE and it works fine.

Perhaps the 'someone else' mentioned below actually wants that kind of
behaviour, ie address comparison.

My concern is the reusabilty of the tree. If someone else comes along
and makes NODETYPE some object (not a pointer), then the dereferencing
in my find routine will bomb right?

Can you elaborate a little more on how the STL handles this?

std::set<int*> m;

The default comparison for 'm' will also only compare addresses.
I need to provide my own comparison operator if I want something else.

struct s {
bool operator()(int * a, int * b) {
return a[5] < b[5];
}
};
std::set<int*, s> ms;

 

[Kai-Uwe Bux]

It's a tree that I wrote.

The tree is templated and can store anything of NODETYPE.

When I instantiate the tree, I make each node a pointer to my custom
class.

In my custom class I have == overloaded.

When I do a search for a node I provide it a NODETYPE to find.

It doesn't find it because even though the NODETYPE I provide as
search criteria is the same as a node in the tree, they aren't
occupying the same memory so the == operator never goes true. I have
to dereference int the NODETYPE and it works fine.

My concern is the reusabilty of the tree. If someone else comes along
and makes NODETYPE some object (not a pointer), then the dereferencing
in my find routine will bomb right?

Can you elaborate a little more on how the STL handles this?

One way of going about this, is to define the nodes in terms of the template
parameter. E.g.:


template < typename T >
struct tree {

typedef T value_type;

private:

struct tree_node {

value_type the_value;
tree_node * the_parent;
tree_node * the_first_child;
tree_node * the_next_sibling;
tree_node * the_prev_sibling;

};

tree_node * the_root_node;

// more stuff


}; // tree


Best

Kai-Uwe Bux

 

[Mark P]

I have a tree of pointers and I need the ability to search the tree
for a specific node. The problem is I can't provide that pointer for
the node I'm looking for as criteria. The only critieria I can provide
is a node that is the same and will == true.

So naturally this would work if my tree was not of pointers but of
objects. Since it's of pointers, it compares my node criteria against
every node in the tree and the memory addresses aren't the same so
it's not found.

If I force the tree to deference the node before comparing it works
but then what if my tree was of objects, not pointers, dereferencing
and object would blow up right?

Any suggestions, solutions?

You'll do much better in this newsgroup if you ask clear and precise
questions. Read over your first paragraph, pretend you don't already
know the problem you're asking about, and see if it makes any sense to you.

As to your question, as best as I can understand it. First of all, as
others have pointed out, you seem to be reinventing the wheel. The STL
has set and map classes which likely do what you're doing, only much
better. If you insist upon making your own class, then at least look at
the design choices made in the STL and see how you can use those for
yourself. For example, the set and map classes use a template parameter
to specify how comparisons are performed. By default, operator< is
used, but if that is not sufficient, the user may specify their own
function.

Mark

 

[Ron Fox]

Your search function must allow as a parameter
a 'predicate' function or function object that
determines what 'finding' means...rather than using
operator==.

This is fairly common in e.g. STL containers
and used by the STL find_if, etc....

This allows the guy calling the search function
to determine what it means to find an item in the
tree and makes your searching not only possible but
much more flexible.

If it were me I'd probably be using an STL set
instead of rolling my own templated tree.


Ron