Download files - 2.11 KB

Introduction

In C and C++, a two dimensional array is represented as an array of arrays. The array type is the same for each element and an element is accessed using the array subscript operator in row major order. For example, we may have:

int array[10][10];
...
array[0][0] = 1;

The two dimensional array is useful in many applications including math programming and data representation. For example, a system displaying historical prices of a stock may use a matrix to store data points for a given set of days. Each column may represent a day and each row may represent a set of points for the day. In such a system, one may be tempted to stream the data out using XML; however, this is not necessary. XML at times adds to the processing time of the data and expands the actual size of the data transmitted needlessly.

The built in two dimensional array has some limitations. In particular, it can not easily resize the array or allow the programmer to add another row or add another column. The functionality of adding and deleting rows and columns is useful in representing spread sheet like data. For example, a user may want to add another set of data points representing stock prices for a given day. This lead to the creation of a C++ matrix class which was designed to encapsulate this behavior.

Background

A matrix class is a class that allows for two dimensional array representation. The class was developed as a C++ template that allows the user to specify what the underlying type of the element is. However, it is implemented using a vector of a vector approach which allows for the use of the C++ array subscript operator as if the matrix class was a built in array of arrays type. The class; however, retains the ability to resize the rows and columns.

For example, the following is possible (where 'd' is a vector of a vector):

d[i][j]=k++;

In addition to the array subscript operator support, the class has the ability of allowing the user to add a row or add a column, as well as the ability to delete a row or delete a column. For example, the following is also possible:

matrix<int> m(2,4);
...
// Test delete row
m.del_row(3);
cout < < m;
...
// Test add row
matrix<int>::matrix_row_t row;
row.resize(4);
for(int i = 0; i < 4; i++) {
     row[i]=100;
}
m.add_row(3,row);
cout < < m;

Notice how the code does not use XML as an internal representation. It instead relies on the STL. The core implementation of the class is based on the following logic:

template < class T>
class matrix {
   public:
   typedef vector<vector<T> >matrix_t;
   typedef vector<T> matrix_row_t;
   typedef vector<T> matrix_col_t;
   ...
};

Where the class provides the following methods for adding and deleting a row or column:

void add_row(int _row, matrix_col_t &_col)
      throw(runtime_error);
void del_row(int _row);
void add_col(int _col, matrix_row_t &_row)
      throw(runtime_error);
void del_col(int _col);

The code to perform the add row and add column operations is slightly more complicated than one might imagine but still readable. The idea is to first create a temporary matrix with the appropriate row or column resized by one. Then the code adds the new row or column by first copying the existing matrix data into the resized temporary matrix and then adding the new row or column to it in the appropriate position. Similarly, the deleting a row or column requires creating a resized temporary matrix and copying the fields that we would like to keep into a temporary matrix. At the end of operations, the matrix is then updated with the new temporary matrix. Notice that doing these type of operations using XML as an underlying representation is not necessary or efficient. Its best to store the data using an STL container and perform the operations on those containers. As an illustration, consider the following code for 'add_row':

void add_row(int _row, matrix_col_t &_col)
      throw(runtime_error)
   {
      if(_row >= (row + 1) || _row < 0) {
         throw runtime_error("matrix<T>::add_row:: row out-of-bounds");
      }
      matrix_t tmp;
      tmp.resize(row + 1);
      for(int i = 0; i < (row + 1); i++) {
         tmp[i].resize(col);
      }
      for(int i = 0; i < _row; i++) {
         for(int j = 0; j < col; j++) {
            tmp[i][j] = m[i][j];
         }
      }
      for(int j = 0; j < col; j++) {
         tmp[_row][j] = _col[j];
      }
      for(int i = _row + 1, ii = _row; ii < row; i++, ii++) {
         for(int j = 0; j < col; j++) {
            tmp[i][j] = m[ii][j];
         }
      }
      m = tmp;
      row = row + 1;
   }

Additionally, the user can resize the rows and columns of the matrix. The class also supports an ostream operator for debugging and there are methods to stream out and stream in the data as well as an ability to dump the output in html.

void resize(int _row, int _col);
friend
ostream &operator>>(ostream &out, matrix &obj);
string stream_out() const;
void stream_in(string _m);
string to_html() const;

Using the Code

The code is easy to use and allows the user to add and delete rows and columns from the class as well as resize the rows and columns. An example use might be:

   matrix<int> m(2,4);
   matrix<int>::matrix_t &d = m.get_data();
   int k = 0;
   for(int i = 0; i < m.get_row(); i++) {
      for(int j = 0; j < m.get_col(); j++) {
         d[i][j]=k++;
      }
   }
   cout << m;

Points of Interest

The code accomplishes the stream in and stream out of the internal data without using XML. When streaming out the data, the row and column sizes are outputted followed by the data in row major order. All the elements are seperated using a single white space character. When streaming in, the row and column size are read and the data is read from the stream into the matrix. This allows us to store the data in a compact format and transmit it across a network connection if necessary. The class was designed to hold integer and floating point data.

Using XML to stream the data can actually be very costly. For example, if the matrix had 1000 rows and 1000 columns with each element representing an integer, then we would need 1000000 bytes minimum to stream the data. If XML is used to wrap each point using markup such as:

<point>0</point>

then for each integer we would be adding an additional 17 bytes of data. Additionally, we would need to identify the rows and columns using markup. Of course this would need to be processed using an XML processor which would further add to the processing time and complexity of the code. However, looking at the matrix class stream out and stream in operators, we have the following simple and efficient logic both in terms of space and time complexity:

string stream_out() const
   {
      ostringstream out;
      out << row << " " << col << " ";
      for(int i = 0; i < row; i++) {
         for(int j = 0; j < col; j++) {
            out << m[i][j] << " ";
         }
      }
      return out.str();
   }
   void stream_in(string _m)
   {
      istringstream in(_m,istringstream::in);
      in >> row;
      in >> col;
      m.resize(row);
      for(int i = 0; i < row; i++) {
         m[i].resize(col);
      }
      for(int i = 0; i < row; i++) {
         for(int j = 0; j < col; j++) {
            in >> m[i][j];
         }
      }
   }

A C++ Matrix Class