tags:

views:

211

answers:

4

I am writing a function to rotate a NxN matrix by 90 degree.

Here is my function

// "matrix" is an n by n matrix  
void rotateMatrix(int ** matrix, int n)
{
    for(int layer=0; layer < n; layer++)
    {
        int first = layer, last = n - layer -1;
        for(int i=0; i<n; i++)
        {
            int temp = matrix[i][last];
            matrix[i][last] = matrix[first][i];
            matrix[first][i] = matrix[i][first];
            matrix[i][first] = matrix[last][i];
            matrix[last][i]=temp;
        }
    }
}

Here is how I initialize and call the function in main function:

int m[5][5] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25};
rotateMatrix(m,5);

What I got from my IDE is:

> error: cannot convert ‘int (*)[5]’ to
> ‘int**’ for argument ‘1’ to ‘void
> rotateMatrix(int**, int)’

I kinda know why it's wrong since "m" is a int* . However, I am not sure I can I solve this problem?

+1  A: 

An array is not exactly the same thing as a pointer. In particular, a pointer to an array is not a pointer to a pointer. It's just a regular pointer to the first object of the array. An array of arrays likewise doesn't contain any pointers.

Much array confusion can be alleviated in C++ by using array references:

void rotateMatrix(int (&matrix)[5][5], int n) // matrix is ref to 5x5 array

Now there is no pointer vs array confusion whatsoever.

Potatoswatter
however, I want to keep the size of the matrix to be flexible, that's why I have the parameter "n" in the function.
nababa
@nababa: In that case, you want FredOverflow's template in case it's flexible but only at compile time, or Jefromi's pointer arithmetic if it really can be any size. However, consider using something besides raw pointers for variable-sized arrays in C++.
Potatoswatter
Then don't use a C array for the purpose. Consider using std::vector<std::vector>> instead.
Arafangion
I'm not a fan of `vector< vector<...> >`. Either use pointer arithmetic inside a plain `vector<...>` or use `valarray` or another dedicated multidimensional container.
Potatoswatter
@Potatoswatter: Why not? Granted, it would be better if you used a true multidimensional container, especially if you used a template, but what is wrong with vector<vector<..>> compared with raw C arrays?
Arafangion
@Ara: More indirection, less locality, more overhead, no continuity for iterators between rows.
Potatoswatter
+2  A: 

To actually solve your problem, assuming you're sticking with plain ol' arrays, and that the size needs to be arbitrary, you're going to have to make a couple of changes.

First, you need to pass in just a single pointer int*. A 2D array is not an array of pointers (or a pointer to a pointer), it's just a 1D array that the compiler knows to treat as a 2D array (i.e. the [3][4] element in a 5x5 array is at position 3*5+4). This does mean that you'll have to typecast the 2D array before passing it in, since the compiler doesn't want to discard that extra information.

Second, you'll have to access it as a 1D array. Like the example above, m[i][j] can be found at m[n*i+j].

Edit, to address the downvotes: this answer is not intended as a full explanation of array and pointer typing. It is simply trying to tell the OP a way to pass an arbitrary-sized 2D array into a function and perform some operation on it. I don't believe I said anything incorrect, just incomplete.

Jefromi
This is a common misconception. A 2D array is a contiguous region of memory, but it also has a type, and that type has dimensions. `int a[5][5]` and `int b[25]` are different things. The difference in types is not only a picky detail, but something that is enforced by the compiler. In this case, with `void foo( int * );` you can use `b` as argument but not `a`. The opposite goes for `void bar( int *[5] );`
David Rodríguez - dribeas
@David: Sorry, I tried to simplify. The point was that you can't actually pass in a full 2D array type, with the information about (arbitrary) dimensions - only a 1D array.
Jefromi
Sure you can pass a 2D or more array. See my answer.
Potatoswatter
@Potatoswatter: Not one of arbitrary size. But yeah, as you said in your comment there, raw pointers aren't very C++y.
Jefromi
A: 

You can keep your function the same, but you cannot pass static arrays in. You'll need to make dynamic arrays.

int size = 5;
int** m; 
m = new int**[size];
for (int i =0; i < size; ++i){
   m[i] = new int*[size];
}

/* Assign values to every element of m, using a for loop */
rotateMatrix(m, size);
patros
That's going to a lot of trouble and risk to keep the function the same…
Potatoswatter
Those aren't dynamic arrays. Dynamic arrays suggest that they allocate more memory automatically as needed.
Arafangion
Sorry, dynamically allocated array.
patros
+1  A: 

Are the dimensions of the matrix known at compile time? If so:

template <size_t n>
void rotateMatrix(int (&matrix)[n][n])
{
    ...
}
FredOverflow
This is the final approach I adopted. But the answers by @Jefromi and @Potatoswatter helped me a lot. Thank you all guys.
nababa