for_each() and two-dimensional array

[Eric Lilja]

Hello, in one of my classes I have this member variable:
Tile ***tiles_; where Tile is another one of my classes.

>From this pointer-to-pointer-to-pointer-to-Tile I allocate a two-

dimensional array of Tile-pointers (dimensions are of equal sizes).
Last, I allocate a Tile object for each pointer in the 2d-array.
Anyway, I often need to traverse the entire array and perform
operations so until now I've used alot of constructs like this:

for (int y = 0; y < num_rows; ++y)
{
for (int x = 0; x < num_cols; ++x)
{
// Do something
}
}

I was thinking of if I can use std::for_each() instead and if it would
be a good idea. I made the following test program and it prints 1, 2,
3, 4 on two different compilers so it seems to be correct, and
standards-compliant but I wanted to hear what you have to say about
it.
#include <iostream>

using namespace std;

struct foobar
{
void operator()(const int i)
{
cout << i << endl;
}
};

int main()
{
const int rows = 2;
const int cols = 2;
int foo[cols][rows] = {{1, 2}, {3, 4}};
for_each(&(foo[0][0]), &(foo[0][0]) + (rows * cols), foobar());
}

- Eric

[John Harrison]

Eric Lilja wrote:

Hello, in one of my classes I have this member variable:
Tile ***tiles_; where Tile is another one of my classes.

>>From this pointer-to-pointer-to-pointer-to-Tile I allocate a two-

dimensional array of Tile-pointers (dimensions are of equal sizes).
Last, I allocate a Tile object for each pointer in the 2d-array.
Anyway, I often need to traverse the entire array and perform
operations so until now I've used alot of constructs like this:

for (int y = 0; y < num_rows; ++y)
{
for (int x = 0; x < num_cols; ++x)
{
// Do something
}
}

I was thinking of if I can use std::for_each() instead and if it would
be a good idea. I made the following test program and it prints 1, 2,
3, 4 on two different compilers so it seems to be correct, and
standards-compliant but I wanted to hear what you have to say about
it.
#include <iostream>

using namespace std;

struct foobar
{
void operator()(const int i)
{
cout << i << endl;
}
};

int main()
{
const int rows = 2;
const int cols = 2;
int foo[cols][rows] = {{1, 2}, {3, 4}};
for_each(&(foo[0][0]), &(foo[0][0]) + (rows * cols), foobar());
}

- Eric

You code makes the assumption that the 2D array is contiguous in memory
(in effect it treats a 2D array as if it were a 1D array). This is true
for the test code you've written but is not necessarily true for your
real code.

The way to do this correctly would be to stop using all those pointers
(you're writing C++ after all). For_each doesn't need pointers, instead
it can use iterators. Write a 2D array class, that has an method that
returns an iterator which allows you to iterate through the 2D array as
if it were 1D. Something like this

class TileArray_2D
{
TileArray_2D(int rows, int cols);
TileIterator_1D begin_1d();
TileIterator_1D end_1d();
};

class TileIterator_1D
{
Tile* operator*();
TileIterator_1D& operator++();
};
TileArray_2D foo(rows, cols);
for_each(foo.begin_1d(), foo.end_1d(), foobar());

I think you're in need of a good book on C++ and the standard template
library. Nicolai Josuttis is your man.

john

[Eric Lilja]

On 23 Maj, 07:24, John Harrison <[e-mail]:

Eric Lilja wrote:

Hello, in one of my classes I have this member variable:
Tile ***tiles_; where Tile is another one of my classes.

>From this pointer-to-pointer-to-pointer-to-Tile I allocate a two-

dimensional array of Tile-pointers (dimensions are of equal sizes).
Last, I allocate a Tile object for each pointer in the 2d-array.
Anyway, I often need to traverse the entire array and perform
operations so until now I've used alot of constructs like this:

for (int y = 0; y < num_rows; ++y)
{
for (int x = 0; x < num_cols; ++x)
{
// Do something
}
}

I was thinking of if I can use std::for_each() instead and if it would
be a good idea. I made the following test program and it prints 1, 2,
3, 4 on two different compilers so it seems to be correct, and
standards-compliant but I wanted to hear what you have to say about
it.
#include <iostream>

using namespace std;

struct foobar
{
void operator()(const int i)
{
cout << i << endl;
}
};

int main()
{
const int rows = 2;
const int cols = 2;
int foo[cols][rows] = {{1, 2}, {3, 4}};
for_each(&(foo[0][0]), &(foo[0][0]) + (rows * cols), foobar());
}

- Eric

You code makes the assumption that the 2D array is contiguous in memory
(in effect it treats a 2D array as if it were a 1D array). This is true
for the test code you've written but is not necessarily true for your
real code.

This is one thing that worries me.

>
The way to do this correctly would be to stop using all those pointers
(you're writing C++ after all). For_each doesn't need pointers, instead
it can use iterators. Write a 2D array class, that has an method that
returns an iterator which allows you to iterate through the 2D array as
if it were 1D. Something like this

I know perfectly well it doesn't need pointers. Nine times out of ten,
if
not more, I use it with iterators. However, I think that it's very
convenient to able to use raw pointers with for_each() and others.

>
class TileArray_2D
{
TileArray_2D(int rows, int cols);
TileIterator_1D begin_1d();
TileIterator_1D end_1d();

};

class TileIterator_1D
{
Tile* operator*();
TileIterator_1D& operator++();

};

TileArray_2D foo(rows, cols);
for_each(foo.begin_1d(), foo.end_1d(), foobar());

I think I will do this, but what should my end() return?

>
I think you're in need of a good book on C++ and the standard template
library. Nicolai Josuttis is your man.

I have it already.

>
john

- Eric

[John Harrison]

>>

>TileArray_2D foo(rows, cols);
for_each(foo.begin_1d(), foo.end_1d(), foobar());

I think I will do this, but what should my end() return?

Doesn't really matter, all that matters is that if you have an iterator
that references the last element of the array, and then you increment
that iterator, it will then be equal to the iterator that end() returns.

john

[Eric Lilja]

On 23 Maj, 22:18, John Harrison <[e-mail]:

TileArray_2D foo(rows, cols);
for_each(foo.begin_1d(), foo.end_1d(), foobar());

I think I will do this, but what should my end() return?

Doesn't really matter, all that matters is that if you have an iterator
that references the last element of the array, and then you increment
that iterator, it will then be equal to the iterator that end() returns.

john

Ok, here's my result. I tried to make my extremely simple matrix class
with a nested iterator class reusable, so I wrote a templated base
class (abstract) that handles everything except the allocating of the
elements in the matrix. Here's the resulting code:

MatrixBase.h:
#ifndef MATRIXBASE_H
#define MATRIXBASE_H

template<typename T>
class MatrixBase
{
public:
MatrixBase(int num_rows, int num_columns)
: num_rows_(num_rows), num_columns_(num_columns) {}

virtual ~MatrixBase() { /* TODO: Deallocate memory. */ }

virtual void allocate() = 0;

class MatrixIterator
{
public:
MatrixIterator()
: matrix_(0), row_(-1), column_(-1), num_rows_(-1),
num_columns_(-1) {}

friend class MatrixBase;

T * operator*()
{
if (row_ < 0 || row_ >= num_rows_ ||
column_ < 0 || column_ num_columns_)
throw; // FIXME

return matrix_->tiles_[column_][row_];
}

MatrixIterator& operator++()
{
if (row_ == num_rows_ - 1 && column_ == num_columns_ - 1)
{
row_ = -4711; /* -4711 is a special value that denotes
end. */
column_ = -4711;
}
else if (column_ == num_columns_ - 1)
{
++row_;
column_ = 0;
}
else
{
++column_;
}

return *this;
}

bool operator!=(const MatrixBase::MatrixIterator& rhs)
{
return
matrix_ != rhs.matrix_ || row_ != rhs.row_ ||
column_ != rhs.column_;
}

private:
MatrixIterator(MatrixBase *matrix, int num_rows,
int num_columns, int row = 0, int column = 0)
: matrix_(matrix), num_rows_(num_rows),
num_columns_(num_columns), row_(row), column_(column) {}

MatrixBase *matrix_;

int num_rows_;
int num_columns_;
int row_;
int column_;
};

MatrixIterator begin()
{
return MatrixIterator(this, num_rows_, num_columns_);
}

MatrixIterator end()
{
return MatrixIterator(this, num_rows_, num_columns_, -4711,
-4711);
}

protected:
T ***tiles_;

int num_rows_;
int num_columns_;
};

#endif

TileMatrix.h:
#ifndef TILEMATRIX_H
#define TILEMATRIX_H

#include "MatrixBase.h"

#include <cassert>
#include <iostream>

class Tile
{
public:
Tile(int x, int y) : x_(x), y_(y) {}

friend std::ostream& operator<<(std::ostream& os, const Tile& rhs)
{
os << "(x, y) = (" << rhs.x_ << ", " << rhs.y_ << ")";

return os;
}

private:
int x_, y_;
};

class TileMatrix : public MatrixBase<Tile>
{
public:
TileMatrix(int rows, int columns) : MatrixBase<Tile>(rows, columns)
{ allocate(); }

virtual ~TileMatrix() {}

virtual void allocate()
{
assert(num_rows_ 0 && num_columns_ 0);

tiles_ = new Tile**[num_rows_];

for (int y = 0; y < num_rows_; ++y)
{
tiles_[y] = new Tile*[num_columns_];

for (int x = 0; x < num_columns_; ++x)
{
tiles_[y][x] = new Tile(x, y);
}
}
}
};

#endif
Testprogram in main.cpp:
#include "TileMatrix.h"

using namespace std;

int
main()
{
TileMatrix matrix(2, 2);

for (TileMatrix::MatrixIterator itr = matrix.begin(); itr !=
matrix.end(); ++itr)
{
cout << *(*itr) << endl;
}
}
Sorry for such a lot of code, but I couldn't make it much smaller
without taking away the base functionality that needs to be there. I
did leave out deallocation code in this post, though, to get rid of a
few lines at least. When run, the test program outputs:
$ ./runme.exe
(x, y) = (0, 0)
(x, y) = (0, 1)
(x, y) = (1, 0)
(x, y) = (1, 1)

So it seems to work. Is that what you had in mind I should do, John?
Others are more than welcome to respond too, of course. Writing the
above code was a good exercise for me. :)

- Eric

[John Harrison]

Comments below, but basically looks fine to me.

Eric Lilja wrote:

On 23 Maj, 22:18, John Harrison <[e-mail]:

>>>TileArray_2D foo(rows, cols);
for_each(foo.begin_1d(), foo.end_1d(), foobar());
I think I will do this, but what should my end() return?

Doesn't really matter, all that matters is that if you have an iterator
that references the last element of the array, and then you increment
that iterator, it will then be equal to the iterator that end() returns.

john

Ok, here's my result. I tried to make my extremely simple matrix class
with a nested iterator class reusable, so I wrote a templated base
class (abstract) that handles everything except the allocating of the
elements in the matrix.

I don't understand this reasoning. Why can't the memory allocation go in
the same class as everything else?

Here's the resulting code:

>
MatrixBase.h:
#ifndef MATRIXBASE_H
#define MATRIXBASE_H

template<typename T>
class MatrixBase
{
public:
MatrixBase(int num_rows, int num_columns)
: num_rows_(num_rows), num_columns_(num_columns) {}

virtual ~MatrixBase() { /* TODO: Deallocate memory. */ }

virtual void allocate() = 0;

class MatrixIterator
{
public:
MatrixIterator()
: matrix_(0), row_(-1), column_(-1), num_rows_(-1),
num_columns_(-1) {}

friend class MatrixBase;

T * operator*()

You could drop the assumption that says you Matrix must be a matrix of
pointers. You get a bit more flexibilty that way. And I don't see
anything else that would prevent this.

You also need two versions of operator*, one const and one non-const.
Assuming you stay with pointers they would look like this

T*& operator*()
{
...
}
T* operator*() const
{
...
}

or if you switched to let your vector hold anything like this

T& operator*()
{
...
}
const T& operator*() const
{
...
}

The non-const version allows you to change elements of the vector using
the iterator.

{
if (row_ < 0 || row_ >= num_rows_ ||
column_ < 0 || column_ num_columns_)
throw; // FIXME

return matrix_->tiles_[column_][row_];
}

MatrixIterator& operator++()
{
if (row_ == num_rows_ - 1 && column_ == num_columns_ - 1)
{
row_ = -4711; /* -4711 is a special value that denotes
end. */
column_ = -4711;

Wouldn't row_ == num_rows_ be a more natural way of saying you are at
the end?

}
else if (column_ == num_columns_ - 1)
{
++row_;
column_ = 0;
}
else
{
++column_;
}

return *this;
}

bool operator!=(const MatrixBase::MatrixIterator& rhs)

Show be

bool operator!=(const MatrixBase::MatrixIterator& rhs) const

{
return
matrix_ != rhs.matrix_ || row_ != rhs.row_ ||
column_ != rhs.column_;
}

You also need

bool operator==(const MatrixBase::MatrixIterator& rhs) const

plus various other things.

Look up iterator_traits in Josuttis, you iterator isn't a fully fledged
iterator until you've fulfilled all the iterator requirements.

>
private:
MatrixIterator(MatrixBase *matrix, int num_rows,
int num_columns, int row = 0, int column = 0)
: matrix_(matrix), num_rows_(num_rows),
num_columns_(num_columns), row_(row), column_(column) {}

MatrixBase *matrix_;

int num_rows_;
int num_columns_;

The itrator class has a pointer to the matrix class, so it could get
these values from the matrix class. It's definitely good to make
iterators as small as possible since they get copied frequently.

int row_;
int column_;
};

MatrixIterator begin()
{
return MatrixIterator(this, num_rows_, num_columns_);
}

MatrixIterator end()
{
return MatrixIterator(this, num_rows_, num_columns_, -4711,
-4711);
}

protected:
T ***tiles_;

int num_rows_;
int num_columns_;
};

#endif

TileMatrix.h:
#ifndef TILEMATRIX_H
#define TILEMATRIX_H

#include "MatrixBase.h"

#include <cassert>
#include <iostream>

class Tile
{
public:
Tile(int x, int y) : x_(x), y_(y) {}

friend std::ostream& operator<<(std::ostream& os, const Tile& rhs)
{
os << "(x, y) = (" << rhs.x_ << ", " << rhs.y_ << ")";

return os;
}

private:
int x_, y_;
};

class TileMatrix : public MatrixBase<Tile>
{
public:
TileMatrix(int rows, int columns) : MatrixBase<Tile>(rows, columns)
{ allocate(); }

virtual ~TileMatrix() {}

virtual void allocate()
{
assert(num_rows_ 0 && num_columns_ 0);

tiles_ = new Tile**[num_rows_];

This allocation

>
for (int y = 0; y < num_rows_; ++y)
{
tiles_[y] = new Tile*[num_columns_];

and this allocation, could go in the base class, I think.

>
for (int x = 0; x < num_columns_; ++x)
{
tiles_[y][x] = new Tile(x, y);
}
}
}
};

#endif

Good job.

john

[Eric Lilja]

[old text removedd to make post shorter]

Ok, seems my first reply didn't make it through. At least I cannot see
it a few hours after posting so here we go again. Thanks, John, for
your valuable input! I believe I made the code a whole lot better with
your suggestions. For example, getting rid of double-storing the
number of columns of rows cleaned up alot. I haven't read the Josuttis
section you suggested yet and I know this is very lacking
implementation, but it's alot better than what I had at first. Here's
the updated code:

#ifndef MATRIXBASE_H
#define MATRIXBASE_H

#include <cassert>

template<typename T>
class MatrixBase
{
public:
MatrixBase(int num_rows, int num_columns)
: num_rows_(num_rows), num_columns_(num_columns) {}

virtual ~MatrixBase()
{
/* TODO: Deallocate memory. */
}

/* Also handle the rule of three... */

virtual void allocate()
{
assert(num_rows_ 0 && num_columns_ 0);

tiles_ = new T**[num_rows_];

for (int y = 0; y < num_rows_; ++y)
{
tiles_[y] = new T*[num_columns_];
}
}

class MatrixIterator
{
public:
MatrixIterator()
: matrix_(0), row_(-1), column_(-1) {}

friend class MatrixBase;

/*
* If we don't return a reference to a pointer, we can't do:
*itr = new Foo(bar);
*/
T *& operator*()
{
if (row_ < 0 || row_ >= matrix_->num_rows_ ||
column_ < 0 || column_ matrix_->num_columns_)
throw; // FIXME

return matrix_->tiles_[column_][row_];
}

MatrixIterator& operator++()
{
if (row_ == matrix_->num_rows_ - 1 && column_ == matrix_-

>num_columns_ - 1)

{
/*
* Now when row_ == matrix_->num_rows_ and column_ ==
matrix_->num_columns_
* that means we are at the end.
*/
++row_;
++column_;
}
else if (column_ == matrix_->num_columns_ - 1)
{
++row_;
column_ = 0;
}
else
{
++column_;
}

/* Maybe add special case for if operator++() is called on an
* end() iterator? */

return *this;
}

/* MSVC++ wants a typename here or it will issue a warning. */
bool operator!=(const typename MatrixBase::MatrixIterator& rhs)
const
{
return
matrix_ != rhs.matrix_ || row_ != rhs.row_ ||
column_ != rhs.column_;
}

/* MSVC++ wants a typename here or it will issue a warning. */
bool operator==(const typename MatrixBase::MatrixIterator& rhs)
const
{
return !(*this != rhs);
}

private:
MatrixIterator(MatrixBase *matrix, int row = 0, int column = 0)
: matrix_(matrix), row_(row), column_(column) {}

MatrixBase *matrix_;

int row_;
int column_;
};

MatrixIterator begin()
{
return MatrixIterator(this);
}

MatrixIterator end()
{
return MatrixIterator(this, num_rows_, num_columns_);
}

protected:
T ***tiles_;

int num_rows_;
int num_columns_;
};

#endif

TileMatrix.h
#ifndef TILEMATRIX_H
#define TILEMATRIX_H

#include "MatrixBase.h"

#include <iostream>

class Tile
{
public:
Tile(int x, int y) : x_(x), y_(y) {}

friend std::ostream& operator<<(std::ostream& os, const Tile& rhs)
{
os << "(x, y) = (" << rhs.x_ << ", " << rhs.y_ << ")";

return os;
}

private:
int x_, y_;
};

class TileMatrix : public MatrixBase<Tile>
{
public:
TileMatrix(int rows, int columns) : MatrixBase<Tile>(rows, columns)
{ allocate(); }

virtual ~TileMatrix() {}

virtual void allocate()
{
MatrixBase<Tile>::allocate();

/* We could use iterators here but I want call the Tile
constructor
* with its index in the matrix. */
for (int x = 0; x < num_columns_; ++x)
{
for (int y = 0; y < num_rows_; ++y)
{
tiles_[y][x] = new Tile(x, y);
}
}

/*
* Iterator version:
*
* for (MatrixBase<Tile>::MatrixIterator itr = begin(); itr !=
end(); ++itr)
* {
* *itr = new Tile(foo, bar);
* }
*/
}
};

#endif
Does it look better? One thing that worries me is if I should be more
"helpful" if the user calls operator++() on an iterator that is
already at the end?

- Eric

[John Harrison]

>

Does it look better? One thing that worries me is if I should be more
"helpful" if the user calls operator++() on an iterator that is
already at the end?

- Eric

Yes, looks better.

It's really your call whether to include error checking. You'll likely
save yourself some debugging headaches if you do, and in this case it's
a pretty simple check to make. Throw an exception if you detect an
error, because although it's easy to detect errors, it's not clear how
to handle them in this code.

If you do include error checking then not only operator++ on an iterator
that has reached the end, but also operator* on an iterator at the end.

john

[Eric Lilja]

On 26 Maj, 23:43, John Harrison <[e-mail]:

Does it look better? One thing that worries me is if I should be more
"helpful" if the user calls operator++() on an iterator that is
already at the end?

- Eric

Yes, looks better.

It's really your call whether to include error checking. You'll likely
save yourself some debugging headaches if you do, and in this case it's
a pretty simple check to make. Throw an exception if you detect an
error, because although it's easy to detect errors, it's not clear how
to handle them in this code.

If you do include error checking then not only operator++ on an iterator
that has reached the end, but also operator* on an iterator at the end.

john

Thanks for your valuable input (again), John! I will include error
checking
in operator++ and operator* then. Maybe inside an #ifdef DEBUG block.

However, right now I'm struggling to get my iterator working if my
MatrixBase
object is const. Maybe you could elaborate a bit more what I need to
do?
Do I need to create a new iterator class similar to const_iterator
found
in many stl containers?
I tried creating const versions of begin(), end() and operator*() but
either
I did it wrong or it's not enough, because I get errors. I don't have
the
code available right now but I will post it if I can't get it working.

- Eric

[John Harrison]

Eric Lilja wrote:

On 26 Maj, 23:43, John Harrison <[e-mail]:

>>Does it look better? One thing that worries me is if I should be more
"helpful" if the user calls operator++() on an iterator that is
already at the end?
- Eric

Yes, looks better.

It's really your call whether to include error checking. You'll likely
save yourself some debugging headaches if you do, and in this case it's
a pretty simple check to make. Throw an exception if you detect an
error, because although it's easy to detect errors, it's not clear how
to handle them in this code.

If you do include error checking then not only operator++ on an iterator
that has reached the end, but also operator* on an iterator at the end.

john

Thanks for your valuable input (again), John! I will include error
checking
in operator++ and operator* then. Maybe inside an #ifdef DEBUG block.

However, right now I'm struggling to get my iterator working if my
MatrixBase
object is const. Maybe you could elaborate a bit more what I need to
do?
Do I need to create a new iterator class similar to const_iterator
found
in many stl containers?

Yes, and very tedious it is too.

Iterator and const_iterator have much in common. For instance their data
members will be the same, operator== will be the same for both, although
operator++ is different (different return type) the technique for
incrementing both kinds of iterator is the same, etc. etc. So two
techniques tend to be used. Either derive iterator and const_iterator
from a common base, or derive iterator from const_iterator. Don't forget
that you can assign an iterator to a const_iterator but not the other
way around. If you take the second of my suggestions you get this
behaviour automatically, otherise your const_iterator class will need a
constructor that takes an iterator.

I tried creating const versions of begin(), end() and operator*() but
either
I did it wrong or it's not enough, because I get errors. I don't have
the
code available right now but I will post it if I can't get it working.

No you need two classes and two sets of methods. Const begin() returns
const_iterator, operator* is always const because it doesn't change the
iterator itself, (this is not what I told you earlier).

>
- Eric

john

[Eric Lilja]

On 27 Maj, 08:13, John Harrison <[e-mail]:

Eric Lilja wrote:

On 26 Maj, 23:43, John Harrison <[e-mail]:

>Does it look better? One thing that worries me is if I should be more
"helpful" if the user calls operator++() on an iterator that is
already at the end?
- Eric
Yes, looks better.

It's really your call whether to include error checking. You'll likely
save yourself some debugging headaches if you do, and in this case it's
a pretty simple check to make. Throw an exception if you detect an
error, because although it's easy to detect errors, it's not clear how
to handle them in this code.

If you do include error checking then not only operator++ on an iterator
that has reached the end, but also operator* on an iterator at the end.

john

Thanks for your valuable input (again), John! I will include error
checking
in operator++ and operator* then. Maybe inside an #ifdef DEBUG block.

However, right now I'm struggling to get my iterator working if my
MatrixBase
object is const. Maybe you could elaborate a bit more what I need to
do?
Do I need to create a new iterator class similar to const_iterator
found
in many stl containers?

Yes, and very tedious it is too.

Iterator and const_iterator have much in common. For instance their data
members will be the same, operator== will be the same for both, although
operator++ is different (different return type) the technique for
incrementing both kinds of iterator is the same, etc. etc. So two
techniques tend to be used. Either derive iterator and const_iterator
from a common base, or derive iterator from const_iterator. Don't forget
that you can assign an iterator to a const_iterator but not the other
way around. If you take the second of my suggestions you get this
behaviour automatically, otherise your const_iterator class will need a
constructor that takes an iterator.

I tried creating const versions of begin(), end() and operator*() but
either
I did it wrong or it's not enough, because I get errors. I don't have
the
code available right now but I will post it if I can't get it working.

No you need two classes and two sets of methods. Const begin() returns
const_iterator, operator* is always const because it doesn't change the
iterator itself, (this is not what I told you earlier).

- Eric

john

Hi John! Based on your input I've made the following changes. The
MatrixBase no longer makes the assumption that it's being instantiated
with a pointer type. As you said, there's no reason of doing that. I
also made a Iterator class with two child classes, MatrixIterator and
ConstMatrixIterator and I've changed MatrixBase::begin()/end() to
reflect that. Here's my code and it seems to work. I can iteratate
over a const MatrixBase object using the ConstMatrixIterator and I can
use MatrixIterator if I have non-const object and want to change what
the iterator points to. The code posted below compiles with three
different compilers. I haven't figured out how to handle assignment of
iterators you mentioned or if I can put the boolean operators in the
base class. Comments? I have all the functionality I need now, but if
there are some simple changes I could make to make it better, I'd love
to hear them. :) I'm putting this to work in my implementation of the
game of life, one of my current projects. :) This part of the project
has taken a lot more work than I expected, but I've learnt alot!

The code:

#ifndef MATRIXBASE_H
#define MATRIXBASE_H

#include <cassert>

template<typename T>
class MatrixBase
{
public:
MatrixBase(int num_rows, int num_columns)
: num_rows_(num_rows), num_columns_(num_columns) {}

virtual ~MatrixBase()
{
for (int y = 0; y < num_rows_; ++y)
{
for (int x = 0; x < num_columns_; ++x)
{
delete tiles_[y][x];
}

delete[] tiles_[y];
}

delete[] tiles_;
}

/* Also handle the rule of three... */

virtual void allocate()
{
assert(num_rows_ 0 && num_columns_ 0);

tiles_ = new T*[num_rows_];

for (int y = 0; y < num_rows_; ++y)
{
tiles_[y] = new T[num_columns_];
}
}

class Iterator
{
protected:
Iterator(const MatrixBase *matrix = 0, int row = -1, int column
= -1)
: matrix_(matrix), row_(row), column_(column) {}

public:
Iterator& operator++()
{
if (row_ == matrix_->num_rows_ - 1 && column_ == matrix_-

>num_columns_ - 1)

{
/* Now when row_ == matrix_->num_rows_ and column_ ==
matrix_->num_columns_
* that means we are at the end. */
++row_;
++column_;
}
else if (column_ == matrix_->num_columns_ - 1)
{
++row_;
column_ = 0;
}
else
{
++column_;
}

/* Maybe add special case for if operator++() is called on an
* end() iterator? */
return *this;
}

protected:
T& dereference()
{
if (row_ < 0 || row_ >= matrix_->num_rows_ ||
column_ < 0 || column_ matrix_->num_columns_)
throw; // FIXME

return matrix_->tiles_[column_][row_];
}

const MatrixBase *matrix_;

int row_;
int column_;
};

class MatrixIterator : public Iterator
{
public:
MatrixIterator() : Iterator(0, -1, -1) {}

friend class MatrixBase;

T& operator*()
{
return Iterator::dereference();
}

/* MSVC++ wants a typename here or it will issue a warning. */
bool operator!=(const typename MatrixBase::MatrixIterator& rhs)
const
{
return
Iterator::matrix_ != rhs.matrix_ || Iterator::row_ !=
rhs.row_ ||
Iterator::column_ != rhs.column_;
}

/* MSVC++ wants a typename here or it will issue a warning. */
bool operator==(const typename MatrixBase::MatrixIterator& rhs)
const
{
return !(*this != rhs);
}

private:
MatrixIterator(MatrixBase *matrix, int row = 0, int column = 0)
: Iterator(matrix, row, column) {}
};

class ConstMatrixIterator : public Iterator
{
public:
ConstMatrixIterator() : Iterator(0, -1, -1) {}

friend class MatrixBase;

const T& operator*()
{
return Iterator::dereference();
}

/* MSVC++ wants a typename here or it will issue a warning. */
bool operator!=(const typename MatrixBase::ConstMatrixIterator&
rhs) const
{
return
Iterator::matrix_ != rhs.matrix_ || Iterator::row_ !=
rhs.row_ ||
Iterator::column_ != rhs.column_;
}

/* MSVC++ wants a typename here or it will issue a warning. */
bool operator==(const typename MatrixBase::ConstMatrixIterator&
rhs) const
{
return !(*this != rhs);
}

private:
ConstMatrixIterator(const MatrixBase *matrix, int row = 0, int
column = 0)
: Iterator(matrix, row, column) {}
};

MatrixIterator begin()
{
return MatrixIterator(this);
}

ConstMatrixIterator begin() const
{
return ConstMatrixIterator(this);
}

MatrixIterator end()
{
return MatrixIterator(this, num_rows_, num_columns_);
}

ConstMatrixIterator end() const
{
return ConstMatrixIterator(this, num_rows_, num_columns_);
}

protected:
T **tiles_;

int num_rows_;
int num_columns_;
};

#endif

- Eric

[John Harrison]

Eric Lilja wrote:

On 27 Maj, 08:13, John Harrison <[e-mail]:

>Eric Lilja wrote:

>>On 26 Maj, 23:43, John Harrison <[e-mail]:
Does it look better? One thing that worries me is if I should be more
"helpful" if the user calls operator++() on an iterator that is
already at the end?
- Eric
Yes, looks better.
It's really your call whether to include error checking. You'll likely
save yourself some debugging headaches if you do, and in this case it's
a pretty simple check to make. Throw an exception if you detect an
error, because although it's easy to detect errors, it's not clear how
to handle them in this code.
If you do include error checking then not only operator++ on an iterator
that has reached the end, but also operator* on an iterator at the end.
john
Thanks for your valuable input (again), John! I will include error
checking
in operator++ and operator* then. Maybe inside an #ifdef DEBUG block.
However, right now I'm struggling to get my iterator working if my
MatrixBase
object is const. Maybe you could elaborate a bit more what I need to
do?
Do I need to create a new iterator class similar to const_iterator
found
in many stl containers?

Yes, and very tedious it is too.

Iterator and const_iterator have much in common. For instance their data
members will be the same, operator== will be the same for both, although
operator++ is different (different return type) the technique for
incrementing both kinds of iterator is the same, etc. etc. So two
techniques tend to be used. Either derive iterator and const_iterator
from a common base, or derive iterator from const_iterator. Don't forget
that you can assign an iterator to a const_iterator but not the other
way around. If you take the second of my suggestions you get this
behaviour automatically, otherise your const_iterator class will need a
constructor that takes an iterator.

>>I tried creating const versions of begin(), end() and operator*() but
either
I did it wrong or it's not enough, because I get errors. I don't have
the
code available right now but I will post it if I can't get it working.

No you need two classes and two sets of methods. Const begin() returns
const_iterator, operator* is always const because it doesn't change the
iterator itself, (this is not what I told you earlier).

>>- Eric

john

Hi John! Based on your input I've made the following changes. The
MatrixBase no longer makes the assumption that it's being instantiated
with a pointer type. As you said, there's no reason of doing that. I
also made a Iterator class with two child classes, MatrixIterator and
ConstMatrixIterator and I've changed MatrixBase::begin()/end() to
reflect that. Here's my code and it seems to work. I can iteratate
over a const MatrixBase object using the ConstMatrixIterator and I can
use MatrixIterator if I have non-const object and want to change what
the iterator points to. The code posted below compiles with three
different compilers. I haven't figured out how to handle assignment of
iterators you mentioned or if I can put the boolean operators in the
base class. Comments?

You can (and should) put the operator== and operator!= in the base class.

You get the MatrixIterator to ConstMatrixIterator assignment behaviour
by writing a constructor for ConstMatrixIterator that takes a
MatrixIterator

class ConstMatrixIterator : public Iterator
{
public:
ConstMatrixIterator() : Iterator(0, -1, -1) {}
ConstMatrixIterator(const MatrixIterator& rhs)
: Iterator(rhs.matrix_, rhs.row_, rhs.column_) {}

This constructor will be called whever you assign or construct a
ConstMatrixIterator from a MatrixIterator. You probably need to make
ConstMatrixIterator a friend of MatrixIterator to make that work.

I have all the functionality I need now, but if

there are some simple changes I could make to make it better, I'd love
to hear them. :)

Well...

Iterating backwards (i.e. operator--).

Postfix increment i.e. it++ instead of ++it.

Your return type for operator++ is not correct, according to STL
iterator requirements, might be fine as far as you requirements go.
ConstMatrixIterator::operator++ should return ConstMatrixIterator& and
MatrixIterator::operator++ should return MatrixIterator&. You do this in
a similar way to the way you've used dereference in the base class.
Write a void method called increment (say) in the base class. Then write
operator++ in ConstMatrixIterator and MatrixIterator with the correct
return types. Each operator++ calls increment from the base class.

Finally iterator_traits.

Of coourse feel free to ignore all this, if it working well for you
that's fine. But if you try you iterator with one of the STL algorithms
and it doesn't compile then the reason is probably one of the items above.
I'm putting this to work in my implementation of the

game of life, one of my current projects. :) This part of the project
has taken a lot more work than I expected, but I've learnt alot!

john

[Eric Lilja]

On 27 Maj, 23:51, John Harrison <[e-mail]:

Hi John! Based on your input I've made the following changes. The
MatrixBase no longer makes the assumption that it's being instantiated
with a pointer type. As you said, there's no reason of doing that. I
also made a Iterator class with two child classes, MatrixIterator and
ConstMatrixIterator and I've changed MatrixBase::begin()/end() to
reflect that. Here's my code and it seems to work. I can iteratate
over a const MatrixBase object using the ConstMatrixIterator and I can
use MatrixIterator if I have non-const object and want to change what
the iterator points to. The code posted below compiles with three
different compilers. I haven't figured out how to handle assignment of
iterators you mentioned or if I can put the boolean operators in the
base class. Comments?

You can (and should) put the operator== and operator!= in the base class.

Ok, I will do that. I just worried about what would happen if someone
tried to compare a MatrixIterator with a ConstMatrixIterator, if
that's even supposed to be allowed.

>
You get the MatrixIterator to ConstMatrixIterator assignment behaviour
by writing a constructor for ConstMatrixIterator that takes a
MatrixIterator

class ConstMatrixIterator : public Iterator
{
public:
ConstMatrixIterator() : Iterator(0, -1, -1) {}
ConstMatrixIterator(const MatrixIterator& rhs)
: Iterator(rhs.matrix_, rhs.row_, rhs.column_) {}

This constructor will be called whever you assign or construct a
ConstMatrixIterator from a MatrixIterator. You probably need to make
ConstMatrixIterator a friend of MatrixIterator to make that work.

Right, will do this. Thanks!

>
I have all the functionality I need now, but if

there are some simple changes I could make to make it better, I'd love
to hear them. :)

Well...

Iterating backwards (i.e. operator--).

Postfix increment i.e. it++ instead of ++it.

Your return type for operator++ is not correct, according to STL
iterator requirements, might be fine as far as you requirements go.
ConstMatrixIterator::operator++ should return ConstMatrixIterator& and
MatrixIterator::operator++ should return MatrixIterator&. You do this in
a similar way to the way you've used dereference in the base class.
Write a void method called increment (say) in the base class. Then write
operator++ in ConstMatrixIterator and MatrixIterator with the correct
return types. Each operator++ calls increment from the base class.

Doh, that's what I had at the beginning but somehow I thought that
could get away with having it in the base class.

>
Finally iterator_traits.

Of coourse feel free to ignore all this, if it working well for you
that's fine. But if you try you iterator with one of the STL algorithms
and it doesn't compile then the reason is probably one of the items above.

I'm putting this to work in my implementation of the

game of life, one of my current projects. :) This part of the project
has taken a lot more work than I expected, but I've learnt alot!

john

Thanks again, John! Will post back if I get any problems with these
last changes. If I don't, I probably will let this part of the project
rest for a while. Thanks so much for your help!

- Eric

[Eric Lilja]

On 28 Maj, 00:01, Eric Lilja <[e-mail]:
[snip]

>

You can (and should) put the operator== and operator!= in the base class.

Ok, I will do that. I just worried about what would happen if someone
tried to compare a MatrixIterator with a ConstMatrixIterator, if
that's even supposed to be allowed.

As I suspected, if I put those operators in the base class I can
compare a MatrixIterator with a ConstMatrixIterator, which I couldn't
before. But why do I want to do that? It sounds, on you, that it's
important that those operators are in the base iterator class. I'm not
disputing that, I just wondered why I want to be able to compare
iterators of different subclasses. Could you shed some light on that,
please? :)

[snip]

- Eric

[John Harrison]

Eric Lilja wrote:

On 28 Maj, 00:01, Eric Lilja <[e-mail]:
[snip]

>>You can (and should) put the operator== and operator!= in the base class.

Ok, I will do that. I just worried about what would happen if someone
tried to compare a MatrixIterator with a ConstMatrixIterator, if
that's even supposed to be allowed.

As I suspected, if I put those operators in the base class I can
compare a MatrixIterator with a ConstMatrixIterator, which I couldn't
before. But why do I want to do that? It sounds, on you, that it's
important that those operators are in the base iterator class. I'm not
disputing that, I just wondered why I want to be able to compare
iterators of different subclasses. Could you shed some light on that,
please? :)

Iterators are modelled after pointers. It's legal to compare a pointer
with a const pointer so why not with iterators? This code is perfectly legal

char x[10];
char* p = x;
const char* cp = p;

if (p == cp)
...

It seems harmless to me, might even be useful occasionally.

This is related to the fact that you can assign iterators to const
iterators. If would be strange if you could write

iterator i = ...;
const_iterator ci = i;

but then couldn't write

if (ci == i)

john

[Eric Lilja]

On 28 Maj, 08:43, John Harrison <[e-mail]:

Eric Lilja wrote:

On 28 Maj, 00:01, Eric Lilja <[e-mail]:
[snip]

>You can (and should) put the operator== and operator!= in the base class.
Ok, I will do that. I just worried about what would happen if someone
tried to compare a MatrixIterator with a ConstMatrixIterator, if
that's even supposed to be allowed.

As I suspected, if I put those operators in the base class I can
compare a MatrixIterator with a ConstMatrixIterator, which I couldn't
before. But why do I want to do that? It sounds, on you, that it's
important that those operators are in the base iterator class. I'm not
disputing that, I just wondered why I want to be able to compare
iterators of different subclasses. Could you shed some light on that,
please? :)

Iterators are modelled after pointers. It's legal to compare a pointer
with a const pointer so why not with iterators? This code is perfectly legal

char x[10];
char* p = x;
const char* cp = p;

if (p == cp)
...

It seems harmless to me, might even be useful occasionally.

This is related to the fact that you can assign iterators to const
iterators. If would be strange if you could write

iterator i = ...;
const_iterator ci = i;

but then couldn't write

if (ci == i)

john

Right, I have moved my two boolean operators to the base class. But
I'm having trouble implementing so that you can assign a
MatrixIterator to a ConstMatrixIterator (btw, just a copy constructor,
not assignment operator too?), it compiles with GCC 4.2.0 without a
friend declaration but it doesn't compile with GCC 3.4.4 or MSVC++ 8.0
SP1, not even with a friend declaration!

My ConstIterator:
class ConstMatrixIterator : public Iterator
{
public:
friend class MatrixBase;
#if defined __GNUC__ && __GNUC__ == 3
#warning "Compiling with GCC 3.*, turning MatrixIterator into a
friend"
friend class MatrixIterator;
#elif defined _MSC_VER
#pragma message("Compiling with MSVC++, turning MatrixIterator into a
friend.")
friend class MatrixIterator;
#endif

ConstMatrixIterator() : Iterator(0, -1, -1) {}

ConstMatrixIterator(const MatrixIterator& rhs)
: Iterator(rhs.matrix_, rhs.row_, rhs.column_) {}

const T& operator*()
{
return Iterator::dereference();
}

/* These should be in the child classes so we get the return
type correct. */
ConstMatrixIterator& operator++()
{
Iterator::increment();

return *this;
}

private:
ConstMatrixIterator(const MatrixBase *matrix, int row = 0, int
column = 0)
: Iterator(matrix, row, column) {}
};

To trigger the error:
TileMatrix::ConstMatrixIterator itr3(itr1); where itr1 is of type
MatrixIterator.
Errors from gcc 3.4.4:
g++ -Wall -Wextra -std=c++98 -pedantic -g -c main.cpp
In file included from TileMatrix.h:4,
from main.cpp:1:
MatrixBase.h:133:2: warning: #warning is a GCC extension
MatrixBase.h:133:2: warning: #warning "Compiling with GCC 3.*, turning
MatrixIterator into a friend"
MatrixBase.h: In constructor
`MatrixBase<T>::ConstMatrixIterator::ConstMatrixIt erator(const
MatrixBase<T>::MatrixIterator&) [with T = Tile*]':
main.cpp:28: instantiated from here
MatrixBase.h:98: error: `const
MatrixBase<Tile*>*MatrixBase<Tile*>::Iterator::mat rix_' is protected
MatrixBase.h:142: error: within this context
MatrixBase.h:100: error: `int MatrixBase<Tile*>::Iterator::row_' is
protected
MatrixBase.h:142: error: within this context
MatrixBase.h:101: error: `int MatrixBase<Tile*>::Iterator::column_' is
protected
MatrixBase.h:142: error: within this context
make: *** [main.o] Error 1

MSVC++ errors similar, complains about protected variables. Is this
fixable or should wrap the entire copy constructor inside macros so it
only gets included for gcc 4.2.0?

- Eric