On Feb 18, 2:12 am, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
> Jerry Coffin wrote:
> > In article <269b4ba8-b244-4dcb-a03f-
> > 65d9d5504...@i7g2000prf.googlegroups.com>, travis.bow...@gmail.com
> > says...
> >> So this is a driving me nuts. I need some more eyes on
> >> this. I have a written a Tree structure that mimics a Menu
> >> tree for a kiosk (no sorting, infinite children per node).
> >> Each node contains a pointer to its parent and a vector of
> >> children nodes. Here is a snippet of the pertinent bits
> >> driving me crazy.

> > Why not have each node literally contain a vector of child
> > nodes?

> > struct node {
> > std::vector<node> children;

> Do you mean std::vector<node*>?

> If you mean what you wrote, the code is not guaranteed to
> compile and if it does, it has undefined behavior since node
> is an incomplete type at this point and therefore
> std::vector<node> is not good. See [17.4.3.6/2].

And even if it happens to work in some cases... I hate to think
of what's going to happen to the parent pointer he used (a
node*) when the parent's parent gets more children.

Within a graph, nodes more or less have identity. Which means
no copying. Unless...

struct node
{
std::vector< int > children ;
int parent ;
static std::vector< node >
ourHome ;
// ...
} ;

All of the nodes in ourHome, with links being implemented as
indexes into ourHome.

(And no, I'm not really recommending anything like that:-).
Except maybe as a joke, or for programmers used to Fortran IV.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34