error: cannot convert ‘int (*)[4]’ to ‘int**’ | SWAPPING ARRAYS

Question

I am trying to write a function that swap two arrays in O(1) time complexity. However, when i try to write the function parameters, I get the error:

error: cannot convert ‘int (*)[4]’ to ‘int**’

Here is my code:

#include <iostream>
using namespace std;


void swap_array_by_ptr(int* a[], int* b[]) {
    int* temp = *a;
    *a = *b;
    *b = temp;
}

int main()
{
    int fr[] = {1,2,3,4};
    int rv[] = {4,3,2,1};
    
    swap_array_by_ptr(&fr, &rv);
    
    for (int i = 0; i < 4 ; i++) {
        cout << fr[i] << " ";
    }
    
    cout << endl;
    
    for (int i = 0; i < 4 ; i++) {
        cout << rv[i] << " ";
    }
}

However, when i tried to define the arrays with 'new' command, this works as expected as below:

#include <iostream>
using namespace std;


void swap_array_by_ptr(int** a, int** b) {
    int* temp = *a;
    *a = *b;
    *b = temp;
}

int main()
{
    int fr = new int[4]{1,2,3,4};
    int rv = new int[4]{4,3,2,1};
    
    swap_array_by_ptr(&fr, &rv);
    
    for (int i = 0; i < 4 ; i++) {
        cout << fr[i] << " ";
    }
    
    cout << endl;
    
    for (int i = 0; i < 4 ; i++) {
        cout << rv[i] << " ";
    }
}

Is there any way that i can define the arrays with [] method and swap the arrays by sending these arrays with '&array' method ?

As I believe, there must be a way to do that, I only achieve this when I'm trying to do with 'new' method. However, is there any way to swap two arrays in O(1) complexity with sending parameters as
swap_array_by_ptr(&fr, &rv); ?

Thanks for help.

You can't swap this type of array. Also `c++` and `c` are different languages. Had you used std::array<> which is the c++ array you can swap that. — drescherjm, Nov 11 '22 at 21:05
I appreciate your attention Sir, could you please check the edited version of my question ? I edited the correct version of the code where i defined arrays with new keyword. Please, check again. — yildomer, Nov 11 '22 at 21:07
Multidimensional arrays are arrays of arrays, not arrays of pointers. — John Bollinger, Nov 11 '22 at 21:08
This code isn't *really* swapping the arrays at all. It's swapping two pointers. — Eljay, Nov 11 '22 at 21:09
I also want to say that my purpose is writing a function for this operation and I need this to happen in O(1) complexity, I guess the std::array<> iterates the array for the operation, so the complexity must be O(n). — yildomer, Nov 11 '22 at 21:09
@Eljay I completely agree with you, this is OK for this case, however, is there any way to use the array as a pointer than swap two pointer for arrays ? As i did in the second (correct) version. — yildomer, Nov 11 '22 at 21:10
A C-style array is not a pointer. It's an array. C-style arrays *decay* into pointers to their first element, for your convenience, but that's just a helpful language behavior. (That helpful behavior can be a bit of a puzzler once you realize that it is happening, and until you've internalized why it is happening.) — Eljay, Nov 11 '22 at 21:13

Vlad from Moscow · Accepted Answer · 2022-11-11T21:37:38.213

1

You can not swap two arrays with O( 1 ). You need to swap each pairs of corresponding elements of two arrays.

In the first program

int fr[] = {1,2,3,4};
int rv[] = {4,3,2,1};

swap_array_by_ptr(&fr, &rv);

the expressions &fr and &rv have type int( * )[4] while the corresponding function parameters in fact has the type int **

void swap_array_by_ptr(int* a[], int* b[]) {

after adjusting the parameters having array types to pointers to the array element types by the compiler.

So the compiler issues an error.

You could use standard function std::swap declared in the header <utility> the following way

std::swap( fr, rv );

But in any case its complexity is O( n ).

In the second program there are at least typos. Instead of

int fr = new int[4]{1,2,3,4};
int rv = new int[4]{4,3,2,1};

you have to write

int *fr = new int[4]{1,2,3,4};
int *rv = new int[4]{4,3,2,1};

In this case you are not swapping arrays themselves. That is the arrays will still store their initial values. You are swapping pointers that point to the dynamically allocated arrays.

To be sure that arrays are not swapped consider the following demonstration program.

#include <iostream>
using namespace std;


void swap_array_by_ptr(int** a, int** b) {
    int* temp = *a;
    *a = *b;
    *b = temp;
}

int main()
{
    int fr[] = { 1,2,3,4};
    int rv[] = {4,3,2,1};

    int *p1 = fr;
    int *p2 = rv;
    
    swap_array_by_ptr( &p1, &p2 );
    
    for (int i = 0; i < 4 ; i++) {
        cout << p1[i] << " ";
    }
    
    cout << endl;
    
    for (int i = 0; i < 4 ; i++) {
        cout << p2[i] << " ";
    }

    cout << endl;

    for (int i = 0; i < 4 ; i++) {
        cout << fr[i] << " ";
    }
    
    cout << endl;
    
    for (int i = 0; i < 4 ; i++) {
        cout << rv[i] << " ";
    }

    cout << endl;
}

edited Nov 11 '22 at 21:37

answered Nov 11 '22 at 21:26

Vlad from Moscow

301,070
26
186
335

Oh, thanks for typo warning Sir, I made these typos while writing question into here. I got the idea. Do you mean that assuming that i have corrected my typos in second version, the only way to swap two arrays in O(1) complexity is using pointer and the function for this is the one in the second version ? I mean, there is no way to swap two arrays, literally arrays and not pointers, with O(1) complexity, right ? – yildomer Nov 11 '22 at 21:33
You could use `std::vector` and swapping that is O(1): [https://en.cppreference.com/w/cpp/container/vector/swap2](https://en.cppreference.com/w/cpp/container/vector/swap2) – drescherjm Nov 11 '22 at 21:34
1

@yildomer Yes you can not swap arrays with O( 1 ). You can swap pointers that point to arrays with O( 1 ). The array themselves will be unchanged. – Vlad from Moscow Nov 11 '22 at 21:35
I know the idea of vectors but i did not prefer to use them in this case Sir. Instead, i guess you understood my purpose. "I mean, there is no way to swap two arrays, literally arrays and not pointers, with O(1) complexity, right ?" – yildomer Nov 11 '22 at 21:36
There is no way to do what you want if you want to stick to just arrays. – drescherjm Nov 11 '22 at 21:37
@drescherjm I appreciate your time and effort Sir, i got it, thank you. – yildomer Nov 11 '22 at 21:39
Can't I create pointers for the arrays I defined as {int fr[] = { 1,2,3,4};} and then swap the pointers ? I mean, I am trying to apply the function that I wrote in second version but defining with fr[] method. I am asking that creating pointers for the array i defined then swapping pointers, not directly swapping arrays ? – yildomer Nov 11 '22 at 21:46
@yildomer Arrays themselves are not swapped if you are swapping pointers to them. – Vlad from Moscow Nov 11 '22 at 21:48
Okay but let's say I want to use only the pointers to do some operations on an array, and I want to swap these two pointers. My question is creating a pointer in a such way that I would be able to swap these pointers ? But, I want to define the arrays as [] method. – yildomer Nov 11 '22 at 21:49
@yildomer As I showed in the demonstration program you can introduce pointers like int fr[] = { 1, 2, 3, 4 }; int *p = fr; In thi case the pointer p will point to the first element of the array fr. – Vlad from Moscow Nov 11 '22 at 21:51
Got the logic behind it Sir, thanks for patience. :) – yildomer Nov 11 '22 at 21:53

John Bollinger · Answer 2 · 2022-11-11T22:30:07.017

It is a syntactic quirk inherited from C that a declaration of a function parameter as an array is automatically converted to a declaration as a corresponding pointer. This is not as odd as it might first seem, however, because it dovetails with the automatic conversion of function arguments of array type to corresponding pointers, also inherited from C.^*

Thus, this declaration ...

void swap_array_by_ptr(int* a[], int* b[]) {

... is equivalent to this one:

void swap_array_by_ptr(int **a, int **b) {

. But the arguments you are passing do not match. This, for example,

    int fr[] = {1,2,3,4};

declares fr as an array of 4 int. If it were passed as a function argument, it would be automatically converted to a pointer to the first element, thus of type int *. Types int * and int ** are not compatible.

On the other hand, what you actually try to pass, &fr is the address of an array 4 int, of type int(*)[4]. This also is incompatible with int **, because arrays are not pointers.

You could write your function like this:

void swap_array_by_ptr(int (*a)[4], int (*b)[4]) {
    int temp[4];
    memcpy(temp, a, sizeof(a));
    memcpy(a, b, sizeof(b));
    memcpy(b, temp, sizeof(temp));
}

That would be compatible with the call in your code. Do note, however, that that is specific to array size 4, and you're not really gaining anything useful from that. You could, however, convert it to a template:

template<class T, std::size_t n>
void swap_array(T (*a)[n], T (*b)[n]) {
    T temp[n];

    memcpy(temp, a, sizeof(a));
    memcpy(a, b, sizeof(b));
    memcpy(b, temp, sizeof(temp));
}

That handles arrays of any element type and size,^** as long as the sizes match. Of course, it scales as O(N) with array size, in both time and auxiliary space.

Such time scaling is unavoidable. To swap two objects you need to read each at least once and write each at least once, and that requires time proportional to the size of the objects. But you could reduce the space overhead to O(1) by swapping the arrays element by element in a loop. That would very likely be slower, but the time complexity would still be O(N).

Of course, you can also use std::swap() on arrays. It is quite similar to the template above, but uses references to the arrays instead of pointers to them.

^*This is a specific case of a much more general behavior.
^**So long as the temporary array does not turn out to be too large for the stack.

Wow, Sir, it is different point of view, unfortunately, I assumed that if 'fr' is converting to int* automatically, getting address of it by & operator, will generate int** type, but it didn't, as you said. Why did not it happen ? Can you please explain it more ? — yildomer, Nov 11 '22 at 21:59
@yildomer, one of the few exceptions to arrays being automatically converted to pointers is when they are the operand of the address-of operator (unary `&`). There's not really any more to it than that that's the rule. — John Bollinger, Nov 11 '22 at 22:00

score -1 · Answer 3 · answered Nov 11 '22 at 21:17

-1

Change the swap_array_by_ptr function from 'swap_array_by_ptr(int** a, int** b)' to 'swap_array_by_ptr(int* a, int* b)'.

void swap_array_by_ptr(int* a, int* b) {
    int* temp = *a;
    *a = *b;
    *b = temp;
}

here's a link to a similar question: Swapping 2 arrays in C

answered Nov 11 '22 at 21:17

Quantale

1
1

No way Sir, {int* temp = *a;} in this line, you attempt to assign an integer to a pointer. This generates an error. Additionally, the question is not similar. – yildomer Nov 11 '22 at 21:27

error: cannot convert ‘int (*)[4]’ to ‘int**’ | SWAPPING ARRAYS

3 Answers3