1

There is something I still don't quite understand about the way matrices and other multidimensional arrays are represented in C and C+ and how to allocate them dynamically.

Consider the following code segment:

int main()
{
    int n;
    cin >> n;
    int a[n][n];
    ...
}

If I understand correctly, this allocates an n by n matrix of integers on the stack. The (i,j)-th element of the matrix can be accessed using a[i][j]. The compiler automatically converts this into an access into the (n*i+j)-th element of a one dimensional array actually allocated.

Suppose now that I would like to allocate the n by n matrix a on the heap, instead of the stack. I can then do the following:

int main()
{
    int n;
    cin >> n;
    int** a;
    a = new int*[n];
    for (int i=0;i<n;i++) a[i] = new int[n];
    ...
}

I can now access the (i,j)-th element again as a[i][j]. However, this is not exactly equivalent to the situation above as I actually had to allocate space for n*n int's, plus n pointers to int. Also, accessing a[i][j] now entails two accesses to memory instead of just one. On the other hand, the index computation n*i+j is avoided.

Suppose now that I am interested in n by m matrices where m is small, e.g., m=2. Using the array of row pointers then wastes 33% of the space. Is there any way of avoiding that?

I can of course allocate a one-dimensional array and do the index arithmetic myself, but this does not seem to be the best solution to me.

Any information would be appreciated!

user1290928
  • 11
  • 3

5 Answers5

1

You could do 

 int *mat = new int[n*n];

then use mat[n*i+j]

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
1

Rather you would allocate one linear array of ints:

int main()
{
    int n;
    cin >> n;
    int *a;
    a = new int[n*n];
}

Doing the index math yourself is a good way to go.

Ed J
  • 101
  • 2
  • I mentioned that option at the end of my question. I am curious to know whether there is a way of avoiding doing the index math myself. – user1290928 Mar 25 '12 at 07:58
1

You could reverse the allocation order. If you are concerned about 33% or whatever memory being taken up due to "row" pointers, why not just turn the rows into the columns and vice versa? Then, instead of [i][j] you'd access an element with [j][i]. Of course, this may or may not be practical in your situation, it's hard to say without more information.

But really, I see no problems using index maths, there's nothing inherently wrong with it.

Alex Z
  • 2,500
  • 2
  • 19
  • 23
  • reversing the order of the indices is a good idea. It does not solve the problem completely as in a dynamic setting sometimes there are more rows and sometimes there are more columns. Also, if I want to store many 2 by 2 matrices, 33% of the space would be wasted in any case. – user1290928 Mar 25 '12 at 08:16
  • Of course, there is nothing morally wrong about doing the index arithmetic myself. It just seems strange that there is apparently no one of asking the compiler to do it for me. – user1290928 Mar 25 '12 at 08:18
  • You could always try to abstract it behind a class. I'm sure you could find an elegant way of doing this. edit: Actually, another answer already suggests this – Alex Z Mar 25 '12 at 08:26
  • I could definitely define a matrix class. This is suggested in one of the other answers. The question is whether this can also be down "with bare hands", so to speak. Thanks for your help. – user1290928 Mar 25 '12 at 08:29
1

You could create a class that did the index math for you, if that's where you're not liking things.

class Matrix
{
    public:
        Matrix(int iRows, int iCols)
        : mRows(iRows), mCols(iCols), m(new int[mRows*mCols]) { }
        ~Matrix() { delete [] m; }

        int &element(int iRow, int iCol) { return m[iRow * mCols + iCol]; }

        int mRows, mCols, *m;
};
Ed J
  • 101
  • 2
  • Thanks for the suggestion. Is it really necessary to define such a class. Is there no built in support for the situation I describe? – user1290928 Mar 25 '12 at 08:22
  • Hmmm ... I haven't really given it much thought. I'm so used to just doing the math. Is it really that inconvenient? – Ed J Mar 25 '12 at 09:24
  • The best I can think of is to use a macro? #define ndx(r,c,n) (n*r+c) – Ed J Mar 25 '12 at 09:30
  • Using macros is dangerous. For example, in your macro it would be much better to put n,r and c in parentheses. Doing the math is not that inconvenient. I just strikes me as odd that it is necessary. – user1290928 Mar 25 '12 at 12:20
  • I have always found it confusing to use two dimensional indexing because I can never remember whether it's column major or row major, especially given that it varies from language to language. Assuming the matrix to be a linear array, and doing the math just seems clearer to me. I never use multi-dimensional indexing. – Ed J Mar 25 '12 at 13:54
0

You can't do

int n;
cin >> n;
int a[n][n];

because the compiler needs to know exact size you will need on the stack during compile time. This is not possible when you are asking for it at run time :-) On the other hand you can do

#define N 10
int a[N][N];

In the other cases, you have to use dynamic allocation.

And allocation in C works just like that you allocate one piece of contiuous memory, indexes like a[i][j] are just syntactic sugar to jump into that memory, you can as well do *(a + k*i + j), where k is the size of the inner array.

tchap
  • 1,047
  • 8
  • 10
  • I checked the code above using the g++ compiler and it does work! You are invited to check it yourself. – user1290928 Mar 25 '12 at 08:01
  • In any case. Thanks for your help! – user1290928 Mar 25 '12 at 08:13
  • Ah, here is the answer http://stackoverflow.com/questions/1204521/dynamic-array-in-stack – tchap Mar 25 '12 at 08:16
  • Thanks for the link! This does clarify the situation with respect to the allocation on the stack. Even though it is not standard, it seems to work with g++. As it is not standard, it is probably not such a good idea to use it. – user1290928 Mar 25 '12 at 08:27