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
14  5577 
"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
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.
"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.
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
"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...
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.
"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).
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?
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
"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...
"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...
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
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;
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; This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
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...
|
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...
|
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<>...
|
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...
|
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...
|
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...
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
| |
