Сложность замены двух строк в векторе и массиве с помощью функции подкачки

Question

В чем сложность замены двух строк в 2D-векторе и в 2D-массиве, я тестировал сложность времени на обоих, кажется, что в обмене векторов почти O(1), но в массивах работает медленнее, так что же действительно сложность, почему разные?

в массивах (очень медленно):

int arr[N][N]; 
// input the array elements 
while (q--) { // number of queires 
    int x, y; 
    scanf("%d %d", &x, &y); 
    swap(arr[x], arr[y]); 
} 

в векторах тот же код выше, но вместо того, чтобы использовать int arr[N][N] я использую vector<<vector>>

Answer 1

std::swap оптимизирует Перекачка std::vector с использованием move semantics. По существу, это сводится к замене нескольких внутренних указателей между двумя std::vector. Неважно, сколько значений в векторах. Это обмен указателей, более или менее. Постоянное время.

Нет таких ярлыков с встроенными массивами. Все значения в массивах должны быть скопированы.

Перенос семантики был одним из основных дополнений к C++ 11.

Чтобы уточнить, в упрощенных чертах, std::vector это класс, который выглядит следующим образом:

template<typename T> 
class vector { 

    T *data; 
    size_t data_size; 
}; 

Там намного больше, чем только что, но это получает через точку: все, что std::swap нужно сделать заключается в перемещении указателей (и data_size и нескольких других битов) между двумя векторами и там вы идете: содержимое векторов было заменено. Никакое фактическое копирование данных не требуется.