recursive/self-referential 模板（使用指针）是否可以实例化 and/or 专用于 C++？

Question

我想使用映射、向量和数组从 STL 实例化一个模板，如下所示：

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

省略号只是表示无限递归定义的伪代码，当然不可能打出来。基本上，向量应该只包含指向其他地图的指针，这些地图在 structure/definition 中与包含向量的地图相同。我知道有使用类和结构的解决方法，问题是是否可以仅使用模板。我希望我能以某种方式将整个外部地图定义为某种“模板变量”或其他占位符，例如“T”，然后编写以下内容：

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

在这里我将单独定义 T 为指代整个地图。但是由于递归，这样的变量 T 将根据自身定义，即本身是 T 的子组件。稍后我会在运行时根据需要在堆上分配更多映射并将指向它们的指针插入向量中，例如然后我可以递归地（不确定地经常）遍历向量中的映射，这样我就可以在堆上实例化更多映射，再次在向量中保存指向它们的指针。

是否有一种（优雅的）方法来做到这一点（如果有的话）？

Answer 1

通过抽象出递归变量，您走在了正确的轨道上：

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

问题是要找到一个类型 T 使得 T == F<T>。这称为找到 fixed point。在这些术语中，我们想要一个模板 Fix 采用模板模板参数，这样 Fix<F> == F<Fix<F>>.

抽象地说，在惰性函数式语言中，Fix<F> = F<Fix<F>> 可以作为 Fix<F> 的定义。这巧合地告诉我们 C++ 中发生故障的确切原因。在 C++ 符号中，这个假设的定义看起来像：

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

这基本上取决于惰性，但模板本质上是惰性的，所以这不是问题。真正的问题是名称查找。在 C++ 中，我们不能在 right-hand 端引用 Fix。这是一个有点人为的限制，但这是我们的语言。

我看不出解决这个问题的方法，所以我无法避免引入一个通用的辅助结构：

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

虽然别名不能在定义中引用它们自己的名称，但类和结构可以。

所有这些都解决了，我们有了解决方案：

// 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.

recursive/self-referential 模板（使用指针）是否可以实例化 and/or 专用于 C++？

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

c++

parameters

templates

specialization