用C++实现余弦查找表

Question

这里有一段代码，应该会生成一个2048个元素的余弦查找表，代码来自于顾昌毅的《嵌入式系统构建》一书。

#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++的基础有一定了解。由于书中从未真正解释过，我对以下代码片段的实现方式以及下面这段话的实现方式（也是从书中取出的）非常困惑：

“模板特化和类继承将帮助我们摆脱constexpr函数仅能将返回状态作为其函数体的限制，这就是当表格大小增加时必须手动填充查找表的原因。”

如果有任何帮助，我将不胜感激。我理解constexpr模板部分将生成实际值，但我确实不知道struct正在做什么以及如何构建最终数组。

- xtrinch

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>会匹配原始模板的以下偏特化：

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

- Akira