Hierarchy container?

This is a discussion on Hierarchy container? within the C++ Programming forums, part of the General Programming Boards category; Is there any container class that can arrange objects into a hierarchy, in such a way that each object in ...

  1. #1
    Registered User
    Join Date
    Aug 2004
    Posts
    11

    Hierarchy container?

    Is there any container class that can arrange objects into a hierarchy, in such a way that each object in the hierarchy knows that's above it, what's below it, what's next to it, etc?

    Thanks,
    wannaB_geek

  2. #2
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    Binary Tree comes to mind.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  3. #3
    Registered User
    Join Date
    Aug 2004
    Posts
    11
    A binary tree just puts objects into a hierarchy for accessibility purposes. What I need is a container that allows you to create a specific hierarchy, more like an org-chart type of hierarchy.

    Does anyone know of such a container class exists?

    Thanks,
    wannaB_geek

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    As a standard container in STL or C/C++, probably not. Has anybody ever made such a container, maybe. Could you make such a container? Depends on your skill level. If you can't, your chances of getting good advice/assistance are excellent if you can describe exactly what you want, and demonstrate a good faith effort on your part. I suspect it will be some sort of a tree, though. Maybe with nodes like this:

    struct Node
    {
    string title;
    list<Node *> underlings;
    }

  5. #5
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    A tree is perhaps not general enough. If I had time, I might elaborate a bit on a type of structure you seem to be looking for, but for now, I'll just point you toward a term to search for: directed acyclic graph or DAG. Essentially, you have nodes, and you have uni-directional connections between nodes. There are a host of algorithms you can use to find properties or search them. The book Introduction to Algorithms by Rivest et al has some bits about graph algorithms, though there are certainly other (less pricey) places to get the information. There is a book published by Dover called Graph Theory on the subject of graphs. More theoretical and less practical, but, being a Dover book, it is rather affordable.

    Cheers
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  6. #6
    Registered User
    Join Date
    Aug 2004
    Posts
    11
    Here's a rough framework of what I'm trying to do:

    The tree class would provide the structure for the hierarchy, in addition to pointers to relatives. It would function somewhat like a forking linked list.

    Code:
    template <T>
    
    class Tree <T> {
      T myObject;   // the object at the current level
      Tree<T>* parent;   // the parent object
      /* sorry, I'm kinda new at this.  Is the correct syntax for a pointer
       * to a container Tree<T>* or Tree*<T> ? */
      std::vector<Tree<T>*> children;    // the child objects
      std::vector<Tree<T>>::iterator sibling;
       /*  The sibling iterator should point to the first object in the
        *   parent tree's child vector */
      Tree<T>* top;
      freind T;  // is this legal?
      // friend Leaf<T> // if I use the Leaf class (below)
      // various methods
    }
    The most difficult part (it seems to me anyway) would be the means of interfacing between the Tree (structure) and the objects themselves.
    One possibility that comes to mind is to create a seperate interface class:
    Code:
    template <T>;
    
    class Leaf<T> {
      T myObject;  // the current object
      // put in references to Tree member variables
      // put in interface functions
    }
    This would allow the Tree class to provide the structure while the Leaf class would provide a way for the object itself and the Leaf class to provide the interface between the objects themselves and the Tree or another object managing the Tree and the Tree.
    This would provide the added benifit of letting the object itself be independent of the Tree.

    The other part I'm wondering about, which I'm not really sure how to do, is how to keep the tree accurate (when something is moved, does everything connected to it know that it's been moved?).

    Does what I'm doing so far look like it will work?

    In terms of a DAG, what I need for this particular purpose is just a tree hierarchy. It also seems to me that a Tree class decended from a DAG class wouldn't be as efficient as one built by itself.

    Thanks for all your help,
    WannaB_Geek.

  7. #7
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    If you've never written a tree class before, a leaf is usually defined as a node with no children and the root as a node with no parent. The interaction between node and container comes with the tree class methods, just like in a list class.

  8. #8
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Here is a link to a Binary Tree tutorial: http://www.cprogramming.com/tutorial/lesson18.html
    While this isn't exactly what you are looking for, you can probably learn a good bit from it.

    As far as destroying a node, consider this: You have a node you want to destroy. You know its parent (even if it is NULL), and you know its children. When you destroy the node, you'll lose parts of the tree unless you make sure that some connection from the parent of the deleted node to the children of the deleted node is put in place.

    Also, the root, the middle, and the leaf nodes are generally all members of the same class with NULL links in the appropriate places, but if you really wanted to make them separate classes, they should at least derive from a common base class. Note that this would make attaching things to a leaf node more complicated than necessary, though.

    Also, your template syntax is a bit off. Here are two equivalent examples:
    Code:
    template<class T>
    struct foo
    {
    };
    
    template<typename T>
    struct bar
    {
    };
    Cheers
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Base container class question
    By Raigne in forum C++ Programming
    Replies: 8
    Last Post: 11-04-2008, 03:56 PM
  2. sorting container
    By l2u in forum C++ Programming
    Replies: 6
    Last Post: 09-01-2007, 01:12 PM
  3. stl container to store more than 1 type
    By sujeet1 in forum C++ Programming
    Replies: 7
    Last Post: 05-09-2007, 04:10 AM
  4. Replies: 1
    Last Post: 01-23-2006, 06:12 PM
  5. Linked List Queue Implementation help
    By Kenogu Labz in forum C++ Programming
    Replies: 8
    Last Post: 09-21-2005, 10:14 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21