 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| C++ Trees Part 1 |
|
 |
Ainokea Member since: 3/15/2004 From: Keaau, HI, United States |
|||
 Posted - 1/16/2005 11:15:24 PM |
||||
| Good article and good timing. Just yesterday I went to look in the STL docs to find a tree container only to learn there is none! ______________________________________________________________________________________ With the flesh of a cow. |
||||
|
||||
|
crupp Member since: 7/12/2003 From: Germany |
|||
 Posted - 1/17/2005 5:13:18 AM |
||||
| For me, everybody who's able to write an error-free tree class is a guru. Especially the delete()-operations are incredibly tricky, if you have a balanced tree. Right now i am fighting with a B-Tree implementation, just for fun. it's a small database library which i have started for the third time now because i never managed to get the B-Tree correct... |
||||
|
||||
|
JohnBolton Member since: 4/3/2002 From: Belmont, CA, United States |
|||
|
Posted - 1/17/2005 8:50:25 PM |
||||
| No reasonable person would implement a tree class using std::map. The fact that std::map is implemented using a tree does not make it suitable for implementing a tree class. I think your article could be improved by removing the part about implementing a tree class using std::map. I don't think there is a lot of use for a generic tree class. There are many different kinds of trees and each has its pros and cons, and the best choice of tree depends on the application. There is no tree implementation that is sufficient for all applications. My guess is that these are the reasons there is no tree class in STL. Perhaps the better solution is to have a "tree" paradigm (much like the "container" paradigm), and then have a family of tree classes that implement the paradigm (much like vector, list, map, etc. implement containers). Your core::tree could evolve into the "tree" specification, rather than being an implementation itself. Finally, consider submitting your tree class for inclusion in the boost library. |
||||
|
||||
 |
Fruny Moderator Member since: 11/16/2001 From: Paris, France |
|||
 Posted - 1/18/2005 10:51:18 AM |
||||
| Like JohnBolton, I am speechless when I see your implementation of a tree using a map... I would never do that. As you correctly pointed out, that's not what is it for... so why use it as your motivating example? I mean, I follow the same path to justify using a C array over your core::tree<> when I need a finite amount of storage... And regarding your comment about the "extra integer" in the map ... that's what the set class template is for. I'm not attacking your tree class design (yet  ) - though the remark "core::trees<> are core::tree<>::iterators." has me a bit worried (particularly regarding a sane implementation of preincrement) - but such a contrived example, and the fact that you don't even explain how you arrived to that design using a map casts doubt on the quality of your core::tree design and implementation.JohnBolton - how about boost::graph? A tree is a special case of a graph. |
||||
|
||||
|
jgottschlich Member since: 1/18/2005 From: USA |
|||
 Posted - 1/18/2005 7:07:52 PM |
||||
| Hi there everybody - Thanks for the great feedback! Below, I've tried to address some of your well made points: 1. I understand that in your software development experience you may not have seen a tree implementation using std::maps. However, in my experience, I've seen it done by numerous programmers (extremely talented programmers too) in all the development environments I've been in. I've only worked for three different software companies, but each company has had various people implementing trees using maps. Ouch! Since it seemed like a reoccurring theme to me (in my personal experience), I thought I'd address the tree implementation with std::map right off the bat. =) Additionally, I do see why these programmers use the std::map implementation to generate trees (which is another reason I included it). Their tree implementations use an STL container and it only requires a minor amount of tweaking to turn it into a tree. Using any other standard container to create a tree would require more work to do the same thing. However, as we all agree, the drawbacks of this implementation are really severe. =) 2. The great thing about the core::tree implementation is it allows you to create any kind of tree you want; binary trees, balance binary trees, 2-3-4 trees, red/black trees, etc. And sometimes, you really do just want a tree that's formed external (i.e. XML trees, AI decision trees) that doesn't internally "hork" your inserts for balancing and what not. Instead, you want the tree built to preserve the external tree __exactly__ the way its formed externally. Reordering the tree would break the tree integrity. A great example of this are basic decision trees - reordering for balance would break the tree because each decision leads to a specific outcome that must follow its parent. =) In my game, Nodeka, I use trees for this reason a good deal (all my AI stuff uses the core::tree family this way). I'm really excited to show you the second article for the core::trees which will explain just how cool it is to have a generic tree that allows you to use it in a various number of ways based on your individual situation. I don't want to give too much away though, so I'll zip it for now. =) 3. As for using a std::set to save the wasted integer, that's a great idea. But you'd have some difficulty making that work since you wouldn't be able to generate a tree from a set directly. You could modify the set though, for example, by making it a std::set< std::pair<> >. In which case, it'd require you to re-introduced the wasted integer. =( Unless there's something I'm missing (which is always a possibility, hehe). Thanks for the great feedback! I appreciate your comments and hope that my response clarifies some of the points that weren't clear enough in the first article. My apologies for being vague in certain parts and hopefully, the second article will be more clear. =) Talk to you soon! Justin |
||||
|
||||
|
Seriema Member since: 6/15/2001 From: Stockholm, Sweden |
|||
 Posted - 1/19/2005 6:55:40 AM |
||||
| Although core::tree<> seems to be nice and all I still would've prefered you NOT listing the code for implementing a tree with map. If you have encountered that several times you can just mention that it's a bad idea, and some points why. Reading all that useless code just... blah :/ the code COULD be downloaded in the end, but still unnecessary. I think the article presents a good library. But in a way the article seems misdirected somehow? =/ [ ThumbView: Adds thumbnail support for DDS, PCX, TGA and 16 other imagetypes for Windows XP Explorer. ] [ Chocolate peanuts: Brazilian recipe for home made chocolate covered peanuts. Pure coding pleasure. ] |
||||
|
||||
|
rootrott Member since: 3/12/2003 |
|||
|
Posted - 1/20/2005 9:03:10 AM |
||||
| I believe one of the STL implementations has a rb tree, and perhaps another. I forget if it was STLport or what... I believe they use the trees as a basis for some of the other data structures. Seth |
||||
|
||||
|
TheMummy Member since: 11/1/1999 From: Gerzen, Germany |
|||
 Posted - 1/23/2005 6:40:02 AM |
||||
| I just want to point out that there is a paper about writing a tree skeleton that is able to reflect much of the diversity of tree types. "Matt Austern, Bjarne Stroustrup, Mikkel Thorup, and John Wilkinson: Untangling the Balancing and Searching of Balanced Binary Search Trees. Software - Practice & Experience. Vol 33, Issue13. October 2003." The source code appendix is available here: http://parasol.tamu.edu/archive/2003/bintree-appendix.pdf It uses policy classes to create lots of different tree types. I recently saw a different approach that implements features like, avl or red_back balancing, k-ary node types or selection of subtrees using mutators. These mutators are recuring templates that are composed in a linear inheritance hierarchy, each of them mutating different aspects of the base class, or the node type. Hard to read, if you try to look in the source, but verry comfortable to use. |
||||
|
||||
|
johdex Member since: 1/12/2005 From: Stockholm, Sweden |
|||
|
Posted - 1/24/2005 5:24:44 PM |
||||
| Hi, IMHO an important thing to realize about trees is that they typically have two kinds of uses: - explicit, when used e.g. for decision trees - implicit, when used to implement sets optimized for search. The second kind of use is already pretty well covered by the STL (set<>, and map<>). I have no doubt that your design may be interesting in the explicit case, but you have not yet convinced me it is suitable for implicit uses. More concretely, these are the things I disliked in your article: - Your sample implementation of trees using maps is rather confusing (for the reasons mentioned in the posts above). My personal experience in teaching tells me it is often a bad idea to show the wrong way of doing things to your students, especially if they had not yet thought of it (it will just confuse them) - I don't understand the notion of a tree of leaves ("core::tree<Leaf>"). Don't all trees have leaves??? I would have expected that the template parameter would be used for the type of values stored in internal nodes and leaves, e.g. core::tree<int>. Now that I am writing, I realize you may even need two parameters: one for the nodes, one for the leaves. An arithmetic expression of the form A+B*C could then be represented using a tree<ArithOperation, Identifier>. What's the template parameter used for in your case? I could figure that out reading your code, but it should be obvious from the text. - A tree iterator is itself a tree? I don't like this idea. This idea is often used for linked lists, because the typical C implementation of a list uses the same structure for (1) the head of the list (which is identifiable to the list itself), (2) for each element (node) of the list and (3) for iterators. However, I really don't think that conceptually, (1) is the same as (2) and (3). The same argument goes for trees. A list<T>::iterator is not a list<T>, and I think that's right. - While I was writing the sentence above, I realized that your point of view makes sense if you consider that you iterate over the sub-trees of a tree, instead of iterating over its nodes. I hope I do not sound too harsh, that is really not my intent. -- Top10 Racing Simulation needs more developers! http://www.top10-racing.org |
||||
|
||||
|
mstorer Member since: 7/8/2003 From: Vista, USA |
|||
|
Posted - 5/18/2005 7:29:14 PM |
||||
| Not sure where to begin. The map->tree implementation you gave is pretty messed up if ya ask me (though you didn't). "Straw Man" argument and all that. 1) If you're going to use consecutively numbered nodes, why not just use a vector? You wouldn't have any wasted 'int's laying around. 2) inserting something and then finding it is Bad STL. "insert()" returns a pair<iterator,bool>. The iterator points to what was just inserted and the bool is... something else. IIRC, true means it replaced an existing value. All your "insert(blah); iter = find(blah);" can be replaced (much more efficently) with "iter = insert(blah).first;". This of course begs the question of why you're maintaining the iter at all, but I'm assuming you'd explain it later. I kinda turned my nose up at your article when I saw Bad STL as a justification for a roll-your-own class heirarchy. 3) Check out "Design Patterns". Specifically, the "Composite". It suggests that leaves and nodes should be treated uniformly whenever possible, having a "composite" derived from "leaf". Leaves has various operations that can be performed on them, and composites perform those operations on all their children (which may be leaves or more composites, doesn't matter). 4) Check out boost::graph 5) None the less, a red-black tree available To The Masses would be a Very Good Thing. |
||||
|
||||
|
jgottschlich Member since: 1/18/2005 From: USA |
|||
 Posted - 7/13/2005 3:41:05 AM |
||||
| Actually, the insert does return an iterator: iterator insert(const T &inT, bool (*pObj)(const T&, const T&)) { tree *createdTree = new tree(inT); if (NULL == createdTree) throw "allocation failed"; return iterator(i_insert(createdTree, this, pObj)); } The reason why I separated out the insert and find into two separate lines of code is to make it more clear what exactly is going on (and how to use the API) to programmers less familiar with STL. The header is attached to this article, had you referenced it you would have seen the interface of insert returning an iterator. =) Cheers, Justin |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
