14
\$\begingroup\$

Please have a look at these iterators which I use for my Sudoku solver. They behave slightly different from STL iterators and don't implement all functionality that would be needed to use them in a stl context. But the basic idea behind them was to clean up the code in the Sudoku program that makes heavy use of the three access patterns (row, col, block) that I implemented.

The most "important" iterator is the BlockIterator, since without that iterating over all nine fields in a block looked quite ugly. Iterating rows and columns wasn't that bad, but since I started writing the stuff I decided to create a complete set.

Some technical details:

The grid class holds an (evil) array of pointers to Field objects, that's one dimensional (I could have used a two dimensional array as well, but I often do it this way and feel quite comfortable with modulo operations). Maybe I will replace this with a vector later.

The grid class adds a few static functions to calculate offsets in the array based on row, col or block positions.

class Grid {
public:
    Grid();
    Grid(std::string s);

    class Iterator {
    public:
        Iterator(Grid* g) : grid(g), it(0){}
        Field* operator*(){return field;}
        void operator++(){
            ++it;
            if(it < 9) field = calc_field();
            else field = NULL;
        }
    protected:
        virtual Field* calc_field() = 0;
        Field* field;
        Grid* grid;
        int it;
    };

    class RowIterator : public Iterator {
    public:
        RowIterator(Grid* g, int row) : Iterator(g){
            row_offset = row * size; //Grid::block_offset(block);
            field = calc_field();
        }
        Field* calc_field(){
            int field_index = row_offset + it;
            return grid->field[field_index];
        }
    protected:
        int row_offset;
    };

    class ColIterator : public Iterator {
    public:
        ColIterator(Grid* g, int col) : Iterator(g){
            col_offset = col;
            field = calc_field();
        }
        Field* calc_field(){
            int field_index = it * size + col_offset;
            return grid->field[field_index];
        }
    protected:
        int col_offset;
    };

    class BlockIterator : public Iterator {
    public:
        BlockIterator(Grid* g, int block) : Iterator(g){
            block_offset = Grid::block_offset(block);
            field = calc_field();
        }
        Field* calc_field(){
            int field_index = block_offset + ((it / 3) * size) + (it % 3);
            return grid->field[field_index];
        }
    protected:
        int block_offset;
    };

    RowIterator& row_iter(int row){return *(new RowIterator(this, row));}
    ColIterator& col_iter(int col){return *(new ColIterator(this, col));}
    BlockIterator& block_iter(int block){return *(new BlockIterator(this, block));}

(...)

    static int block_offset(int block){return ((block / 3) * size * 3) + ((block % 3) * 3);}

protected:
        Field* field[grid_size];

Sample usage:

This function is called, when I set a value in a field. It goes through all fields, that would possibly be influenced by this field (same row, col or block)

void Field::do_exclusions(){
    // row
    for(Grid::RowIterator it = grid->row_iter(row); *it; ++it)
        (*it)->set_excluded(value);
    // col
    for(Grid::ColIterator it = grid->col_iter(col); *it; ++it)
        (*it)->set_excluded(value);
    // block
    for(Grid::BlockIterator it = grid->block_iter(block); *it; ++it)
        (*it)->set_excluded(value);
}

So please tell me, if something like this would be "acceptable" (not to mention "best practices"), even if it somehow takes a very free view on the iterator concept.

And of course every idea how this could be improved is welcome.

PS: I tried to add a tag "iterator" but I'm not allowed for too few reputation.

\$\endgroup\$
8
\$\begingroup\$

In my first quick scan through, here are some things I want to bring up:

  • If you are going to overload operators, do it the way the users of the language expect, or don't do it at all. I expect operator++ to return something, not be a void.
  • Does block_offset really need to be public?
  • On that same note, do your actual concrete implementations of the iterators need to be public, since you have methods to create them that are public? Would it make sense for anyone to ever want to create them a different way?
\$\endgroup\$
  • \$\begingroup\$ The third point is excellent. It is pretty much never necessary to explicitly create an iterator, as they are always tied to the collection being iterated over. So, the implementation should be hidden. \$\endgroup\$ – Michael K Feb 2 '11 at 17:59
  • \$\begingroup\$ Thanks Mark. I changed block_offset and the classes to protected. I thought the classes would need to be public, to allow them to be used outside of the Grid class. But code still compiles. block_offset was public, because before I implemented the iterators, I used it everywhere for the purpose to "manually" iterate the fields. \$\endgroup\$ – thorsten muller Feb 2 '11 at 17:59
  • \$\begingroup\$ The iterator types themselves need to be public if you want to create variables of those types. @Michael: The for loop code in the question needs them to be public, since it doesn't appear Field is a friend of Grid. \$\endgroup\$ – Fred Nurk Feb 2 '11 at 18:02
  • \$\begingroup\$ I took the operator from some online sample. I will have a look at Stroustrup or some other source to see how to implement them properly. I didn't think much about returning anything, since at least here I only need the incremental functionality. \$\endgroup\$ – thorsten muller Feb 2 '11 at 18:04
  • 2
    \$\begingroup\$ @Thorsten: They only need to be public if you want to explicitly reference them as a type, otherwise you can use the abstract base. With regards to operator++, here is a good resource: parashift.com/c++-faq-lite/operator-overloading.html#faq-13.14 \$\endgroup\$ – Mark Loeser Feb 2 '11 at 18:08
4
\$\begingroup\$

There is a memory leak in Grid::row_iter(), et al. Why use new in this case? I'd prefer

RowIterator row_iter(int row){return RowIterator(this, row);}
\$\endgroup\$
  • \$\begingroup\$ Thanks for pointing that out. I use those iterators only at a few places in the program. So I didn't notice this yet. \$\endgroup\$ – thorsten muller Mar 2 '11 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.