472,975 Members | 1,396 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,975 software developers and data experts.

Storing a tree in a std::list<>


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
Jul 22 '05 #1
14 5522
"Dave" <be***********@yahoo.com> wrote...
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
Jul 22 '05 #2
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.
Jul 22 '05 #3

"Jeff Schwab" <je************@comcast.net> wrote in message
news:YI********************@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.
Jul 22 '05 #4
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?

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
Jul 22 '05 #5

"Alan Johnson" <al****@mailandnews.com> wrote in message
news:40********@news.ua.edu...
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?

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


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...
Jul 22 '05 #6
On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"
<be***********@yahoo.com> wrote,
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.

Jul 22 '05 #7

"David Harmon" <so****@netcom.com.invalid> wrote in message
news:41****************@news.west.earthlink.net...
On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"
<be***********@yahoo.com> wrote,
My goal in using std::list<> is to avoid explicit memory management (and itsproblems) but still have the convenient use of pointers. A node goes in thelist, 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.


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).
Jul 22 '05 #8
On Sun, 6 Jun 2004 06:42:36 -0700 in comp.lang.c++, "Dave"
<be***********@yahoo.com> wrote,
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.


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?

Jul 22 '05 #9
Dave wrote:

"David Harmon" <so****@netcom.com.invalid> wrote in message
news:41****************@news.west.earthlink.net...
On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"
<be***********@yahoo.com> wrote,
My goal in using std::list<> is to avoid explicit memory management (and itsproblems) but still have the convenient use of pointers. A node goes in thelist, 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.


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
Jul 22 '05 #10

"David Harmon" <so****@netcom.com.invalid> wrote in message
news:40***************@news.west.earthlink.net...
On Sun, 6 Jun 2004 06:42:36 -0700 in comp.lang.c++, "Dave"
<be***********@yahoo.com> wrote,
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.


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...
Jul 22 '05 #11

"Denis Remezov" <RE*********************@yahoo.removethis.ca> wrote in
message news:40***************@yahoo.removethis.ca...
Dave wrote:

"David Harmon" <so****@netcom.com.invalid> wrote in message
news:41****************@news.west.earthlink.net...
On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"
<be***********@yahoo.com> wrote,
>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.

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


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...
Jul 22 '05 #12
Dave wrote:

"Denis Remezov" <RE*********************@yahoo.removethis.ca> wrote in
message news:40***************@yahoo.removethis.ca...
Dave wrote:

"David Harmon" <so****@netcom.com.invalid> wrote in message
news:41****************@news.west.earthlink.net...
> On Sat, 5 Jun 2004 17:13:05 -0700 in comp.lang.c++, "Dave"
> <be***********@yahoo.com> wrote,
> >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.
>

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


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::pointer 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
Jul 22 '05 #13
On Sun, 6 Jun 2004 10:59:50 -0700 in comp.lang.c++, "Dave"
<be***********@yahoo.com> wrote,
std::list<tree*> children; This is only storing pointers to nodes, not nodes themselves.


You're right. Make that

std::list<tree> children;

Jul 22 '05 #14
Dave wrote:
"Alan Johnson" <al****@mailandnews.com> wrote in message
news:40********@news.ua.edu...
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?

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

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;

Jul 22 '05 #15

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: Anton | last post by:
Hello ! I am writing a small program and wondering whether this expression is right? std::list< std::string > strList I mean that this is container into container and don't know the side...
0
by: Sebastian Faust | last post by:
Hi, I am thinking now for a while about a design decision. I would be glad if you can give me some advices which is maybe the better way for solving my problem. I wanna do something like...
4
by: Mikhail N. Kupchik | last post by:
Hi All. I have a question regarding C++ programming language standard. It is related to standard library, not to the core language. Is it portable to instantiate template class std::list<>...
6
by: PengYu.UT | last post by:
Hi, Suppose I have a list which contains pointers. I want the pointer got by dereferencing the iterator be a pointer pointing to a const object. But std::list<const T*>::const_iterator doens't...
2
by: Ben Pfaff | last post by:
The C++ standard says in 23.2.2.4 "list operations" that the various forms of splice invalidate iterators and references to the spliced elements. This makes the splice operation a lot less useful...
17
by: Isliguezze | last post by:
Does anybody know how to make a wrapper for that iterator? Here's my wrapper class for std::list: template <class Tclass List { private: std::list<T*lst; public: List() { lst = new...
2
by: DJRhino | last post by:
Was curious if anyone else was having this same issue or not.... I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 4 Oct 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central...
0
by: Aliciasmith | last post by:
In an age dominated by smartphones, having a mobile app for your business is no longer an option; it's a necessity. Whether you're a startup or an established enterprise, finding the right mobile app...
4
NeoPa
by: NeoPa | last post by:
Hello everyone. I find myself stuck trying to find the VBA way to get Access to create a PDF of the currently-selected (and open) object (Form or Report). I know it can be done by selecting :...
3
NeoPa
by: NeoPa | last post by:
Introduction For this article I'll be using a very simple database which has Form (clsForm) & Report (clsReport) classes that simply handle making the calling Form invisible until the Form, or all...
1
by: Teri B | last post by:
Hi, I have created a sub-form Roles. In my course form the user selects the roles assigned to the course. 0ne-to-many. One course many roles. Then I created a report based on the Course form and...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 1 Nov 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM) Please note that the UK and Europe revert to winter time on...
0
NeoPa
by: NeoPa | last post by:
Introduction For this article I'll be focusing on the Report (clsReport) class. This simply handles making the calling Form invisible until all of the Reports opened by it have been closed, when it...
4
by: GKJR | last post by:
Does anyone have a recommendation to build a standalone application to replace an Access database? I have my bookkeeping software I developed in Access that I would like to make available to other...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.