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]

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.

 

[Travis]

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




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.

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

 

[Guest]

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


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.