How to make an iterator for my Matrix class

[Stefano112]

Hi, i'm making a matrix class, here is my code:

#ifndef MATRICE_H
#define MATRICE_H

#include <iostream>

template <class T> class matrice {

 public:
  
  typedef int sizet;
  typedef T valuet;
  
 matrice(): _data(0), _row(0), _col(0) {}; //costruttore default
  
  matrice(sizet rw, sizet cl) { //causa errore in valgrind
    _data=new valuet*[rw];
    for(sizet i=0;i<rw;i++)
      _data[i]=new valuet[cl];
    _row=rw;
    _col=cl;
  }
  
  matrice(sizet rw, sizet cl, valuet value) {
    _data=new valuet*[rw];
    for(sizet i=0;i<rw;i++) {
      _data[i]=new valuet[cl];
      for(sizet j=0;j<cl;j++)
	_data[i][j]=value;
    }
    _row=rw;
    _col=cl;
  }

  matrice(const matrice &other) { //copy constructor
    _row=other._row;
    _col=other._col;
    _data=new valuet*[_row];
    for(sizet i=0;i<_row;i++) {
      _data[i]=new valuet[_col];
      for(sizet j=0;j<_col;j++)
	_data[i][j]=other._data[i][j];
    }
  }

  ~matrice() { //distruttore
    for (sizet i=0;i<_row;i++)
      delete[] _data[i];
    delete[] _data;
    _data=0;
  }

  matrice& operator=(const matrice &other){ //operatore =
    if (this!=&other) {
      for (sizet i=0;i<_row;i++)
	delete[] _data[i];
      delete[] _data;
      _row=other._row;
      _col=other._col;
      _data=new int*[_row];
      for(sizet i=0;i<_row;i++) {
	_data[i]=new int[_col];
	for(sizet j=0;j<_col;j++)
	  _data[i][j]=other._data[i][j];
      }
    }
    return *this;
  }
  
  sizet getSize() const {
    return _row*_col;
  }

  sizet getRow() const {
    return _row;
  }
  
  sizet getCol() const {
    return _col;
  }

  valuet getValue(sizet x, sizet y) const {
    return _data[x][y];
  }

  void setValue(sizet x, sizet y, valuet value) {
    _data[x][y]=value;
  }
  
  valuet &operator()(sizet x, sizet y) { //lettura e scrittura
    return _data[x][y];
  }
  
  const valuet &operator()(sizet x, sizet y) const { //solo lettura
    return _data[x][y];
  }

 private:
  
  valuet **_data;
  sizet _row;
  sizet _col;

};

struct is_even {
  inline bool operator()(const int value) const {
    return value%2==0 ? true : false;
  }
};

struct is_letter {
  inline bool operator()(const char value) const {
    return (value>='a' && value<='z') || (value>='A' && value<='Z') ? true : false;
  }
};

template <class T>
std::ostream &operator<<(std::ostream &left, const matrice<T> &right) {
  for(typename matrice<T>::sizet i=0;i<right.getRow();i++){
    for(typename matrice<T>::sizet j=0;j<right.getCol();j++)
      left<<right.getValue(i,j)<<" ";
    left<<std::endl;
  }
  return left;
}

template <class T, class F> 
bool verify(const matrice<T> &mat, const F &fun) {
  bool ret=true;
  for(typename matrice<T>::sizet i=0;i<mat.getRow();i++)
    for(typename matrice<T>::sizet j=0;j<mat.getCol();j++)
      ret=ret && fun(mat.getValue(i,j));
  return ret;
}

#endif

This is a project for school, now is required to implement an iterator that goes through every element of the matrix (first all the element of the first row, then all the element of the second row, and so on)
i made a class iterator with the ++ operator that just increment the pointer, while begin() return the first element of the matrix and end() the last, but doing so it reads all the element of the matrix but also other data between the rows, how can i fix it?
please help me!
ps: sorry for my english but i'm italian!

[Banfa]

The data in your matrix is not contiguous, that is you do not allocate it as a single block of data but rather you allocate an array of pointers and then to each pointer to allocate an array of the value types.

That means that when you are at the end of a row of data you have no guarantee (and in fact it is very unlikely) that the start of the next row is in the next memory location.

You have a couple of options

1. Your iterators ++ operator needs to be more complex. When the operator runs it needs to detect if it is at the end of the current row and it is start using the next row explicitly.
2. You data structure needs to be less complex. Rather than an array of pointers to arrays of value types you could simple implement this as a one single dimensioned array of value types. You use the row and column to calculate the correct index in this array for any given cell. Direct cell access is marginally more complex but data management and iterators complexity are both reduced.

[Stefano112]

thanks a lot for your answer, unfortunately i cannot use the second option cause the teacher asked us to not implement the matrix in that way
I have already tried the first option, but i wasn't able to make it works...cause i would need to compare my pointer with _data[row][_col-1], then if they are the same skip to _data[row+1][0], else i would just increment my pointer
The problem is that i dont understand how can i make _data of an istance of my class matrix available in my class iterator, so that i can compare it to my pointer...can i pass it by reference in the constructor of the iterator?would it work?

ps:again, sorry for my english and thanks for your help!

[weaknessforcats]

that i dont understand how can i make _data of an istance of my class matrix available in my class iterator, so that i can compare it to my pointer...can i pass it

Just look in the C++ vector header and see how iterators are implemented in the Standard Library. You will find the iterator for a class is itself a class nested inside the class it iterates.

class A
{
    public:

        class Iterator
        {

        };
};

main()
{
   A::Iterator obj;   //obj is an iterator for A
}

Next, I don't see what your problem is. a) You have an array of pointers so
_data[r] os a row of your matrix. Then b) you allocated the columns so that _data[r][c] is an element of your matrix. This is all fine.

What's not fine is _data[r][c- offset] to position you to an element in another row. You will need to use manually adjust the row index r and then position to the correct element.

I really recommend you read Arrays Revealed in the C++ Insights to really see why this so.

[Stefano112]

WARNING:i know it's a long post (cause there is a lot of code), but i m asking just for a little problem, please try to help me even if it's long cause i really need your help!

ok now i fixed the main problem, now when i try to read or to set all the elements of the matrix it works, but i have another little problem, first of all, here is my class iterator (nested inside class matrice (matrix in italian :P), and the two functions begin() and end() of the class matrice:

  class iterator {
    friend class const_iterator;
    friend class matrice;

    
  public:
    typedef std::forward_iterator_tag iterator_category;
    typedef T valuet;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef T& reference;

  iterator() : ptr(0),col(0),c(0)  {}
  
  iterator(const iterator &other) : ptr(other.ptr), col(other.col), c(other.c) {}
    
    iterator& operator=(const iterator &other) {
       ptr=other.ptr;
      col=other.col;
      c=other.c;
      return *this;
    }

    ~iterator() {}

    valuet *operator*() const {
      return *ptr;
    }
    

    valuet *operator->() const {
      return *ptr;
    }
    
    bool operator==(const iterator &other) const {
      return ptr==other.ptr;
    }

    bool operator!=(const iterator &other) const {
      return !(*this==other);
    }

    bool operator==(const const_iterator &other) const {
      return ptr==other.ptr;
    }

    bool operator!=(const const_iterator &other) const {
      return !(*this==other);
    }

    iterator &operator++() {
      c++;
      if (c==col) {
		*ptr=*ptr-(col-1);
	++ptr;
	c=0;
	} else
      ++(*ptr);
      return *this;
    }

    iterator operator++(int) {
      iterator tmp(ptr,riga,col,c);
      c++;
      if (c==col) {
	*ptr=*ptr-(col-1);
	++ptr;
	c=0;
      }
      else
	++(*ptr);
      return tmp;
    }

  private:
    valuet **ptr;
    int col;
    int c;
    iterator(valuet **p,int cl) : ptr(p), col(cl), c(0) {}
    iterator(valuet **p, int cl, int co) : ptr(p), riga(po), col(cl), c(co) {}
    
  };//iteratorRow

  
  iterator begin() {
    return iterator(_data,_col);
  }

  
  iterator end() {
    return iterator(_data+_row,_col);
  }

so now it works when i try to run something like this:

  matrice<int>::iterator it,ite;
 for (it=b.begin(),ite=b.end(); it!=ite;++it){ //b is a matrix of int
   std::cout << **it << " ";
   **it=1;
}

it writes all the elements of the matrix (skipping values between rows), and it sets all the elements to 1

but i have a problem if i try to run something like this:

it=b.begin();
  it++;
  ite=++it;
  it++;++it;
  matrice<int>::iterator iter;
   for (iter=b.end(); ite!=iter;ite++)
   std::cout << **ite << " ";

the problem is that when i increment it (it++,++it), also ite is incremented (despite there's no ite++ :/)..i think the problem is with **ptr, that in someways is shared by both iterator, but i cannot make it works...i don't understand how to fix this problem!i'm trying hard but i really need your help!

[weaknessforcats]

Both of your iterators have the same address in ptr. So when you ++ interator A you use *ptr and update the thing that ptr points at. That's the same object the ptr in your other iterator points at.

Your operator++ must ++ ptr and not *ptr.

For example, in this array:

1 2 3 4 5 6 7 8 9

an iterator pointing at 5 when incremented will point at 6. That is, the iterator contains the address of the specific element and not the address of a pointer to the specific element.

If this array is viewed as:

1 2 3
4 5 6
7 8 9

the address of the element in the iterator is the same since all arrays are really one-dimensional.

[Stefano112]

but my array is bidimensional (**_data), so when i have:
1 2 3
4 5 6
7 8 9

there are same values between the rows (like a 0 and a 33...but i think they can change :P)
so how can i move from a row to an another without incrementing both *ptr and ptr?
thanks for your answer weaknessforcats , i have to finish this project in a few days but i can't fix this last problem :/ i hope someone can help me!

[weaknessforcats]

Again I say, there are no multidimensiona l arrays on C or C++. Everything is one-dimensional. Each element has an address. The array is contiguous. Element 5 is the address of element 0 + 4 x sizeof(the element). It has ot be this way otherwise pointer aritmentic does not work.

An iterator is to point to an element. That is, it contains the address of an element. Not the address of something else.

Your iterator needs to contain a simple pointer to the element.

If your array is "mult-dimensional" it is only becuse you say so. That neing the case you can create code to view the array as multi-dimensional.

You might read the C Forum Insight article Arrays Revealed. What I am saying here is covered in about the last example.

[Stefano112]

well but as also Banfa said the data in my matrix are not contiguos, so if i have
1 2 3
4 5 6
7 8 9
element 5 will not be the address of element 0 + 4 x sizeof(the element)...if i add sizeof(element) to element 3, i will get a value that is not in the first row, and is not in the second row, it's just between the two rows!
So as Banfa said i have to make my operator++ of the iterator more complicated, i've done it and it works, but i have this new problem that i wrote before, you said that it's because i don't have to increment *ptr but ptr, but if i dont increment *ptr i'm not able to pass from one row to another skipping values between rows...
As you said my iterator needs to contain a simple pointer to the element, and it would fix my last problem, but with a simple pointer to the element it would not be able to skip values between rows, cause my data are not contiguos...

[weaknessforcats]

This is your matrix class method:

matrice(sizet rw, sizet cl) { //causa errore in valgrind 
    _data=new valuet*[rw]; 
    for(sizet i=0;i<rw;i++) 
      _data[i]=new valuet[cl]; 
    _row=rw; 
    _col=cl; 
  }

Look at your allocations:
1) first an array oif pointers,
2) then an array of elements for each pointer.

This is identical to

_

data = new valuet[rw][cl];

except that now your array is contiguous. Remember, to call it an array, the elements must be contiguous.

But even if you keep your original scheme, the iterator should know the structure and perform whatever calculations are necessary to acquire the address of a single pointer. A non-contiguous array can't use pointer arithmetic, but it is doable. Personally. I would allocate an [rw][cl] array provided I know the dimensions at the outset and they will not change during the life of the program.

In any case, I say for the third time: You need the address of a single element to be returned from your array and not the address of something else. Otherwise, it's not an iterator.

I say that because you should be able to create iterators that each point to different array elements allowing you to iterate over that range.

[Stefano112]

thanks again for your patience, now i'm trying to do it like you suggested...
i've declared data like a pointer to my value type (valuet *data), then in constructor when i do:
data = new valuet[row][col];
i get this error:
error: 'col' cannot appear in a constant-expression

it doesn't allow me to create a bidimensional array but just a normal array...

[weaknessforcats]

That's because there are no multi-dimensional arrays in C or C++. You always have to specify the element size so the compiler can generate the correct allocation code. That means cl must be a const value.

You may need cl to be a const class member and you set a value in cl using the initializer list of your constructors.