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

arrays, c++, pointers, stl, swap

Solution

Using `std::swap` (that uses member function swap) for vectors (`std::vector`) has a complexity of `O(1)`.

From the C++ Standard:

void swap(vector& x);

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

11 Complexity: Constant time.

You could "swap arrays" with a constant time if they were allocated dynamically with operator `new`. In this case, you indeed could swap only pointers that point to the first elements of the 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;
}

The output is:

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 done in `std::vector`.

Problem

How can we swap 2 arrays in constant complexity or `O(1)`? Is there a way that we can do this? I have tried using pointers but it is giving an error Moreover, this won't help because it is just interchanging the pointers but not the arrays: ``` #include <algorithm> int AA[100], *A=AA, BB[100], *B=BB; swap(A, B); ``` I have tried using vectors assignment operator as well but they have LINEAR complexity i.e. `O(N)` not constant. So, is there any way we can swap two arrays in `O(1)`? (by using pointers or something else) I have tried searching on the internet and found a link to codeforces ( http://codeforces.com/blog/entry/11971 ) but this is not helping.

Original source