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