Recursive std::map?
I took the advice of others on this list and attempted to read Stroustrup's 'Phone Book'. I believe I've learned a lot thus far, but I'm still in the dark on many issues. It has come to pass that after learning to write the cannonical 'hello world' in a given language, my next self-inflicted pedagogical exarcise is to write some kind of recursive data structure representation of a binary tree. The simple version of the data structure is something like: struct Node { char * data; Node * left_child; Node * right_child; }; I actually created code that used something very similar to this several winters past in C++. As it turns out, I was merely writing 'C' code with some C++ I/O features added. I'm now attempting something similar using STL and real OO in C++. A good example of the kind of structure I'm trying to create would be a simple file system, or XML document tree. The basic idea is this: Node[*Node][*Node][*Node][*Node][...][*Node] | | | | ... | | | | | V | | | V Node[*Node][*Node][...][*Node] | | V Node[*Node][*Node][*Node][*Node][...][*Node] | V Node[*Node][*Node][*Node][*Node][...][*Node] V Node[*Node][*Node][*Node][*Node][...][*Node] Node[*Node][*Node][*Node][*Node][...][*Node] Each node would have it's own representative data such as name, state(e.g., expanded || collapsed, date of creation), as well as a collection of children. For various reasons I attempted to accomplish this with a std::map rather than a std::vector, or similar. A vector may actually be more tractible, and appropreate for this task. In either case, I am at a loss for how to create such a recursive tree using the STL. Does anybody understand my objective? If so, do you know of an approach to solving this problem with an STL container? I haven't finished Stroustrup's book, so I may have an good example sitting right here on my desk. Steven
in a given language, my next self-inflicted pedagogical exarcise is to write some kind of recursive data structure representation of a binary tree.
The simple version of the data structure is something like:
struct Node { char * data; Node * left_child; Node * right_child; }; A few years ago as an exercise, I wrote a template version of an AVL
On Fri, 4 Jul 2003 12:32:16 -0700 "Steven T. Hatton" <hattons@globalsymmetry.com> wrote: tree (eg. a self balancing binary tree). In my tree there are 2 classes: The outer class, avltree, and an inner node. I think the STL provides a very good basic set of useful data structures, but they may not be sufficient for some uses. My implementation did not have iterators, and I'm not sure how I would implement an iterator in a binary tree. -- Jerry Feldman <gaf@blu.org> Boston Linux and Unix user group http://www.blu.org PGP key id:C5061EA9 PGP Key fingerprint:053C 73EC 3AC1 5C44 3E14 9245 FB00 3ED5 C506 1EA9
On Friday 04 July 2003 12:37 pm, Jerry Feldman wrote:
On Fri, 4 Jul 2003 12:32:16 -0700
"Steven T. Hatton" <hattons@globalsymmetry.com> wrote:
in a given language, my next self-inflicted pedagogical exarcise is to write some kind of recursive data structure representation of a binary tree.
The simple version of the data structure is something like:
struct Node { char * data; Node * left_child; Node * right_child; };
A few years ago as an exercise, I wrote a template version of an AVL tree (eg. a self balancing binary tree). In my tree there are 2 classes: The outer class, avltree, and an inner node.
I think the STL provides a very good basic set of useful data structures, but they may not be sufficient for some uses.
I have to confess, without the ability to do some kind of recursion, I don't see where I would have much use for such a library. It looks as though there may be a solution. I am just now looking this over. This looks like a fantastic course: http://www.cs.uiowa.edu/~rlawrenc/teaching/030/Notes/
My implementation did not have iterators, and I'm not sure how I would implement an iterator in a binary tree.
I guess one could do some kind of infix, prefix or postfix traversal, or simply iterate over the children. In the case of a binary tree, that doesn't make a lot of sense. In the case of an N-ary(sic) tree, that may make more sense. Steven
On Fri, 4 Jul 2003 16:30:01 -0700 "Steven T. Hatton" <hattons@globalsymmetry.com> wrote:
I have to confess, without the ability to do some kind of recursion, I don't see where I would have much use for such a library. It looks as though there may be a solution. I am just now looking this over. This looks like a fantastic course:
http://www.cs.uiowa.edu/~rlawrenc/teaching/030/Notes/
My implementation did not have iterators, and I'm not sure how I would implement an iterator in a binary tree.
I guess one could do some kind of infix, prefix or postfix traversal, or simply iterate over the children. In the case of a binary tree, that doesn't make a lot of sense. In the case of an N-ary(sic) tree, that may make more sense. My implementation is fully recursive including both an preorder and inorder traversal. I just did not implement some of the generic algrithms and iterators. Generally, the STL contains most of the tools you need. While I don't have Rogue Wave, they have all sorts of good types, including binary trees.
The problem with the standard STL types is that they don't handle searches well, but a balanced binary tree handles insertions and searches very efficiently. (The down side is that if you do not have some kind of balancing algorithm, your tree could end up as a linked list). -- Jerry Feldman <gaf@blu.org> Boston Linux and Unix user group http://www.blu.org PGP key id:C5061EA9 PGP Key fingerprint:053C 73EC 3AC1 5C44 3E14 9245 FB00 3ED5 C506 1EA9
On Friday 04 July 2003 12:32 pm, Steven T. Hatton wrote:
I took the advice of others on this list and attempted to read Stroustrup's 'Phone Book'. I believe I've learned a lot thus far, but I'm still in the dark on many issues. [snip] Steven
Is this a problem for all attempts at recursive templates? http://www.csci.csusb.edu/dick/examples/trex.cc // template recursion // This is from the draft standard and soome articles in trade papers // However Gnu CC 2.7.0 template<int i> int fac() { return i>1 ? i*fac<i-1>() : 1; } int fac<0>() { return 1; } #include <iostream.h> int main() { cout<< fac<0>(); cout<< fac<7>(); } /* trex.cc:7: parse error before `<' trex.cc: In function `int main()': trex.cc:13: cannot resolve overloaded function `fac' based on non-function type trex.cc:13: no match for `operator <<(class _IO_ostream_withassign, {unknown typ e})' trex.cc:13: parse error before `(' trex.cc:14: cannot resolve overloaded function `fac' based on non-function type trex.cc:14: no match for `operator <<(class _IO_ostream_withassign, {unknown typ e})' trex.cc:14: parse error before `(' */
Steven T. Hatton wrote:
On Friday 04 July 2003 12:32 pm, Steven T. Hatton wrote:
I took the advice of others on this list and attempted to read Stroustrup's 'Phone Book'. I believe I've learned a lot thus far, but I'm still in the dark on many issues.
[snip]
Steven
Is this a problem for all attempts at recursive templates?
http://www.csci.csusb.edu/dick/examples/trex.cc
// template recursion // This is from the draft standard and soome articles in trade papers // However Gnu CC 2.7.0
template<int i> int fac() { return i>1 ? i*fac<i-1>() : 1; }
int fac<0>() { return 1; }
No. The code should work if you replace it with the following: template<int i> int fac() { return i > 1 ? i * fac<(i - 1) % 20>() : 1; } No need to define fac<0>. The trick here is to use % to ensure that the only values of i that fac<i> can be instantiated for are 0-19. Effectively you create a lookup table for factorials. However, there is a catch: you can only use fac with constants: i.e. the following won't even compile for( int i = 0; i < 20; ++i ){ std::cout << fac<i>( x ); } If that's the effect you want, create a real lookup table. The technique might be more useful in something like: template<int i, class T> T power( T t ) { return i > 0 ? t * power<(i - 1) % 4,T>( t ) : 1; } -- JDL Non enim propter gloriam, diuicias aut honores pugnamus set propter libertatem solummodo quam Nemo bonus nisi simul cum vita amittit.
Node[*Node][*Node][*Node][*Node][...][*Node] | | | | ... | | | | | V | | | V Node[*Node][*Node][...][*Node] | | V Node[*Node][*Node][*Node][*Node][...][*Node] | V Node[*Node][*Node][*Node][*Node][...][*Node] V Node[*Node][*Node][*Node][*Node][...][*Node] Node[*Node][*Node][*Node][*Node][...][*Node]
Each node would have it's own representative data such as name, state(e.g., expanded || collapsed, date of creation), as well as a collection of children.
For various reasons I attempted to accomplish this with a std::map rather than a std::vector, or similar. A vector may actually be more tractible, and appropreate for this task. In either case, I am at a loss for how to create such a recursive tree using the STL. Does anybody understand my objective? If so, do you know of an approach to solving this problem with an STL container?
The following will do it. I've used a list but a vector would also be fine. I've put in a couple of examples of recursive algorithms. Note that the tree need not actually be binary. #include<iostream> #include<list> class tree { public: tree( double size ){ node_size = size; } void add_node( tree* b ){ subnodes.push_back( b ); } double total_size(){ double size = node_size; for( std::list<tree*>::const_iterator i = subnodes.begin(); i != subnodes.end(); ++i ){ size += (*i)->total_size(); } return size; } double max_size(){ struct { double operator()( double x, double y ){ return x > y ? x : y; } } max; double size = node_size; for( std::list<tree*>::const_iterator i = subnodes.begin(); i != subnodes.end(); ++i ){ size = max( size, (*i)->max_size() ); } return size; } double node_size; private: std::list<tree*> subnodes; }; int main() { tree* root = new tree( 4 ); tree* node1 = new tree( 3 ); tree* node2 = new tree( 7 ); root->add_node( node1 ); root->add_node( node2 ); tree* node = node1; node1 = new tree( 2 ); node2 = new tree( 9 ); node->add_node( node1 ); node->add_node( node2 ); node = node2; node1 = new tree( 1 ); node2 = new tree( 2 ); node->add_node( node1 ); node->add_node( node2 ); std::cout << "Sum of node values = " << root->total_size() << std::endl; std::cout << "Maximum of node values = " << root->max_size() << std::endl; exit(0); } -- JDL Non enim propter gloriam, diuicias aut honores pugnamus set propter libertatem solummodo quam Nemo bonus nisi simul cum vita amittit.
participants (3)
-
Jerry Feldman -
John Lamb -
Steven T. Hatton