erase und remove aus der stl

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());