Archived

This topic is now archived and is closed to further replies.

Promag

STL classes: Tree??

Recommended Posts

Hi there I want to know if there is any implemention of a class Tree (not a binary tree), and if it exists, where I can find it. Thanks, Bye

Share this post


Link to post
Share on other sites
Not in the STL, which works at a higher level of abstraction than this. Certain functionality and complexity guarantees are made, from which you choose the container that fulfils your functional requirements. The underlying representation of the container is an implementation detail. So, you need to specify your container requirements, not what underlying container representation you want.

--
1st law of programming: Any given program, when running, is obsolete.

Share this post


Link to post
Share on other sites
Let''s say I want to write GUI. A tree seems like a good way of organizing windows according to inheritance. On the other side, I need another structure (a list?) to handle the z-order. Do you think using tree is the way to go about it? Then the z-list can have just pointers (or better, handles) to data stored in the tree?

Share this post


Link to post
Share on other sites
SabreMan speaks the truth! If you want guaranteed log(n) access to elements, though, use a set or a map. If you want to trade space for time, use a hash_set or a hash_map.

Share this post


Link to post
Share on other sites
The tree is an implementational detail - the reason STL doesn''t contain a Tree class is because it''s usually poor form to think of implementing things in terms of trees. Instead, your structures link together to form a tree implicity. For example, a GUI might have a GUI Widget or Window class, and each one contains a pointer to a parent and a list of children, sorted by z-order. The overall structure is that of a tree, but you don''t need a tree class.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost ]

Share this post


Link to post
Share on other sites
I beg to differ. I can think of many areas where a generic tree that has unlimited children is useful - meshes hierachies , file directories structure, BSP(?), etc.

Such a tree class can be found at.

http://www.damtp.cam.ac.uk/user/kp229/tree/#overview

Share this post


Link to post
Share on other sites

Perhaps you should take a look at Boost (http://www.boost.org)
which has a "graph" container (a tree is a special kind
of graph). It even has its own book written for it, called,
oddly enough, The Boost Graph Library.


Premature optimizations can only slow down your project even more.

Share this post


Link to post
Share on other sites
quote:
Original post by Kylotan
I''ve never seen a directory structure that was implemented as a tree They just happen to look like one.


NTFS is implemented with a B* tree.



The world holds two classes of men -- intelligent men without religion, and religious men without intelligence. Abu''l-Ala-Al-Ma''arri (973-1057; Syrian poet)

Share this post


Link to post
Share on other sites