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]

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?

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]

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.

 

[Dave]

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.

 

[Alan Johnson]

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

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]

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

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]

On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"

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).

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.

 

[Denis Remezov]

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).

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<tree_node*> children;
tree_node* parent;
//...
};

Denis

 

[Dave]

On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"


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.

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]

On Sun, 6 Jun 2004 06:42:36 -0700 in comp.lang.c++, "Dave"

Unfortunately, this method does not provide any memory management.

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?

 

[Dave]

On Sun, 6 Jun 2004 06:42:36 -0700 in comp.lang.c++, "Dave"



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?

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]

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<tree_node*> children;
tree_node* parent;
//...
};

Denis

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]

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...

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::reference and
Allocator:ointer 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]

On Sun, 6 Jun 2004 10:59:50 -0700 in comp.lang.c++, "Dave"

std::list<tree*> children;

This is only storing pointers to nodes, not nodes themselves.

You're right. Make that

std::list<tree> children;

 

[Jeff Schwab]

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...

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

T* p = &reference;