Re: Tree driving me nuts!
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=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34