用 C++ 进行余弦查找 table

Question

这是一个应该生成 2048 个元素的余弦查找 table 的片段，摘自顾长义的《构建嵌入式系统》一书：

#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;

注意：为 C++11 编写。

我来自 Java 世界，我对 C++ 的基础知识有一定的了解。由于书中从未真正解释过，我真的很困惑这段代码是如何完成任务的，以及它是如何实现以下内容的（也从书中摘录）：

Template specialization and class inheritance will help us get rid of the restriction that constexpr function can only have return state as its function body, which is why the lookup table has to be manually populated when the table size increases.

如有任何帮助，我们将不胜感激。我理解带有 constexpr 模板的部分会生成实际值，但我真的不确定结构在做什么以及最终数组是如何构造的。

Answer 1

首先让我们看一下下面一行：

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

lookup_table 将从 lookup_table_expand<uint16_t, 2048> 结构中保存的 values 数组复制构造。这很简单，现在让我们看看模板实例化完成后会发生什么。

我们有一个主体为空的主模板（前向声明就足够了，我们不会以这种形式使用它）：

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

lookup_table_expand<uint16_t, 2048> 将匹配主模板的以下 partial specialization：

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...> {
};

因为继承，上面的模板将使用不断增长的模板递归实例化parameter list，直到当前模板与主模板的以下部分特化不匹配：

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> 继承，因此最终您可以从该结构访问它。

用 C++ 进行余弦查找 table

Cosine lookup table with c++

c++

c++11

templates

lookup-tables