CODEWITHSUNDEEP
c++arrayspointersstlswap
naman
naman

Reputation: 85

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

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.

Upvotes: 2

Views: 6223

Answers (1)

Vlad from Moscow
Vlad from Moscow

Reputation: 311058

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.

Upvotes: 6

Related Questions