 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| C Trees Part 2: Basic core::treeFunctionality |
|
 |
AndyTX Member since: 7/9/2001 From: Waterloo, Canada |
|||
 Posted - 4/17/2005 7:05:29 PM |
||||
| Gotta say - these tree articles and implementation are extremely well done, and very fitting with the style of the rest of the STL (which is a good thing). Thank you very much! |
||||
|
||||
|
djbuzzkill Member since: 4/17/2005 From: Los Angeles, CA, United States |
|||
|
Posted - 4/18/2005 12:21:43 AM |
||||
| Not bad. However, one nitpick i have is implementing functions in the iterators. The role of iterators in c++ is to abstract the concept of pointer manipulation. once you start adding functions like 'push_back' it clutters up the role the object. This was pointed out in Andrei Alexandrescu's Modern C++ Design and I thought it made sense. That and the fact that there is also the function duplicated in the tree<> iteself. </ $0.02> |
||||
|
||||
|
jgottschlich Member since: 1/18/2005 From: USA |
|||
 Posted - 4/18/2005 3:19:13 AM |
||||
| Thanks for the feedback. Actually djbuzzkill, the role of the iterator changes based on what it's trying to achieve. A common example of this is the concept of an iterator adaptor. An iterator adaptor is an iterator that does more than just iterate - thus the "adapting" part. As explained by Josuttis in his "C++ Standard Library" book, there are several kinds of iterator adaptors, one such is an insert iterator. My tree<>::iterator acts much like an insert iterator adaptor - except it's really more than that. I share your concern about duplicate code in the tree<> and the iterator. Thankfully, the iterator just wraps the tree's calls so casts are unnecessary. So using the iterator is natural and doesn't cause programmer errors by incorrect casting mechanisms. Most of the tree based iterator API calls are simply a messaging system into the tree to prevent programmer error with C or C++ style casts that are unnecessary. So don't worry - no duplicated code is done within the iterator that's already done within the tree - it's just a wrapper. Thanks for reading and sharing your feedback, =) Justin |
||||
|
||||
|
arBmind Member since: 4/24/2005 From: Dresden, Germany |
|||
|
Posted - 4/24/2005 8:18:53 AM |
||||
| jgottschlich, your article is well written. No tree<> implementation will satisfy all needs. The most conflicting questions: - an iteration between tree<>::begin() and tree<>::end() should iterate over all nodes in the tree or should they iterate only the next level ? - should each node be a tree for himself, or is it better to get a host-container and treat the nodes as parts of the container ? - should a dereferencing of the iterator give a tree-node or the userdefined data ? Each question can be answered different in some situations. For me personally, i would not like to follow your decisions. For a general stl-like-container you missed some important concepts, even thou not all stl-container concept can be applied to a tree<> implementation. |
||||
|
||||
|
jgottschlich Member since: 1/18/2005 From: USA |
|||
|
Posted - 4/25/2005 7:25:18 PM |
||||
| Hi arBmind - Thanks for the feedback. begin() starts at the beginning of each level and end() signifies the end of that level - this is explained in the API section. It's easy to do full tree iteration using this philosophy. However, doing single level iteration without using this implementation is much harder and more clumsy. It's implemented in this manner to accommodate the most "easy to use" layout for both methodologies. As explained in the article, each tree is a node in the tree and vice versa, much like how trees normally behave. Knuth argues this as the "correct" way to think of trees and who am I to argue with Dr. Knuth? =) Additionally, deferencing an iterator is like dereferencing a node, so it returns the data - I actually used this as one of the examples (maybe you missed that part). As iterators are trees, as explained in the first section, dereferencing an iterator can't return anything other than the data. I do concur that creating a generic tree is a hard thing to do, but I'm not sure which part of your concerns are valid here. Perhaps you can clarify? Whatever the case, thanks for the feedback. Justin |
||||
|
||||
|
arBmind Member since: 4/24/2005 From: Dresden, Germany |
|||
|
Posted - 4/26/2005 5:31:48 PM |
||||
| I fully understand how your tree<>-Implementation works. And I think there are good reasons to do it just like that. To argue that Knuth has defined how to understand a tree is a bit far off. I respect what Mr. Knuth has done. But why should i stop using my brain? just, not to conflict with his ideas? Ok, lets make some nails with heads, without conflicting the idea of Knuth you mentioned. How do you think about the following code (refering to your last sample with the numbers.) tree_container<int> tree; tree<int> node; node = tree.push_back(1); node = node.push_back(2); node.push_back(4); node.push_back(5); node.push_back(6); node = tree.root().push_back(3); node.push_back(7); node.push_back(8); node.push_back(9); That way all nodes are a tree<>-implementation, as you wish it. The difference is just, that there is a tree_container, which manages the memory for the whole tree. Now imagine using tree_container<>.begin() and tree_container<>.end() to iterate over all the node-items in the whole tree. Now it makes sense to say, that tree<>.begin() and tree<>.end() just iterates over the direct descendants of the tree<>-node. I hope you understand what i mean. It's not that your implementation is better or worse, but there are a whole lot of possiblities to implement a tree. |
||||
|
||||
|
jgottschlich Member since: 1/18/2005 From: USA |
|||
|
Posted - 4/29/2005 2:48:09 AM |
||||
| Hi arBmind - Thanks for the further insight and response. I was only half-way serious about Knuth, I couldn't agree with you more about continuing to question things. =) Additionally, thanks for explaining your points further - I see what you mean and there's definitely merit to the concepts your referring to. =) Cheers, Justin |
||||
|
||||
|
AlessandroASQ Member since: 6/15/2005 From: Brasilia, Brazil |
|||
 Posted - 6/15/2005 11:52:09 AM |
||||
| Justin Gottschlich, I'am brazilian, and my English is not good. I use its library under Windows and functions perfectly, but under Linux it does not compile. You have any suggestion... Errors: /home/osx/cdrview/src/serv/comum/Listas/tree.h:804: ISO C++ forbids declaration of `iterator' with no type /home/osx/cdrview/src/serv/comum/Listas/tree.h:804: parse error before `&' token /home/osx/cdrview/src/serv/comum/Listas/tree.h:809: ISO C++ forbids defining types within return type /home/osx/cdrview/src/serv/comum/Listas/tree.h:809: declaration of template ` template<class T> tree_iterator tree_iterator()' /home/osx/cdrview/src/serv/comum/Listas/tree.h:35: conflicts with previous declaration `template<class T> class tree_iterator' /home/osx/cdrview/src/serv/comum/Listas/tree.h:35: previous non-function declaration `template<class T> class tree_iterator' /home/osx/cdrview/src/serv/comum/Listas/tree.h:809: conflicts with function declaration `template<class T> tree_iterator tree_iterator()' /home/osx/cdrview/src/serv/comum/Listas/tree.h: In function `tree_iterator<T> tree_iterator()': /home/osx/cdrview/src/serv/comum/Listas/tree.h:809: only constructors take base initializers /home/osx/cdrview/src/serv/comum/Listas/tree.h: At global scope: /home/osx/cdrview/src/serv/comum/Listas/tree.h:814: parse error before `&' token /home/osx/cdrview/src/serv/comum/Listas/tree.h:814: ISO C++ forbids declaration of `tree_iterator' with no type /home/osx/cdrview/src/serv/comum/Listas/tree.h: In function `int tree_iterator(...)': /home/osx/cdrview/src/serv/comum/Listas/tree.h:814: `int tree_iterator(...)' redeclared as different kind of symbol /home/osx/cdrview/src/serv/comum/Listas/tree.h:35: previous declaration of ` template<class T> class tree_iterator' /home/osx/cdrview/src/serv/comum/Listas/tree.h:35: previous non-function declaration `template<class T> class tree_iterator' /home/osx/cdrview/src/serv/comum/Listas/tree.h:814: conflicts with function declaration `int tree_iterator(...)' /home/osx/cdrview/src/serv/comum/Listas/tree.h:814: `i' undeclared (first use this function) /home/osx/cdrview/src/serv/comum/Listas/tree.h:814: (Each undeclared identifier is reported only once for each function it appears in.) /home/osx/cdrview/src/serv/comum/Listas/tree.h:814: only constructors take base initializers /home/osx/cdrview/src/serv/comum/Listas/tree.h:814: confused by earlier errors, bailing out |
||||
|
||||
|
Daniel Miller Member since: 12/19/2004 From: Austin, TX, United States |
|||
|
Posted - 6/15/2005 11:56:56 AM |
||||
| This will be a good read, considering I am implimenting trees right now in C#. Actually, please stop writing interesting articles, so I won't have spend time reading them!  |
||||
|
||||
|
T1Oracle Member since: 8/18/2005 From: District Heights |
|||
|
Posted - 10/25/2005 1:31:03 AM |
||||
| This looks very interesting although I have a few questions. How are child nodes contained in the tree? Are they in a vector or array, or are they in a linked list? From what I see it seems that your tree's are n-trees (not sure if that's a standard term) that allow for a varying amount of child nodes on each node in the tree. I have been planning on writting my own n-tree template and a template for something I call an xtree (I believe I read that exact term for this before) which is a generic tree that has a set number X child nodes per node where X is set on construction. My xtree could be defined as a binary tree, a quad tree, an oct tree, or any other variation in between through templating. Anyway, I also have another question, what about custom allocators? I have yet to implementing any, but from your code that feature seems to be overlooked. It does look like good work though. |
||||
|
||||
|
AlessandroASQ Member since: 6/15/2005 From: Brasilia, Brazil |
|||
|
Posted - 1/19/2006 12:00:39 PM |
||||
Quote: Hi,,, After 5 months,, I came back to need to compile this "tree.h" in my work. I discovered that the problem is related to the namespace. If I use "using namespace std;" before "#include 'tree.h'",,, dont work. But, if I use "using namespace std;" after "#include 'tree.h'",,, then compile. Any have a solution??? thks. |
||||
|
||||
|
John V Member since: 12/27/2006 From: Germantown, MD, United States |
|||
|
Posted - 12/27/2006 4:56:39 AM |
||||
| When I tried to compile the template multitree with dev-c++ 4.9.9.2, a number of lines, including the following line in class multitree_iterator, produced the same compilation error. static const iterator& end_iterator() { return end_of_iterator; } The error is ISO C++ forbids declaration of `iterator' with no type This may be related to class iterator not being visible at this point and also to end_of_iterator being of type multitree_iterator. One solution is to insert the following typedef before the line typedef multitree_iterator iterator; |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
