Storing a tree in a std::list<>

[Dave]

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?

Thanks,
Dave

[Victor Bazarov]

Re: Storing a tree in a std::list&lt;&g t;

"Dave" <better_cs_now@ yahoo.com> wrote...[color=blue]
> 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[/color]
changes.[color=blue]
> 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[/color]
parent[color=blue]
> / child vertices need to stay put if we've got pointers to them somewhere!
>
> Am I correct in my assertion?[/color]

Well, no, not really. 'std::list<>' is ideal for storing elements
of a doubly-linked lists because that's what it's designed to do.

What you're talking about should probably be its own data structure
and you can use std::list to store the children of a node, but not
the entire tree.

class tree {
std::list<tree* > children;
tree* parent;
public:
// some kind of interface
};

Of course, your interface may require quick access to the 'next
sibling', so you might be better off with a real tree-like structure

class tree_node {
tree_node *parent;
tree_node *first_child;
tree_node *prev_sib, *next_sib;
public:
// some kind of interface
};

class tree {
tree_node *root;
public:
// whatever
};

You will need to implement all by yourself, but it's going to be
efficient and easy to understand and maintain.

Victor

[Jeff Schwab]

Re: Storing a tree in a std::list&lt;&g t;

Dave wrote:[color=blue]
> 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?[/color]

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.

[Dave]

Re: Storing a tree in a std::list&lt;&g t;


"Jeff Schwab" <jeffrey.schwab @comcast.net> wrote in message
news:YImdnVNNxP xZwV_dRVn-ug@comcast.com. ..[color=blue]
> Dave wrote:[color=green]
> > 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[/color][/color]
changes.[color=blue][color=green]
> > This makes a std::list<> ideal for storing vertices of an arbitrary[/color][/color]
n-ary[color=blue][color=green]
> > tree where a vertex contain pointers to its parent / children. These[/color][/color]
parent[color=blue][color=green]
> > / child vertices need to stay put if we've got pointers to them[/color][/color]
somewhere![color=blue][color=green]
> >
> > Am I correct in my assertion?[/color]
>
> 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.[/color]

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.

[Alan Johnson]

Re: Storing a tree in a std::list&lt;&g t;

Dave wrote:[color=blue]
> 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?
>
> Thanks,
> Dave
>
>[/color]

While that probably is true for almost any implementation, I don't think
that the standard actually requires it. What it does require is that
adding/removing elements (as well as most other operations) do not
invalidate any iterators to elements of the list.

Alan

[Dave]

Re: Storing a tree in a std::list&lt;&g t;


"Alan Johnson" <alanwj@mailand news.com> wrote in message
news:40c267a1$1 @news.ua.edu...[color=blue]
> Dave wrote:[color=green]
> > 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[/color][/color]
changes.[color=blue][color=green]
> > This makes a std::list<> ideal for storing vertices of an arbitrary[/color][/color]
n-ary[color=blue][color=green]
> > tree where a vertex contain pointers to its parent / children. These[/color][/color]
parent[color=blue][color=green]
> > / child vertices need to stay put if we've got pointers to them[/color][/color]
somewhere![color=blue][color=green]
> >
> > Am I correct in my assertion?
> >
> > Thanks,
> > Dave
> >
> >[/color]
>
> While that probably is true for almost any implementation, I don't think
> that the standard actually requires it. What it does require is that
> adding/removing elements (as well as most other operations) do not
> invalidate any iterators to elements of the list.
>
> Alan[/color]

Hmmm, references too. But yes, technically not pointers. I wonder if one
can assume that iterators and references not being invalidated implies that
pointers are not invalidated...

[David Harmon]

Re: Storing a tree in a std::list&lt;&g t;

On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"
<better_cs_now@ yahoo.com> wrote,[color=blue]
>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).[/color]

Take Victor's tip. By using a std::list for a member variable, you get
the memory management you are looking for and you also get your tree
structure.

[Dave]

Re: Storing a tree in a std::list&lt;&g t;


"David Harmon" <source@netcom. com.invalid> wrote in message
news:41068b32.1 90869726@news.w est.earthlink.n et...[color=blue]
> On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"
> <better_cs_now@ yahoo.com> wrote,[color=green]
> >My goal in using std::list<> is to avoid explicit memory management (and[/color][/color]
its[color=blue][color=green]
> >problems) but still have the convenient use of pointers. A node goes in[/color][/color]
the[color=blue][color=green]
> >list, and that node has pointers to its parent and children (which also
> >reside in the list).[/color]
>
> Take Victor's tip. By using a std::list for a member variable, you get
> the memory management you are looking for and you also get your tree
> structure.
>[/color]

Unfortunately, this method does not provide any memory management. It's
precisely the memory management that I'm looking for, not the C-style way of
implementing an n-ary tree (which, by the way, I'm not saying is a perfectly
valid approach; it's just not what I'm attempting to accomplish at the
moment).

[David Harmon]

Re: Storing a tree in a std::list&lt;&g t;

On Sun, 6 Jun 2004 06:42:36 -0700 in comp.lang.c++, "Dave"
<better_cs_now@ yahoo.com> wrote,[color=blue][color=green]
>> Take Victor's tip. By using a std::list for a member variable, you get
>> the memory management you are looking for and you also get your tree
>> structure.[/color][/color]
[color=blue]
>Unfortunatel y, this method does not provide any memory management.[/color]

Sure it does. For instance, if you delete a node the std::list
destructor deletes all the nodes under it. What more are you asking
for?

[Denis Remezov]

Re: Storing a tree in a std::list&lt;&g t;

Dave wrote:[color=blue]
>
> "David Harmon" <source@netcom. com.invalid> wrote in message
> news:41068b32.1 90869726@news.w est.earthlink.n et...[color=green]
> > On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"
> > <better_cs_now@ yahoo.com> wrote,[color=darkred]
> > >My goal in using std::list<> is to avoid explicit memory management (and[/color][/color]
> its[color=green][color=darkred]
> > >problems) but still have the convenient use of pointers. A node goes in[/color][/color]
> the[color=green][color=darkred]
> > >list, and that node has pointers to its parent and children (which also
> > >reside in the list).[/color]
> >
> > Take Victor's tip. By using a std::list for a member variable, you get
> > the memory management you are looking for and you also get your tree
> > structure.
> >[/color]
>
> Unfortunately, this method does not provide any memory management. It's
> precisely the memory management that I'm looking for, not the C-style way of
> implementing an n-ary tree (which, by the way, I'm not saying is a perfectly
> valid approach; it's just not what I'm attempting to accomplish at the
> moment).[/color]

It does provide memory management, assuming that the tree_node class has a
proper destructor. All data are referenced or aggregated by tree nodes.
When you delete a tree node, its destructor will have to dispose of the
children. The implementation should be quite straightforward .

If you ever have to delete a subtree hanging from a node, you will have to
provide those destructors's functionality anyway; the general list will not
do the job automatically in this case.

You may want to consider the following as alternatives to the two options
given by Victor (but they may not always be appropriate). In the first
case, in fact, there is no explicit memory management for tree data
(just like in your general list). The second one has the advantage of
quick access to children; you know the maximum size for the vector since
you are talking about n-ary trees.

class tree_node {
std::list<tree_ node> children;
tree_node* parent;
//...
};

or
class tree_node {
std::vector<tre e_node*> children;
tree_node* parent;
//...
};

Denis

[Dave]

Re: Storing a tree in a std::list&lt;&g t;


"David Harmon" <source@netcom. com.invalid> wrote in message
news:40cf3a3f.2 7852757@news.we st.earthlink.ne t...[color=blue]
> On Sun, 6 Jun 2004 06:42:36 -0700 in comp.lang.c++, "Dave"
> <better_cs_now@ yahoo.com> wrote,[color=green][color=darkred]
> >> Take Victor's tip. By using a std::list for a member variable, you get
> >> the memory management you are looking for and you also get your tree
> >> structure.[/color][/color]
>[color=green]
> >Unfortunatel y, this method does not provide any memory management.[/color]
>
> Sure it does. For instance, if you delete a node the std::list
> destructor deletes all the nodes under it. What more are you asking
> for?
>[/color]

Here was the suggestion:

class tree {
std::list<tree* > children;
tree* parent;
public:
// some kind of interface
};

This is only storing pointers to nodes, not nodes themselves. When I delete
an object of class tree, it is true that the std::list<tree *> destructor
will be invoked. But destroying the pointers in no way affects the nodes
pointed to. They still remain. If no other copies of the pointers exist
elsewhere, I've just created a memory leak. This is essentially the old
C-style way of building an arbitrary tree, just fancied up a small bit with
the use of std::list<>. As I acknowledged in a previous post, this is a
perfectly valid approach. But nonetheless, it's not what I'm looking for...

If I smartened up the tree destructor to properly dispose of its children
(and they of their children, etc...), we'd be getting somewhere, but now
we're right back to explicit memory management, which is exactly what I am
trying to avoid... It may be that there is no good way to do what I want
without explicit memory management or without rediculous contortions to do
so and, if so, that's fine. I am just trying to thoroughly explore the
possibility and not give up on it right away...

[Dave]

Re: Storing a tree in a std::list&lt;&g t;


"Denis Remezov" <REMOVETHISdeni s_remezov@yahoo .removethis.ca> wrote in
message news:40C3045F.4 CEDD412@yahoo.r emovethis.ca...[color=blue]
> Dave wrote:[color=green]
> >
> > "David Harmon" <source@netcom. com.invalid> wrote in message
> > news:41068b32.1 90869726@news.w est.earthlink.n et...[color=darkred]
> > > On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"
> > > <better_cs_now@ yahoo.com> wrote,
> > > >My goal in using std::list<> is to avoid explicit memory management[/color][/color][/color]
(and[color=blue][color=green]
> > its[color=darkred]
> > > >problems) but still have the convenient use of pointers. A node goes[/color][/color][/color]
in[color=blue][color=green]
> > the[color=darkred]
> > > >list, and that node has pointers to its parent and children (which[/color][/color][/color]
also[color=blue][color=green][color=darkred]
> > > >reside in the list).
> > >
> > > Take Victor's tip. By using a std::list for a member variable, you[/color][/color][/color]
get[color=blue][color=green][color=darkred]
> > > the memory management you are looking for and you also get your tree
> > > structure.
> > >[/color]
> >
> > Unfortunately, this method does not provide any memory management. It's
> > precisely the memory management that I'm looking for, not the C-style[/color][/color]
way of[color=blue][color=green]
> > implementing an n-ary tree (which, by the way, I'm not saying is a[/color][/color]
perfectly[color=blue][color=green]
> > valid approach; it's just not what I'm attempting to accomplish at the
> > moment).[/color]
>
> It does provide memory management, assuming that the tree_node class has a
> proper destructor. All data are referenced or aggregated by tree nodes.
> When you delete a tree node, its destructor will have to dispose of the
> children. The implementation should be quite straightforward .
>
> If you ever have to delete a subtree hanging from a node, you will have to
> provide those destructors's functionality anyway; the general list will[/color]
not[color=blue]
> do the job automatically in this case.
>
> You may want to consider the following as alternatives to the two options
> given by Victor (but they may not always be appropriate). In the first
> case, in fact, there is no explicit memory management for tree data
> (just like in your general list). The second one has the advantage of
> quick access to children; you know the maximum size for the vector since
> you are talking about n-ary trees.
>
> class tree_node {
> std::list<tree_ node> children;
> tree_node* parent;
> //...
> };
>
> or
> class tree_node {
> std::vector<tre e_node*> children;
> tree_node* parent;
> //...
> };
>
> Denis[/color]

Oh, that first idea looks akin to what I'm seeking! The only issue that
remains is the parent pointer. The Standard states that modifying
operations on a list don't invalidate iterators or references, but it
doesn't speak to pointers. Of course, from a practical point of view, it is
almost certain to be fine. But I don't like accepting "almost certain"!
I'm thinking maybe putting a parent iterator rather than a parent pointer in
the struct would do the trick...

[Denis Remezov]

Re: Storing a tree in a std::list&lt;&g t;

Dave wrote:[color=blue]
>
> "Denis Remezov" <REMOVETHISdeni s_remezov@yahoo .removethis.ca> wrote in
> message news:40C3045F.4 CEDD412@yahoo.r emovethis.ca...[color=green]
> > Dave wrote:[color=darkred]
> > >
> > > "David Harmon" <source@netcom. com.invalid> wrote in message
> > > news:41068b32.1 90869726@news.w est.earthlink.n et...
> > > > On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"
> > > > <better_cs_now@ yahoo.com> wrote,
> > > > >My goal in using std::list<> is to avoid explicit memory management[/color][/color]
> (and[color=green][color=darkred]
> > > its
> > > > >problems) but still have the convenient use of pointers. A node goes[/color][/color]
> in[color=green][color=darkred]
> > > the
> > > > >list, and that node has pointers to its parent and children (which[/color][/color]
> also[color=green][color=darkred]
> > > > >reside in the list).
> > > >
> > > > Take Victor's tip. By using a std::list for a member variable, you[/color][/color]
> get[color=green][color=darkred]
> > > > the memory management you are looking for and you also get your tree
> > > > structure.
> > > >
> > >
> > > Unfortunately, this method does not provide any memory management. It's
> > > precisely the memory management that I'm looking for, not the C-style[/color][/color]
> way of[color=green][color=darkred]
> > > implementing an n-ary tree (which, by the way, I'm not saying is a[/color][/color]
> perfectly[color=green][color=darkred]
> > > valid approach; it's just not what I'm attempting to accomplish at the
> > > moment).[/color]
> >
> > It does provide memory management, assuming that the tree_node class has a
> > proper destructor. All data are referenced or aggregated by tree nodes.
> > When you delete a tree node, its destructor will have to dispose of the
> > children. The implementation should be quite straightforward .
> >
> > If you ever have to delete a subtree hanging from a node, you will have to
> > provide those destructors's functionality anyway; the general list will[/color]
> not[color=green]
> > do the job automatically in this case.
> >
> > You may want to consider the following as alternatives to the two options
> > given by Victor (but they may not always be appropriate). In the first
> > case, in fact, there is no explicit memory management for tree data
> > (just like in your general list). The second one has the advantage of
> > quick access to children; you know the maximum size for the vector since
> > you are talking about n-ary trees.
> >
> > class tree_node {
> > std::list<tree_ node> children;
> > tree_node* parent;
> > //...
> > };
> >
> > or
> > class tree_node {
> > std::vector<tre e_node*> children;
> > tree_node* parent;
> > //...
> > };
> >
> > Denis[/color]
>
> Oh, that first idea looks akin to what I'm seeking! The only issue that
> remains is the parent pointer. The Standard states that modifying
> operations on a list don't invalidate iterators or references, but it
> doesn't speak to pointers. Of course, from a practical point of view, it is
> almost certain to be fine. But I don't like accepting "almost certain"!
> I'm thinking maybe putting a parent iterator rather than a parent pointer in
> the struct would do the trick...[/color]

A potential weakness of that idea is that removing a tree_node with a
purpose of using it elsewhere (not just deleting) means copying of the whole
subtree hanging from it. If you never have to do that, then it works well.

I don't see how a pointer could get invalidated as long as a corresponding
reference is valid. First, imagine that a reference type was defined as a
user type rather than T&. Since you cannot overload operator . (dot), it
would not be possible to use a value of that type for member access in the
usual way.
In fact, reference types for containers are defined in terms of reference
types of the corresponding allocators. One requirement for allocators
is to define reference as T&.
Now, if you have a valid reference value, you can apply operator & to it
and get the address of the same object all the time.

I have only a vague idea on the history of Allocator::refe rence and
Allocator::poin ter types. I'd imagine (and I think I heard about it
somewhere) that they could have something to do with a need to address
different memory models, for example, far memory pointers alongside with
the ususal ones (far T* and T*), but I'll stop speculating here.
The semantics should be the same, anyway.

Denis

[David Harmon]

Re: Storing a tree in a std::list&lt;&g t;

On Sun, 6 Jun 2004 10:59:50 -0700 in comp.lang.c++, "Dave"
<better_cs_now@ yahoo.com> wrote,[color=blue]
> std::list<tree* > children;[/color]
[color=blue]
>This is only storing pointers to nodes, not nodes themselves.[/color]

You're right. Make that

std::list<tree> children;

[Jeff Schwab]

Re: Storing a tree in a std::list&lt;&g t;

Dave wrote:[color=blue]
> "Alan Johnson" <alanwj@mailand news.com> wrote in message
> news:40c267a1$1 @news.ua.edu...
>[color=green]
>>Dave wrote:
>>[color=darkred]
>>>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[/color][/color]
>
> changes.
>[color=green][color=darkred]
>>>This makes a std::list<> ideal for storing vertices of an arbitrary[/color][/color]
>
> n-ary
>[color=green][color=darkred]
>>>tree where a vertex contain pointers to its parent / children. These[/color][/color]
>
> parent
>[color=green][color=darkred]
>>>/ child vertices need to stay put if we've got pointers to them[/color][/color]
>
> somewhere!
>[color=green][color=darkred]
>>>Am I correct in my assertion?
>>>
>>>Thanks,
>>>Dave
>>>
>>>[/color]
>>
>>While that probably is true for almost any implementation, I don't think
>>that the standard actually requires it. What it does require is that
>>adding/removing elements (as well as most other operations) do not
>>invalidate any iterators to elements of the list.
>>
>>Alan[/color]
>
>
> Hmmm, references too. But yes, technically not pointers. I wonder if one
> can assume that iterators and references not being invalidated implies that
> pointers are not invalidated...[/color]

I certainly would think so, you can get a pointer to the variable via

T* p = &reference;