使用交换函数交换向量和数组中两行的复杂性

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 使用 move semantics 优化 std::vector 的交换。本质上，它归结为在两个 std::vector 之间交换一些内部指针。向量中有多少个值并不重要。这或多或少是一个指针交换。恒定时间.

原生数组没有这样的快捷方式。数组中的所有值都要乖乖复制。

移动语义是 C++11 的主要新增功能之一。

简而言之，std::vector 是 class，如下所示：

template<typename T>
class vector {

    T *data;
    size_t data_size;
};

不仅如此，还有更多内容，但这说明了重点：std::swap 需要做的就是移动指针（和 data_size，以及其他一些位），在两个向量之间，你去：向量的内容已被交换。不需要实际的数据复制。

Complexity of swapping two rows in vector and array using swap function