c++ - 在不循环 C++ 的情况下划分二维数组

Question

我对 C++ 还很陌生，正在尝试编写 Strassen 算法来乘以矩阵。部分算法要求我将矩阵分成四个部分，例如

4 5 6 7
6 7 8 9
1 2 3 4
2 3 5 6

分区:

4 5   6 7
6 7   8 9

1 2   3 4
2 3   5 6

(然后递归地再次使用每个部分并进行分区)。我想在不循环和复制原始矩阵中的数据的情况下对矩阵进行分区(因为这会花费更多时间)。我正在阅读的书说矩阵是使用“索引计算”进行分区的，通过原始矩阵的一系列行索引和一系列列索引来识别子矩阵。我不确定这是什么意思。

另外，我不确定我应该使用二维数组还是 vector ？我看到很多人推荐 vector ，但到目前为止我已经用二维数组编写了所有内容，所以我希望我想要的东西可以用二维数组实现。

p.s 可以假设矩阵的维度总是 2 的幂并且是 nxn(正方形)。此外，我已经看到很多与此类似的问题，但实际上没有一个能提供我正在寻找的解决方案。

谢谢

Answer 1

您可以创建一个直接支持子矩阵作为 View 的矩阵类:

template<typename T>
struct Matrix {
    int rows, cols, stride;
    std::vector<T> data; // Possibly empty for a view
    T *ptr;

    // A fresh matrix (owning its data)
    Matrix(int rows, int cols)
        : rows(rows), cols(cols), stride(cols),
          data(rows*cols),
          ptr(&data[0])
    {
    }

    // A view of a sub-matrix (pointing to the original data!)
    Matrix(Matrix& m, int row0, int col0, int rows, int cols)
        : rows(rows), cols(cols), stride(m.stride),
          ptr[&m(row0, col0)]
    {
    }

    T& operator()(int row, int col) {
        return ptr[row*stride + col];
    }

    ...
};

当然，您需要确保 View 不会超过拥有矩阵，并且如果不禁止该操作，您需要注意复制 View 对象的含义。

添加显式操作(如将 View 转换为拥有矩阵)可能很有用(如果复制构造函数不打算这样做)。