c++ - 使用交换函数交换 vector 和数组中两行的复杂性

Question

在 2D vector 和 2D 数组中交换两行的复杂度是多少，我测试了两者的时间复杂度似乎在 vector 交换中几乎是 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]);
}

在 vector 中使用与上面相同的代码，但不是使用 int arr[N][N]我用 vector<<vector>>

Answer 1

std::swap 使用 move semantics 优化 std::vector 的交换.本质上，它归结为在两个 std::vector 之间交换一些内部指针。 vector 中有多少个值并不重要。这或多或少是一个指针交换。常数时间。

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

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

简而言之，std::vector 是一个如下所示的类:

template<typename T>
class vector {

    T *data;
    size_t data_size;
};

除此之外还有很多其他内容，但这说明了重点:std::swap 需要做的就是移动指针(和 data_size ，和其他一些位)，在两个 vector 之间，然后你去: vector 的内容已被交换。不需要实际的数据复制。