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)?
CodePudding user response：
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);