递归/自引用模板（使用指针）可以在 C++ 中实例化和/或专门化吗？

Question

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

地图*>>>元素；

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

地图>元素；

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

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

Answer 1

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

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

问题是找到一个类型 T 使得 T == F。这称为查找固定点。在这些方面，我们需要一个模板 Fix 接受模板模板参数，使得 Fix == F<修复>。

抽象地，在惰性函数式语言中，Fix = F> 可以用作 Fix 的定义。这恰好告诉我们 C++ 中到底发生了什么问题。在 C++ 表示法中，这个假设的定义如下所示：

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

这从根本上取决于惰性，但模板本质上是惰性的，因此这不是问题。真正的问题是名称查找。我们不能引用C++中右侧的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);

请在 godbolt 上查看此内容。