замена двух столбцов в матрице, представленной вектором

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), что не является проблемой, так как я могу просто использовать тетсру и заменить между двумя непрерывными блоками памяти, но проблема заключается в том, что меня также попросят заменить два заданных столбца (опять же по индексам) на время 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 и т. Д. Чтобы поменять два столбца, вы просто меняете свои записи на карте. Если вам также необходимо пройти весь массив по ряду, вам нужно будет проконсультироваться с картой о порядке столбцов.