How can we swap 2 arrays in constant complexity or O (1)?

Question

How can we swap 2 arrays in constant complexity or O (1)? is there a way we can do this? I tried using pointers, but it gives an error

plus this will not help, because it is just a permutation of pointers, but not arrays

#include <algorithm> int AA[100], *A=AA, BB[100], *B=BB; swap(A, B); 

I also tried using the vector assignment operator, but they have LINEAR complexity, i.e. O (N) is not a constant, so can you somehow swap the two arrays in O (1)? (using pointers or something else)

i hv tried searching the net, found a link to codeforces ( http://codeforces.com/blog/entry/11971 ), but that doesn’t help.

Answer 1

Using std::swap (using a swap element) for vectors ( std::vector ) has O (1) complexity.

From the C ++ standard

void swap (vector & x);

10 Effects: Exchanges the contents and capacity () * of this with an x.

11 Difficulty: Constant time .

You can “swap arrays” with constant time if they were dynamically allocated using the new operator. In this case, you can really only change pointers pointing to the first elements of arrays.

for example

 #include <iostream> #include <algorithm> int main() { int **a = new int *[2]; a[0] = new int[5] { 0, 1, 2, 3, 4 }; a[1] = new int[5] { 5, 6, 7, 8, 9 }; for ( size_t i = 0; i < 2; i++ ) { for ( size_t j = 0; j < 5; j++ ) std::cout << a[i][j] << ' '; std::cout << std::endl; } std::cout << std::endl; std::swap( a[0], a[1] ); for ( size_t i = 0; i < 2; i++ ) { for ( size_t j = 0; j < 5; j++ ) std::cout << a[i][j] << ' '; std::cout << std::endl; } std::cout << std::endl; delete [] a[0]; delete [] a[1]; delete [] a; return 0; } 

Output signal

 0 1 2 3 4 5 6 7 8 9 5 6 7 8 9 0 1 2 3 4 

In fact, the same operation is performed in std :: vector.