Algorithms on matrix. Pointer/No pointer in the prototype issue.

  • (2 Pages)
  • +
  • 1
  • 2

26 Replies - 811 Views - Last Post: 24 February 2013 - 05:32 PM Rate Topic: -----

#16 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5940
  • View blog
  • Posts: 12,866
  • Joined: 16-October 07

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 20 February 2013 - 06:17 AM

Stop right now. Why the hell are you passing (matrix, rows, cols) all over the place? Why isn't this a class and be done with it?

e.g.
class Matrix {
public:
	Matrix(unsigned rows, unsigned cols);
	Matrix(const Matrix &);
	~Matrix();
	unsigned getRows() const;
	unsigned getCols() const;
	int getValue(unsigned row, unsigned col) const;
	void setValue(unsigned row, unsigned col, int value);
private:
	unsigned rows, cols;
	int *data;
};

void print(const Matrix &);



Arrays are messy and unsafe. You wrap them up in a class and work from there. At the very least, you do cleanup with the destructor to avoid memory leaks.
Was This Post Helpful? 1
  • +
  • -

#17 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3666
  • View blog
  • Posts: 11,496
  • Joined: 05-May 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 20 February 2013 - 06:50 AM

View Postdomenico, on 20 February 2013 - 07:54 AM, said:

It was late yesterday and I really didn't explained myself properly.
What I wanted to say is
If matrixes work like that ( index = row * WIDTH_OF_MATRIX + col ),
why did I get different outputs when I changed my printMatrix from this
printMatrix( const int * const matrix, const int ROWS, const int COLS )
{
   for ( int i = 0; i < ROWS * COLS; ++i )
   {
      cout << *( matrix + i ) << '\t';
      if ( ( i + 1 ) % COLS == 0 )
         cout << '\n';
   }
}

to this
void printMatrix( int ** const matrix, const int ROWS, const int COLS )
{			
	for ( int row = 0; row < ROWS; ++row )
	{
		for ( int col = 0; col < COLS; ++col )
			cout << matrix[ row ][ col ] << '\t';
			
		cout << '\n';
	}
}


Shouldn't the second inherently do the same thing as the first one?


The results don't match because the first function passes a pointer to integer, while the latter passes a pointer to a pointer of integer. So in the first code, matrix + i is computing matrix + i * sizeof(int) as the actual physical memory location of the integer, whereas the second code's matrix[row][col] is computing matrix + row * sizeof(int *) + col * sizeof(int).

This post has been edited by Skydiver: 20 February 2013 - 06:50 AM

Was This Post Helpful? 1
  • +
  • -

#18 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3666
  • View blog
  • Posts: 11,496
  • Joined: 05-May 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 20 February 2013 - 07:05 AM

Don't let our responses to your questions discourage you from asking more questions. I can see that you want to understand how the language works, and hence the series of questions you have. I remember having the same type of questions as well when I was learning C, but my approach to figuring things out was to look at the disassembly to see what was really happening. I had that luxury because I had taught myself assembly prior to learning C, and was also lucky enough to be using a "dumb" compiler that didn't optimize the code too much.

What book are you using to learn C/C++ ? I would have expected it to explain one dimensional and two dimensional arrays, but just in case, I hope that this can supplement your learning: http://www.cplusplus...utorial/arrays/
Was This Post Helpful? 1
  • +
  • -

#19 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1112
  • View blog
  • Posts: 4,619
  • Joined: 09-June 09

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 20 February 2013 - 09:20 PM

Quote

The results don't match because the first function passes a pointer to integer, while the latter passes a pointer to a pointer of integer.

I think he is more interested on why the one dimensional implementation output does not match the two dimensional output - not the specific differences in the implementation.

The reason why your outputs don't match is probably because of the way you are outputting them (might wanna double check the modulus operation).

Anyways, maybe a working example of the two different implementations will help clarify.

The results don't match because the first function passes a pointer to integer, while the latter passes a pointer to a pointer of integer.

#include <iostream>

struct Matrix2D {
   int **data;
   int rows; 
   int cols;
};

struct Matrix1D {
   int *data;
   int rows;
   int cols;
};

void initMatrix1D(Matrix1D &matrix, int rows, int cols) {
   matrix.rows = rows;
   matrix.cols = cols;
   matrix.data = new int[rows * cols];
   for(int i=0; i<rows * cols; i++)
      matrix.data[i] = i;
}

void initMatrix2D(Matrix2D &matrix, int rows, int cols) {
   matrix.rows = rows;
   matrix.cols = cols;
   matrix.data = new int*[rows];
   for(int i=0; i<rows; i++) {
      matrix.data[i] = new int[cols];
      for(int j=0; j<cols; j++) {
         matrix.data[i][j] = i * rows + j;
      }
   }
}

void printMatrix1D(Matrix1D &matrix) {
   for(int i=0; i<matrix.rows * matrix.cols; i++) {
      std::cout<<matrix.data[i]<<" ";
      if(i && i % matrix.cols == 0)
         std::cout<<std::endl;
   }
   std::cout<<std::endl;
}

void printMatrix2D(Matrix2D &matrix) {
   for(int i=0; i<matrix.rows; i++) {
      for(int j=0; j<matrix.cols; j++) {
         std::cout<<matrix.data[i][j]<<" ";
      }
      std::cout<<std::endl;
   }
   std::cout<<std::endl;
}

int main() {
   Matrix1D mat1D;
   Matrix2D mat2D;

   initMatrix1D(mat1D, 5, 5);
   initMatrix2D(mat2D, 5, 5);

   printMatrix1D(mat1D);
   printMatrix2D(mat2D);


   return 0;
}


This post has been edited by jjl: 20 February 2013 - 09:20 PM

Was This Post Helpful? 0
  • +
  • -

#20 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 21 February 2013 - 12:58 PM

View PostSkydiver, on 20 February 2013 - 06:50 AM, said:

The results don't match because the first function passes a pointer to integer, while the latter passes a pointer to a pointer of integer. So in the first code, matrix + i is computing matrix + i * sizeof(int) as the actual physical memory location of the integer, whereas the second code's matrix[row][col] is computing matrix + row * sizeof(int *) + col * sizeof(int).


What do you mean sizeof ( int *)? On my PC sizeof( matrix[ 0 ] ) is 4.

Quote

I think he is more interested on why the one dimensional implementation output does not match the two dimensional output - not the specific differences in the implementation.


I see no better way to know why the two implementations differ than by knowing how my machine interprets my code.
I checked your code, and the output part behave exacly as I'd have expected.
Though, I don't expect the two output methods below not priting the same thing.
#include <iostream>
using std::cout;
using std::endl;

int main( )
{
	int rows = 3;
	int cols = 4;
	
	int ** matrix = new int * [ rows ];
	for ( int row = 0; row < rows; ++row )
		matrix[ row ] = new int [ cols ];

	// checking what skydiver said...
	cout << "matrix[ 0 ], is a pointer having size: " << sizeof( matrix[ 0 ] ) << endl;

	for ( int row = 0; row < rows; ++row )
		for ( int col = 0; col < cols; ++col )
			matrix[ row ][ col ] = row * cols + col + 1;
			
	cout << "Let's print the matrix using method #1:" << endl;		
	for ( int row = 0; row < rows; ++row )
		for ( int col = 0; col < cols; ++col )
			cout << matrix[ row ][ col ] << ( ( col + 1 ) % cols == 0 ? "\n" : "\t" );
		
	cout << "Let's print the matrix using method #2:" << endl;
	for ( int i = 0; i < rows * cols; ++i )
		cout << *( matrix + i ) << ( ( i + 1 ) % cols == 0 ? "\n" : "\t" );
		
	// Why method #1 and method #2 output is not the same?
	// Aren't matrix's elements disposed in coutiguous cells of memory starting from the one pointed by matrix?
	
	cout << "Freeing matrix memory . . ." << endl;
	for ( int row = 0; row < rows; ++row )
		delete [ ] matrix[ row ];
	delete [ ] matrix;
	
	return 0;
}


I posted this code on codepad.org where you can see the output without compiling it on your own
http://codepad.org/uKZRcxMp

This post has been edited by domenico: 21 February 2013 - 01:01 PM

Was This Post Helpful? 0
  • +
  • -

#21 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 21 February 2013 - 01:15 PM

View PostSkydiver, on 20 February 2013 - 07:05 AM, said:

Don't let our responses to your questions discourage you from asking more questions. I can see that you want to understand how the language works, and hence the series of questions you have. I remember having the same type of questions as well when I was learning C, but my approach to figuring things out was to look at the disassembly to see what was really happening. I had that luxury because I had taught myself assembly prior to learning C, and was also lucky enough to be using a "dumb" compiler that didn't optimize the code too much.

Glad to hear that! I just started to follow a course on computer architecture that will became an assembly language course soon, as the teacher aticipated.
Nice to know it will affect in a positive way even high level language programming :)/>/>

View PostSkydiver, on 20 February 2013 - 07:05 AM, said:

What book are you using to learn C/C++ ? I would have expected it to explain one dimensional and two dimensional arrays, but just in case, I hope that this can supplement your learning: http://www.cplusplus...tutorial/arrays

I use Deitel&Deitel's C++ How To Program 2nd edition ( EDIT: I rectify, 2nd italian edition seems to be the corresponding of the 5th US edition ) (in US it's out the 7th but i really couldn't afford learning something new in english a year and a half ago), and I like it pretty much. Maybe the only negative is that it explains everything taking a lot of pages, but that's a plus for a beginner, who is left with little to no doubts on how to operate at the end of the chapters.
The first volume doesn't cover dynamic memory allocation, though... Maybe it's time to buy the second one :P/>/

This post has been edited by domenico: 21 February 2013 - 01:29 PM

Was This Post Helpful? 0
  • +
  • -

#22 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1112
  • View blog
  • Posts: 4,619
  • Joined: 09-June 09

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 21 February 2013 - 07:29 PM

Quote

Though, I don't expect the two output methods below not priting the same thing.

Ok I see what you are asking. You matrix is declared as a double pointer like so
int ** matrix = new int * [ rows ];
	for ( int row = 0; row < rows; ++row )
		matrix[ row ] = new int [ cols ];



Here are the two printing methods
cout << "Let's print the matrix using method #1:" << endl;		
	for ( int row = 0; row < rows; ++row )
		for ( int col = 0; col < cols; ++col )
			cout << matrix[ row ][ col ] << ( ( col + 1 ) % cols == 0 ? "\n" : "\t" );
		
	cout << "Let's print the matrix using method #2:" << endl;
	for ( int i = 0; i < rows * cols; ++i )
		cout << *( matrix + i ) << ( ( i + 1 ) % cols == 0 ? "\n" : "\t" );



The problem that you are having is that you do not understand pointer indirection. When you have an array of pointers, like matrix, each element in the matrix points to another pointer.

In this line
cout << *( matrix + i ) << ( ( i + 1 ) % cols == 0 ? "\n" : "\t" );


You are dereferencing a double pointer only once. You are not getting the value of the matrix at index i, rather you are getting the address of where element i points (hence the hex outputs).

This type of output will never work because the data of the matrix is not continuous on the heap. The double array of pointers is continuous, but there pointers in the array do not have to point to consecutive memory locations on the heap.

This type of output would of worked if the 2D array were defined on the stack, where all of the memory is allocated sequentially. Multiple calls to new does not guarantee that memory will allocate sequentially.



Hope that makes sense.

This post has been edited by jjl: 21 February 2013 - 07:38 PM

Was This Post Helpful? 1
  • +
  • -

#23 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 24 February 2013 - 09:48 AM

OK, thank you for all your replies.
I tried to modfy my method#2 in something that would've worked, but I've even more confused myself :D
To print matrix on the screen I've used the statement
cout << *( matrix + i ) << ( ( i + 1 ) % cols == 0 ? "\n" : "\t" );

and that was wrong and thank to you I got why, but let's focus on the *( matrix + i ) part
At first I tried to change it with *( *(matrix) + i ) + j and here is why:
1. I want to reach the location where pointers to rows are located, so i write *(matrix), that is, dereference matrix.
2. Once I've reached them, I want to add i*sizeof( *int ) to go to the pointers that, once dereferenced, will lead me to the first element of the i th row, so I write *( *(matrix) + i ).
3. I have to add j*sizeof(int) to go to the j th element of the row ( that is, matrix[ i ][ j ] ) so I write *( *(matrix) + i ) + j.

I found I was wrong even this time, so I tried to find some correct implementation.
Both *( *(matrix + i) + j) and **(matrix + i) + j are doing fine now.
It's sad bacause, aren't they two completely different things? :S

What passage ( 1, 2 or 3 ) do you think is wrong up there?

This post has been edited by domenico: 24 February 2013 - 09:54 AM

Was This Post Helpful? 0
  • +
  • -

#24 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1112
  • View blog
  • Posts: 4,619
  • Joined: 09-June 09

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 24 February 2013 - 02:42 PM

Passage (1) is incorrect. You matrix is an array of pointers. *(matrix + ROW) will take you to a pointer to a specific row (equivalent to matrix[ROW]).

*(matrix + 0) //pointer to row 0
*(matrix + 1) //pointer to row 1
*(matrix + 2) //pointer to row 2
ect..



Now that you have a pointer to a specific row, you need to deference to a specific column by *(*(matrix + ROW) + COL) (equivalent to matrix[ROW][COL])

*((*matrix + 1) + 1) //element 1, 1 of matrix



i.e.
	int rows = 3;
	int cols = 4;
	
	int ** matrix = new int * [rows];
	for ( int row = 0; row < rows; ++row ) {
		matrix[row] = new int [cols];
      for(int col=0; col<cols; col++) 
         matrix[row][col] = row * cols + col;
   }
	
	for ( int row = 0; row < rows; ++row ) {
		for ( int col = 0; col < cols; ++col )
			cout << *(*(matrix + row) + col) << " ";
      cout<<'\n';
   }
	


This post has been edited by jjl: 24 February 2013 - 02:47 PM

Was This Post Helpful? 0
  • +
  • -

#25 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 24 February 2013 - 03:10 PM

MINUS REP IT'S OBVIOUSLY A MISCLICK.
How do I repair?

This post has been edited by domenico: 24 February 2013 - 03:12 PM

Was This Post Helpful? 0
  • +
  • -

#26 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 24 February 2013 - 03:52 PM

I see. I thought that after a dynamic matrix allocation ( let's suppose rows = 3, cols = 2 ), the heap would've been something like:

Posted Image

Now, if I understood correctly it should be more like this:

Posted Image

is it right? ( sorry for the black screen, but it's midnight here and white kills my eyes.. )

This post has been edited by domenico: 24 February 2013 - 03:56 PM

Was This Post Helpful? 0
  • +
  • -

#27 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1112
  • View blog
  • Posts: 4,619
  • Joined: 09-June 09

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 24 February 2013 - 05:32 PM

Your first diagram is more correct. Since you have a double pointer, you need two arrows (dereferences) to get to the data.

Here are some lectures on double pointers that I watched when learning systems programming. If you watch them you will understand the pointer indirection

Double Ptrs A
Double Ptrs B

This post has been edited by jjl: 24 February 2013 - 05:33 PM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2