Member struct declared in base, defined in derived class

[Ninereeds]

I'm messing around with using mixin-layers (look for papers by Yannis
Smaragdakis and Don Batory) to define data structures. One issue is
that nodes tend to have pointers to other nodes - the pointers have to
point to the full node type, and have to be referenced before that
full node type is known.

One solution is to use the 'fixpoint construction' to get an apparent
circular dependency...

class c_Final : public c_Layer2< c_Layer1 <c_Final> > {};

I'm always a bit nervous about this, though, so I was wondering about
alternatives. It seemed to me that all I really need to do is to
declare the final node type in a base class, but define it in a
derived class.

So, I tried the following experiment...

class c_Base
{
public:
struct c_Full_Node;

struct c_Node
{
c_Full_Node *m_Parent;
};
};

class c_Derived1 : public c_Base
{
public:
struct c_Base::c_Full_Node : public c_Base::c_Node
{
int m_Data;
};

typedef c_Base::c_Full_Node c_Full_Node;
};

//class c_Derived2 : public c_Base
//{
// public:
// struct c_Base::c_Full_Node : public c_Base::c_Node
// {
// char m_Data;
// };
//
// typedef c_Base::c_Full_Node c_Full_Node;
//};

//////////

int main(int argc, char* argv[])
{
c_Derived1::c_Full_Node l_Node1;

l_Node1.m_Parent = 0;
l_Node1.m_Data = 0;

//c_Derived2::c_Full_Node l_Node2;

//l_Node2.m_Parent = 0;
//l_Node2.m_Data = 0;

return EXIT_SUCCESS;
}

The commented out code does not compile, for fairly obvious reasons -
it tries to create a second definition of c_Base::c_Full_Node.

This seems like a perfect solution to the problem to me, since it
doesn't give the appearance of peering into the future. I haven't
wrapped it up in templates to do real mixin layer stuff yet, but I
can't see any *additional* reasons why that shouldn't work.

What can I say. I've learned to think twice before saying "that would
never work" with C++, or I would never have even tried this
experiment.

That said, all I have proved is that it seems to work with Microsoft
Visual C++ 2003. This doesn't mean that it *should* work, according to
the standard.

So - can anyone tell me whether this is standard-compliant, portable
code? I haven't got a clue myself.

 

[Ninereeds]

Applying this with mixin layer templates turned out to be a little
fiddly, because the base for the mixin layers cannot be templated. I
have built a working example, though.

It does require more code to do the composition than using the
fixpoint thing, since it needs the initial struct to be defined before
the composition, and then needs 'capping off' at the end with another
non-template struct.

Also, it looks like there's no real point to this when the base class
for the composition isn't templated. In the following example,
c_Base::c_Full_Node could have been defined outside of c_List, and it
is probably less confusing to do so.

I have achieved my goal, in that I can build data structures using
mixin layers but without using the fixpoint construct anyway, and I'm
kicking myself for not realising it's this simple.

The question remains, though - does the C++ standard require that it
is legal to have a struct/class that is declared in a base class, but
defined in its derived class?

The full example follows...


namespace mixins
{
// Required base class for starting the mixin
// composition - defines the empty base for the
// node structure that other mixin layers refine.
template<class B> struct c_List_Base : public B
{
typedef typename B::c_Full_Node c_Full_Node;

struct c_Node { };
};

template<class B> struct c_List_Fwd : public B
{
typedef typename B::c_Full_Node c_Full_Node;

struct c_Node : public B::c_Node
{
c_Full_Node *m_Next;
};
};

template<class B> struct c_List_Bwd : public B
{
typedef typename B::c_Full_Node c_Full_Node;

struct c_Node : public B::c_Node
{
c_Full_Node *m_Prev;
};
};

template<class B, class T> struct c_List_Data : public B
{
public:
typedef typename B::c_Full_Node c_Full_Node;

struct c_Node : public B::c_Node
{
T m_Data;
};
};
};

//////////
// Composition needs more code using this technique, though the
// principle is simple enough.

struct c_Base
{
// We need a new initial mixin layer for each composition,
// since we need a new c_Full_Node type declaration for
// composition or else the definitions would conflict.
struct c_Full_Node;

// May as well define the empty base for the node here as well
struct c_Node {};
};

// Step by step composition
struct c_List_000 : public mixins::c_List_Base< c_Base > {};
struct c_List_001 : public mixins::c_List_Fwd < c_List_000 > {};
struct c_List_002 : public mixins::c_List_Bwd < c_List_001 > {};
struct c_List_003 : public mixins::c_List_Data< c_List_002, int > {};

// Cap off the composition

struct c_List : public c_List_003
{
struct c_Base::c_Full_Node : public c_List_003::c_Node {};
typedef c_Base::c_Full_Node c_Node;
};

//////////

int main(int argc, char* argv[])
{
c_List::c_Full_Node l_Node1;

l_Node1.m_Next = 0;
l_Node1.m_Prev = 0;
l_Node1.m_Data = 0;

return EXIT_SUCCESS;
}

 

[Ninereeds]

The whole of this thread so far turns out to be pointless. What I
should be doing is...

struct c_Node;
struct c_List : public c_Mixin2< c_Mixin1< c_Node* > > {};
struct c_Node : public c_List::c_Node {};

That is, the mixin layers simply accept a node identifier type as one
of the arguments at the start. This can be a pointer to a struct that
hasn't been defined yet (as above) or it could be an integer
identifier or whatever.

If the node identifier is a pointer, simply forward-reference the
pointed-to type.

This creates a problem with any algorithms that are defined by the
mixin-layers to work on the data structure, since they cannot assume
that node IDs are pointers. This can be resolved by using policies
passed to the appropriate mixin layers as arguments. Policy members
might be simple inlines to access fields using "->", or they might be
more complex functions to look nodes up in a separate container or
file.

Interesting, how policies and mix-in layers can complement each other.
Though since they're basically the template versions of existing OOP
techniques, it's no big surprise.