Переключение строк и столбцов в матрице с сложностью O (1)

Question

Итак, для домашней работы одной из вещей, с которой мне было поручено, является замена двух строк или двух столбцов друг на друга с помощью матрицы, построенной в объекте типа класса , используя эти 3 параметра для определения его:

size_t _R;// Number of rows. 
size_t _C;// Number of columns. 
std::vector<T> mat;// array of T type variables to represent the matrix. 

Например, если у меня было 3 строк и 3 столбцов и вектор массив INT из 1,2,3,4,5,6,7,8,9, замена строк 0 и 1 показала бы это как 4,5,6,1,2,3,7,8,9.

Таким образом, создание свопа происходит не из-за проблемы, но я не понимаю, как это сделать: Как вы собираетесь сделать это с сложностью O (1)?
Что я хотел сделать, это индивидуально переключаться между каждым типом в строке/столбце, но тогда это будет O (n), правильно? Потому что это будет зависеть от количества элементов в каждой строке/столбце. не

EDIT: Пример кода для того, что я пробовал:

void swap_rows(const size_t& r1, const size_t& r2) { 
    for (size_t i = 0; i < _C; i++) 
    { 
     T temp = mat[i + (r1 * _C)]; 
     mat[i + (r1 * _C)] = mat[i + (r2 * _C)]; 
     mat[i + (r2 * _C)] = temp; 
    } 
} 

Но я считаю, что это O (п) сложность, поэтому не годен: р

Answer 1

Один из способов сделать это, чтобы применить изменения строк и столбцов для каждого из ваших размеров, как:

std::vector<size_t>(_R) row_i; 
std::vector<size_t>(_C) col_i; 

это то каждый инициализируется, например, {0, 1, 2} соответственно. Затем получить доступ к детали де-ссылками через эти коллекции:

T getItem(size_t row, size_t column) 
{ 
    return mat[ (row_i[row] * _C) + col_i[col]) ]; 
} 

Это даст вам деталь T на row, col, но с добавлением разыменовывается через модифицирующую строку и столбец.

Теперь, чтобы поменять местами две строки, например, нужно просто сказать:

std::swap(row_i[0], row_i[1]); 

и вуаля, в следующий раз, когда вы получить доступ к этому, строки 0 & 1 будет переключен. Не имеет значения, есть ли у вас матрица 3 x 3 или 1000 x 1000, время модификации - это просто замена двух целых векторов.

Answer 2

Вектор - это случайный доступ без косвенности, поэтому ваша проблема всегда O (_C) * O (2) = O (_C) для 2 строк в векторе.

Если вы хотите, чтобы O (1) представляли матрицу как массивы строк, вы можете поменять два указателя строк. Тогда замена двух столбцов означает, что вы получили тот же результат O (_R).