Re: using vector to encapulate a tree - non const copy constructors
terry wrote:
The object vector<A> does not contain any object
of type A and should be regarded as similar to a collection of (as yet
unassigned) pointers of type A*. The same sort of object as you would
use if you were constructing a tree by hand.
That's just it. Technically, you do not know how vector<> is
implemented. You certainly cannot infer that it has a collection of
A*, or even pointer to a not-yet-allocated array of A. Suppose I
replace std::vector with
template <typename X> struct Vector
{
X buffer[16];
} ;
I am permitted to do this. Why? When you reach into the STL grab bag
for vector, you are implicitly accepting certain stipulations prescribe
by that container, namely that you do *not* have the option of peering
into its implementation and making use of (abusing) it. In other words,
if vector<T> claims to be able to contain T, then it should be able to
provide any implementation that conforms to the stipulations. So if
mytree is declared as:
class mytree: public T, protected std::vector<mytree>{}
Then technically, mytree is a std::vector of itself. How can something
be a container of itself?
I have written numerous post over the past 5 years admonishing people
to be more careful to call things what they are and not something
similar. In this case, you are using "mytree" as both a tree and a
node in the tree. This notion as always been incorrect, even in C, but
in C, we did not have a choice - there was no mechanism to allow true
encapsulation. The code above is conceptually erroneous, and it is
merely by fortune that you are able to define such a construct. If you
were to change the name "mytree" to "mytreenode", then of course, the
code would still compile. Then you could get into a debate as to
wether mytree is a mytreenode or mytreenode is a mytree.
The declaration really does encapulate a tree and can (I have) be used
effectively. I really don't agree that it is erroneous - it is there!
It does not, at least not any more than a link structure in plain C
would "encapsulate" a tree. If mytree is a vector<mytree>, then that
would mean that mytree would be able to contain itself. This is
conceptually irregular, and that the compiler allows you to declare
some construct that gives the (false) impression that you have made
"something" does not mean that you have actually made that thing. :)
To see, this ask yoursef if your abstraction holds firm in the face of
insert mytree into itself. You cannot, at least with any abitrary
definition of vector<> that conforms to the contract specified by
vector<>.
You should also ask yourself what happens when you have a mytree that
has 0 elements in it. Is it still a mytree? What if the T part of a
mytree (mytreenode) takes up by default construction 16,384 bytes? You
would have a mytree that is empty, yet physically contains 1 node, yet
in real life contains no nodes, but wastes 16,384 bytes to simply exist
as a 0-node "tree". You are not allowed to cheat here. You cannot
say, "Oh, that's a strange situation. I will tell whoever uses mytree
that they should not have big T's because that would be wasteful."
I had hoped my examples near the end of the original posting would be
clear.
IMO, one of the worst mistakes computer science professors make in
teaching data structure is not being fastidious in their expositions of
linked data structures. The notion that a fully contained, assignable,
constructible, wieldable tree is the same as one node of such a tree is
conceptually incorrect. In fact, as I have stated comp.theory, this
directly caused said computer scientists to define the height of a
1-node binary tree to be 0 when the height should be 1.
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]