交换用向量表示的矩阵中的两列

Question

我有以下问题:我有一个表示二维矩阵的向量，我有行数和列数，几乎没有其他不相关的东西。

// A synomon for the type of the grayvalues
typedef unsigned int grayvalue_t;
static_assert(std::numeric_limits<grayvalue_t>::max()<=
              std::numeric_limits<size_t>::max(),
              "grayvalue_t maximum should be smaller than size_t maximum");

// Number of rows
size_t _R;
// Number of columns
size_t _C;
// Maximum grayvalue
grayvalue_t _MAX_G;
// Pixels' grayvalues
std::vector<grayvalue_t> _pixels;

我被要求在O(1)中交换两个给定的行(由索引给出)，这不是一个问题，因为我只需要在两个连续的内存块之间使用memcpy和替换，但是问题是，我还被要求在O(1)时间内交换两个给定的列(同样是由索引)，但是在这种情况下，矩阵的列不是向量中的连续内存块。

/// swaps between rows r1 and r2
/// Time complexity: O(1)
void swap_rows(const size_t& r1, const size_t& r2) {

}

/// swaps between columns c1 and c2
/// Time complexity: O(1)
void swap_cols(const size_t& c1, const size_t& c2) {

}

我有遗漏什么吗？想找人帮忙。

谢谢!

Answer 1

和很多其他CS问题一样，答案是:再多一层间接。

一个选项是维护一个映射，将矩阵中的列索引映射到向量中的实际索引。也就是说，矩阵列并不总是按顺序存储，而行中的元素将保持连续。映射从0到0 1到1开始映射，依此类推。要交换两列，只需交换它们在映射中的条目。如果还需要按行遍历整个数组，则需要查阅有关列的顺序的地图。