c++ - 消除 C++ 中的递归模板实例化

Question

我想定义一个可以在不同地方(在文件范围内)调用的宏，以便创建可以执行某些操作的函数。 (在下面的示例中，函数只是打印一条消息，但当然我的真正意图是做一些其他有用的事情。)挑战在于我想要一些“管理器”功能(在我的示例中，它只是 main() )以某种方式成功地将它们全部调用(以任何顺序)，而没有任何代码依赖于宏调用(当然，宏调用本身除外)。我的意思是，一旦文件被写入，另一个程序员将​​能够在不同的地方插入一些新的宏调用或删除一些现有的调用，并且代码仍然可以工作而无需进一步更改。我意识到这可以使用静态对象来完成，但我想探索一种不同的方法。我将使用一些模板技巧和事实__LINE__是单调递增的。

#include <iostream>
using namespace std;

template<int i>
inline void f()
{
   f<i-1>();
}

#define START_REGISTRATION                                \
template<>                                                \
inline void f<__LINE__>() {}  /* stop the recursion */    \
template<> void f<__LINE__>()  /* force semicolon */

#define REGISTER(msg)                                     \
template<>                                                \
inline void f<__LINE__>()                                 \
{                                                         \
   cout << #msg << endl;                                  \
   f<__LINE__ - 1>();                                     \
}                                                         \
template<> void f<__LINE__>()  /* force semicolon */

// Unrelated code ...

START_REGISTRATION;

// Unrelated code ...

REGISTER(message 1);

// Unrelated code ...

REGISTER(message 2);

// Unrelated code ...

REGISTER(message 3);

// Unrelated code ...

// manager function (in this case main() )
int main()
{
   f<__LINE__>();
}

这打印

message 3
message 2
message 1

正如预期的那样。

该解决方案有一些缺点。

无法调用 REGISTER在同一条线上两次。

如果 #line 会中断被玩。

需要在 REGISTER 的所有调用之后放置经理.

由于递归实例化而增加了编译时间。

除非 f 的“虚拟”实例化都内联了，运行时的调用堆栈深度将与 START_REGISTRATION; 之间的行数一样大和 f<__LINE__>();在经理。

代码膨胀:除非 f 的“虚拟”实例化都内联了，实例化的数量同样会很大。

过多的实例化递归深度可能会达到编译器的限制(我的系统默认为 500)。

问题 1-4 我并不介意。通过让每个函数返回一个指向前一个函数的指针，并让管理器使用这些指针来迭代地调用函数而不是让它们相互调用，可以消除问题 5。可以通过创建类似的类模板构造来消除问题 6，该构造能够为 REGISTER 的每次调用进行计算。在前一次调用中实例化了哪个函数，因此只实例化了实际执行某些操作的函数。过多的实例化会从函数模板转移到类模板，但类实例化只会给编译器带来负担；他们不会触发任何代码生成。所以我真正关心的是问题 7，问题是:有没有办法重构事物，以便编译器迭代而不是递归地进行实例化。我也对完全不同的方法持开放态度(除了那些涉及静态对象的方法)。一个简单的解决方案是在管理器之前将所有注册组合在一起(或添加 STOP_REGISTRATION 宏以结束注册块)，但这会破坏我的主要目的(在定义它的代码旁边注册内容)。

编辑:有一些有趣的建议，但恐怕我没有明确我希望实现的目标。我真的对两件事很感兴趣:解决所提出的问题(即，没有静态，每个注册单行，添加/删除注册时没有额外的更改，虽然我忽略了这么说，但只有标准 C++ --- 因此，没有提升)。正如我在下面的评论中所说，我的兴趣本质上更多是理论性的:我希望学习一些新技术。因此，我真的很想专注于重组事物，以便消除(或至少减少)递归或找到满足我上面列出的约束的不同方法。

编辑 2: MSalter 的解决方案向前迈出了一大步。一开始我以为每次注册都会产生排队的全部成本，但后来我意识到当然一个函数只能被实例化一次，所以在实例化方面我们付出与线性搜索相同的代价，但是递归深度变为对数。如果我解决了这个问题，我会发布一个完整的解决方案，消除问题 5-7。不过，看看它是否可以在恒定的递归深度下完成仍然很好，最好是实例化数量与调用数量成线性关系(a-la the boost solution)。

编辑 3:这是完整的解决方案。

#define START_REGISTRATION                                          \
template<int lo, int hi>                                            \
struct LastReg {                                                    \
  enum {                                                            \
     LINE_NUM = LastReg<(lo + hi)/2 + 1, hi>::LINE_NUM ?            \
        static_cast<int>(LastReg<(lo + hi)/2 + 1, hi>::LINE_NUM) :  \
        static_cast<int>(LastReg<lo, (lo + hi)/2>::LINE_NUM)        \
  };                                                                \
};                                                                  \
template<int l>                                                     \
struct LastReg<l, l> {                                              \
   enum { LINE_NUM = 0 };                                           \
};                                                                  \
template<int l>                                                     \
struct PrevReg {                                                    \
   enum { LINE_NUM = LastReg<__LINE__ + 1, l - 1>::LINE_NUM };      \
};                                                                  \
template<int l> void Register() {}                                  \
template<int l> void Register()  /* force semicolon */


#define REGISTER(msg)                                               \
template<>                                                          \
struct LastReg<__LINE__, __LINE__> {                                \
   enum { LINE_NUM = __LINE__ };                                    \
};                                                                  \
template<>                                                          \
void Register<__LINE__>()                                           \
{                                                                   \
   cout << __LINE__ << ":" << #msg << endl;                         \
   Register<PrevReg<__LINE__>::LINE_NUM>();                         \
}                                                                   \
template<> void Register<__LINE__>()  /* force semicolon */


#define END_REGISTRATION                                            \
void RegisterAll()                                                  \
{                                                                   \
   Register<PrevReg<__LINE__>::LINE_NUM>();                         \
}                                                                   \
void RegisterAll()  /* force semicolon */


START_REGISTRATION;

REGISTER(message 1);

REGISTER(message 2);

END_REGISTRATION;


int main()
{
   RegisterAll();
}

Answer 1

您面临的问题是您正在对 f<i> 进行线性搜索。 ，这会导致过多的实例化。

解决办法是让f<i>调用 g<i,0> .这反过来调用 g<i,i/2>和 g<i/2,0> , 拨打 g<i,i/2+i/4> , g<i/2+i/4,i/2> , g<i/2,i/4>和 g<i/4, 0>异端。你当然会专攻 g<__LINE__, __LINE__>内REGISTER() .

实例化 f<65536>仍然会导致 65536 次模板实例化(您有效地检查了所有先前的 65536 行)，但递归深度仅限于 log(65536) 或 16 个级别。这是可行的。