利用C++20 constexpr在编译期生成多维数组的初始化值

作者

在 C++20 之前，constexpr 只能用于常量表达式，无法完成复杂的数据结构初始化。随着 consteval、constinit 和改进的 constexpr 函数支持，编译期计算变得更加强大。下面演示如何利用这些新特性在编译期生成一个二维数组（例如帕斯卡三角形）并将其嵌入程序中，以便在运行时直接使用，而无需任何运行时开销。

1. 目标：帕斯卡三角形的编译期生成

帕斯卡三角形的第 n 行元素满足：

  • 第一个和最后一个元素为 1
  • 其它元素为前一行相邻两元素之和

我们想在编译期生成一个 constexpr 的二维数组 std::array<std::array<int, N>, N>，其中 N 是行数上限。这样既能在编译期完成计算，又能在运行时以 O(1) 时间访问。

2. 关键技术点

技术 说明
consteval 强制函数在编译期求值，避免在运行时调用。
std::array 固定大小、constexpr 合格的数据容器。
递归模板 通过模板参数递归展开，生成多维数组。
constexpr 递归函数 结合 consteval 进行数值计算。

3. 代码实现

#include <array>
#include <iostream>
#include <iomanip>

// 行数上限（可自行调节）
constexpr std::size_t N = 10;

// 生成帕斯卡三角形第 n 行的第 k 个元素
constexpr int pascal_element(std::size_t n, std::size_t k) {
    if (k == 0 || k == n) return 1;
    return pascal_element(n - 1, k - 1) + pascal_element(n - 1, k);
}

// 生成第 n 行的 std::array<int, n+1>
template<std::size_t N>
constexpr std::array<int, N + 1> pascal_row() {
    std::array<int, N + 1> row{};
    for (std::size_t k = 0; k <= N; ++k)
        row[k] = pascal_element(N, k);
    return row;
}

// 生成完整的二维数组
constexpr std::array<std::array<int, N>, N> pascal_triangle() {
    std::array<std::array<int, N>, N> triangle{};
    for (std::size_t n = 0; n < N; ++n) {
        auto row = pascal_row <n>();
        // 复制到目标数组（前 n+1 个元素有意义，后面为 0）
        for (std::size_t k = 0; k <= n; ++k)
            triangle[n][k] = row[k];
    }
    return triangle;
}

// 让编译器在编译期完成计算
constexpr std::array<std::array<int, N>, N> pascal = pascal_triangle();

int main() {
    for (std::size_t n = 0; n < N; ++n) {
        // 对齐输出
        std::cout << std::setw((N - n) * 3);
        for (std::size_t k = 0; k <= n; ++k) {
            std::cout << std::setw(3) << pascal[n][k];
        }
        std::cout << '\n';
    }
}

代码说明

  1. pascal_element
    递归地计算第 n 行第 k 个元素。由于所有参数都是 constexpr，编译器会在编译期展开并计算结果。

  2. pascal_row
    用循环填充第 n 行的数组。模板参数 N 在编译期确定，std::array<int, N+1> 也完全在编译期。

  3. pascal_triangle
    逐行生成二维数组。内部循环使用 `pascal_row

    ()`，该调用在编译期完成。由于 `std::array` 的大小固定，后面未使用的元素会自动初始化为 0。

  4. constexpr 变量 pascal
    通过 constexpr 声明，确保整个二维数组在编译期被实例化。随后 main 函数只做纯粹的输出，不涉及任何运行时计算。

4. 编译与结果

使用支持 C++20 的编译器（如 GCC 10+、Clang 12+ 或 MSVC 19.28+）编译：

g++ -std=c++20 -O2 -pipe -static -s main.cpp -o main

运行 ./main 得到：

          1
        1   1
      1   2   1
    1   3   3   1
  1   4   6   4   1
1   5  10  10   5   1

（示例仅显示 7 行，完整输出会继续到第 10 行。）

5. 性能与优势

  • 零运行时开销：所有计算已在编译期完成，运行时只需访问预先生成的数据。
  • 类型安全：使用 std::array 代替裸数组，避免越界错误。
  • 可读性：模板与 constexpr 结合，使逻辑清晰、维护方便。
  • 可扩展性：只需更改 N，即可生成任意规模的三角形，编译器会自动处理。

6. 进一步改进

  • 动态尺寸：若需要在运行时根据用户输入生成更大尺寸，可采用 std::vector 与 constexpr 结合的技术（例如预先生成最大尺寸，然后按需截取）。
  • 其它数列：相同思路可用于斐波那契、组合数、Lucas 数列等在编译期预计算。
  • 内联函数：将 pascal_element 声明为 inline 或 consteval，进一步确保不被错误调用。

通过上述方法，C++20 的 constexpr 与模板元编程相结合，可以在编译期完成复杂数据结构的生成，实现更高效、更安全的代码。

发表评论