Re: Storing a tree in a std::list<>

From: Dave (better_cs_now_at_yahoo.com)
Date: 06/06/04 

Date: Sat, 5 Jun 2004 17:13:05 -0700

"Jeff Schwab" <jeffrey.schwab@comcast.net> wrote in message
news:YImdnVNNxPxZwV_dRVn-ug@comcast.com...
> Dave wrote:
> > Hello all,
> >
> > After perusing the Standard, I believe it is true to say that once you
> > insert an element into a std::list<>, its location in memory never
changes.
> > This makes a std::list<> ideal for storing vertices of an arbitrary
n-ary
> > tree where a vertex contain pointers to its parent / children. These
parent
> > / child vertices need to stay put if we've got pointers to them
somewhere!
> >
> > Am I correct in my assertion?
>
> I believe so. However, the idea doesn't seem especially graceful; what
> are its advantages to storing pointers to nodes in the list, rather than
> actual nodes? This achieves the same affect.
>
> As a side-note, the list could be used to store arbitrary graphs, not
> just trees. If you're only dealing with trees, what need is there for
> the list? You can get to any node from any other node by traversing the
> tree, you could order the nodes in a std::vector, etc.

My goal in using std::list<> is to avoid explicit memory management (and its
problems) but still have the convenient use of pointers. A node goes in the
list, and that node has pointers to its parent and children (which also
reside in the list). By having the nodes in a std::list, I can destroy an
arbitray tree in one fell swoop by simply destroying the list. No complex
memory management problems. Let the STL do it for me!

So, the list really isn't used as such. I don't iterate over it, sort it,
splice it or anything like that. It's just a way to have the whole tree
cleaned up automatically.

And as far as I can tell, once I put a node in the list, it will stay put -
its address will never change. list was chosen because this is not
necessarily true of other containers.

Relevant Pages

  • Re: Tree traversal algorithm
    ... This is pretty easy if you have a binary tree and child pointers you can follow. ... From an SQL point of view it would be far nicer to store trees as nested sets, where each node has a left and right index number indicating how many children it has. ... The parent pointer structure we have now makes it trivially easy to share parent trees - with the cost of making queries very hard/inefficient, ...
    (comp.graphics.algorithms)
  • Re: Co-optation Today
    ... a node with a single child is perfectly sound. ... Those aren't trees, since they have multiple paths between nodes. ... Biblical Hebrew gave rise to Modern Hebrew ... parent and zero or more children which includes one. ...
    (talk.origins)
  • Re: simplebinary tree
    ... You should look up AVR trees and red/black trees. ... typedef struct node { ... void inorder(sn *root) ... parent = x = NULL; ...
    (comp.lang.c)
  • Re: parent pointers in AST nodes
    ... Is it common / useful to supply a pointer to the node's parent as ... * This can simplify some AST processing tasks, ... You can easily pass down a chain of parent link pointers during ... the visitor pattern pops out of a simple ...
    (comp.compilers)
  • Re: hacker challenge - traverse a list
    ... came from (a link to your parent) in the node. ... Fortunately the link holding the address of the child you are going to ... you can do a clever trick with moving pointers around that implicitly ... could do the trick, but again one needs to remember the "state" (number ...
    (comp.programming)