Tree vs Map

[Travis]

I've created a custom Tree template. The tree mimics a menu tree and
has the following properties.
- nodes are identified by a unique name
- any node can have infinite child nodes
- nodes are not sorted so traversal is breadth first looking for the
key
- nodes are inserted by identifying the desired parent

This works out well once the tree is constructed because it actually
resembles the menu tree but as with a lot of things in programming,
that may not always be advantageous. So I'm wondering if it would
really benefit me going to something like the stl map structure?

Thanks.

[Simon Wollwage]

Re: Tree vs Map

Am Mon, 09 Jul 2007 15:37:11 +0000 schrieb Travis:

I've created a custom Tree template. The tree mimics a menu tree and has
the following properties.
- nodes are identified by a unique name - any node can have infinite
child nodes - nodes are not sorted so traversal is breadth first looking
for the key
- nodes are inserted by identifying the desired parent
>
This works out well once the tree is constructed because it actually
resembles the menu tree but as with a lot of things in programming, that
may not always be advantageous. So I'm wondering if it would really
benefit me going to something like the stl map structure?
>
Thanks.

something like this would be good if you want to use a map:

struct entry {
string caption;
entry* next;
entry* sub;
};

map<string, entry*menu;

but i recommend __gnu_cxx::hash _map for this. std::map is slow cause it
uses an AVL-Tree under it's surface.

--
/(bb|[^b]{2})/
"Microsoft - We put the bill in billionaire"

[Travis]

Re: Tree vs Map

On Jul 9, 8:55 am, Simon Wollwage <wollwagesi...@ yahoo.co.jpwrot e:

Am Mon, 09 Jul 2007 15:37:11 +0000 schrieb Travis:
>

I've created a custom Tree template. The tree mimics a menu tree and has
the following properties.
- nodes are identified by a unique name - any node can have infinite
child nodes - nodes are not sorted so traversal is breadth first looking
for the key
- nodes are inserted by identifying the desired parent

>

This works out well once the tree is constructed because it actually
resembles the menu tree but as with a lot of things in programming, that
may not always be advantageous. So I'm wondering if it would really
benefit me going to something like the stl map structure?

>

Thanks.

>
something like this would be good if you want to use a map:
>
struct entry {
string caption;
entry* next;
entry* sub;
>
};
>
map<string, entry*menu;
>
but i recommend __gnu_cxx::hash _map for this. std::map is slow cause it
uses an AVL-Tree under it's surface.
>
--
/(bb|[^b]{2})/
"Microsoft - We put the bill in billionaire"

Then I might just stick with my current custom tree. The nice thing
about it is once it's created, traversal is very efficient. I'm either
going to the children or the too the parent which are already known
and don't require searching. Insertion (only done at initialization of
the program) might be costly though. Hmmmm

[=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=]

Re: Tree vs Map

On 2007-07-09 17:55, Simon Wollwage wrote:

Am Mon, 09 Jul 2007 15:37:11 +0000 schrieb Travis:
>

>I've created a custom Tree template. The tree mimics a menu tree and has
>the following properties.
>- nodes are identified by a unique name - any node can have infinite
>child nodes - nodes are not sorted so traversal is breadth first looking
>for the key
>- nodes are inserted by identifying the desired parent
>>
>This works out well once the tree is constructed because it actually
>resembles the menu tree but as with a lot of things in programming, that
>may not always be advantageous. So I'm wondering if it would really
>benefit me going to something like the stl map structure?
>>
>Thanks.

>
something like this would be good if you want to use a map:
>
struct entry {
string caption;
entry* next;
entry* sub;
};
>
map<string, entry*menu;
>
but i recommend __gnu_cxx::hash _map for this. std::map is slow cause it
uses an AVL-Tree under it's surface.

No, more likely a red-black tree. An as to the speed, for the usage that
the OP has it would probably not be noticeable even if searches were linear.

--
Erik Wikström