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

Question

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>>

I think you're confusing the concepts of complexity and experimental results - which was faster when you tested them? — tinkertime, Dec 03 '16 at 14:34
when I run both codes, the vector runs faster, I mean in terms of the output result. — seif gamal, Dec 03 '16 at 14:37
By the way, I hope you don't use those `scanf` calls in real code. — Christian Hackl, Dec 03 '16 at 15:22

score 1 · Accepted Answer · edited May 23 '17 at 11:53

1

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.

edited May 23 '17 at 11:53

Community

1
1

answered Dec 03 '16 at 14:37

Sam Varshavchik

114,536
5
94
148

Good point, I have one question. We can see the complexity of swap on array and vector, we know it. But, how does the array look like, I mean, why can't array look same as vector? with allocation only once? I know that it is different, why can't it be so? e.g. data = new T[N]; allocate once for array shouldn't it be good? – Manohar Reddy Poreddy Jun 05 '18 at 15:49
That's what smart pointers are for. Use the right tool for the right job. – Sam Varshavchik Jun 05 '18 at 17:42
I know smart pointers. The question was "Why can't array look same as vector, with allocation only once?", so *swap* can swap pointers the same way. – Manohar Reddy Poreddy Jun 06 '18 at 01:36
Because if "an array look the same as vector" then there wouldn't be any reason to to have an array in the first place, when one can simply use the vector. There are reasons why there are both arrays and vectors. They are different. They have different properties. Arrays are better at some things. Vectors are better at other things. If they weren't, if they were exactly the same, then this would be quite a silly situation, because one of them would be completely redundant. It's like asking why we have both trains and buses, and why we can't simply have trains drive on the roads, like buses. – Sam Varshavchik Jun 06 '18 at 02:14
Oh no. I know they are different because they are different. The question was on 'swap'. The question was "Why can't array look same as vector (in its representation with respect to swap optimization), with allocation only once?", so 'swap' can swap pointers the same way. – Manohar Reddy Poreddy Jun 06 '18 at 02:31
Fine for end of story, at least you got somewhere to the point from smart pointers. – Manohar Reddy Poreddy Jun 06 '18 at 03:02

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

1 Answers1