Writing a C++ iterator

[JonB]

I have some data in "tabular" form, meaning it is in rows & columns/two-dimensional array.

I have various different operations which need performing on (all elements in) a row, a column or a square (meaning a "square area" of rows+columns). For convenience --- instead of coding for each of these cases separately (which I have done so far, and the code is getting large) --- I would like an iterator which can be invoked to visit all elements in any one of these, i.e. go through each element of a row, column or square.

I have kept clear of C++ iterators because they look ugly (to me) and require a bit of boilerplate code. But now is the time for me to bite the bullet.

Can/how can I design a single iterator which (presumably) takes a parameter on first invocation to tell it whether I want a row-iteration, a column-iteration or a square-iteration? It would store that in its state, and when asked for the "next" element in the iteration it would use that to decide whether, from its current position, to increment the column, the row, or (potentially) both when moving to the next row down in a "square"?

I assume this is the right thing to do. I want callers to create the iterator telling it which of row/column/square it wants to iterate, then it can move to whatever is the correct "next" element without caller caring how it does that so that caller can just do whatever it wants on that next iterator element.

[SGaist]

Hi,

How do you store that data ?

Did you consider using functional programming to parse your data structure ?

As for adding the iterator to your class, from an API point of view, I would go with something like rowIterator and columnIterator with the index as parameter.

[fcarney]

It seems to me, after refreshing my mind on iterators, that the datatype itself would have to have a reference/pointer to the container. As the iterator seems to only have knowledge of the discrete data type stored in the container. So your container would need to give a pointer to itself to each item added to the container. Also if using something like a vector, it would need an index. I suppose a hash could be used too. Then the increment and decrement operators would have context of where this data resides in the container.

Sounds like an interesting challenge.

[JonB]

@SGaist
The data is just stored in a 2-dimensional array.

I want one iterator which can be instructed to move around the array either by row or by column or by "square". I do not want 3 separate iterators, one of which is by row, another by column and the third by "square".

Ignoring the syntax for the moment, I want to be able to do:

for iterate_by [row or column or square] :
    do_something(element)

[fcarney]

I guess the iterator itself could take more arguments rather than storing data about the container in the datatype. This could also define the type of iterator it becomes.

[JonB]

@fcarney
That's what I'm trying to ask. Can you write an iterator which moves around its data in an order specified by a parameter to its constructor or start() method? Its internals can deal with how that parameter affects how it calculates its "next" item. Then I can have a single generic iterator which can move through either row, column or square according to what I p[ass it when I create/start it.

[fcarney]

@JonB well if you look at that page I linked you can see what a generic forward iterator looks like. If you look at the begin() and end() functions you could have different versions of begin/end that initialize data inside the iterator. This would require multiple constructors for the different modes of the iterator. You would need container reference, some kind of parameters for shape. I would start with row and column and work up to square. I am guessing this will take a few iterations to sort out. Sorry for the pun.

[JonB]

@fcarney I didn't see your earlier post, looking at the link now.

Blimey, I don't need anything that complicated! But thanks. My types and parameters are all the same in all cases. Sometimes I want to iterate_by('row', 6): do_something(element), sometimes iterate_by('column', 5): do_something(element), sometimes iterate_by('square', 3): do_something(element) where row or column or square is a parameter to a function. The only difference is how each of these calculates the "next()` index into the array (e.g. iterate by row will increment column, iterate by column will increment row, etc.).

At the moment I have to do:

if (direction == `row`)
    row_iterator:
        do_something(element)
else if (direction == `column`)
    column_iterator:
        do_something(element)
else if (direction == `square`)
    square_iterator:
        do_something(element)

It's getting messy. I want

combined_iterator(direction):
        do_something(element)

instead.

I need to create my iterator with a parameter telling it whether to move by row/column/square; I need to store that parameter in the iterator and use it to calculate what next() will do. I'm sure it's easy, I just need to read up on the syntax, how iterators work. Sigh :)

[fcarney]

Another option would be to give info about the shape to be used in the iterator. Then calculate all the data used in the shape and store that in the iterator. Then the iterator becomes a simple cycle through a list of pointers iterator as the sub container is stored in the iterator. Might be cumbersome for large amounts of data though.

Edit: Don't store that actual data, just store pointers to the data in the iterator.

[JonB]

@fcarney
See my latest post above which crossed with yours. This really ought be simple, a couple of lines of extra code in the iterator.

[Chris Kawa]

Do you need to distinguish if it's a row, column or square? Can you just generalize as (x,y,w,h)? Then you could have e.g.

for (MyIterator it(data, 0,7,42,1); !it.atEnd(); ++it) //iterate over row 7 of width 42 
    do_something(*it);

for (MyIterator it(data, 7,0,1,42); !it.atEnd(); ++it) //iterate over column 7 of height 42
    do_something(*it);

for (MyIterator it(data, 6,9,42,42); !it.atEnd(); ++it) //iterate over a 42x42 square starting at pos 6,9
    do_something(*it);

iterator would then store the data pointer, position and dimensions. Calculating the index for operator * would be standard modulo over the width offset by the start coords.

[JonB]

@Chris-Kawa
Thanks for replying, Chris.

This is closer. My case is even simpler.

• The whole array is 9x9, fixed.
• I either want to iterate the 9 cells in a row, or the 9 cells in a column, or the 9 cells (3x3) in a "square", where a square's top-left is always at a row/column both divisible by 3 (i.e. there are a total of just 9 squares, just as for rows or columns).

Hence my iterator constructor/state only needs (a) whether to iterate over a row/column/square plus (b) which number (always 0--8) for the desired row/column/square. The iterator only needs to move forward.

I will then want to be able to call the common do_something() function on the current element in the iteration.

I have given up on writing the code for a std::iterator as I don't need all its power, and I like to keep code as minimal as possible. For now, at least I have designed it using a struct with state and just a couple of methods:

    enum CellGroupIteratorDirection { Row, Column, Square };
    struct CellGroupIterator
    {
        CellGroupIteratorDirection direction;    // iterate over row/column/square
        int row0, col0;    // calculated starting (row,col) for row/column/square
        int row, col;    // current (row,col) reached in iteration

        CellGroupIterator(CellGroupIteratorDirection direction, int param);  // construct and begin an iteration, param is desired row/column/square number
        bool atEnd() const;    // return whether the iteration has finished the row/column/square
        bool next();    // update (row,col) to the next cell in the iteration
    };

You can guess that next() examines direction to determine how to increment row/col to get to the next cell in the iteration. And similarly for atEnd() to decide whether it has completed the row/column/square.

I can now write loops like:

for (CellGroupIterator cgit(Row, desiredRow); !cgit.atEnd(); cgit.next())
    do_common_something(cgit.row, cgit.col);

for (int square = 0; square < 9; square++)
    for (CellGroupIterator cgit(Square, square); !cgit.atEnd(); cgit.next())
        do_common_something(cgit.row, cgit.col);

Trust me, this will allow me to reduce a lot of duplicated code, where I currently have same code repeated depending on whether the iteration loop is by row/column/square, but I want to do the same inner stuff whichever of these it is.

I realise I could (doubtless) write the extra wrapper code to implement it as a std::iterator, but this will do me for what I need.

Any comment? :)