Frage zur For Loop

Hallo zusammen,

ich habe zur Übung um in C++ reinzukommen einmal das Sieb des Eratosthenes zum finden von Primzahlen programmiert. Meine Implementierung hat aber einen Bug, den ich in meiner For-Schleife meine gefunden zu haben, aber nicht verstehe, warum er auftritt. Hier ist erstmal der Code:

struct markable_digit {
private:
    friend std::ostream& operator<<(std::ostream&, const markable_digit &);

public:
    markable_digit() {
        this->digit = 1;
        this->marked = false;
    }

    markable_digit& operator=(const int &rhs) {
        this->digit = rhs;
    }

    int digit;
    bool marked;
};

std::ostream& operator<<(std::ostream &os, const markable_digit &a) {
    return os << a.digit;
}

std::vector<int> sieve_of_eratosthenes(int n) {
    std::vector<markable_digit> range(n);
    std::iota(range.begin(), range.end(), 1);

    // skip number 1
    auto it = range.begin();
    it->marked = true;

    // start with number 2
    std::vector<int> found_primes;
    while (++it != range.end()) {

        if (it->marked) {
            continue;
        }

        found_primes.push_back(it->digit);

        for (auto next_multiple = it; next_multiple->digit <= n; next_multiple += it->digit) {
            next_multiple->marked = true;
            if (it->digit == 5) {
                cerr << next_multiple->digit << " " << next_multiple->marked << " " << (next_multiple->digit + it->digit <= n) << endl;
            }
        }
    }

    return found_primes;
}

Die For-Schleife in Zeile 41 wird einmal zu viel aufgerufen. Daher auch meine if-Abfrage zu Debug zwecken. Rufe ich die Funktion nun mit der Zahl 20 auf, so erhalte ich folgenden Output durch das cerr:

Bis zu der Zeile 20 1 0 läuft alles, wie ich es auch erwarte. Ich verstehe aber nicht, wie die letzte Zeile zu stande kommt. Schließlich ist der Ablauf der For Schleife:
1. Initialisierung
2. Prüfen der Bedingung
3. Ausführen des Funktionsrumpfes
4. Erhöhen
5. Weiter bei Punkt 2

Zu dem Zeitpunkt, wo cerr den Wert 20 ausgiebt, dürfte die Bedingung für einen weiteren Durchlauf ja eigentlich nicht mehr erfüllt sein (was auch durch die 0 ausgedrückt wird).

Daher wollte ich hier mal um Verständnishilfe fragen, warum ich dieses Verhalten in meinem Code habe. Für weitere Anmerkungen zu meinem Code wäre ich auch dankbar. Befinde mich ja schließlich noch in der Lernphase

Viele Grüße und schönen abend euch noch

hustbaer

Überleg dir mal wohin next_multiple zu dem Zeitpunkt wo die 20 ausgegeben wird zeigt, und was du danach damit anstellst.

ps: Mit welchem Compiler und welchen Einstellungen testest du?

Dein Iterator ist nach dem letzten next_multiple += it->digit nicht mehr im gültigen Bereich. Du musst irgendwo einen Check einbauen damit du nicht über das Ende hinaus ließt.

hustbaer

Achje sebi nicht immer gleich alles verraten.
Er soll ja lernen seine Fehler selbst zu finden.

Ja sorry
Mir ist in Visual Studio direkt der Debug Build beim operator+ explodiert... Ist also kein großes Geheimnis. Wie er das verhindert kann der TO sich ja selbst überlegen.

Ahhh, ja jetzt sehe ich es auch. Nachdem cerr die 20 ausgegeben hat, wird der Iterator erhöht und zeigt ins Nirwana, wo dann die Zahl 0 abgelegt zu sein scheint. Ich bedanke mich bei euch beiden, Sebi hats tatsächlich verraten :p
Dennoch ein Lernerfolg, da bin ich mir sicher

hustbaer

Und da sebi707 es gerade angesprochen hat...
In einer passenden IDE mit passenden Compiler-Einstellungen (Debug Build) explodiert dir das sofort statt dir ne 0 hinzuschreiben.
Hilft enorm solche und 1000 andere Fehler schon während des Entwickelns zu finden.
Solltest du verwenden wenn du nicht auf SM stehst oder so.