doppelte Schleife

Ich habe folgenden Algorithmus:

for (auto gs = v.begin(); gs != v.end(); ++gs)
    {
        for (auto gs2 = gs; gs2 != v.end(); ++gs2)
        {
            if (<Bedingung an gs und gs2, die symmetrisch ist in gs und gs2>)
            {
                print(*gs);
                print(*gs2);
                break;
            }
        }
    }

Diesen will ich beschleunigen, und zwar etwa so:

for (auto gs = v.begin(); gs != v.end(); ++gs)
    {
        for (auto gs2 = gs; gs2 != v.end(); ++gs2)
        {
            if (<Bedingung an gs und gs2, die symmetrisch ist in gs und gs2>)
            {
                print(*gs);
                print(*gs2);
                v.erase(gs);
                v.erase(gs2);
                break;
            }
        }
    }

Wie mache ich das, so dass es keine Speicherzugriffsfehler wegen der iteratoren gs und gs2 gibt?

KN4CK3R

schau dir mal den Rückgabewert der Funktion an

SeppJ

Was soll das werden? Der zweite Code macht was anderes als der erste (wenn man mal die Ungültigkeit der Iteratoren vernachlässigt), denn beim zweiten Code kann ein Wert aus der Menge nur genau einmal behandelt werden, während beim ersten Code die Bedingung mehrmals für einen Wert erfüllt werden kann. Ist das beabsichtigt?

Du könntest den Containertypen einschränken, dass erase wenigstens Iteratoren vor dem gelöschten Element gültig lässt (d.h. alle Container außer deque sind erlaubt), dann kannst du erst das hintere Element (gs2) löschen, danach das vordere und den Rückgabewert von erase benutzen. Für deque könntest du eine spezielle Implmentierung basierend auf Indizes schreiben.

Ich habe übrigens Zweifel, ob das irgendwas beschleunigt. erase ist bei vielen Containern ganz schön teuer! Bei einem random access Containern könntest du eine Liste der noch gültigen Indizes führen und über diese iterieren. Bei anderen Containern hast du kein so großes Problem, da das Löschen relativ flott geht und die Iteratoren gültig bleiben, da könntest du ohnehin bei deiner Lösung bleiben. Ein Mittelding stellen set-artige Container dar, bei denen das Löschen immerhin logarithmisch in der Containergröße ist. Müsste man mal ausprobieren, ob die Zeiten da noch akzeptabel sind.