c++ How to implement self referencing type

Drawing Hands is a lithograph by the Dutch artist M. C. Escher
Drawing Hands is a lithograph by the Dutch artist M. C. Escher

What is it? A type (struct or class) whose instance contains one or more references to the instance of the same type.

A sketch:

// Self Referencing type
struct SR { 

   char state;
const SR & ref;

};

Why would anybody do this?

Is another question. After I implement this, I might give some valid use-cases. But it turns out it is surprisingly non-trivial to implement this simple type in C++17.

First (we all know, do we not?) one has to initialize the references as type (class or struct ) members.  Trying :

SR{}

As expected returns a compiler error response:

error: reference member of type 'const SR &' is uninitialized

I do oblige and create the next version

struct SR {
char state{} ;
const SR & ref{} ;
};

Trying to instantiate this struct (in Wandbox, using clang), produces a somewhat cryptic message, at first glance:

default member initializer for 'ref' needed within the definition of enclosing class 'SR' outside of member functions

Much later it turned out this message was a clue leading to the solution. clang++ is known for its good and clear error messages. But this one is a definite head-scratcher.

Also, it has to be said, Visual Studio 2017 IDE has produced another but a bit clearer message:

the generated default constructor cannot be used in an initializer for its own data member

Ok, that would be funny, but perhaps we need to initialize the ref member in a good old pre-modern c++98 way? Let’s try and do the next version.

struct SR {
char state{} ;
const SR & ref{} ;
SR () : ref( /* what to put here? */) {}
};

Just to immediately realise the chicken-and-egg situation. To initialize the ref member we need to give it a reference to SR. But we are constructing the SR. So we need a reference to non constructed SR? Or some such thing.

If ref would be a pointer that would be a nullptr. But ref is a reference, not a pointer.  Outside of this problem context, this is very clear and easy to understand. Reference cannot exist without being initialized.

// not a valid c++ --> const int & iref
// reference must be initialized immediately upon 
// declaration
const int & iref = 42 ;
We surely all know this. But how to do this in the context of self-referencing type like SR here, is?

We need to initialize SR reference member with default SR instance before one exists.

Not to prolong this “essay” too much and to give you some useful c++ code let me jump to the end of the journey.

After trying to decipher that cryptic clang++ message and googling for an hour or two, or more, I realized I could initialize the ref with the instance of SR with the help of C++ “forward declaration”  AND the ‘extern’ keyword.

// forward declare SR
struct SR ;
// forwad declare extern instance 

//  of SR
// declaration that uses extern and has
// no initializer is not a definition!

extern SR null_sr ;
//

struct SR {
const SR & ref{
// use the extern-aly declaredinstance
// not fully instantiated here
null_sr
} ;

char state{} ;
};
// here finalize the definition aka instance
// for the extern declaration above
SR null_sr{} ;

Immediately after this, I found the relevant page on cppreference , about reference members. I should have looked into that before. It contains this solution too.

I have to admit clang++ message is cryptic but it gave me the vital clue indeed. After I wasted several hours.

And as it turns out, this issue was not standardized and solved before C++14.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.