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"
On Friday 04 July 2003 12:37 pm, Jerry Feldman wrote:
On Fri, 4 Jul 2003 12:32:16 -0700
"Steven T. Hatton"
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"
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
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
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
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
participants (3)
-
Jerry Feldman
-
John Lamb
-
Steven T. Hatton