利用 C++17 constexpr 进行编译期数组排序

作者

在 C++17 之前，constexpr 函数只能返回基本类型或者 POD（Plain Old Data）结构，且内部只能使用 if、switch、循环等限制性语句，导致在编译期对复杂数据结构进行操作非常困难。随着 C++20 的到来，constexpr 逐渐解放，被允许包含更复杂的语句、递归、甚至 try-catch，这为编译期计算打开了大门。下面我们用 C++17 的语法演示如何在编译期实现一个简单的数组排序，并通过 static_assert 在编译时验证结果。

1. 目标

给定一个固定大小的整数数组 std::array<int, N> arr，我们想在编译期把它升序排列，返回一个新的 std::array<int, N>。我们还想在编译时对排列结果进行断言，确保排序算法正确。

2. 思路

  • 由于 constexpr 函数在 C++17 中只能使用循环和条件判断，不能递归，故我们采用“冒泡排序”算法，它可以通过循环实现。
  • 为了在编译期返回一个新的数组，我们在 constexpr 函数里创建一个临时数组 std::array<int, N> sorted 并在循环中对其进行排序，然后返回。
  • 通过 static_assert，我们可以在编译期对返回的结果与期望的已排序数组进行比较，验证排序逻辑。

3. 代码实现

#include <array>
#include <cstddef>
#include <iostream>

// 1. constexpr 冒泡排序
template<std::size_t N>
constexpr std::array<int, N> bubble_sort(const std::array<int, N>& input) {
    std::array<int, N> arr = input; // 复制到局部数组，方便修改
    // 冒泡排序
    for (std::size_t i = 0; i < N - 1; ++i) {
        for (std::size_t j = 0; j < N - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr; // 返回排好序的数组
}

// 2. 比较两个 std::array 是否相等
template<std::size_t N>
constexpr bool arrays_equal(const std::array<int, N>& a, const std::array<int, N>& b) {
    for (std::size_t i = 0; i < N; ++i) {
        if (a[i] != b[i]) return false;
    }
    return true;
}

int main() {
    // 原始数组
    constexpr std::array<int, 6> unsorted = {5, 3, 8, 1, 4, 2};
    // 编译期排序
    constexpr std::array<int, 6> sorted = bubble_sort(unsorted);

    // 期望的已排序数组
    constexpr std::array<int, 6> expected = {1, 2, 3, 4, 5, 8};

    // 编译期断言
    static_assert(arrays_equal(sorted, expected), "编译期排序错误！");

    // 运行时输出
    for (int v : sorted) {
        std::cout << v << ' ';
    }
    std::cout << '\n';
}

4. 说明

  1. constexpr 复制
    constexpr std::array<int, N> arr = input;
    在 C++17 中，constexpr 允许对 std::array 进行值复制，因为它是 POD 类型。这样我们可以在排序过程中对 arr 进行修改。

  2. 冒泡排序循环
    冒泡排序的核心是两层循环。外层循环控制已经排好序的尾部，内层循环执行一次“冒泡”。在 constexpr 里使用循环是合法的，只要所有循环控制量在编译期可求值。

  3. 编译期断言
    static_assert(arrays_equal(sorted, expected), "编译期排序错误！");
    这条语句会在编译阶段执行 arrays_equal，若返回 false 则导致编译错误。这样可以在程序运行前保证排序逻辑正确。

  4. 运行时输出
    虽然排序在编译期完成，但我们仍然可以在运行时输出结果，验证程序的完整性。

5. 扩展

  • 更复杂的排序：可以替换冒泡排序为插入排序、选择排序甚至快速排序。只需保持所有操作在 constexpr 里完成即可。
  • 可变长度：如果你想让函数支持任意类型数组，可以使用模板 std::array<T, N> 并将 T 设为 auto。
  • C++20 改进：在 C++20 中，constexpr 函数支持 if constexpr、递归等功能，可以更轻松地实现归并排序或堆排序。

6. 小结

通过 constexpr 关键字，我们可以把计算推到编译期，减少运行时开销。本文演示了如何在 C++17 环境下用 constexpr 实现冒泡排序，并利用 static_assert 在编译期验证结果。随着 C++ 语言的进化，未来会有更多更强大的编译期计算工具，值得我们持续关注和学习。

发表评论