Title: Student Code Critique Competition 33

This is an interesting case; the student knows they have a problem and have even gone to the extent of trying the program on two different compilers. However they don't seem to know what to do with the results of their test! The first thing to do was to try and reproduce the problem.

This was surprisingly hard - I compiled the code and tested it with a matrix size of 3 and it seemed to work perfectly with Microsoft VC 6.0.

Microsoft VC 7.1 failed to compile the program - <iostream.h> is obsolete - so I changed it to the ISO standard <iostream> and added the appropriate std:: prefixes to cin, cerr and endl. The code again seemed to work faultlessly.

I next tried mingw and gcc also complained that the program used iostream.h not iostream (so I used the file fixed for VC 7.1) and it also complained that main should return int. So I'm not sure what version of gcc the student was using.

My first response in this sort of situation would usually be to try and get a better fault report from the student. I'd want the answer to three questions:

However the Student Code Critique is not interactive in this sense so I'll just press on...

What does it mean when a program works when compiled with one compiler but not with another?

In my experience this is usually because the program accesses memory it shouldn't be using. The underlying problem probably occurs with the code generated by both compilers, but there are no (obvious) symptoms with one of them. This is because the actual layout of memory is different in the two compilers (or even with the same compiler when, for example, the optimiser is turned on).

It is very often worth compiling and running a program with multiple compilers - sometimes you get more information from additional compiler warnings and other times the runtime error handling provides additional clues to the problem.

In this case we only have the program failing with one compiler, and even worse I can't reproduce it. So without more ado let's dive into the code itself.

On reading the code it is fairly clear what the problem is; the first allocation of memory for the variables A, B and C does not involve N.

new (double *) allocates enough memory for a single double* - but we actually want an array of N pointers.

It is at first sight surprising that the code works at all - it just goes to show that writing only a little bit off the end of allocated memory can sometimes seem to work!

So it would be very easy to suggest the student changes:

A = new (double *);

to:

A = new double*[N];

and similarly for B and C.

But is this helpful? As the saying has it, "give a man a fish and you feed him for a day, teach a man to fish and you feed him for life".

There are some other problems also lurking in this code but attempting to fix them directly leads into deeper waters.

I would recommend that most users of C++ start out by staying well away from operator new and letting the standard library allocate the memory for them where possible.

So, looking at the problem with a library user's hat on, what do I want?

I want a class which gives me the characteristics of a matrix.

Sadly the standard library doesn't come with one of these - but it does supply a vector class and we can create a matrix by having a vector of vectors. Alternatively we can search for a matrix class that we can download from the Internet. A quick search with "C++ matrix class" reveals several possible candidates.

If we want to stick with the standard library solution then we can define a row as a vector of double and a matrix as a vector of rows:

#include <vector>
class row : public std::vector<double> {};
class matrix : public std::vector<row> {};

Now the code to initialise the matrices is a matter of resizing the vectors rather than allocating the memory ourselves. This has several benefits over using raw pointers

I hate writing anything twice, so I would probably suggest the student writes a simple helper function and calls it when needing to initialise a matrix:

void init(matrix & A, int size) {
  A.resize(size);
  for(int idx = 0; idx != size; ++idx)
    A[idx].resize(size);
}

This would make the code as presented work immediately and the student would also hopefully have less problems with memory allocation in future.

I might suggest, as an exercise for the student, that they move the matrix multiplication into a separate function so it could be reused and to improve the readability of the code. I would probably initially suggest a free standing function with a prototype like this:

matrix operator*(matrix const & A, matrix const & B);

So my initial solution to the student's problem looks like this:

#include <iostream>
#include <vector>
class row : public std::vector<double> {};
class matrix : public std::vector<row> {};
void init(matrix & A, int size) {
  A.resize(size);
  for(int idx = 0; idx != size; ++idx)
    A[ idx ].resize( size );
}
matrix operator*(matrix const & A, matrix const & B) {
  int const N(A.size());
  matrix result;
  init(result, N);
  for(int k=0; k<N; k++)
    for(int i=0; i<N; i++) {
      double sum = 0.0;
      for(int j=0; j<N; j++)
        sum += A[i][j]*B[j][k];
      result[i][k] = sum;
    }
  return result;
}
int main(void) {
  int N, i, j;
  matrix A, B;
  std::cout << "Dimension of Matrix ?" << std::endl;
  std::cin >> N;
  init(A, N);
  init(B, N);
  for(i=0; i<N; i++)
    for(j=0; j<N; j++) {
      std::cout << "A[" << i << "][" << j << "] = ?"
                << std::endl;
      std::cin >> A[i][j];
    }
  for(i=0; i<N; i++)
    for(j=0; j<N; j++) {
      std::cout << "B[" << i << "][" << j << "] = ?"
                << std::endl;
      std::cin >> B[i][j];
    }
  matrix C = A * B;
  std::cout << std::endl << std::endl << std::endl;
  for(i=0; i<N; i++)
    for(j=0; j<N; j++)
      std::cout << "C[" << i << "][" << j << "] = "
                << C[i][j] << std::endl;
  return 0; // keeps MSVC happy
}

We would then have two free-standing functions operating on objects of the matrix class; we can then move on to suggest ways in which the row and matrix classes could be enhanced by using member functions and constructors. We might then move on to discuss using composition rather than inheritance.

There are a number of other ways this solution could also be improved, for example to generalise by data type or to improve the input and output, but at this stage I suspect trying to do any more would simply confuse things for the student.

The main problem with this code is that it is structured badly. You should always split long functions up into small simple units, which makes programs clearer and more reusable. It also makes it easier to test. Whenever you write code, turn it into generic functions or classes that can be reused. So what you really want is a general-purpose Matrix class that you can use in any application that requires a matrix. Rewrite your main() function to look something like this:

int main() { 
  Matrix a, b; 
  int size = input_matrix_size(); 
  input_matrix(size, a); 
  input_matrix(size, b); 
  std::cout << a * b; 
  return 0; 
}

This makes the main() function much clearer, and all the real work is done elsewhere. We have changed the return type of main() function to be standards conforming, and it is conventional to return 0 from main() to indicate no error. Other minor problems with your code are that it is in general preferable to use pre-increment ++j instead of postincrement j++ and that you should #include <iostream>, not the deprecated <iostream.h>. That will require you to put using namespace std in your code, or else qualify cout, cin and endl with std::. Don't #include <process.h>, that isn't needed. Your code should check that its inputs are valid.

The constructor of the Matrix class should allocate the data, while the destructor should free the data. This highlights another problem with your code: you don't free the arrays. In commercial software, forgetting to free memory can be disastrous since the system will eventually run out of memory. Therefore we need to pass the size of the array to the constructor, and since we are writing a library class, we might as well cater for non-square matrices as well. Your code did not work reliably because you did not allocate the first array correctly, it should be an array of size N of arrays of size N. Note also how the array is deleted in the destructor, it is important to use the delete [] notation when deleting an array, since this will matter when objects in the array have destructors.

One should hide the internal data of the class by making it private, and access and manipulate the data via accessor methods. One can overload the [] operator to access the cells of the matrix, so that if you have a matrix m, you can write m[x] to access a column in your matrix, and therefore m[x][y] to access a particular cell. So here is a Matrix class that allocates the data, and provides accessor methods:

class Matrix1 {
  unsigned width, height; 
  double **cols; 
public: 
  Matrix1(unsigned w, unsigned h)
      : width(w), height(h) {
    cols = new double*[height]; 
    for(unsigned i=0; i<width; ++i) 
      cols[i] = new double[height]; 
  }
  ~Matrix1() {
    for(unsigned i=0; i<width; ++i) 
      delete [] cols[i]; 
    delete [] cols; 
  }
  double *operator[](unsigned col) {return cols[col];} 
  unsigned get_width()  { return width; } 
  unsigned get_height() { return height; } 
};

So we're done right? Not by a long way! The most important problem is safety, and at the moment the copy constructor and the assignment operator don't work correctly, so writing

a = b; 
Matrix x = y;

will crash the program. The compiler provides default implementations that will in this case do the wrong thing. It will only copy the pointer, so some arrays will not be freed, whilst other arrays will be freed twice. The constructor of Matrix is not exception safe, and could leak memory on an exception. Making the class robust and writing safe copy constructors and assignment operators would be straightforward, but quite laborious. The code does not initialize the cells in the matrix to zero, which would be a nice feature of the constructor.

You can replace C-style arrays with std::vector, and your code becomes

class Matrix2 {
  unsigned width, height; 
  std::vector<std::vector<double> > cols; 
public: 
  Matrix2(int w, int h) : width(w), height(h),

      cols(w, std::vector<double>(h)) {}
  std::vector<double> &operator[](unsigned col)
                        { return cols[col]; } 
  unsigned get_width()  { return width; } 
  unsigned get_height() { return height; } 
}; 

This code is much shorter, clearer, nicer and safer, since all of the functionality we need has already been implemented by the vector class, and all of the default methods like copy construction, assignment and destruction are all taken care of by the vector. The : notation in the Matrix is used to initialize its members, which initializes the array with w elements each a vector of length h, and the vector initializes the contents to zero.

The moral of the story is that one should almost never use pointers and arrays, always use STL containers and iterators. Because Matrix is a generic container, it should comply with the norms of the STL as much as possible. This allows it to be used with STL-compliant algorithms, and will make it easier to use and understand. So it needs as much standard functionality as appropriate, such as a begin(), end(), iterator, const_iterator, reverse_iterator, swap(), at() and operators like +, -, *. One should provide const and non-const versions of methods, so that the container is usable when const. Implement operators << and >> to read and write the matrix to a stream. Like other containers, it should be templated on the type it contains, so that we could could have a matrix of any type of value, such as integers, bools, floats, std::complex or even other matrices. One might also perform bounds checking.

Although std::vector provides a perfectly acceptable solution, the C++ STL has std::valarray, that is intended specifically for writing multi-dimensional arrays. It is much more versatile since it can use "slices", linear subsets of an array, based upon FORTRAN's BLAS (Basic Linear Algebra Subprograms) library, offering high-performance multi-dimensional array manipulation. [Stroustroup] provides an implementation of a Matrix class based upon valarray and slices, so I do not need to repeat it here. A slice can represent any linear subsequence of an array, so can represent both a row and a column. However it may be easier to organize the array into columns and just return the correct offset into the array.

T *operator[](unsigned col)
                       { return &data[height*col]; } 
const T *operator[](unsigned col) const
                       { return &data[height*col]; } 

If the size of the matrix is fixed, it may be better to specify the dimensions of the matrix in template parameters. This has the advantage that the compiler can then generate optimal code by unrolling loops, and the contents of the matrix can be stored inside the matrix object itself, rather than performing additional memory allocation and deallocation.The crucial benefit is that the dimensions of the matrices can be checked by the compiler, so that matrices of the wrong sizes are prevented from being added or multiplied, and the compiler can check that a matrix is square for certain operations. It is much better to catch errors at compile-time than run-time.

template<typename T, unsigned W, unsigned H=W> 
class Matrix3 {
  T cells[W][H]; 
public: 
  T *operator[](unsigned col) { return cells[col]; } 
  const T *operator[](unsigned col) const
                              { return cells[col]; } 
  unsigned get_width() const  { return W; } 
  unsigned get_height() const { return H; } 
}; 
template<typename T, unsigned W,
         unsigned H, unsigned N> 
Matrix3<T,W,H> operator*(const Matrix3<T, N, H> &m1,
                       const Matrix3<T, W, N> &m2) {
  Matrix3<T,W,H> result; 
  for(unsigned i=0; i<W; ++i) {
    for(unsigned j=0; j<H; ++j) {
      T sum = T(); // Initializes to zero
      for(unsigned k=0; k<N; ++k) 
        sum += m1[k][i] * m2[j][k]; 
      result[i][j] = sum; 
    } 
  } 
  return result; 
}

The first thing which jumps out at me as I skim through the code is the lack of any (appropriate) commenting. The code has got no comments at all, which means a big drawback to any code. The student would lose a large amount of marks if he/she was a student of mine. Not only each mentally separate piece of code needs its own comment(s), but also the code needs to be commented - say at the beginning of the program - for its (potential) reader about what it's generally supposed to do. The next overall point about this code is that the student has well tested the program, yet he/she hasn't developed any diagnosis. He/she could have done that say by observing the size of what he/she allocates (using the sizeof operator, for example).

I then start wondering whether this code really flawlessly gets compiled under any standard conforming implementation. The student has used std::cout as well as std::cin, yet he/she hasn't anywhere told the compiler that he/she means the cout and cin of std.

Another matter of style is the poor way of program interaction with its user. I'll delve deeper into that throughout the criticism below. For the moment, however, especially for students, I say that it is a very good practice to get used to let the user know what the program is supposed to do. This could easily be done using a short series of initial prompts to the user before he/she starts the I/O process. Afterwards, let's go through the code. The first line:

#include <iostream.h>

should be re-written as:

#include <iostream>

I say that because the Standard has allowed the header files to be implemented with extensions other than .h (§16.2, Phrase 5 and §17.4.1.2, Footnote 158).

The next line, in fact, led me into doubt. I checked the Standard to see whether there really is such a standard header. And, there is not. Thus

#include <process.h>

should be fully omitted. The following line

void main(void)

although may work under many implementations, is not portable (§3.6.1, Phrase 2 of 98 Standard).

int N, i, j, k;

This line should not be written here. Variables should be declared as close as possible to where they got used. Furthermore, as far as I can see, those variables are all supposed to hold sizes. Therefore, it's quite irrational to prefer int to size_t for their type. I'll again come to that as I proceed through the code.

double **A, **B, **C;

Assuming that the decision of playing with matrices using double**s is a good decision - which turns out not to be so - for the mere sake of extendibility, should be replaced by:

typedef double** Matrix;
Matrix A, B, C;

This way, the code will work easily by merely changing the typedef as he/she decides to change the data structure using which he/she wants to play with matrices.

Another big mistake is:

double sum = 0.0;

here. I'll mention in the following where it is best to do that.

using std::cout;
using std::cin;
cout << "Dimension of Matrix? " << endl;
size_t N;
cin >> N;

As you can see, I've added statements as per what I've previously spoken about. Another point about any input is to check the input stream for (possible) errors. Hence:

if(!cin) { ... }

(Perhaps the use of some exceptions.)

A = new (double *) [N];
B = new (double *) [N];
C = new (double *) [N];

When you do:

A = new (double *);

what you get is a single pointer to a pointer to double, and not an array of pointers to pointer to double. To get the latter, you need to write what I have.

I tried a lot to find out why the student has come to the observation that it works for N = 2, whilst it does not for N = 3. The only reasonable guess of mine is the following snippet from the Standard (§18.4.1.2, Footnote 211):

That is, I think for N = 2, the above space for storing supplemental information allocated invisibly by VC++ suffices, whilst it does not suffice for N = 3. I guess, furthermore, that for little N's - which are much likely to suffice for the student's test cases - cygwin does a similar job in allocating a space which happens to be satisfactory.

Another important point, the necessity of which may not become that obvious at academy, but somehow plays a vital role in commercial programming, is the validation of any try for allocation. This means that, under normal conditions such as that of ours, any such try should be put in a try/catch block.

for(size_t i = 0; i < N; ++i) {
  A[i] = new double[N];
  B[i] = new double[N];
  C[i] = new double[N];
}

Yep! That's right. I've defined i inside the for body. The reason is what I've already mentioned; variables should always be declared as close to their application as possible. Furthermore, they should not be present outside the scope they are supposed to function.

Anybody having a little experience of overloading in C++ knows enough why should one always prefer the prefix operator ++ to its postfix counterpart. Although you may argue that, in this case, we're dealing with built-in types, and no modern compiler may leave optimising it off, I insist on what I told. Why? 'Cause of two important points: First, this kind of optimisation - although quite common - is not guaranteed. Second, it is a good practice to get used to that. Having that done, you'll never lose efficiency whilst dealing with objects constructing/destructing of which is much more than wasteful.

Again this for body should all lie in a try/catch block. Let's go further.

cout << "Enter matrix A: (Please enter each
         row in one line.)" << endl;
for(size_t i = 0; i < N; ++i) {
  for(size_t j = 0; j < N; ++j)
    cin >> A[i][j];
  cin.get();
}

There are many ways for inputting a matrix. The one chosen by the student is not appropriate however. What's wrong with it? It prompts something to the user each time, and asks him/her to enter each element again and again. One plausible way seems to be that of mine, in which I ask the user only one time about what he/she is supposed to do. This way has got another advantage, and that's the fact that it well equally works for when we want to input from files. Furthermore, human beings find it much more natural as they're working with 2 by 2 matrices. We should then check the input stream for possible errors. The next for body should be replaced with a similar one like above.

for(size_t i = 0; i < N; ++i)
  for(size_t j = 0; j < N; ++j) {
    double sum = 0.0;
    for(size_t k = 0; k < N; ++k)
      sum += A[i][k] * B[k][j];
    C[i][j] = sum;
  }

That is, I've defined sum at the best possible position. Anywhere outside this body sum would be meaningless. After a few blank lines in output

cout << "A * B = " << endl;
for(size_t i = 0; i < n; ++i) {
  std::copy(C[i][0], C[i][N],
    std::ostream_iterator<double>(cout, " "));
  cout << endl;
}

Here, I've suited the already-at-hand tool of the Standard, std::copy(). Note that this needs the addition of #include <algorithm> as well as #include <iterator> at the top of the program.

And another extremely important point which this student - like many other newbies - has forgotten is to delete[] the allocated memory. That is:

for(size_t i = 0; i < N; ++i) {
  delete[] A[i];
  delete[] B[i];
  delete[] C[i];
}
delete[] A;
delete[] B;
delete[] C;

And, the rest of the code which has not been included in the journal...

Assuming that there is no better candidate than raw pointers, I recommend the student to reconsider the code. Yes, the code is quite trivial. But, it's a mixture of many different creatures. It does its input, it constructs its own objects, it performs the multiplication, it then outputs the resulting matrix, and finally, it destructs the objects. These are the major steps, not? This is a very good point showing us the necessity of splitting the code into different functions with names indicating what's intended. Here is what will be the result: (All the following code is off-hand. The deadline is close, and I've got to finish the criticism. So, please don't be fussy.)

int main() {
  cout << "This programme ...";
  cout << "Dimension of matrices? ";
  size_t N;
  cin >> N;
  Matrix A, B, C;
  Construct(A, N);
  Construct(B, N);
  Construct(C, N);
  Input(A, cin);
  Input(B, cin);
  C = Multiply(A, B);
  Output(C, cout);
  Destruct(A);
  Destruct(B);
  Destruct(C);
  return 0;
}

I'm wondering whether there could ever be a guy aware of OOP, whom the above code does not whet appetite for assembling a class - an ADT, in other words - which serves the job much neater.

In fact, considering the very little code above, one should have gotten quite sure that playing with raw pointers also very dangerous, is very cumbersome. A well arisen question then is that isn't there any facility in C++ which can ease the job? Oh yes, there are. You can say use their majesty vector<>s. This way, you get rid of all the allocation, evaluation of allocation, and deallocation stuff. All of those bothers are now settled by the aids of automatically served features of vector<>. This way, you should end up with something like

int main() {
  cout << "Dimension? ";
  Matrix<double>::size_type n;
  cin >> n ;
  Matrix<double> A(n), B(n), C(n);
  cout << "Enter A:" << endl;
  cin >> A;
  cout << "Enter B:" << endl;
  cin >> B;
  C = A * B;
  cout << "A * B = " << endl << C;
  return 0;
}

Do you see what's happened? You've ended up with nothing apart from the abstract problem at hand. Full stop. Wow!

The editor's choice is:

Calum Grant

Please email <francis@robinton.demon.co.uk> to arrange for your prize.