1

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?

Potatoswatter
  • 134,909
  • 25
  • 265
  • 421
nababa
  • 1,251
  • 3
  • 13
  • 20
  • related question: http://stackoverflow.com/questions/546860/passing-arrays-and-matrices-to-functions-as-pointers-and-pointers-to-pointers-in I'm sure there are a zillion more here. – Cascabel Aug 16 '10 at 22:16
  • You could improve your function I think. There is no need for both of your loops to span the whole [0, n) range. You can loop just over one quarter of the entire matrix and 5 swaps inside the inner loop will do the rotation around the centre. – Maciej Hehl Aug 16 '10 at 23:00

4 Answers4

2

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.

Cascabel
  • 479,068
  • 72
  • 370
  • 318
  • 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 Aug 16 '10 at 23:03
  • @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. – Cascabel Aug 16 '10 at 23:08
  • Sure you can pass a 2D or more array. See my answer. – Potatoswatter Aug 17 '10 at 00:16
  • @Potatoswatter: Not one of arbitrary size. But yeah, as you said in your comment there, raw pointers aren't very C++y. – Cascabel Aug 17 '10 at 01:40
2

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

template <size_t n>
void rotateMatrix(int (&matrix)[n][n])
{
    ...
}
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
  • This is the final approach I adopted. But the answers by @Jefromi and @Potatoswatter helped me a lot. Thank you all guys. – nababa Aug 17 '10 at 13:49
1

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
  • 134,909
  • 25
  • 265
  • 421
  • 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 Aug 16 '10 at 22:07
  • @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 Aug 17 '10 at 00:18
  • Then don't use a C array for the purpose. Consider using std::vector> instead. – Arafangion Aug 17 '10 at 00:59
  • 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 Aug 17 '10 at 01:20
  • @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> compared with raw C arrays? – Arafangion Aug 17 '10 at 01:29
  • @Ara: More indirection, less locality, more overhead, no continuity for iterators between rows. – Potatoswatter Aug 17 '10 at 02:29
0

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
  • 7,719
  • 3
  • 28
  • 37