Re: Values vs. references for deep, nested structures.

It is easy to raise a lot of heat over this approach to construction of a
tree. Structurally, a tree is simply a pair of a value and a container of
(possibly trivial) trees so I feel the original post presents a logical
approach.

In general, the syntax of a template passing itself to a base class template

is so standard in so many contexts that it is hard to see how, short of
deliberately using blocking constructions, implimentations of containers
written in C++ will fail on this, providing the container itself does not
contain any instance of T as a variable (using new and delete to manage all
instances of T). But this last event can happen, microsofts implementation
of std::list did for a while I think and the construction failed as a
result. For a short while so did vector.

I can imagine that the iterator checking implemented in current versions of
VS2008 might have some problems, but even here, the fact that one is going
to have to create ones own iterator classes to navigate these structures
means that one should be able to overcome the main problems.

There are very practical reasons for structuring trees in this way because
one can ensure better locality of.

The problems with the approach come when you add and remove branches, do
internal copies after insertions etc.

I experimented a lot many years ago with this approach, and with a little
effort it worked very well with older versions of compilers because you
could use an implicit move semantics by defining different assignment and
copy construction operators for const arguments and non-const arguments, but

then at least the Microsoft implementation tightened up and even internally
only used the const version. I think the reason for this was to make sure
that if move operations failed then roll back worked and everything was
still exception safe. But effectively it blocked the approach at a practical

level.

BUT with MOVE semantics becoming official and presumably exception safe this

should really change, and I would be very surprised if the standard
containers did not take advantage of them. In this case, providing that you
define move constructors and assignment operators for your tree, in the same

way that you must already define assignment, copy operators... for your tree

class so it can be used in your vector, you should be away.

For some reason, certain people have a real aversion to these
constructions - but I think they are wrong; obviously one should not have a
virtual function anywhere in sight but the place for these virtual objects
is not at the level of small objects being bashed around in trees. But it is

a classical and tight reuse of code and conforms exactly to one way of
thinking about tree like structures such as expressions.

Having said that I think I would use

#include <vector>

typedef int ValueType;

struct MyTree{

ValueType mValue;

std::vector<MyTree> myChildren;

MyTree (const MyTree & myTree);

MyTree & operator=(const MyTree & myTree);

// C++0x extensions (not checked)

//MyTree (MyTree && myTree);

//MyTree & operator=(MyTree && myTree);

//...

};

So that, instead of int, my "value" could be a pointer to implementation
type object (with all the relevant smart pointers and polymorphism) if I
wanted it to be. In this case the structure could allow values contained by
nodes to be very different types from one node to the next without changing
the basic tree syntax.

By the way, since the size of vector<MyTree> should be known at declaration,

presumably before instantiation, I think that most implementations should
produce a complete type for MyTree at the correct time and so the code would

obey the standards. In any case it compiles in Comeau in strict mode.

Hope this is helpful.

Terry

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]