c++ - 当表示为对象的一维 vector 时有效地旋转 NxM 矩阵 (C++)

Question

到目前为止，我想出了顺时针旋转 NxM(N 不一定等于 M)矩阵(当它表示为高度和宽度变量分别存储的一维 vector 时)的唯一方法如下:

struct matrix
{
  vector<int> data;
  int height;
  int width;

  void rotate_90()
  {
    vector<int> newdata(height*width);
    for(int index = 0; index < height*width; index++)
    {
      int x = index % width;
      int y = index/width; // integer division
      int nextindex = (x+1)*height - 1 - y;
      newdata[nextindex] = data[index];
    }
    data = newdata;
    int temp = height;
    height = width;
    width = temp;
  }
};

虽然这种方法确实有效，但我相信还有一种更有效的方法(特别是在节省时间方面；空间不是问题)。必须创建一个全新的 vector ，然后用新的 vector 覆盖旧的 vector ，这对我来说并不合适。有没有更有效的解决方案？

请记住，我上面提供的只是为了说明。我实际代码中的 data vector 使用对象而不是整数；使用整数只是为了更容易测试。因此，像 Eigen 这样的线性代数库在这里无济于事。

Answer 1

如果可能的话，我会尽量避免完全复制数据，并且只在访问元素时转换索引:

struct matrix {
  vector<int> data;
  int height;
  int width;

  int& at(int x,int y) { return data(x + y*width); }

  struct rotated_view {
    matrix& base;
    rotated_matrix_view(matrix& base) : base(base) {}
    int& at(int x,int y) { return base.at(y,base.height-x-1); }
  }

  rotated_view rotated() { return rotated_view(*this); }
};

请注意，根据您的访问模式，这可能会有相当差的性能。另一方面，按列访问原始矩阵中的元素几乎与通过 rotated_matrix_view 按行访问它们一样低效。如果您确实关心性能(当然您关心，否则为什么要使用 C++；)我建议您同时尝试索引转换和实际轮换，看看哪个更好。