 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Jeff Donner
Guest
|
 Posted: Sat Oct 18, 2003 1:43 pm Post subject: Why no STL tree proposed? |
 |
|
Past posts in this newsgroup have argued that it's ok that
there is no tree type (user) in the STL because there are
so many different things wanted of them which affect design.
But, that surely can't be an obstacle now, template design
being what it is (in fact you could probably just adapt
Boost::graph a little). So, is anyone else surprised
there haven't been any proposed? Are they just not used
often enough to be worth someone's time to make a proposal?
Also, is there a deadline (or even estimate) for
the library TC being finished?
thanks,
Jeff Donner
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Bob Bell
Guest
|
| Posted: Sat Oct 18, 2003 11:15 pm Post subject: Re: Why no STL tree proposed? |
|
|
Jeff Donner <jdonner0@n.o.s.earthlink.p.a.m.net> wrote
| Quote: | Past posts in this newsgroup have argued that it's ok that
there is no tree type (user) in the STL because there are
so many different things wanted of them which affect design.
But, that surely can't be an obstacle now, template design
being what it is (in fact you could probably just adapt
Boost::graph a little). So, is anyone else surprised
there haven't been any proposed? Are they just not used
often enough to be worth someone's time to make a proposal?
Also, is there a deadline (or even estimate) for
the library TC being finished?
|
Why not propose one yourself?
Bob
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Sun Oct 19, 2003 8:47 am Post subject: Re: Why no STL tree proposed? |
|
|
On 18 Oct 2003 09:43:48 -0400, Jeff Donner
<jdonner0@n.o.s.earthlink.p.a.m.net> wrote:
| Quote: | Past posts in this newsgroup have argued that it's ok that
there is no tree type (user) in the STL because there are
so many different things wanted of them which affect design.
But, that surely can't be an obstacle now, template design
being what it is (in fact you could probably just adapt
Boost::graph a little).
|
Since a tree is just a rooted acyclic graph, why change anything?
| Quote: | So, is anyone else surprised
there haven't been any proposed? Are they just not used
often enough to be worth someone's time to make a proposal?
|
There is no list in the STL and nobody is proposing one. Do
not confuse the std::list sequence with a list any more than
you would confuse an AVL-tree ordered sequence with a tree.
What interface do you want?
Tree ();
Tree (T const&, Tree const&, Tree const&);
Tree (Tree const&);
~Tree ();
Tree& operator= (Tree const&);
T const& root () const;
T& root ();
Tree const& left () const;
Tree& left ();
Tree const& right () const;
Tree& right ();
bool empty () const;
void swap (T&);
Since all trees can be represented as binary trees, that should
cover everything.
Is that what you want? Is it what "everyone" wants? Alternative?
What does a tree iterator look like?
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Aaron Bentley
Guest
|
| Posted: Sun Oct 19, 2003 9:44 pm Post subject: Re: Why no STL tree proposed? |
|
|
John Potter wrote:
| Quote: |
What interface do you want?
Tree ();
Tree (T const&, Tree const&, Tree const&);
Tree (Tree const&);
~Tree ();
Tree& operator= (Tree const&);
T const& root () const;
T& root ();
Tree const& left () const;
Tree& left ();
Tree const& right () const;
Tree& right ();
bool empty () const;
void swap (T&);
Since all trees can be represented as binary trees, that should
cover everything.
Is that what you want? Is it what "everyone" wants? Alternative?
|
An interface like that would be terribly painful to use for non-binary
trees.
For the work I do, this would be more appropriate:
Tree ();
Tree (T const&, Tree const&, Tree const&);
Tree (Tree const&);
~Tree ();
Tree& operator= (Tree const&);
T& value ();
Tree &previous();
Tree const &previous() const;
Tree &next();
Tree const &next() const;
Tree &parent();
Tree const &parent() const;
Teee &firstchild();
Teee const &firstchild() const;
bool empty () const;
void swap (T&);
Since all binary trees can be represented as non-binary trees, that
should cover everything. :-)
| Quote: | What does a tree iterator look like?
|
I think you have to have to have at least two types of iterator--
depth-first and breadth-only.
Aaron
--
Aaron Bentley
www.aaronbentley.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Antoun Kanawati
Guest
|
| Posted: Mon Oct 20, 2003 10:09 pm Post subject: Re: Why no STL tree proposed? |
|
|
Aaron Bentley wrote:
| Quote: | For the work I do, this would be more appropriate:
Tree ();
Tree (T const&, Tree const&, Tree const&);
Tree (Tree const&);
~Tree ();
Tree& operator= (Tree const&);
T& value ();
Tree &previous();
Tree const &previous() const;
Tree &next();
Tree const &next() const;
Tree &parent();
Tree const &parent() const;
Teee &firstchild();
Teee const &firstchild() const;
bool empty () const;
void swap (T&);
Since all binary trees can be represented as non-binary trees, that
should cover everything. 
|
From my experience with trees, I have needed many varieties, and
only very few can be satisfied with the interface above.
If your tree is not a representation of a collection or sequence
(such as std::rb_tree), then it is often the case that the child-links
require some sort of label. Search trees based on prefixes, for
example, use such an approach; for example, for many games, the
game-tree has the structure [Move, mapping<Response, Tree>];
prefix-search trees also have a similar structure. Here, I use the
word 'mapping', since the mapping is not necessarily a std::map.
Further wrinkles appear when the children may be of mixed types, for
example: packages, classes, and interfaces.
Also, there's the business of inserting new subtrees under an
existing node, or simply building the tree bottom-up. The
interface point: "Tree (T const&, Tree const&, Tree const&);"
implies copy-construction of the children (arbitrary size),
or significant elaboration of the memory management scheme
with associated implications on the interface.
Thus, unlike std::map<> (and hash_map<>), the problem of
defining the general purpose interface for a "Tree", is
not so simple. Even the problem of defining the interface
for a homogenous general purpse tree runs into issues,
when dealing with tree construction and manipulation.
The only tree-like construct in the standard library that
I know of is std::rb_tree, and that is a very restricted
case of trees.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carl Daniel
Guest
|
| Posted: Tue Oct 21, 2003 3:49 pm Post subject: Re: Why no STL tree proposed? |
|
|
Antoun Kanawati wrote:
| Quote: | The only tree-like construct in the standard library that
I know of is std::rb_tree, and that is a very restricted
case of trees.
|
There is no such class in the standard C++ library, although most
implementations do in fact use Red/Black trees to implement std::set, map,
multiset and multimap.
-cd
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Aaron Bentley
Guest
|
| Posted: Tue Oct 21, 2003 4:04 pm Post subject: Re: Why no STL tree proposed? |
|
|
Hi Antoun,
Antoun Kanawati wrote:
| Quote: | Aaron Bentley wrote:
For the work I do, this would be more appropriate:
Tree ();
Tree (T const&, Tree const&, Tree const&);
Tree (Tree const&);
~Tree ();
Tree& operator= (Tree const&);
T& value ();
Tree &previous();
Tree const &previous() const;
Tree &next();
Tree const &next() const;
Tree &parent();
Tree const &parent() const;
Teee &firstchild();
Teee const &firstchild() const;
bool empty () const;
void swap (T&);
Since all binary trees can be represented as non-binary trees, that
should cover everything. :-)
From my experience with trees, I have needed many varieties, and
only very few can be satisfied with the interface above.
|
This was more-or-less my point-- that it would be hard to craft a
standard tree that pleased all. For my purposes, the interface above
would almost suit, but it actually needs at least an addchild(Tree *)
method or Tree &addchild(Tree::value_type const &) method.
| Quote: | If your tree is not a representation of a collection or sequence
(such as std::rb_tree), then it is often the case that the child-links
require some sort of label.
|
Our trees represent XML data, so all non-leaf nodes (and some leaves)
are labels. But we store node labels in the nodes themselves.
| Quote: | Search trees based on prefixes, for
example, use such an approach; for example, for many games, the
game-tree has the structure [Move, mapping<Response, Tree>];
prefix-search trees also have a similar structure. Here, I use the
word 'mapping', since the mapping is not necessarily a std::map.
|
The children contained in a map? Hmm. We need to preserve an arbitrary
ordering, so an std::map wouldn't work for us, but I can imagine many
cases where it would. It's funny-- when we do job our job interviews,
we ask applicants to design a tree. I've seen designs based on linked
lists and designs based on arrays and designs based on vectors. So far,
no map designs.
| Quote: | Further wrinkles appear when the children may be of mixed types, for
example: packages, classes, and interfaces.
|
Or XML tags, attributes, PIs and text. . .
| Quote: | Also, there's the business of inserting new subtrees under an
existing node, or simply building the tree bottom-up.
|
| Quote: | The interface point: "Tree (T const&, Tree const&, Tree const&);"
implies copy-construction of the children (arbitrary size),
or significant elaboration of the memory management scheme
with associated implications on the interface.
|
My bad-- that should not have been included. A
Tree::Tree(Tree::value_type const &) constructor would be more useful.
| Quote: | Thus, unlike std::map<> (and hash_map<>), the problem of
defining the general purpose interface for a "Tree", is
not so simple.
|
You're preaching to the choir-- I couldn't agree more.
Aaron
--
Aaron Bentley
www.aaronbentley.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Wed Oct 22, 2003 1:22 am Post subject: Re: Why no STL tree proposed? |
|
|
On 20 Oct 2003 18:09:04 -0400, Antoun Kanawati <antounk (AT) comcast (DOT) net>
wrote:
| Quote: | From my experience with trees, I have needed many varieties, and
only very few can be satisfied with the interface above.
|
I read this as there is no such thing as a tree abstraction. A tree
is just a raw pointer to a struct that contains whatever is needed. I
have seen this elswhere. I don't want a tree library, I just want to
use trees the way that I want to use them. A tree is a simple data
structure with many different uses. No argument, just interested in
why it is that way.
| Quote: | If your tree is not a representation of a collection or sequence
(such as std::rb_tree),
|
I accept that an rb_tree or any other search tree is not a tree
abstraction, it is an ordered list abstraction. There is no way
to do tree things with a search tree.
t.left().right().swap(t.right().left());
| Quote: | then it is often the case that the child-links
require some sort of label.
|
Edges in the rooted acyclic graph have data? Could they be included
in the child? It has a single in edge.
| Quote: | Search trees based on prefixes, for
example, use such an approach; for example, for many games, the
game-tree has the structure [Move, mapping<Response, Tree>];
prefix-search trees also have a similar structure. Here, I use the
word 'mapping', since the mapping is not necessarily a std::map.
|
I'm ignorant. Can you educate me?
| Quote: | Further wrinkles appear when the children may be of mixed types, for
example: packages, classes, and interfaces.
|
But the children are all the same type, namely trees. Are you talking
about the data in the root of a tree? What is different about this
from any other container? A parse tree contains operators and operands
which must be resolved to something common no matter how you define the
tree.
| Quote: | Also, there's the business of inserting new subtrees under an
existing node, or simply building the tree bottom-up. The
interface point: "Tree (T const&, Tree const&, Tree const&);"
implies copy-construction of the children (arbitrary size),
or significant elaboration of the memory management scheme
with associated implications on the interface.
|
We each gave you everything you need. Don't you like the interface?
Given t.left().empty() and a desire to insert data there.
tree(data, tree(), tree()).swap(t.left());
Not a problem. Building bottom up can also be done.
tree& spliceIntoLeft (tree& left, T const& data, tree& right) {
tree temp(data, tree(), tree());
temp.left().swap(left);
temp.right().swap(right);
temp.swap(left);
return left;
}
Left is now the new tree and both temp and right are empty. The
only copy was the data item. Nothing fancy, you can do deep
copy or splice as desired. You do need to quit chasing pointers
and think about trees.
| Quote: | Thus, unlike std::map<> (and hash_map<>), the problem of
defining the general purpose interface for a "Tree", is
not so simple. Even the problem of defining the interface
for a homogenous general purpse tree runs into issues,
when dealing with tree construction and manipulation.
|
Such as?
| Quote: | The only tree-like construct in the standard library that
I know of is std::rb_tree, and that is a very restricted
case of trees.
|
I do not even consider it a tree. It is an implementation
detail of an ordered collection and does nothing that trees
do. However, it could be implemented using that binary tree.
A rotate right should be fun.
void rotateRight (tree& p) {
tree c;
c.swap(p.left());
c.right().swap(p.left());
c.right().swap(p);
c.swap(p);
}
In case anyone missed it, the functions presented are non-member,
non-friend. The interface is complete.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Wed Oct 22, 2003 1:23 am Post subject: Re: Why no STL tree proposed? |
|
|
On 19 Oct 2003 17:44:52 -0400, Aaron Bentley <aaron.bentley (AT) utoronto (DOT) ca>
wrote:
| Quote: | An interface like that would be terribly painful to use for non-binary
trees.
|
Maybe, but I think the abstraction is minimal.
| Quote: | For the work I do, this would be more appropriate:
|
Great! You do work with trees which could use an abstraction.
| Quote: | Tree ();
Tree (T const&, Tree const&, Tree const&);
|
I assume that the two trees are first-child and sibling.
| Quote: | Tree (Tree const&);
~Tree ();
Tree& operator= (Tree const&);
T& value ();
|
I called this root, but value will do. You also need a const version.
| Quote: | Tree &previous();
Tree const &previous() const;
Tree &next();
Tree const &next() const;
|
Bidirectional traversal of siblings. Ok.
| Quote: | Tree &parent();
Tree const &parent() const;
|
I left that out because it is a little problem. The root of the
tree does not really have an empty parent tree.
bool leafBinary (Tree const& t) {
return t.left().empty() && t.right().empty();
}
bool leafNary (Tree const& t) {
return t.firstchild().empty();
}
bool root (Tree const& t) {
return t.parent().empty();
}
When I implemented the above with parent, I made root a member
function which makes it fatter. Since t is const, the const
parent could return a static empty tree const.
What is the complexity requirement for parent in your version?
Mine is of course constant and yours might be.
| Quote: | Teee &firstchild();
Teee const &firstchild() const;
|
Descend a level. Ok.
| Quote: | bool empty () const;
void swap (T&);
Since all binary trees can be represented as non-binary trees, that
should cover everything.
|
I am ignoring the smiley and assuming that you are serious. Either can
be implemented as a wrapper of the other. The binary version has fewer
members to actually implement.
| Quote: | What does a tree iterator look like?
I think you have to have to have at least two types of iterator--
depth-first and breadth-only.
|
Not sure what you mean here. There are three depth-first traversals of
a binary tree and two of an Nary tree. There is one breadth-first
traversal of either. An iterator might do any of those traversals via
++ and --; however, it could also work up and down. ++ goes right and
-- goes left. What goes up? Does it matter? There are no algorithms
that work on trees. Without any algorithms, who needs iterators?
Without iterators, all we have is a container. The STL is designed on
algorithms not containers. Maybe that answers the original question.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Wed Oct 22, 2003 1:30 am Post subject: Re: Why no STL tree proposed? |
|
|
On 21 Oct 2003 12:04:37 -0400, Aaron Bentley <aaron.bentley (AT) utoronto (DOT) ca>
wrote:
| Quote: | This was more-or-less my point-- that it would be hard to craft a
standard tree that pleased all. For my purposes, the interface above
would almost suit,
|
Would my guess that you have no tree class be correct? I usually find
that nobody really wants a tree. It is way too much fun to chase
pointers to let some library do it.
| Quote: | but it actually needs at least an addchild(Tree *)
method or Tree &addchild(Tree::value_type const &) method.
|
It need not be a member.
Tree& addSibling (Tree& t, T const& item) {
return t.empty() ? (Tree(item, Tree(), Tree()).swap(t), t)
: addsibling(t.next(), item);
}
Tree& addchild (Tree& t, T const& item) {
return addsibling(t.firstChild(), item);
}
Or, if it may be added as the first child.
Tree& addchild (Tree& t, T const& item) {
Tree c(item, Tree(), Tree());
c.next().swap(t.first());
c.swap(t.first());
return t.first();
}
| Quote: | The interface point: "Tree (T const&, Tree const&, Tree const&);"
implies copy-construction of the children (arbitrary size),
or significant elaboration of the memory management scheme
with associated implications on the interface.
My bad-- that should not have been included.
|
Why not? Your interface seems to say, a tree is either empty or it
has a root with a firstchild tree and a next tree. The default ctor
handles the first case and this constructor handles the second case.
It is also very useful in implementing the copy ctor. However, there
is a problem with a root having a non-empty sibling. Seems unavoidable
in you design.
| Quote: | A Tree::Tree(Tree::value_type const &) constructor would be more
useful. |
Only a convience as shown above.
In addition to the problem with testing for root mentioned in my other
post, how do you test for being firstchild? Is the following valid?
bool firstchild (Tree const& t) {
return t.previous().empty();
}
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Antoun Kanawati
Guest
|
| Posted: Wed Oct 22, 2003 3:59 pm Post subject: Re: Why no STL tree proposed? |
|
|
Carl Daniel wrote:
| Quote: | Antoun Kanawati wrote:
The only tree-like construct in the standard library that
I know of is std::rb_tree, and that is a very restricted
case of trees.
There is no such class in the standard C++ library, although most
implementations do in fact use Red/Black trees to implement std::set, map,
multiset and multimap.
|
Sorry about the mistake. rb_tree is actually a common extension, like
hash-based containers.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Glen Low
Guest
|
| Posted: Wed Oct 22, 2003 6:19 pm Post subject: Re: Why no STL tree proposed? |
|
|
| Quote: | What interface do you want?
Tree ();
Tree (T const&, Tree const&, Tree const&);
Tree (Tree const&);
~Tree ();
Tree& operator= (Tree const&);
T const& root () const;
T& root ();
Tree const& left () const;
Tree& left ();
Tree const& right () const;
Tree& right ();
bool empty () const;
void swap (T&);
|
Why not just
template <typename T, template class tree
{
...
const Container <tree & children() const;
Container <tree & children();
};
.... to represent the direct children, instead of left and right? Where
Container is some STL container [I know, I know, template template
params don't work well with STL containers... this is not a final
design and probably would work only on sequences not associative
containers, but you get the idea. A proper design would probably use a
traits class instead of a template template parameter.]
This has the advantage of being minimal but supporting as many direct
children as you want. You can then use a fixed 2-element container for
binary trees for example, or use a map if you want labelled nodes. Any
pre- or post-order traversal can be done with a free function
(algorithm) to preserve the minimal interface.
Cheers,
Glen Low, Pixelglow Software
www.pixelglow.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Antoun Kanawati
Guest
|
| Posted: Wed Oct 22, 2003 6:35 pm Post subject: Re: Why no STL tree proposed? |
|
|
John Potter wrote:
| Quote: | Also, there's the business of inserting new subtrees under an
existing node, or simply building the tree bottom-up. The
interface point: "Tree (T const&, Tree const&, Tree const&);"
implies copy-construction of the children (arbitrary size),
or significant elaboration of the memory management scheme
with associated implications on the interface.
We each gave you everything you need. Don't you like the interface?
[snipped: binary tree manipulations]
Thus, unlike std::map<> (and hash_map<>), the problem of
defining the general purpose interface for a "Tree", is
not so simple. Even the problem of defining the interface
for a homogenous general purpse tree runs into issues,
when dealing with tree construction and manipulation.
Such as?
|
The use of binary trees to represent general trees dates
back to the days of LISP and cons-cells. I have done it
sufficiently many times, in sufficiently many languages.
However, I want trees where I can find an arbitrary child
at a node in constant time. I want trees where I can
label the links to the subtrees without having to infest
the node data with edge labels. And, I want trees that
solve some problems that are neither syntax nor searches
on ordered data.
An internal binary tree representation is sufficient
to represent any tree "structure". Whether such a
representation is usable for purposes other than
representing the structure and traversing the structure
is not clear. For example, requiring constant-time find's
for subtrees.
Similary, this goes for construction and manipulation
of trees.
And, the most important problem with trees is that
they are pointers. No matter how you slice it or
dice it, the recursive nature of trees demands
indirection in the representation, and that indirection
has to be exposed to the user (unlike std::container's
which deal strictly with values).
The exposure of indirection is unnatural in the standard
C++ library. None of the standard containers have such
interfaces. However, when you're building trees top-down,
bottom-up, or patching them up, this will have to
come up.
My personal preference is to have enough pieces so that
I can build my own trees without excessive effort. And,
I believe the standard library has nearly all such pieces
[something better than auto_ptr<> would be nice].
--
A. Kanawati
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Antoun Kanawati
Guest
|
| Posted: Wed Oct 22, 2003 6:37 pm Post subject: Re: Why no STL tree proposed? |
|
|
John Potter wrote:
| Quote: | then it is often the case that the child-links
require some sort of label.
Edges in the rooted acyclic graph have data? Could they be included
in the child? It has a single in edge.
|
The edges do not have data, they have "names", and it is required
that you can seek a subtree efficiently by name.
It is possible to migrate the name into the subtree, but that requires
that I have two kinds of trees (the top level, and all others).
A much simpler, and more uniform, representation is to maintain the
links inside the subtree as a mapping<name, tree_pointer>.
With this sort of representation, I need only one sort of tree.
My edges are still pointers, and I can efficiently find a subtree
by "name".
| Quote: | Search trees based on prefixes, for
example, use such an approach; for example, for many games, the
game-tree has the structure [Move, mapping<Response, Tree>];
prefix-search trees also have a similar structure. Here, I use the
word 'mapping', since the mapping is not necessarily a std::map.
I'm ignorant. Can you educate me?
|
A mapping, in the abstract sense, is a function. For example, an
array, or a vector, is a mapping from integral values to the element
type. That is: the representation of the mapping will vary with
your problem domain. In the particular recreational problem I am
playing with, a hash_map<Response, tree_pointer> works well. However,
if I change the encoding function, I can map Response to the range
0..14; in which case, I can use a simple fixed-size array. In both
cases, I am programming against a mapping from responses to subtrees.
| Quote: | Further wrinkles appear when the children may be of mixed types, for
example: packages, classes, and interfaces.
But the children are all the same type, namely trees. Are you talking
about the data in the root of a tree? What is different about this
from any other container? A parse tree contains operators and operands
which must be resolved to something common no matter how you define the
tree.
|
A general purpose tree is not a container, and its structure is
meant for manipulation by the programmer. This means that the
universal tree interface must provide efficient interfaces for
a wide range of applications.
A syntax tree, in its basic form, has minimal requirements: all
it needs to do is reflect the structure of the source, and allow
for very simple access patterns to its subtrees.
For the example listed above (subtrees can be packages, classes,
interfaces), the programmer should be allowed to expect *easy*
and *efficient* access to groups of subtrees (by node type), and
in this case, there is no meaningful ordering among the subtrees.
This has implications on (a) representation, and (b) interface.
And, of course, there's that game strategy tree, which I am fooling
around with, which is also different enough from syntax trees or
class/package/interface trees.
At this point, I hope it is clear that there is significant variety
in the use of trees.
While I have no doubt that a universal representation of syntax
trees, and equivalent constructs, is feasible, I doubt that a
universal tree for all applications is a reasonable concept.
--
A. Kanawati
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Aaron Bentley
Guest
|
| Posted: Thu Oct 23, 2003 3:38 pm Post subject: Re: Why no STL tree proposed? |
|
|
John Potter wrote:
| Quote: | On 21 Oct 2003 12:04:37 -0400, Aaron Bentley
wrote:
Would my guess that you have no tree class be correct?
|
I have a class that represents a specific kind of tree. Is that a yes
or a no? I'm guessing you mean that my tree class isn't generic, and
that's true.
| Quote: | I usually find that nobody really wants a tree.
|
I don't need a generic class, but I hope if there was a suitable one, I
hope I'd use it.
| Quote: | It is way too much fun to chase pointers to let some library do it.
|
I'm not having fun chasing pointers anymore. I almost always
- iterate through direct descendants
- iterate through descendants whose key matches a given pattern
- find the first descendant whose key matches a given pattern
- iterate depth-first through the whole tree
I use previously-written functions for all that.
| Quote: | but it actually needs at least an addchild(Tree *)
method or Tree &addchild(Tree::value_type const &) method.
It need not be a member.
Tree& addSibling (Tree& t, T const& item) {
return t.empty() ? (Tree(item, Tree(), Tree()).swap(t), t)
: addsibling(t.next(), item);
}
Tree& addchild (Tree& t, T const& item) {
return addsibling(t.firstChild(), item);
}
Or, if it may be added as the first child.
Tree& addchild (Tree& t, T const& item) {
Tree c(item, Tree(), Tree());
c.next().swap(t.first());
c.swap(t.first());
return t.first();
}
|
Nicely done.
| Quote: | The interface point: "Tree (T const&, Tree const&, Tree const&);"
implies
[snip]
My bad-- that should not have been included.
Why not? Your interface seems to say, a tree is either empty or it
has a root with a firstchild tree and a next tree.
|
My goal with the design was to present a cleaned-up version of our
XmlElement class, and we don't have anything like that.
| Quote: | The default ctor
handles the first case and this constructor handles the second case.
It is also very useful in implementing the copy ctor. However, there
is a problem with a root having a non-empty sibling. Seems unavoidable
in you design.
|
I can make those problems go away by declaring: there is a unique empty
static node called TREENULL. If you add it as a child, it is ignored.
If call any function returning Tree& or Tree const &, where there is no
node to return, TREENULL will be returned.
I'm not claiming that's a good or wise approach. The class at work
returns pointers. Maybe returning iterators would be better for a
generic design.
| Quote: | A Tree::Tree(Tree::value_type const &) constructor would be more
useful.
Only a convience as shown above.
|
Similarly, Tree(Tree const &, Tree const &) can be implemented in terms
of Tree(T const &) and addchild(Tree *). Since they can achieve the
same things, "useful" is the wrong term, and the right term is something
like "conformant to my design prejudices".
| Quote: | In addition to the problem with testing for root mentioned in my other
post, how do you test for being firstchild? Is the following valid?
bool firstchild (Tree const& t) {
return t.previous().empty();
}
|
Could be. TREENULL could be used here, e.g. t.previous() would return
TREENULL, and TREENULL.empty() would return true.
--
Aaron Bentley
www.aaronbentley.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
