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);
...
m.del_row(3);
cout < < m;
...
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];
}
}
}
