Выполнение функции времени компиляции C

#c #template-meta-programming

#c #шаблон-метапрограммирование

Вопрос:

В моем коде есть строковые теги, которые преобразуются в числа и используются для поиска значений в структуре значений тегов.

У меня есть что-то вроде этого:

 void foo()
{
    type value = search("SomeTag");
}

Где поиск определяется следующим образом:

 type search(const char* tag)
{
    return internal_search(toNumber(tag));
}

Поскольку во время компиляции тег all time является постоянным, я хочу удалить вызов, который преобразует тег в число из функции поиска. Я знаю, что во время компиляции можно выполнить некоторые простые функции, используя шаблоны (http://en.wikipedia.org/wiki/Compile_time_function_execution ), но я не знаю точно, как выполнить итерацию по строке, заканчивающейся нулем, и сохранить промежуточные значения в шаблоне. Не могли бы вы привести простой пример, который повторяет строку, заканчивающуюся нулем, и добавляет символы в общедоступную переменную, пожалуйста?

1. В качестве альтернативы, возможно, toNumber можно было бы сохранить карту всех тегов, которые он видел, и их числовое значение, чтобы вам приходилось оплачивать стоимость преобразования только один раз за тег? Это не так эффективно, как использование языка шаблонов для выполнения оценки во время компиляции, но я бы поспорил, что таким образом код будет намного более читаемым и поддерживаемым.

2. TTBOMK вы не можете выполнять итерации по строкам во время компиляции.

3. @aroth Я думаю, что функция ToNumber работает быстрее, чем поиск, даже если бы я использовал поиск log2.

4. @sbi: Ты вроде как можешь; взгляни на boost::mpl::string. Но вы должны писать 'all ','your',' str','ings' так (используя тот факт, что a char на самом деле может состоять из 4 символов).

5. Я вижу, на самом деле это не числовые строки. Почему бы не использовать препроцессор и общий заголовочный файл? #define TAG_SPEED 12414121 Вы могли бы сгенерировать этот файл непосредственно из базы данных.

Ответ №1:

Звучит так, как будто вы хотите повысить.MPL boost::mpl::string . Было бы более или менее тривиально написать метафункцию для преобразования mpl::string в целочисленный тип во время компиляции с использованием mpl::fold (или не выполнить компиляцию, если строковый литерал не представляет допустимое целочисленное значение).

Редактировать:

Я не совсем уверен, что вы ищете, поэтому здесь фактически два разных ответа в зависимости от интерпретации:

ЕСЛИ то, что вы ищете, — это преобразование строки во время компиляции в целочисленное значение (например, so "425897" может быть распознано как целочисленная константа 425897 во время компиляции), тогда можно использовать Boost.MPL, как я и предлагал:

 #include <cstddef>
#include <boost/type_traits/is_integral.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/is_signed.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/char.hpp>
#include <boost/mpl/contains.hpp>
#include <boost/mpl/end.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/find_if.hpp>
#include <boost/mpl/fold.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/identity.hpp>
#include <boost/mpl/integral_c.hpp>
#include <boost/mpl/minus.hpp>
#include <boost/mpl/negate.hpp>
#include <boost/mpl/next.hpp>
#include <boost/mpl/not.hpp>
#include <boost/mpl/pair.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/pop_front.hpp>
#include <boost/mpl/push_back.hpp>
#include <boost/mpl/reverse_fold.hpp>
#include <boost/mpl/size_t.hpp>
#include <boost/mpl/string.hpp>
#include <boost/mpl/times.hpp>
#include <boost/mpl/vector.hpp>

namespace details
{
    namespace mpl = boost::mpl;

    typedef mpl::vector10<
        mpl::char_<'0'>, mpl::char_<'1'>, mpl::char_<'2'>, mpl::char_<'3'>,
        mpl::char_<'4'>, mpl::char_<'5'>, mpl::char_<'6'>, mpl::char_<'7'>,
        mpl::char_<'8'>, mpl::char_<'9'>
    > valid_chars_t;

    template<typename IntegralT, typename PowerT>
    struct power_of_10;

    template<typename IntegralT, std::size_t Power>
    struct power_of_10<IntegralT, mpl::size_t<Power> > : mpl::times<
        power_of_10<IntegralT, mpl::size_t<Power - 1u> >,
        mpl::integral_c<IntegralT, 10>
    > { };

    template<typename IntegralT>
    struct power_of_10<IntegralT, mpl::size_t<1u> >
        : mpl::integral_c<IntegralT, 10>
    { };

    template<typename IntegralT>
    struct power_of_10<IntegralT, mpl::size_t<0u> >
        : mpl::integral_c<IntegralT, 1>
    { };

    template<typename IntegralT, typename StringT>
    struct is_negative : mpl::and_<
        boost::is_signed<IntegralT>,
        boost::is_same<
            typename mpl::front<StringT>::type,
            mpl::char_<'-'>
        >
    > { };

    template<typename IntegralT, typename StringT>
    struct extract_actual_string : mpl::eval_if<
        is_negative<IntegralT, StringT>,
        mpl::pop_front<StringT>,
        mpl::identity<StringT>
    > { };

    template<typename ExtractedStringT>
    struct check_valid_characters : boost::is_same<
        typename mpl::find_if<
            ExtractedStringT,
            mpl::not_<mpl::contains<valid_chars_t, mpl::_> >
        >::type,
        typename mpl::end<ExtractedStringT>::type
    > { };

    template<typename ExtractedStringT>
    struct pair_digit_with_power : mpl::first<
        typename mpl::reverse_fold<
            ExtractedStringT,
            mpl::pair<mpl::vector0<>, mpl::size_t<0> >,
            mpl::pair<
                mpl::push_back<
                    mpl::first<mpl::_1>,
                    mpl::pair<mpl::_2, mpl::second<mpl::_1> >
                >,
                mpl::next<mpl::second<mpl::_1> >
            >
        >::type
    > { };

    template<typename IntegralT, typename ExtractedStringT>
    struct accumulate_digits : mpl::fold<
        typename pair_digit_with_power<ExtractedStringT>::type,
        mpl::integral_c<IntegralT, 0>,
        mpl::plus<
            mpl::_1,
            mpl::times<
                mpl::minus<mpl::first<mpl::_2>, mpl::char_<'0'> >,
                power_of_10<IntegralT, mpl::second<mpl::_2> >
            >
        >
    > { };

    template<typename IntegralT, typename StringT>
    class string_to_integral_impl
    {
        BOOST_MPL_ASSERT((boost::is_integral<IntegralT>));

        typedef typename extract_actual_string<
            IntegralT,
            StringT
        >::type ExtractedStringT;
        BOOST_MPL_ASSERT((check_valid_characters<ExtractedStringT>));

        typedef typename accumulate_digits<
            IntegralT,
            ExtractedStringT
        >::type ValueT;

    public:
        typedef typename mpl::eval_if<
            is_negative<IntegralT, StringT>,
            mpl::negate<ValueT>,
            mpl::identity<ValueT>
        >::type type;
    };
}

template<typename IntegralT, typename StringT>
struct string_to_integral2
    : details::string_to_integral_impl<IntegralT, StringT>::type
{ };

template<typename IntegralT, int C0, int C1 = 0, int C2 = 0,
    int C3 = 0, int C4 = 0, int C5 = 0, int C6 = 0, int C7 = 0>
struct string_to_integral : string_to_integral2<
    IntegralT,
    boost::mpl::string<C0, C1, C2, C3, C4, C5, C6, C7>
> { };

Использование будет выглядеть следующим образом:

 type search(int tag) { /*impl... */ }

void foo()
{
    type value = search(string_to_integral<int, '4258','97'>::value);
}

// OR, if you still want to maintain the separation
// between `search` and `internal_search`

type internal_search(int tag) { /*impl... */ }

template<typename TagStringT>
type search()
{
    return internal_search(string_to_integral2<int, TagStringT>::value);
}

void foo()
{
    typedef boost::mpl::string<'4258','97'> tag_t;
    type value = search<tag_t>();
}

Поддержка отрицательных чисел реализована, поддержка обнаружения переполнения — нет (но ваш компилятор, вероятно, выдаст предупреждение).

ЕСЛИ то, что вы ищете, — это сопоставление строки с целым значением во время компиляции (например, so "SomeTag" может быть распознано как целочисленная константа 425897 во время компиляции), затем Boost.MPL по-прежнему решает проблему, но все сопоставления строки с целым значением должны быть известны во время компиляции и зарегистрированы централизованно:

 #include <boost/type_traits/is_same.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/integral_c.hpp>
#include <boost/mpl/map.hpp>
#include <boost/mpl/pair.hpp>
#include <boost/mpl/string.hpp>
#include <boost/mpl/void.hpp>

namespace details
{
    namespace mpl = boost::mpl;

    typedef mpl::map<
        mpl::pair<
            mpl::string<'Some','Tag'>,
            mpl::integral_c<int, 425897>
        >,
        mpl::pair<
            mpl::string<'Some','Othe','rTag'>,
            mpl::integral_c<int, -87>
        >,
        mpl::pair<
            mpl::string<'AnUn','sign','edTa','g'>,
            mpl::integral_c<unsigned, 7u>
        >
    > mappings_t;

    template<typename StringT>
    struct map_string_impl
    {
        typedef typename mpl::at<
            mappings_t,
            StringT
        >::type type;
        BOOST_MPL_ASSERT_NOT((boost::is_same<type, mpl::void_>));
    };
}

template<typename StringT>
struct map_string2 : details::map_string_impl<StringT>::type { };

template<int C0, int C1 = 0, int C2 = 0, int C3 = 0,
    int C4 = 0, int C5 = 0, int C6 = 0, int C7 = 0>
struct map_string : map_string2<
    boost::mpl::string<C0, C1, C2, C3, C4, C5, C6, C7>
> { };

Использование будет выглядеть следующим образом:

 type search(int tag) { /*impl... */ }

void foo()
{
    type value = search(map_string<'Some','Tag'>::value);
}

// OR, if you still want to maintain the separation
// between `search` and `internal_search`

type internal_search(int tag) { /*impl... */ }

template<typename TagStringT>
type search()
{
    return internal_search(map_string2<TagStringT>::value);
}

void foo()
{
    typedef boost::mpl::string<'Some','Tag'> tag_t;
    type value = search<tag_t>();
}

mappings_t это то, что необходимо отредактировать, чтобы сохранить ваши сопоставления строки с целым значением, и, как показано, отображаемые целые значения не обязательно должны быть одного и того же базового типа.

В любом случае, поскольку сопоставление выполняется во время компиляции, search / internal_search (тот, у которого реальная реализация принимает int ) можно заставить принимать целочисленное значение в качестве параметра шаблона, а не в качестве параметра функции, если это имеет смысл для его реализации.

Надеюсь, это ответит на ваши вопросы.

1. Я бы не стал заходить так далеко, утверждая, что это тривиально (по крайней мере, не для меня), но это можно сделать.

2. Пожалуйста, дайте мне реализацию. Это ответ, за который проголосовали больше всего, но я думаю, что это невозможно сделать, как говорили другие. Я проголосую, когда получу полный ответ.

3. @Felics : Отредактировано с использованием полных реализаций. Я привел два подхода, поскольку мне не ясно, что вы на самом деле ищете…

4. Мне нужно сопоставить строку с int, что-то вроде «SomeTag» с 1234567, и вы отвечаете неправильно, потому что вы сопоставляете int с int (‘abcd’ — это int, а не string)

5. @Felics : Определение строки таково: последовательность символов. Хотя 'Some' прямым типом может быть int , семантически он отображается через boost::mpl::string в виде последовательности символов, так что фактически это строка. На самом деле вы хотите сказать, что вам не нравится синтаксис 'Some','Tag' vs. "SomeTag" , который вы могли бы определить за дни до того, как я набрал код для вас, и избавил меня от хлопот; но на самом деле это обе строки. В будущем прочитайте документы, на которые вы ссылаетесь, прежде чем тратить чужое время на запрос кода, а затем банально отклонять его.

Ответ №2:

Вы не можете оперировать строковыми литералами во время компиляции, поэтому то, что вы хотите, неосуществимо так, как вы предложили. Однако, если вы планируете обрабатывать эти строки во время компиляции, то это означает, что вы знаете все строки во время компиляции, и из этого вы могли бы прийти к приемлемым приближениям к тому, что вы хотите.

Приведенный вами код подразумевает, что генерация числа (назовем это хэшем) вызывается каждый раз, когда кто-то ищет тег. Было бы приемлемо свести это к одному вызову? Если это так, вы могли бы определить константы и использовать их вместо строк:

 const int SomeTag       = toNumber("SomeTag"      ); 
const int SomeOtherTag  = toNumber("SomeOtherTag" ); 
const int YetAnotherTag = toNumber("YetAnotherTag"); 
// ...

Затем просто замените все вхождения search("SomeTag") на search(SomeTag) .

При наличии большого количества тегов ввод приведенных выше может быть очень утомительным, и в этом случае может помочь макрос:

 #define DEFINE_TAG(Tag_) const int Tag_ = toNumber(#Tag_); 

DEFINE_TAG(SomeTag); 
DEFINE_TAG(SomeOtherTag); 
DEFINE_TAG(YetAnotherTag); 
// ... 

#undef DEFINE_TAG

1. Это может быть хорошей идеей, потому что это решает большую проблему из enum (мне не нужно включать заголовок во все файлы проекта и перекомпилировать его каждый раз, когда я добавляю новый тег) и из local defines (конфликты тегов). Единственной проблемой здесь является переопределение одного и того же тега в разных файлах и ошибки компоновщика, но.. это можно решить с помощью static const int вместо const int . Спасибо!

2. Итак, вы используете строки, потому что не хотите, чтобы перечисление включалось повсюду? Я полагаю, вы знаете, что на самом деле вы обмениваете производительность во время компиляции на безопасность во время выполнения? Действительно ли это того стоит? Что я делал в прошлом в таких случаях, так это разбивал пространство значений (в вашем случае: enum значения) на независимые блоки (вам пришлось бы использовать const int вместо этого), которые определены в разных заголовках. Тогда вы включаете только один заголовок, который вас интересует, и на него не влияют изменения в других заголовках.

Ответ №3:

Если строковый литерал известен во время компиляции, то, вероятно, нет причин использовать его в качестве строкового литерала. Вы можете использовать перечисление или именованные целые константы.

Если строка передается в функцию поиска с помощью переменной и она неизвестна во время компиляции, то нет никакого способа выполнить toNumber() результат во время компиляции. Тогда хорошим решением является использование какого-либо словаря (например std::map<std::string, int> )

1. Как я уже говорил ранее, функция ToNumber выполняется быстрее, чем поиск.

2. Я думаю, что первый абзац здесь является ключевым. Чтобы сделать это во время компиляции, вам нужно было бы знать все возможные строки во время компиляции. И когда они у вас есть, нет причин не использовать для них символьные константы.

Ответ №4:

Хотя это не время компиляции, я думаю, что это достаточно быстро для вас;

 void foo()
{
    const static auto someTagN = toNumber("SomeTag");
    type value = internal_search(someTagN );
}

1. Это будет выполняться не во время компиляции, а во время глобального построения, поэтому это продлит запуск программы.

2. Это то, чего я хочу избежать, преобразование строк во время выполнения. У меня нет нескольких тегов, которые используются много раз, у меня есть разные теги, которые используются только один или несколько раз.

3. @Jan Hudec Он будет запущен при первом вызове foo, но если foo будет вызван один раз, это не окажет эффекта оптимизации, потому что тег будет преобразован один раз во время выполнения, как это было раньше, и у меня будет глобальная память, заполненная ненужными номерами, которые больше не будут использоваться.

4. @Jan: На самом деле, локальные static переменные инициализируются, когда выполнение программы передает их код инициализации в первый раз. Простым английским языком: someTagN инициализируется при foo() первом вызове.

Ответ №5:

Я знаю, что это, вероятно, не модно, но вы можете сгенерировать хэш-таблицу заранее. Мне нравится использовать gperf для генерации там сантехники.

Я знаю, знаю. Вы хотели что-то, чтобы сделать компиляцию более длительной… Просто говорю 🙂

1. Это не проблема, для отладки это может быть #define X (тег) ToNumber (тег), а для выпуска #define X (тег) someTemplate<тег>::number. Это для оптимизации времени выполнения, и время компиляции не имеет значения.

2. Я наполовину пошутил, я не беспокоюсь о времени компиляции 🙂

3. Время компиляции — большая проблема. В моем текущем проекте полная перестройка может занять несколько часов, и это очень большая проблема 🙂

Ответ №6:

Не уверен, что вы сможете. Мал ли список возможных тегов? Даже если нет, является ли оно маленьким большую часть времени. Если это так, вы можете использовать специализацию шаблона для подмножества тегов

 template<char *tag> 
int toNumber() {
    return toNumber(tag);
}

template<>
int toNumber<"0">() {
     return 0;
}

template<>
int toNumber<"1">() {
     return 1;
}

(предостережения: мой синтаксис специализации может быть неправильным, и я понятия не имею, работает ли это для символа *)

1. Шаблоны не принимают символьные литералы, только адреса констант. Таким образом, вам пришлось бы создавать const char * const переменные для строк и передавать эти константы в шаблоны.

2. Строковые литералы являются значениями lvalues и, следовательно, не могут быть константами времени компиляции. Однако символьные литералы действительно могут быть константами времени компиляции.