当表示为对象的一维向量时,有效地旋转NxM矩阵(C++)

Question

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

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;
  }
};

虽然这种方法确实有效,但我确信有一种更有效的方法(特别是在节省时间方面;空间不是问题).必须创建一个全新的向量然后用新的向量覆盖旧向量并不适合我.有更有效的解决方案吗？

请记住,我上面提供的仅用于说明.data我实际代码中的向量使用对象而不是int; 使用int只是为了让它更容易测试.因此,像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++;)我建议你尝试两者,索引转换和实际轮换,看看哪个更好.