Can a recursive/self-referential template (using pointers) be instantiated and/or specialized in C++?

Question

I want to instantiate a template from the STL, using maps,vectors, and arrays, as follows:

map<some_type,vector<map<some_type,vector...>*>> elements;

The ellipses is just pseudo-code to represent the infinitely recursive definition, which is ofcourse impossible to type out. Basically, the vector should just hold pointers to other maps that are identical in structure/definition to the map in which the vector is contained. I know there are workarounds using classes and structs, the question is whether it is possible using only templates. I was hoping I could somehow define the whole outer map as some kind of "template-variable" or other place-holder such as "T", then write the following:

map<some_type,vector<T*>> elements;

where I would separately define T as referring to the whole map. But due to recursion, such a variable T would be defined in terms of itself, ie sub-components that are themselves T. Later I would then at runtime as necessary allocate more maps on the heap and insert pointers to them in the vector, such that I can then recursively (indefinately often), traverse into the map within the vector, just so that I can then instantiate more maps on the heap, again holding pointers to them within the vector.

Is there an (elegant) way to do this (if at all)?

Answer 1

You were on the right track by abstracting out the recursion variable:

template <typename Self>
using F = std::map<int, std::vector<Self*>>;

The problem is to find a type T such that T == F<T>. This is known as finding the fixed point. In these terms, we want a template Fix taking a template template parameter such that Fix<F> == F<Fix<F>>.

Abstractly, in a lazy functional language, Fix<F> = F<Fix<F>> could serve as a definition of Fix<F>. This coincidentally tells us exactly what breaks down in C++. In C++ notation this hypothetical definition would look like:

template <template<typename> typename F>
using Fix = F<Fix<F>>; // does not compile

This depends fundamentally on laziness, but templates are lazy by nature so that isn't a problem. The real problem is name lookup. We cannot refer to Fix on the right-hand side in C++. That's a somewhat artificial restriction, but that's the language we have.

I cannot see a way around that, so I cannot avoid introducing one generic helper struct:

template <template<typename> typename F>
struct Fix : F<Fix<F>> { };

Although aliases cannot reference their own name in the definition, classes and structs can.

With all of that out of the way, we have our solution:

// Our type
using Type = Fix<F>;

// It instantiates
auto map = Type{};

// The inner type is the same as the outer type
using inner_type = std::decay_t<decltype(*std::declval<Type::mapped_type::value_type>())>;
static_assert(std::is_same_v<Type, inner_type>);

// We can push_back the address of ourself
map[0].push_back(&map);

See this on godbolt.