Creating tree of objects w/o using pointers.

Discussion in 'C++' started by Amit Bhatia, Aug 20, 2006.

  1. Amit Bhatia

    Amit Bhatia Guest

    Hi,
    I have posted this post also for the thread "vector of lists" but since
    it is about something else (though related) I am posting it again under
    new thread.
    I want to make a tree of nodes as follows, but am not sure now if it
    will work:
    In node.h

    class Node
    {
    // some stuff ctors, dtors, etc;
    //Default ctor;

    Node &parent_node; // Could use pointer here but want to avoid it if
    possible. vector< Node & > child_nodes; //Could use pointer here but
    want to avoid it if possible.};

    In tree.h

    class Tree
    {
    //again ctors, dtors, and some other stuff;
    list< Node &> treeofnodes;
    };


    I don't want to create duplicate copies of nodes, and want everything to
    point correctly to elements in the global list treeofnodes.
    I am not sure though if above can be done, as there needs to be some
    kind of default ctor required and I am using references also..
    thanks,
    --a.

    --
     
    Amit Bhatia, Aug 20, 2006
    #1
    1. Advertising

  2. Amit Bhatia

    Amit Bhatia Guest

    I just figured that if I also want to delete elements from the tree I
    am going to need something like pointers and storing references as below
    will not work probably. (??)
    However, can I use iterators instead? And then when I want to delete
    some of them can I just pass the iterator to the erase function of the list
    w/o any problems?

    Amit Bhatia<> wrote:
    >
    >Hi,
    > I have posted this post also for the thread "vector of lists" but since
    >it is about something else (though related) I am posting it again under
    >new thread.
    >I want to make a tree of nodes as follows, but am not sure now if it
    >will work:
    >In node.h
    >
    >class Node
    >{
    >// some stuff ctors, dtors, etc;
    >//Default ctor;
    >
    >Node &parent_node; // Could use pointer here but want to avoid it if
    >possible. vector< Node & > child_nodes; //Could use pointer here but
    >want to avoid it if possible.};
    >
    >In tree.h
    >
    >class Tree
    >{
    >//again ctors, dtors, and some other stuff;
    >list< Node &> treeofnodes;
    >};
    >
    >
    >I don't want to create duplicate copies of nodes, and want everything to
    >point correctly to elements in the global list treeofnodes.
    > I am not sure though if above can be done, as there needs to be some
    >kind of default ctor required and I am using references also..
    >thanks,
    >--a.
    >
    >--
    >
    >




    --
     
    Amit Bhatia, Aug 20, 2006
    #2
    1. Advertising

  3. Note: "Node &" is not a pointer type define instead it stands for reference
    variable.
    "Node *" is a pointer type define.

    "Amit Bhatia" <> дÈëÏûÏ¢ÐÂÎÅ:ec8hu0$n6j$...
    >
    > Hi,
    > I have posted this post also for the thread "vector of lists" but since
    > it is about something else (though related) I am posting it again under
    > new thread.
    > I want to make a tree of nodes as follows, but am not sure now if it
    > will work:
    > In node.h
    >
    > class Node
    > {
    > // some stuff ctors, dtors, etc;
    > //Default ctor;
    >
    > Node &parent_node; // Could use pointer here but want to avoid it if
    > possible. vector< Node & > child_nodes; //Could use pointer here but
    > want to avoid it if possible.};
    >
    > In tree.h
    >
    > class Tree
    > {
    > //again ctors, dtors, and some other stuff;
    > list< Node &> treeofnodes;
    > };
    >
    >
    > I don't want to create duplicate copies of nodes, and want everything to
    > point correctly to elements in the global list treeofnodes.
    > I am not sure though if above can be done, as there needs to be some
    > kind of default ctor required and I am using references also..
    > thanks,
    > --a.
    >
    > --
    >
    >
     
    Chen shuSheng, Aug 20, 2006
    #3
  4. Amit Bhatia

    Bo Persson Guest

    "Amit Bhatia" <> skrev i
    meddelandet news:ec8hu0$n6j$...
    >
    > Hi,
    > I have posted this post also for the thread "vector of lists" but
    > since
    > it is about something else (though related) I am posting it again
    > under
    > new thread.
    > I want to make a tree of nodes as follows, but am not sure now if it
    > will work:
    > In node.h
    >
    > class Node
    > {
    > // some stuff ctors, dtors, etc;
    > //Default ctor;
    >
    > Node &parent_node; // Could use pointer here but want to avoid it if
    > possible. vector< Node & > child_nodes; //Could use pointer here but
    > want to avoid it if possible.};


    You cannot have a vector of references. The vector must be able to
    copy and assign to the elements. That doesn't work for references.

    >
    > In tree.h
    >
    > class Tree
    > {
    > //again ctors, dtors, and some other stuff;
    > list< Node &> treeofnodes;
    > };
    >
    >
    > I don't want to create duplicate copies of nodes,


    Why? Are they *extremely* expensive to copy?

    > and want everything to
    > point correctly to elements in the global list treeofnodes.
    > I am not sure though if above can be done, as there needs to be some
    > kind of default ctor required and I am using references also..
    > thanks,
    > --a.


    I think you try to do this more complicated that it actually has to
    be. The general rule is to go ahead and use the standard containers,
    until you see that your program runs way too slow. Then it is time to
    look into exactly where it takes too much time. Most often you will
    never have to.

    If you store your Nodes by value in a vector, or a list, the container
    will take care of all the problems of ownership and destruction. Using
    prewritten library code saves you a lot of work.


    Bo Persson
     
    Bo Persson, Aug 20, 2006
    #4
  5. Amit Bhatia

    Amit Bhatia Guest

    "Bo Persson" <> wrote:
    >
    >"Amit Bhatia" <> skrev i
    >meddelandet news:ec8hu0$n6j$...
    >>
    >> Hi,
    >> I have posted this post also for the thread "vector of lists" but
    >> since
    >> it is about something else (though related) I am posting it again
    >> under
    >> new thread.
    >> I want to make a tree of nodes as follows, but am not sure now if it
    >> will work:
    >> In node.h
    >>
    >> class Node
    >> {
    >> // some stuff ctors, dtors, etc;
    >> //Default ctor;
    >>
    >> Node &parent_node; // Could use pointer here but want to avoid it if
    >> possible. vector< Node & > child_nodes; //Could use pointer here but
    >> want to avoid it if possible.};

    >
    >You cannot have a vector of references. The vector must be able to
    >copy and assign to the elements. That doesn't work for references.
    >


    I guess then that I should use pointers. so it would be something like

    Node{
    //; ;
    Node *parent_node;
    list<Node*> child_nodes;
    };

    Tree{
    //; ;
    list<Node *> treeofnodes;
    };

    OR (NOT SURE IF THIS WOULD WORK?)

    Node{
    //; ;
    Node *parent_node;
    list<Node*> child_nodes;
    };

    Tree{
    //; ;
    list<Node> treeofnodes;
    };


    But here is another potential problem that I don't want. When I want to
    delete a particular Node, I can just use free on its pointer or
    something. But, if I want this pointer entry to be also deleted from the list
    "treeofnodes" in tree class above, there doesn't seem to be an easy way to
    do it. (?)
    However, I am just wondering if I could use iterators in place of
    pointers above. Stl Lists do have function called erase which takes an
    iterator argument to remove it from the list. And iterators are not
    invalidated if I remove some other ones from the list.So,

    Node{
    //; ;
    Node &parent;
    list< list<Node>:: iterator > child_nodes;
    };

    Tree{
    //; ;
    list<Node > treeofnodes;
    };

    But the question is: is this allowed?

    >>
    >> In tree.h
    >>
    >> class Tree
    >> {
    >> //again ctors, dtors, and some other stuff;
    >> list< Node &> treeofnodes;
    >> };
    >>
    >>
    >> I don't want to create duplicate copies of nodes,

    >
    >Why? Are they *extremely* expensive to copy?
    >
    >> and want everything to
    >> point correctly to elements in the global list treeofnodes.
    >> I am not sure though if above can be done, as there needs to be some
    >> kind of default ctor required and I am using references also..
    >> thanks,
    >> --a.

    >
    >I think you try to do this more complicated that it actually has to
    >be. The general rule is to go ahead and use the standard containers,
    >until you see that your program runs way too slow. Then it is time to
    >look into exactly where it takes too much time. Most often you will
    >never have to.
    >
    >If you store your Nodes by value in a vector, or a list, the container
    >will take care of all the problems of ownership and destruction. Using
    >prewritten library code saves you a lot of work.
    >
    >
    >Bo Persson
    >
    >




    --
     
    Amit Bhatia, Aug 20, 2006
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,129
  2. Marc Thrun
    Replies:
    15
    Views:
    861
    Tim Rentsch
    Oct 4, 2005
  3. 7stud
    Replies:
    11
    Views:
    699
    Dennis Lee Bieber
    Mar 20, 2007
  4. cerr

    pointers, pointers, pointers...

    cerr, Apr 7, 2011, in forum: C Programming
    Replies:
    12
    Views:
    681
  5. anne001
    Replies:
    1
    Views:
    238
Loading...

Share This Page