Von std::vector erben

joomoo

Wenn man während einer Schleife Elemente aus einem Vektor löschen möchte, würde ich das übrigens so machen:

#include <vector>
#include <iostream>

int main()
{
	std::vector<int> v = {5, 1, 4, 5, 123, 5, 5, 10};
	auto end = v.end();
	for(auto it = v.begin(); it != end; ++it)
	{
		while(*it == 5) // nicht if, da ja auch zwei Fünfen hintereinander vorkommen können
		{
			it = v.erase(it);
			--end; // Der vektor ist gerade um ein Element kleiner geworden.
		}
		// Hier kann man jetzt alles wie gewohnt mit dem Vektor machen.
		std::cout << *it << std::endl;
	}
}

Hoffe das ist so richtig. Hab es nur mit GCC 4.5 getestet.

krümelkacker

DocShoe schrieb:

Ist in diesem Fall egal, da er aus der Methode zurückspringt.

Braunstein schrieb:

krümelkackers Funktion löscht alle passenden Elemente im Vektor. Das entspricht damit nicht der Vorgabe.

Ihr habt recht. Ich habe das return an der Stelle übersehen.

joomoo schrieb:

Wenn man während einer Schleife Elemente aus einem Vektor löschen möchte, würde ich das übrigens so machen:

Das ist schade. Es ist nämlich relativ ineffizient gegenüber dem erase-remove-Trick.

Eisflamme

Ja ne. Wenn Du das letzte Element löscht, ist it nach dem Löschen end() und dann versuchst du *it auszugeben.

Wenn du eine interne Schleife machst, musst Du jedes Mal prüfen, ob Du nicht schon bei end bist, so schade es ist. Dafür kannst du Dir das --end sparen, das ist ja doppelt gemoppelt.

HighLigerBiMBam

Du brauchst das while nicht, es geht auch mit if, wenn du den iterator auch um 1 verringerst. Dann hat sich der von Eisflamme bemrkte Fehler von selbst in Luft aufgelöst.

joomoo

krümelkacker schrieb:

joomoo schrieb:

Wenn man während einer Schleife Elemente aus einem Vektor löschen möchte, würde ich das übrigens so machen:

Das ist schade. Es ist nämlich relativ ineffizient gegenüber dem erase-remove-Trick.

Stimmt, hab das gerade mal getestet. Das ist ja ziemlich beeindruckend, warum ist der erase-remove-Weg so schnell?

Eisflamme schrieb:

Ja ne. Wenn Du das letzte Element löscht, ist it nach dem Löschen end() und dann versuchst du *it auszugeben.

Ups, ja das hab ich übersehen. Da fehlt ein

if(it == end)
{
	break;
}

nach der Schleife.

Wenn du eine interne Schleife machst, musst Du jedes Mal prüfen, ob Du nicht schon bei end bist, so schade es ist. Dafür kannst du Dir das --end sparen, das ist ja doppelt gemoppelt.

Wieso kann ich mir das sparen?

HighLigerBiMBam schrieb:

Du brauchst das while nicht, es geht auch mit if, wenn du den iterator auch um 1 verringerst. Dann hat sich der von Eisflamme bemrkte Fehler von selbst in Luft aufgelöst.

Aber dann iteriert man ja über einige Elemente mehrmals. Oder nicht?

HighLigerBiMBam

joomoo schrieb:

Aber dann iteriert man ja über einige Elemente mehrmals. Oder nicht?

Du hast doch gerade ein Element entfernt, also kannst du auch wieder mit dem iterator eins zurückspringen, er wird durch die Schleife eh wieder eins erhöht. Ich greife mal deinen Code auf:

std::vector<int> v = {5, 1, 4, 5, 123, 5, 5, 10}; 
    auto end = v.end(); 
    for(auto it = v.begin(); it != end; ++it) 
    { 
        if(*it == 5) // nicht if, da ja auch zwei Fünfen hintereinander vorkommen können 
        { 
            //edit: undefiniert it-- = v.erase(it); //Und den Iterator verringern zu:
            it = v.erase(it); --it;
            --end; // Der vektor ist gerade um ein Element kleiner geworden. 
        }
		else
		{
			std::cout << *it << std::endl; //Ausgeben nur, wenn nicht verringert wurde
		}
    }

Natürlich darf man nachdem man zurückgesprungen ist, das Element nicht immer ausgeben, weil sonst werden Elemente doppelt ausgegeben. Performance sieht sicher anderst aus, aber ich wollte nur zeigen, dass es auch mit einem "If" möglich ist.

Michael E.

joomoo schrieb:

Stimmt, hab das gerade mal getestet. Das ist ja ziemlich beeindruckend, warum ist der erase-remove-Weg so schnell?

Du führst mehrere vector::erase(it) durch. Bei jedem Durchlauf werden alle Elemente in [it + 1, end) verschoben. Beim erase-remove-Idiom werden alle Elemente höchstens einmal verschoben.

Das Schöne an erase-remove ist, dass das erase nur die Destruktoren der zu entfernenden Elemente aufrufen und die Größe des Vektors verringern muss (eine Integer-Subtraktion). Da wir hier über ints reden, fällt sogar ersteres weg.

camper

HighLigerBiMBam schrieb:

std::vector<int> v = {5, 1, 4, 5, 123, 5, 5, 10}; 
    auto end = v.end(); 
    for(auto it = v.begin(); it != end; ++it) 
    { 
        if(*it == 5) // nicht if, da ja auch zwei Fünfen hintereinander vorkommen können 
        { 
            it-- = v.erase(it); // ?? Ziemlich unklar, was hier passieren soll, allerdings mal überlegen, was passiert, wenn das erste Element gelöscht wird
            --end; // Der vektor ist gerade um ein Element kleiner geworden.
                   // Stimmt. Und damit sind sämtliche Iteratoren, die nach der Löschstelle liegen, ungültig geworden.
        }
		else
		{
			std::cout << *it << std::endl; //Ausgeben nur, wenn nicht verringert wurde
		}
    }

Es geht im Grunde nur so:

for(auto it = v.begin(); it != end; ) 
    { 
        if(*it == 5)
        { 
            it = v.erase(it);
            end = v.end();
        }
		else
		{
			std::cout << *it++ << std::endl;
		}
    }

Wobei zweifelhaft ist, ob die Verwendung von end gegenüber v.end() überhaupt etwas bringt. Wenn es nicht gerade ein char-vector ist, weiß der Compiler dank der alias-Regeln genug, um gleichartig optimieren zu können.
und remove-erase ist sowieso effizienter und kürzer.

LukasBanana

Danke für eure schnellen Antworten
Ich denke ich werde die "vec.erase(std::find...)" methode verwenden.
Ich hab nicht gewusst, dass es auch solche Funktionen in der STL/algorithm lib gibt.
Gruß,
Lukas

Braunstein

LukasBanana schrieb:

D
Ich hab nicht gewusst, dass es auch solche Funktionen in der STL/algorithm lib gibt.

Dann schau mal hier rein und staune.
http://www.cplusplus.com/reference/algorithm/