Подтвердить что ты не робот

Исключение рекурсивного экземпляра шаблона в С++

Я хочу определить макрос, который можно вызвать в разных местах (в области файлов), чтобы создавать функции, которые что-то делают. (В приведенном ниже примере функции просто печатают сообщение, но, конечно, мое реальное намерение состоит в том, чтобы сделать некоторые другие полезные вещи.) Проблема в том, что мне нужна некоторая "менеджерская" функция (в моем примере это будет просто 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.
  • Увеличено время компиляции из-за рекурсивных экземпляров.
  • Если все "dummy" экземпляры f все отложены, глубина стека вызовов во время выполнения будет равна количеству строк между START_REGISTRATION; и f<__LINE__>(); в менеджере.
  • Наложение кода: если только "dummy" экземпляры f не вставлены, количество экземпляров будет таким же большим.
  • Чрезмерная глубина рекурсивности инстанцирования, вероятно, попадет в предел компилятора (по умолчанию 500 в моей системе).

Вопросы 1-4 Я не против. Проблема 5 может быть устранена, если каждая функция возвращает указатель на предыдущую, и если менеджер использует эти указатели для вызова функций итеративно, а не для вызова друг друга. Выпуск 6 можно устранить, создав аналогичную конструкцию шаблона класса, которая может вычислять для каждого вызова REGISTER, какая функция была создана в предыдущем вызове и, таким образом, только создала экземпляр функций, которые действительно что-то делают. Затем избыточное инстанцирование будет смещено от шаблона функции к шаблону класса, но экземпляры класса будут облагать только компилятором; они не будут вызывать генерации кода. Итак, моя настоящая проблема - проблема 7, и возникает вопрос: существует ли способ реструктурировать такие вещи, чтобы компилятор делал экземпляры итеративно, а не рекурсивно. Я также открыт для разных подходов (кроме тех, которые связаны с статическими объектами). Одним простым решением является объединение всех регистраций вместе непосредственно перед менеджером (или добавление макроса STOP_REGISTRATION для завершения блокировки регистраций), но это может привести к нарушению значительной части моей цели (регистрации материала рядом с кодом, который его определяет).

Изменить: Были некоторые интересные предложения, но я боюсь, что не понимаю, что я надеюсь достичь. Меня действительно интересуют две вещи: решение поставленной задачи (т.е. Не статика, одна строка для регистрации, никаких дополнительных изменений при добавлении/удалении регистраций, и, хотя я пренебрег этим сказать, только стандартный С++ --- следовательно, без повышения). Как я уже сказал в комментариях ниже, мой интерес более теоретический по своей природе: я надеюсь изучить некоторые новые методы. Следовательно, я бы очень хотел сосредоточиться на реструктуризации, поэтому рекурсия устраняется (или, по крайней мере, сокращается) или находит другой подход, который удовлетворяет ограничениям, изложенным выше.

Изменить 2: Решение MSalter - большой шаг вперед. Сначала я думал, что каждая регистрация приведет к полной стоимости строк до него, но потом я понял, что, конечно, функция может быть создана только один раз, поэтому с точки зрения экземпляров мы платим ту же цену, что и в линейном поиске, но глубина рекурсии становится логарифмической. Если я подойду к нему, я опубликую полное решение, устраняющее проблемы 5-7. Тем не менее, было бы неплохо увидеть, можно ли это сделать с постоянной глубиной рекурсии и, что лучше, с количеством экземпляров, линейным по количеству вызовов (a-la для ускорения).

Изменить 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();
}
4b9b3361

ОТВЕТЫ

Ответ 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> ectetera. Вы, конечно, специализируетесь на g<__LINE__, __LINE__> внутри REGISTER().

Мгновенное создание f<65536> по-прежнему вызывает 65536 шаблонных экземпляров (вы эффективно проверяете все предыдущие строки 65536), но глубина рекурсии ограничена логом (65536) или 16 уровнями. Это выполнимо.

Ответ 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() - вы должны разрешить статическим конструкторам до его использования.

Ответ 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;
}

Ответ 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 вместо одного вызова макроса), но вы избегаете множества ненужных экземпляров шаблонов.