c++ - Constexpr 行列式(二维 std::array)

Question

我需要编写一个在编译时计算行列式的 constexpr 函数。最明显的解决方案是使用拉普拉斯展开。支持 C++14。

#include <array>
#include <utility>

constexpr int get_cofactor_coef(int i, int j) {
    return (i + j) % 2 == 0 ? 1 : -1;
}

template <int N>
constexpr int determinant(const std::array<std::array<int, N>, N>& a) {
    int det = 0;

    for (size_t i = 0u; i < N; ++i) {
        det += get_cofactor_coef(i, 1) * a[i][0] * determinant<N-1>(GET_SUBMATRIX_OF_A<N-1, I, J>(a);
    }

    return det;
}

template <>
constexpr int determinant<2>(const std::array<std::array<int, 2>, 2>& a) {
    return a[0][0] * a[1][1] - a[0][1] * a[1][0];
}

template <>
constexpr int determinant<1>(const std::array<std::array<int, 1>, 1>& a) {
    return a[0][0];
}

问题是我完全不知道如何编写 GET_SUBMATRIX_OF_A。

我知道我需要:

1. 生成一个序列(可能使用std::integer_sequence)；
2. 从这个序列中排除第 i 行；
3. 复制除第一(第 0)列以外的所有内容；

我的 constexpr 技能几乎不存在。尝试将 a 传递给另一个函数会导致奇怪的错误，例如错误:'* & a' 不是常量表达式。

非常感谢所有帮助!

Answer 1

问题是非const std::array<T, N>::operator[] (返回 T& )在 C++17 之前不是 constexpr，因此很难设置 minor 的元素。

但是，有一个逃生口，那就是std::get<I>(std::array&) 是 constexpr，对结果进行指针运算是完全合法的，所以我们可以重写

a[i]  // constexpr since C++17

作为

(&std::get<0>(a))[i]  // constexpr in C++14!!

也就是说，我们使用std::get要获得对数组第一个成员的 constexpr 引用，获取指向它的指针，并使用内置的 []指针和索引上的运算符。

然后一个二级数​​组成员访问a[i][j]变得非常丑陋但仍然是 constexpr (&std::get<0>((&std::get<0>(a))[i]))[j] ，意思是我们can write get_submatrix_of_a 作为普通constexpr功能:

template<std::size_t N>
constexpr std::array<std::array<int, N - 1>, N - 1>
get_submatrix_of_a(const std::array<std::array<int, N>, N>& a, int i, int j) {
    std::array<std::array<int, N - 1>, N - 1> r{};
    for (int ii = 0; ii != N - 1; ++ii)
        for (int jj = 0; jj != N - 1; ++jj)
            (&std::get<0>(((&std::get<0>(r))[ii])))[jj] = a[ii + (ii >= i ? 1 : 0)][jj + (jj >= j ? 1 : 0)];
    return r;
}

记住 const std::array<T, N>::operator[]已经是constexpr在 C++14 中，因此我们不需要重写次构造的 RHS。