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]

Travis wrote:

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.

<blank stare>

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

<blank stare>

>
Any suggestions, solutions?

I believe it's covered in FAQ 5.8.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[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]

Travis wrote:

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]

Travis wrote:

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

[Kai-Uwe Bux]

Travis wrote:

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

[Obnoxious User]

On Fri, 29 Jun 2007 13:36:57 -0700, Travis wrote:

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*, sms;

--
Obnoxious User

[Mark P]

Travis wrote:

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
Travis wrote:

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?