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.
CodePudding user response：
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;
}
CodePudding user response：
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.
CodePudding user response：
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