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 { 

  const SR & ref;
};

Strange and wonderful. 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{} ; // trivial data
const SR & ref{} ;
};

Trying to instantiate this struct (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 was 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 aka 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 realize 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. References 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
// NOTE: declaration that uses extern and has
// no initializer is not a definition!

extern SR null_sr ;
//

struct SR {
const SR & ref{
// not yet fully defined
null_sr
} ;

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

Works. 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 some time first.

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

Valid use case?

I am not so sure but here is one.  Linked list with no pointers but references.

It is doable with “native references” but easier with the correct usage of standard C++.  Let the code speak.

And here are the usual tests:

I was so bold to post this also here.

Enjoy the standard C++.

So little C++ so much good!
So little C++ so much good!