Косинусная таблица поиска с С++

Вот фрагмент, который должен генерировать таблицу косинусного поиска из 2048 элементов, взятую из книги "Встроенные системы" Changyi Gu:

#include <cmath>
#include <array>

template<typename T>
constexpr T look_up_table_elem (int i) {
    return {};
}

template<>
constexpr uint16_t look_up_table_elem (int i) {
    return round (cos (static_cast <long double>(i) / 2048 * 3.14159 / 4) * 32767);
}


template<typename T, int... N>
struct lookup_table_expand{};

template<typename T, int... N>
struct lookup_table_expand<T, 1, N...> {
    static constexpr std::array<T, sizeof...(N) + 1> values = {{ look_up_table_elem<T>(0), N... }};
};

template<typename T, int L, int... N> 
struct lookup_table_expand<T, L, N...>: lookup_table_expand<T, L-1, look_up_table_elem<T>(L-1), N...> {};


template<typename T, int... N>
constexpr std::array<T, sizeof...(N) + 1> lookup_table_expand<T, 1, N...>::values;

const std::array<uint16_t, 2048> lookup_table = lookup_table_expand<uint16_t, 2048>::values;

Примечание: написано для С++ 11.

Я родом из прежде всего Java-мира, и я хорошо понимаю основы С++. Поскольку в книге она действительно не объяснялась, я действительно смущен тем, как этот сниппет справляется с задачей, и как она достигает следующего (также взятого из книги):

Специализация шаблона и наследование классов помогут нам избавиться от ограничения, что функция constexpr может иметь только состояние возврата в качестве своего тела функции, поэтому таблица поиска должна быть заполнена вручную при увеличении размера таблицы.

Любая помощь будет принята с благодарностью. Я понимаю часть с шаблоном constexpr, которая будет генерировать фактическое значение, но я действительно не уверен, что делает структура и как создается последний массив.

Ответ 1

Для начала рассмотрим следующую строку:

const std::array<uint16_t, 2048> lookup_table =
        lookup_table_expand<uint16_t, 2048>::values;

Там lookup_table будет скопирован из массива values, заключенного внутри структуры lookup_table_expand<uint16_t, 2048>. Это просто, теперь давайте посмотрим, что будет делать при создании шаблона.

У нас есть первичный шаблон с пустым телом (там, где было бы достаточно объявления вперед, мы не будем использовать его в этой форме):

template<typename T, int... N>
struct lookup_table_expand {
};

lookup_table_expand<uint16_t, 2048> будет соответствовать следующей частичной специализации основного шаблона:

template<typename T, int L, int... N> 
struct lookup_table_expand<T, L, N...> :
        lookup_table_expand<T, L - 1, look_up_table_elem<T>(L - 1), N...> {
};

Поскольку наследование вышеприведенного шаблона будет рекурсивно создаваться с растущим шаблоном список параметров, пока текущий шаблон не будет соответствовать следующей частичной специализации первичного шаблона:

template<typename T, int... N>
struct lookup_table_expand<T, 1, N...> {
    static constexpr std::array<T, sizeof...(N) + 1> values = {{
        look_up_table_elem<T>(0), N...
    }};
};

Соответствие шаблону выше произойдет, когда L станет 1 в рекурсии. В этот момент список параметров шаблона (N...) будет содержать результаты вызова следующей функции со значениями от 1 до 2047:

constexpr uint16_t look_up_table_elem(int i) {
    return round(cos(static_cast<long double>(i) / 2048 * 3.14159 / 4) * 32767);
}

Здесь будет инициализирован единственный член шаблона lookup_table_expand (values) со значениями списка параметров шаблона.

Обратите внимание, что values является элементом данных static constexpr, который может быть инициализирован в объявлении class/struct, поэтому следующая строка не нужна:

template<typename T, int... N>
constexpr std::array<T, sizeof...(N) + 1> lookup_table_expand<T, 1, N...>::values;

Массив values наследуется lookup_table_expand<uint16_t, 2048>, поэтому в конце вы можете получить к нему доступ из этой структуры.