erase und remove aus der stl

pumuckl

- Erstens ist es zwar lobesam dass du deinen Code reduzierst, allerdings ist hier die Bedingung im if von Interesse.
- Zweitens ist im Code nicht zu sehen dass du irgendwas mit findIt machst, der Iterator würde also immer auf allPoints.begin() stehen, wenn nicht...
- ... Drittens: solltest du anders als im Code gezeigt findIt irgendwo in allPoints positionieren, kann dir der Aufruf von remove() ein Ergebnis liefern, das vor findit liegt. Der Aufruf von erase() macht in dem Fall den iterator findIt ungültig. Der nächste Zugriff darauf erzeugt undefiniertes Verhalten, und wenn man von undefiniertem Verhalten spricht ist eine Endlosschleife noch harmlos (rein theoretisch wäre es durchaus mit dem Standard vereinbar wenn der Rechner versucht, das Schlumpfenlied auf dem PC-Speaker zu spielen...)

Fellhuhn

Pumuckl redet von den Schlümpfen? Ich glaube die Hölle friert zu!

Überhaupt habe ich noch nie gesehen das der Rückgabewert von remove an erase übergeben wird...

Nexus

Kleiner Fehler:

Fellhuhn schrieb:

findIt = vector.erase(*findIt);

müsste so sein:

findIt = vector.erase(findIt);

Mister Wing

Die if-Bedingung enthält einen Wert den ich suche. Wenn ich den gefunden habe übergebe ich ihm collectPoints und will ihn aus allPointslöschen. Bloss die Adresse von allPoints ändert sich doch am Ende. Mit dem Rückgabewert von remove sag ich ihm doch den neuen Endwert an. Oder?! So hab ich es verstanden in der stl.

Nexus

Es ist dir aber bewusst, dass ein STL-Algorithmus namens find() existiert, der Elemente sucht und einen Iterator auf das erste gefundene Element zurückgibt?

Dann kannst du den nämlich zuerst dereferenzieren und per push_back() anhängen, dann mit erase() aus dem alten Vector löschen.

Fellhuhn

Nexus schrieb:

Kleiner Fehler:

Fellhuhn schrieb:
findIt = vector.erase(*findIt);
müsste so sein:
findIt = vector.erase(findIt);

Soll doch spannend bleiben.

@Wing
remove entfernt alle Elemente in der Range der ersten beiden Parameter die dem dritten entsprechend. vec.erase hingegen löscht nur ein Element und das zwar das, dessen Iterator ihm da übergeben wird. erase gibt dann einen Iterator auf das Element HINTER dem gelöschten zurück. Deswegen wird nur in dem Fall, in dem nichts gelöscht wird, der Iterator manuell verschoben.

camper

Fellhuhn schrieb:

Du veränderst findIt nicht?

//...
if (sollWasLöschen)
  findIt = vector.erase(*findIt);
else
  ++findIt;

Fast, da wir hier ein range-erase mit dem Resultat von remove durchführen wollen, ist der Rückgabewert von erase allerdings uninteressant (nämlich immer end(), und nicht das Folgeelement der Ursprungssequenz). Tatsächlich ist das ohne Kenntnis der Löschbedingung nicht so ohne Weiteres zu korrigieren. Einfach wird es nur, wenn die Löschbedingung derart ist, dass sie immer gleich für das erste gefundene Element erfüllt ist. Dann können wir nebenbei auch den Anwendungsbereich von remove einengen.

for( findIt=allPoints.begin() ; findIt!=allPoints.end() ;  )
{
  if ( ... )
  {
    collectPoints.push_back(*findIt);
 // collectPoints.back statt *findIT um ggf. mit defekten Implementierungen umzugehen, die remove zu naiv implementieren (Vergleichsobjekt ist selbst Element der Sequenz)
    PointVector::iterator erase_begin = remove(findIt, allPoints.end(), collectPoints.back());
    if ( erase_begin == findIt )
    {
        vector.erase(erase_begin, allPoints.end());
    // sowohl erase_begin als auch findIt sind hier ungültig, deshalb mussten wir den Test vor dem erase durchführen, auch wenn das zu einer gewissen
    // Codeduplizität führt
        break;
    }
    vector.erase(erase_begin, allPoints.end());
    // das ursprüngliche Objekt bei *findIt wurde durch remove durch das Folgelement der Ursprungssequenz ersetzt, hier ist also nichts mehr zu tun
  }
// alternativ
//  bool reached_end = ( erase_begin == findIt );
//  vector.erase(erase_begin, allPoints.end());
//  if ( reached_end )
//    break;
// .. wahrscheinlich sogar besser so
  else
    ++findIt;
}

Turing

Was spricht gegen:

PointVector::iterator first_invalid_element;
first_invalid_element = remove(allPoints.begin(), allPoints.end(), my_value);
allPoints.erase(first_invalid_element, allPoints.end());

?

Fellhuhn

camper schrieb:

Fast, da wir hier ein range-erase mit dem Resultat von remove durchführen wollen, ist der Rückgabewert von erase allerdings uninteressant (nämlich immer end(), und nicht das Folgeelement der Ursprungssequenz). Tatsächlich ist das ohne Kenntnis der Löschbedingung nicht so ohne Weiteres zu korrigieren. Einfach wird es nur, wenn die Löschbedingung derart ist, dass sie immer gleich für das erste gefundene Element erfüllt ist. Dann können wir nebenbei auch den Anwendungsbereich von remove einengen.

Wo steht denn was von range-erase? Hab ich das überlesen? Auch "vector" aus deinem Beispiel gibt es nicht in seinem.

Ich verstehe sein Eingangsposting eher so das er alle Elemente auf die if(...) zutrifft aus allPoints entfernt und dafür in collectPoints einfügen will. Nicht mehr.

camper

Fellhuhn schrieb:

camper schrieb:

Fast, da wir hier ein range-erase mit dem Resultat von remove durchführen wollen, ist der Rückgabewert von erase allerdings uninteressant (nämlich immer end(), und nicht das Folgeelement der Ursprungssequenz). Tatsächlich ist das ohne Kenntnis der Löschbedingung nicht so ohne Weiteres zu korrigieren. Einfach wird es nur, wenn die Löschbedingung derart ist, dass sie immer gleich für das erste gefundene Element erfüllt ist. Dann können wir nebenbei auch den Anwendungsbereich von remove einengen.

Wo steht denn was von range-erase? Hab ich das überlesen? Auch "vector" aus deinem Beispiel gibt es nicht in seinem.

Ich verstehe sein Eingangsposting eher so das er alle Elemente auf die if(...) zutrifft aus allPoints entfernt und dafür in collectPoints einfügen will. Nicht mehr.

vector=allPoints - dummer C&P-Effekt aus deinem Posting

Der Range-erase-Aufruf steht im ersten Beitrag.

nochmal korrigiert und übersichtlicher, an den Erklärungen ändert sich nichts

PointVector::iterator findIt=allPoints.begin();
for( bool reached_end = ( findIt == allPoints.end() ); !reached_end ;  )
{
  if ( ... )
  {
    collectPoints.push_back(*findIt);
    PointVector::iterator erase_begin = remove(findIt, allPoints.end(), collectPoints.back());
    reached_end = ( erase_begin == findIt );
    allPoints.erase(erase_begin, allPoints.end());
  }
  else
    reached_end = ( ++findIt == allPoints.end() );
}

Mister Wing

Also, welche von den ganzen Vorschlägen ist nun die Lösung meines Problems?

1. Wert gefunden in allPoints
2. den gefunden Wert in coolectPoints einfügen, dabei aber aus allPoints löschen
3. weiter gehen bis zum nächsten gefunden Wert, Schritt und 1 und 2 wiederholen
4. bis Ende erreicht ist
5. wenn allPoints irgendwann wieder aufgerufen wird, dann sollen diese gelöschten Punkte nicht vorhanden sein

Fellhuhn

Dann reicht das was ich geschrieben hatte.

if (sollWasLöschen){
  collectPoints.push_back(*findIt);
  findIt = allPoints.erase(*findIt);
}else{
  ++findIt; 
}

camper

Fellhuhn schrieb:

Dann reicht das was ich geschrieben hatte.

if (sollWasLöschen){
  collectPoints.push_back(*findIt);
  findIt = allPoints.erase(*findIt);
}else{
  ++findIt; 
}

vector hat keine erase-Funktion, die als Argument ein Objekt des Elementtyps benutzt. Und falls es diese Funktion gäbe, und diese alle Vorkommen des Arguments aus dem vector löschte, verbliebe immer noch die Frage, welche Bedeutung der Rückgabewert bei mehreren gelöschten Elementen haben müsste (womit gleich die Erklärung gegeben ist, warum es diese Funktion nur für assoziative Container gibt).

Mister Wing

Also bei mir stürzt er ab nach Fellhunhs Lösung.

vector<int> vec;

	for(int i = 1; i< 13; i++)
		vec.push_back(i);

	vector<int>::iterator it;
	for ( it = vec.begin() ; it!=vec.end() ; )
	{
		if ( (4-*it == 0) || (9-*it == 0)  )
		{	
			cout << "Geloeschter Wert : " << *it << endl;
			it = vec.erase(it);			 
		}
		else
			it++;

		cout << *it << endl;
	}

	vec.~vector();

Fellhuhn

Weil du bei deinem cout am Ende der Schleife im letzten Durchlauf quasi *vec.end() machst.

Mister Wing

Ok. Lösung gefunden. So ists recht. Vielen Dank Fellhuhn.

Thread kann geschlossen werden.

Mister Wing schrieb:

Also bei mir stürzt er ab nach Fellhunhs Lösung.
vec.~vector();

Ist nicht dein Ernst?!

Mister Wing

Na doch, weil ich ein paar Programmzeilen mehr habe und ich ihn an dieser Stelle zerstören muss.

camper

Ich hatte das so interpretiert, dass die Ausgabesequenz keine Duplikate enthalten darf (als Konsequenz des remove-Aufrufs).
Fellhuhns korrigierte Variante funktioniert, hat aber quadratische Komplexität.
Besser wäre

struct is_candidate_for_collection : std::unary_function<int,bool>
{
    bool operator(int v) const { return v == 9 || v == 4; }
};

...
// Kopiere alle Kandidaten nach collectPoints:
remove_copy_if(allPoints.begin(),allPoints.end(),std::back_inserter(collectPoints),std::not1(is_candidate_for_collection()));
// Lösche alle Vorkommen in allPoints
allPoints.erase(remove_if(allPoints.begin(),allPoints.end(),is_candidate_for_collection()),allPoints.end());

// oder wir schreiben uns einen eigenen single-pass Algorithmus
template<class ForwardIterator, class OutputIterator, class Predicate>
ForwardIterator split_copy_if(ForwardIterator first, ForwardIterator last,OutputIterator out, Predicate pred)
{
    ForwardIterator i = std::find_if(first,last,pred);
    if ( i == last )
        return i;
    for ( *out = *i, ++out, first = i, ++first; first != last; ++first )
    {
        if ( pred( *first ) )
        {
            *out = *first;
            ++out;
        }
        else
        {
            *i = *first;
            ++i;
        }
    }
    return i;
}
// mithin
allPoints.erase(split_copy_if(allPoints.begin(),allPoints.end(),std::back_inserter(collectPoints),is_candidate_for_collection()),allPoints.end());