CODEWITHSUNDEEP
c++vectorstltime-complexityswap
seif gamal
seif gamal

Reputation: 59

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

What's the complexity of swapping two rows in 2D vector and in 2D array, I tested the time complexity on both it seems that in vectors swapping is almost O(1) but in arrays works slower, so what's the indeed complexity, why are different?

in arrays (very slow):

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]);
}

in vectors the same code above but instead of using int arr[N][N] I use vector<<vector>>

Upvotes: 1

Views: 2370

Answers (1)

Sam Varshavchik
Sam Varshavchik

Reputation: 118445

std::swap optimizes swapping of std::vectors using move semantics. Essentially, it boils down to swapping a few internal pointers between the two std::vectors. Doesn't matter how many values are in the vectors. It's a pointer swap, more or less. Constant time.

There are no such shortcuts with native arrays. All values in the arrays must be obediently copied.

Move semantics were one of the major additions to C++11.

To clarify, in simplified terms, a std::vector is a class that looks like this:

template<typename T>
class vector {

    T *data;
    size_t data_size;
};

There's much more to it than just that, but this gets the point across: all that std::swap needs to do is to move the pointers (and data_size, and a few other bits), between the two vectors and there you go: the contents of the vectors have been swapped. No actual data copying is needed.

Upvotes: 1

Related Questions