Sudoku Grid-Spezialzweck-Iteratoren

723
thorsten muller

Bitte sehen Sie sich diese Iteratoren an, die ich für meinen Sudoku-Löser verwende. Sie unterscheiden sich geringfügig von STL-Iteratoren und implementieren nicht die gesamte Funktionalität, die erforderlich wäre, um sie in einem STL-Kontext zu verwenden. Der Grundgedanke dabei war jedoch, den Code im Sudoku-Programm zu bereinigen, der die drei von mir implementierten Zugriffsmuster (row, col, block) intensiv nutzt.

Der "wichtigste" Iterator ist der BlockIterator, denn ohne dass das Durchlaufen aller neun Felder in einem Block ziemlich hässlich aussah. Das Durchlaufen von Zeilen und Spalten war nicht so schlimm, aber seit ich mit dem Schreiben der Sachen angefangen habe, habe ich beschlossen, ein komplettes Set zu erstellen.

Einige technische Details:

Die Grid-Klasse enthält ein (böses) Array von Zeigern auf Field-Objekte, das ist eindimensional (ich hätte auch ein zweidimensionales Array verwenden können, aber ich mache das oft so und fühle mich mit Modulo-Operationen ziemlich wohl). Vielleicht werde ich das später durch einen Vektor ersetzen.

Die Grid-Klasse fügt einige statische Funktionen hinzu, um Offsets im Array basierend auf Zeilen-, Spalten- oder Blockpositionen zu berechnen.

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];

Verwendungsbeispiel:

Diese Funktion wird aufgerufen, wenn ich einen Wert in einem Feld setze. Es werden alle Felder durchlaufen, die möglicherweise von diesem Feld beeinflusst werden (gleiche Zeile, Spalte oder 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);
}

Sagen Sie mir also bitte, ob so etwas "akzeptabel" wäre (von "Best Practices" ganz zu schweigen), auch wenn das Iteratorkonzept irgendwie völlig frei ist.

Und natürlich ist jede Idee willkommen, wie dies verbessert werden kann.

PS: Ich habe versucht, einen Tag "Iterator" hinzuzufügen, aber ich darf nicht zu wenig Ansehen.

Antworten
14

2 Antworten auf die Frage

8
Mark Loeser

In meinem ersten schnellen Durchblick möchte ich einige Dinge ansprechen:

  • Wenn Sie Operatoren überladen möchten, tun Sie dies so, wie es die Benutzer der Sprache erwarten, oder tun Sie es überhaupt nicht. Ich erwarte operator++, etwas zurückzugeben, nicht ein void.
  • Muss block_offsetwirklich öffentlich sein?
  • Müssen Ihre konkreten konkreten Implementierungen der Iteratoren ebenfalls öffentlich sein, da Sie Methoden haben, um sie öffentlich zu erstellen? Wäre es für jemanden sinnvoll, sie jemals anders gestalten zu wollen?
Der dritte Punkt ist ausgezeichnet. Es ist so gut wie nie nötig, explizit einen Iterator zu erstellen, da diese immer an die Iteration der Collection gebunden sind. Die Implementierung sollte also verborgen sein. Michael K vor 10 Jahren 0
Danke, Mark. Ich habe block_offset und die Klassen in protected geändert. Ich dachte, die Klassen müssten öffentlich sein, damit sie außerhalb der Grid-Klasse verwendet werden können. Der Code wird jedoch immer noch kompiliert. block_offset war öffentlich, denn bevor ich die Iteratoren implementiert habe, habe ich es überall verwendet, um die Felder "manuell" zu durchlaufen. thorsten muller vor 10 Jahren 0
Die Iteratortypen selbst müssen öffentlich sein, wenn Sie [Variablen dieser Typen erstellen] möchten (http://codepad.org/L9zlqIpF). @Michael: Der for-Schleifencode in der Frage muss öffentlich sein, da er nicht erscheint. Field ist ein Freund von Grid. Fred Nurk vor 10 Jahren 0
Ich habe den Operator aus einem Online-Muster genommen. Ich werde einen Blick auf Stroustrup oder eine andere Quelle werfen, um zu sehen, wie man sie richtig implementiert. Ich habe nicht viel darüber nachgedacht, etwas zurückzugeben, da ich hier zumindest nur die inkrementelle Funktionalität benötige. thorsten muller vor 10 Jahren 0
@Fred: Im Moment werden sie nur von der Grid-Klasse und von der Field-Klasse (die als Freund deklariert wird) verwendet. Ich werde das anpassen, wenn ich sie anderweitig verwenden muss. thorsten muller vor 10 Jahren 0
@Thorsten: Sie müssen nur öffentlich sein, wenn Sie sie explizit als Typ referenzieren möchten. Andernfalls können Sie die abstrakte Basis verwenden. In Bezug auf operator ++ ist hier eine gute Ressource: http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.14 Mark Loeser vor 10 Jahren 2
@Fred: Müssen sie öffentlich sein, wenn ein Iterator anstelle eines RowIterators usw. zurückgegeben wird? Michael K vor 10 Jahren 0
@Michael: Der abstrakte Iterator kann nicht nach Wert zurückgegeben werden. Iterator muss also nicht öffentlich sein, es sei denn, Sie wollten einen Zeiger oder eine Referenz darauf (anstelle einer Nicht-Zeiger-Nicht-Referenzvariablen), aber für die konkreten abgeleiteten Klassen gilt das Erstellen von Variablen (wie in meinem vorherigen Link). Ich würde sie einfach öffentlich machen, da das Verstecken keinen Sinn hat. Fred Nurk vor 10 Jahren 0
btw: Soll ich den Code in meiner Frage an die Änderungen anpassen, die ich dank Ihrer Hinweise vorgenommen habe? Oder sollte ich es wie in meiner ersten Bearbeitung als Referenz belassen? thorsten muller vor 10 Jahren 0
4
Rob

Es gibt ein Speicherleck in Grid::row_iter()et al. Warum newin diesem Fall verwenden? ich würde bevorzugen

RowIterator row_iter(int row){return RowIterator(this, row);}
Danke, dass du darauf hingewiesen hast. Ich benutze diese Iteratoren nur an wenigen Stellen im Programm. Also habe ich das noch nicht bemerkt. thorsten muller vor 10 Jahren 0