Expert: vijayan - 4/9/2010

Question
Hello,
  I’ve written a program that contains some functions. One of these functions, chseq_r, that I send it for you at the end of this post causes crash during running. It gets an array as input and changes the value of two cells of the array and then returns the result. I think this problem causes while writing or reading from memory. I couldn’t understand the meaning of the error message. It says: "Thread stopped [my file name]:Fault:access violation at 0x4020d2:write of address 0x130a7c". It probable that the problem refers to line 26, l0=seq[j0][k0][h0];. Can you help to find the reason of the crash?

The function is here:

int* chseq_r(int seq[n][kl][hl])
{
int* result=new int[n*kl*hl];
int  j0,k0,h0,j1,k1,h1,  l0,l1,  r,sum_ope=0;
float ls,nr;

for (j=0;j<n;j++){
sum_ope+=(kj[j]*hj[j]);
}
                               
choose_l0:

ls=0;
nr=(1000/sum_ope);
r=rand()%1000;
for(j=0;j<n;j++)
  for(k=0;k<kj[j];k++)
     for(h=0;h<hj[j];h++){
        if(ls<r){
           j0=j;
           k0=k;
           h0=h;
        }
        ls+=nr;
     }                          
l0=seq[j0][k0][h0];
                 
if(l0==1)
  goto choose_l0;


  for(j=0;j<n;j++)
     for(k=0;k<kj[j];k++)
        for(h=0;h<hj[j];h++){
           if(seq[j][k][h]==l0-1){
              j1=j;
              k1=k;
              h1=h;
              l1=seq[j][k][h];
              cout<<"              j1,k1,h1= "<<j1<<k1<<h1;
              if((j1==j0 && k1==k0)||(j1==j0 && h1==h0))
                  goto choose_l0;

              else{
                 seq[j0][k0][h0]=l1;
                 seq[j1][k1][h1]=l0;
                 goto end;
              }}}
end:

for(j=0;j<n;j++)
  for(k=0;k<kl;k++)
     for(h=0;h<hl;h++){
        q=(j*kl*hl)+(k*hl)+h;
        result[q]=seq[j][k][h];
     }

return result;
}

Answer
> The function is here:

> int* chseq_r(int seq[n][kl][hl])

This is not standard C++ and will not compile with a conforming compiler.

Here are some ways in which you could simulate passing multi-dimensional arrays to C++ functions:

part 1
------

it helps to first realize that arrays are *never* actually passed to functions. for example,

void foo( int array[] )
{
 // ...
}

int main()
{
 int a[20] ;
}

the type of the argument to foo is not "array of int", it is "pointer to int". in fact, it would be exactly the same if it were written as

void foo( int* array )
{
 // ...
}

the name of an array is almost always converted to a pointer to the first element of that array. for example:

int b[20] ;
b[3] = 100 ;

the second line is equivalent to *( b + 3 ) = 100 ; where b is a pointer to the first element, and pointer arithmetic is used to reach the 3rd element. that line could just as well have been written this way:
Code:

3[b] = 100 ; // perfectly valid.

this is equivalent to *( 3 + b ) = 100 ; which is equivalent to *( b + 3 ) = 100 ;

once you grasp that array names almost always decay to a pointer to the first element, take another look at the function call from main() above: foo(a) ;. you should understand what this is really doing - it's *not* passing an int array named a to a function that expects an int array. it's passing an int pointer to a function that expects an int pointer. foo(a) ; is equivalent to foo( &( a[0] ) ) ;

now, consider the case of a function (apparently) taking a two-dimensional array:

enum { SIZE = 10 } ;
void bar( int array2d[][SIZE] )
{
 // ...
}

we know better - this function does not take an array at all, but a pointer. we should think of multidimensional arrays in a different way in C:
a 2d array is really a 1d array, each of whose elements is itself a 1d array. it could be equivalently written this way:

enum { SIZE = 10 } ;
void bar( int (*array2d) [SIZE] )
{
 // ...
}

it should begin to become clear now. the type of array2d is "pointer to array of SIZE ints". why does SIZE have to be specified? because it is required for evaluating array subscript operator which requires pointer arithmetic.
array2d actually points to the first of several arrays of ints, and we want to access the third of those arrays: array2d[3] ; this is equivalent to *( array2d + 3 ). note that we are adding 3 to a pointer, and recall that because of pointer arithmetic the address required is 3 * sizeof( *array2d ) bytes past array2d.
in order for the compiler to generate code for this, it needs to know ahead of time what sizeof( *array2d ) is. sizeof( *array2d ) is equivalent to sizeof( int[SIZE] ), therefore the compiler needs to know SIZE at compile time.

it follows that any time you declare a function with an argument which is a multi-dimensional array, you need to specify the size of every dimension except the first; the sizes of those dimensions must be constants known at compile time.

part 2
------

if it's not possible to know the sizes of the dimensions until run time, there are several options. the simplest is to use a std::vector<> (which is much like a java array):

#include <vector>

void foobar( std::vector< std::vector<int> >& two_d_vec )
{
   // set all elements to 8
       for( std::size_t i = 0 ; i < two_d_vec.size() ; ++i )
               for( std::size_t j = 0 ; j < two_d_vec[i].size() ; ++j )
                       two_d_vec[i][j] = 8 ;
}

int main()
{
   typedef std::vector<int> array1d_type ;
   typedef std::vector<array1d_type> array2d_type ;

   // create a 5 X 4 array of int initialized to zero
   array2d_type a( 5U, array1d_type( 4U ) ) ;

       foobar(a) ;
}

a second option is to use an array of pointers:

void foobar2( int** array, ind rows, int cols )
{
   // set all elements to 8
       for( int i = 0 ; i < rows ; ++i )
               for( int j = 0 ; j < cols ; ++j )
                       array[i][j] = 8 ;
}

int main()
{
  int ROWS = 5, COLS = 4 ;
  int** array = new int* [ ROWS ] ;
    
    for( int i = 0 ; i < ROWS ; ++i )
        array[i] = new int[COLS] ;

  foobar2( array ) ;                

    for( int i = 0 ; i < ROWS ; ++i )
        delete[] array[i] ;
  delete[] array ;             
}

a third option is to just use a one dimensional array to simulate a 2d array, and do the pointer arithmetic on our own:

void foobar3( int* array, int rows, int cols )
{
   // set all elements to 8
       for( int i = 0 ; i < rows ; ++i )
               for( int j = 0 ; j < cols ; ++j )
                       array [ i*cols + j ] = 8 ;
}

int main()
{
  int ROWS = 5, COLS = 4 ;
  int* array = new int[ ROWS * COLS ] ;

  foobar3( array ) ;

    delete[] array ;              
}

an option which combines the above two ideas:


void foobar2( int** array, ind rows, int cols )
{
   // set all elements to 8
       for( int i = 0 ; i < rows ; ++i )
               for( int j = 0 ; j < cols ; ++j )
                       array[i][j] = 8 ;
}

int main()
{
  int ROWS = 5, COLS = 4 ;
  int** array = new int* [ROWS] ;
    
  array[0] = new int[ ROWS * COLS ] ;
    
  for ( int i = 1 ; i < ROWS ; ++i )
      array[i] = array[i-1] + COLS ;

  foobar2( array ) ;

    delete[] array[0] ;
    delete[] array ;
}