消除 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

将按预期打印。

该解决方案有一些缺点。

1. 无法在同一行调用 REGISTER 两次。
2. 如果使用 #line 将会中断。
3. 需要将管理器放在所有 REGISTER 调用之后。
4. 由于递归实例化而增加了编译时间。
5. 除非 f 的“虚拟”实例全部内联，否则运行时的调用堆栈深度将与 START_REGISTRATION; 和 之间的行数一样大f<__LINE__>(); 在管理器中。
6. 代码膨胀：除非 f 的“虚拟”实例化都被内联掉，否则实例化的数量同样会很大。
7. 过多的实例化递归深度可能会达到编译器的限制（我的系统默认为 500）。

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

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

编辑 2：MSalter 的解决方案向前迈出了一大步。起初我认为每次注册都会产生排队的全部成本，但后来我意识到，当然一个函数只能实例化一次，因此在实例化方面我们支付与线性搜索相同的价格，但是递归深度变为对数。如果我有时间的话，我将发布一个完整的解决方案，消除问题 5-7。不过，看看是否可以在恒定的递归深度下完成它仍然很好，而且最好是实例化的数量与调用的数量成线性关系（a-la boost 解决方案）。

编辑 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 进行线性搜索，这会导致实例化数量过多。

解决方案是让f调用g。这依次调用 g 和 g，后者又调用 g、g、g 和 >g 等等。当然，您将在 REGISTER() 内专门化 g<__LINE__, __LINE__>。

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

Answer 2

也许是这样的：

template<typename T>
struct register_struct {
    virtual void operator()() = 0;
    register_struct();
    register_struct *pNext;
};

template<typename T>
struct registry {
    static register_struct<T> *chain;
    static void walk() {
        register_struct<T> *p = chain;
        while (p) {
            (*p)();
            p = p->pNext;
        }
    }
};

template<typename T>
register_struct<T> *registry<T>::chain = NULL;

template<typename T>
register_struct<T>::register_struct()
{
    pNext = registry<T>::chain;
    registry<T>::chain = this;
}

#define DECL_REGISTRY(name) \
    struct tag_##name { } ; \
    void name() { registry<tag_##name>::walk(); }

#define JOIN_EXPAND(x, y) JOIN_EXPAND_2(x, y)
#define JOIN_EXPAND_2(x, y) x ## y

// Invoke REGISTER_PRINT at file scope!
#define REGISTER_PRINT(name, text) \
    namespace { \
    static struct : public register_struct<tag_##name> { \
        void operator()() { \
            std::cout << text << std::endl; \
        } \
    } JOIN_EXPAND(rs_##name##_, __LINE__); \
    }

DECL_REGISTRY(foo);

REGISTER_PRINT(foo, "hello")
REGISTER_PRINT(foo, "world")

int main() {
    foo();
    return 0;
}

这将解决递归实例化问题，但您仍然仅限于每行一个注册。然而，由于注册是在文件范围内，所以这应该（希望如此！）不是什么问题。

请注意，如果您希望在 main() 之前调用这些函数，那么使用它是不安全的 - 您必须允许静态构造函数在使用它之前完成。

Answer 3

我曾经做过类似的事情，它只实例化了有限数量的专业化。目标是将所有专业化聚合到一个指针数组中，并通过枚举使用单一方法访问它们，但您可以轻松地将其适应您类似的（正如我认为的）需求。

#include <iostream>

using namespace std;

class I {
public:
    virtual ~I() {};

    virtual void P(int index) = 0;

    enum Item {
        Item0,
        Item1,
        Item2,
        Item3,
        Item4,
        ItemNum
    };
};


template <class T> class A: public I {
public:
    A() {
        Unroll<A<T>, ItemNum> tmp (m_F);
    }
    virtual ~A() {
    }

    void P(int index) { (this->*m_F[index])(); }

protected:
    typedef void (A<T>::*F)();
    F m_F[ItemNum];

    template <int N> void p() { cout << "default!" << endl; }

    template <class W, int C> struct Unroll
    {
        Unroll(typename W::F * dest)
        {
            dest[C-1] = & W::template p<C-1>;
            Unroll<W, C-1> u(dest);
        }
    };
};

template <class T> template <class W> struct A<T>::Unroll<W, 0>
{ public: Unroll(typename W::F * dest) {} };

class B: public A<B>
{
public:

};

template <> template <> void A<B>::p<A<B>::Item1>() { cout << 1 << endl; }
template <> template <> void A<B>::p<A<B>::Item2>() { cout << 2 << endl; }
template <> template <> void A<B>::p<A<B>::Item4>() { cout << "it hacking works!" << endl; }


int main()
{
    I *a = new B;
    for (int i = 0; i < I::ItemNum; ++i) a->P(i);
    return 0;
}

Answer 4

这是一个将递归限制为实际注册的函数数量的解决方案。我没有使用 __LINE__ 作为 id，而是使用 BOOST_PP_COUNTER，这是预处理器可用的递增计数器。

技巧是您不能增加宏内的计数器，因为增量是通过包含头文件来完成的。因此，我也必须依赖文件包含，因此需要两行而不是一行来注册消息（一行用于定义消息，一行用于实际注册消息）。

这是代码：

//register.hpp

#include <boost/preprocessor/slot/counter.hpp>

// general template function, not defined
template <unsigned int ID>
void f();

// base case, to stop recursion
template <>
void f<0>() {}


// macro to "hide" the name of the header to include (which should be in a
// "hidden" folder like "detail" in Boost 
#define REGISTER() "actually_register_msg.hpp"

---

//actually_register_msg.hpp

#include <boost/preprocessor/stringize.hpp>

// increment the counter
#include BOOST_PP_UPDATE_COUNTER()

template<>
inline void f< BOOST_PP_COUNTER >()
{
    std::cout << BOOST_PP_STRINGIZE( MSG_TO_REGISTER ) << std::endl;
    f< BOOST_PP_COUNTER - 1 >(); // call previously registered function
}

// to avoid warning and registering multiple times the same message
#undef MSG_TO_REGISTER

// id of the last registered function
#define LAST_FUNCTION_ID BOOST_PP_COUNTER

---

// main.cpp

#define MSG_TO_REGISTER message 1
#include REGISTER()

#define MSG_TO_REGISTER message 2
#include REGISTER()

#define MSG_TO_REGISTER message 3
#include REGISTER()

int main()
{
    f< LAST_FUNCTION_ID >();
}

与您的代码一样，此打印

message 3
message 2
message 1

当然，注册调用有点不太漂亮（一个 #define 和一个 #include 而不是单个宏调用），但是您可以避免很多不必要的模板实例化。