Problem
I am learning C++, and am writing code to transpose a 2D array and to reverse a 1D-array.
Please look at the invocations. Why do I have to use reverse(arr, 4) for reverse, whereas I have to use transpose(*in_matrix, *out_matrix) for transpose?
There are two ways of writing each function signature. Both seem to give the same results.
Thank you.
EDIT: I know how to solve it with array-subscript. I am doing it this way deliberately for practice. Now I understand there's no point trying this. However, I have added some notes summarised from the answers below.
Code
#include <iostream>
using namespace std;
const int LENGTH = 2;
const int WIDTH = 3;
void printArray(const int arr[], const int N) {
cout << arr[0];
for (int i = 1; i < N; ++i) {
cout << ", " << arr[i];
}
cout << "\n";
}
// void transpose(int* const input, int* const output) { // both these signatures
void transpose(const int input[], int output[]) { // works (I find the top one clearer)
for (int i = 0; i < WIDTH; ++i) {
for (int j = 0; j < LENGTH; ++j) {
*(output + j * WIDTH + i) = *(input + i * LENGTH + j);
}
}
}
// void reverse(int arr[], const int N) { // both these signatures
void reverse(int* arr, const int N) { // works (I prefer this one)
for (int i = 0; i < N / 2; ++i) {
int temp = *(arr + i);
*(arr + i) = *(arr + N - 1 - i);
*(arr + N - 1 - i) = temp;
}
}
int main() {
int arr[4] = {2,4,6,8};
printArray(arr, 4);
reverse(arr, 4); // this works
// reverse(*arr, 4); // this doesn't work
printArray(arr, 4);
int in_matrix[WIDTH][LENGTH];
in_matrix[0][0] = 1;
in_matrix[0][1] = 2;
in_matrix[1][0] = 3;
in_matrix[1][1] = 4;
in_matrix[2][0] = 5;
in_matrix[2][1] = 6;
int out_matrix[LENGTH][WIDTH];
// transpose(in_matrix, out_matrix); // this doesn't work
transpose(*in_matrix, *out_matrix); // this works
cout << "in_matrix is:\n";
for (int i = 0; i < WIDTH; ++i) {
printArray(in_matrix[i], LENGTH);
}
cout << "out_matrix is:\n";
for (int i = 0; i < LENGTH; ++i) {
printArray(out_matrix[i], WIDTH);
}
return 0;
}
Summary of answers
LESSON: DO NOT USE pointer-arithmetic for 2D-arrays
decay
KEY IDEA: arr -----> &arr[0] type int*
This is also the reason the two function signatures are equivalent.
// transpose(int* const input, int* const output) // alt.
Signature: transpose(const int input[], int output[])
i.e. it expects an array of ints (or equiv., a pointer to an int)
(id)
IDENTITY: a[i] = *(a + i) ALWAYS TRUE
Reason transpose(in_matrix, out_matrix) doesn't work:
decay
out_matrix -----> &out_matrix[0] type int(*)[WIDTH]
Reason transpose(*in_matrix, *out_matrix) works:
(id) decay
*out_matrix = out_matrix[0] -----> &(out_matrix[0])[0]
In C, arrays and pointers are a bit intricately mixed up. An array can be considered as a pointer with some 'size' information attached to it (that is not stored anywhere, but the compiler knows). Hence, sizeof when used on an array gives you the size of the contents of the entire array, while on a pointer, it gives the size of the pointer.
When you pass an array to a function, the size information is lost - in effect, the array decays to a pointer. For most practical purposes, a pointer to a type can be used exactly like a one-dimensional array of that type. The array subscript notation ([]) can also be used to access consecutive elements using a pointer.
However, with 2D arrays, this gets more complicated. 2D arrays and double pointers may use the same access syntax of the form a[i][j] but they are not interchangeable. A 2D array decays to a pointer to an array while a double pointer is a pointer to a pointer.
Coming back to your question, the two ways of writing the function signatures are essentially equivalent because 1D arrays decay to pointers when passed to functions. So void reverse(int* arr, const int N) is the same as void reverse(int arr[], const int N).
In your transpose function however, you are passing a 2D array. It would decay to a pointer to an array. But in your function declaration, you are accepting these arguments as arrays (or in effect, pointers). This still works fine because of the quirks of C. A 2D array can be also treated as one big 1D array with the rows laid out consecutively one after the other. It is, however, not the best approach. This also reflects in the fact that you had to de-reference the array names when you passed them to the transpose function, because it expects a 1D array (or a pointer) and not a 2D array (or a pointer to an array).
Also, C/C++ provides a much more elegant way to access arrays than using unwieldy pointer arithmetic. So the following approach is what I would recommend. It should work exactly like the code you originally posted, but would be cleaner and more readable.
#include <iostream>
using namespace std;
const int LENGTH = 2;
const int WIDTH = 3;
void printArray(const int arr[], const int N) {
cout << arr[0];
for (int i = 1; i < N; ++i) {
cout << ", " << arr[i];
}
cout << "\n";
}
void transpose(const int input[][LENGTH], int output[][WIDTH]) {
for (int i = 0; i < WIDTH; ++i) {
for (int j = 0; j < LENGTH; ++j) {
output[j][i] = input[i][j];
}
}
}
void reverse(int* arr, const int N) {
for (int i = 0; i < N / 2; ++i) {
int temp = arr[i];
arr[i] = arr[N - 1 - i];
arr[N - 1 - i] = temp;
}
}
int main() {
int arr[4] = {2,4,6,8};
printArray(arr, 4);
reverse(arr, 4);
printArray(arr, 4);
int in_matrix[WIDTH][LENGTH];
in_matrix[0][0] = 1;
in_matrix[0][1] = 2;
in_matrix[1][0] = 3;
in_matrix[1][1] = 4;
in_matrix[2][0] = 5;
in_matrix[2][1] = 6;
int out_matrix[LENGTH][WIDTH];
transpose(in_matrix, out_matrix);
cout << "in_matrix is:\n";
for (int i = 0; i < WIDTH; ++i) {
printArray(in_matrix[i], LENGTH);
}
cout << "out_matrix is:\n";
for (int i = 0; i < LENGTH; ++i) {
printArray(out_matrix[i], WIDTH);
}
return 0;
}