Frage zu Standardlösung für das Löschen gleicher Elemente am vectorende

[DeletePlox]

Hallo!
Ich habe einen vector<int>, der eine Zahl repräsentieren soll. Die "Ziffern" sind in umgekehrter Reihenfolge angeordnet, sodass an das Ende des vectors beliebig viele Nullen angehangen werden können.
Gibt es eine Standardlösung, alle Nullen am Ende des vectors besonders elegant und effizient mit einem Algorithmus aus der STL zu löschen?
Mein Ansatz sähe irgendwie so aus:

bool pred(const int& i)
{
    return i != 0;
}
//...
std::vector<int> v;
v.erase(find_if(v.rbegin(), v.rend(), pred), v.end());

Allerdings kompiliert das nicht, da find_if nicht mit reverse_iteratoren arbeiten kann. Wie würdet ihr das Problem lösen?

[CStoll]

Wer sagt, daß find_if() nicht mit reverse_iteratoren arbeiten kann? Der schluckt alles, was sich inkrementieren und dereferenzieren lässt. Ein Problem könnte es sein, daß erase() einen normalen Iterator erwartet - aber dagegen hilft reverse_iterator::base().

Edit: Und so sieht das in der Praxis aus: http://ideone.com/FTnZ9

[cooky451]

Nur mal eine kleine noob Frage: Was spricht gegen

void del_vec(std::vector<int>& vec)
{
  while (vec.size() && !vec[vec.size() - 1])
    vec.pop_back();
}

[DeletePlox]

Erstmal danke für die schnelle Antwort!

cooky451 schrieb:

Nur mal eine kleine noob Frage: Was spricht gegen [...]

Hm ich wollte mich hier an die Grundsätze aus Scott Meyers "Effective STL" halten, wo es heißt:
1. "Prefer algorithm calls to hand-written loops"
2. "Prefer range member functions to their single-element counterparts"
Obwohl deine Lösung auch recht elegant aussieht... Ich weis nicht. Welche Version soll ich denn nun nehmen?

[cooky451]

Prefer algorithm calls to hand-written loops

Kann ich nicht so ganz nachvollziehen, ich finde Schleifen kann man besser lesen und langsamer werden die wohl auch nicht sein. Aber gut, der Scott Meyers wird schon wissen was er schreibt, vielleicht erklärt das ja noch jemand.

[volkard]

cooky451 schrieb:

Prefer algorithm calls to hand-written loops

Kann ich nicht so ganz nachvollziehen, ich finde Schleifen kann man besser lesen und langsamer werden die wohl auch nicht sein. Aber gut, der Scott Meyers wird schon wissen was er schreibt, vielleicht erklärt das ja noch jemand.

Ist Quatsch. Wird mit range based for loops bereinigt. Schätze 5 bis 7 Jahre wird's dauern.

Lamdas werden für noch ein wenig Performance-Steigerung führen bei manchen Datenstrukturen. So müssen Bäume nicht mehr immer gefädelt werden oder Aufwärtszeiger haben. Aber das ist eine andere Geschichte.

[CStoll]

In den Algorithmen wird schon einiges an Optimierungen drinstecken, die du mit einer Schleife nicht so leicht hinbekommst - und der Ansatz muß auch nur einmal die Verwaltungsdaten des vector<>s anfassen.

@Plox: Wie du an meinem edit oben sehen kannst - mit einer leichten Korrektur funktioniert dein Lösungsansatz

[seldon]

Vorschlag zur Güte:

v.erase(std::find_if(v.rbegin(), v.rend(), std::bind2nd(std::not_equal_to<int>(), 0)).base(), v.end());

[volkard]

seldon schrieb:

Vorschlag zur Güte:

v.erase(std::find_if(v.rbegin(), v.rend(), std::bind2nd(std::not_equal_to<int>(), 0)).base(), v.end());

Das halte ich für eine Programmierparodie.

[seldon]

Zugegeben, es ist nicht hübsch, aber ein optimierender Compiler dürfte gut damit arbeiten können. Im Vergleich zur push_back-Schleife erwarte ich einen Performancegewinn schlicht dadurch, dass nicht für jedes Element die Verwaltungsinformationen des vectors aktualisiert werden müssen (dafür müsste ein Optimierer schon sehr klug sein), und so ist es, wenn einen die Extrafunktion stört, ein gangbarer Weg.

Mit Lambda-Funktionen wäre es natürlich schöner, aber damit warte ich noch, bis der neue Standard verabschiedet und implementiert ist.

[volkard]

seldon schrieb:

Zugegeben, es ist nicht hübsch, aber ein optimierender Compiler dürfte gut damit arbeiten können. Im Vergleich zur push_back-Schleife erwarte ich einen Performancegewinn schlicht dadurch, dass nicht für jedes Element die Verwaltungsinformationen des vectors aktualisiert werden müssen (dafür müsste ein Optimierer schon sehr klug sein), und so ist es, wenn einen die Extrafunktion stört, ein gangbarer Weg.

Ich habe mit push_back-Schleifen die allerbesten Erfahrungen.
Der pop_back-Schleife würde ich aber auch nicht trauen.

Würde

v.erase(std::find_if(v.rbegin(), v.rend(), std::bind2nd(std::not_equal_to<int>(), 0)).base(), v.end());

vielleicht klarer werden, wenn man es in mehrere Zeilen aufteilt?
Mal angenommrn, wir hätten wenigstens auto.

[seldon]

Richtig, richtig, Denkfehler meinerseits; ich meine natürlich pop_back.

Ansonsten kann man das natürlich in

auto not_zero = std::bind2nd(std::not_equal_to<int>(), 0);
v.erase(std::find_if(v.rbegin(), v.rend(), not_zero).base(), v.end());

aufteilen, aber wenn man schon bei C++11 ist, geht's auch mit

v.erase(std::find_if(v.rbegin(), v.rend(), [](int x) { return x != 0; }).base(), v.end());

[dot]

Nur mal ne Frage: Wenn die Nullen sowieso schon am Ende des vectors liegen, warum kannst du den vector nicht einfach entsprechend verkleinern und fertig?

[volkard]

seldon schrieb:

Ansonsten kann man das natürlich in

auto not_zero = std::bind2nd(std::not_equal_to<int>(), 0);
v.erase(std::find_if(v.rbegin(), v.rend(), not_zero).base(), v.end());

aufteilen

Könnte man nicht auch die Position der ersten 0 oder der letzten nicht-0 oder der letzen von hinten gezählten 0 als Zwischenergebnis nehmen?

[DeletePlox]

dot schrieb:

Nur mal ne Frage: Wenn die Nullen sowieso schon am Ende des vectors liegen, warum kannst du den vector nicht einfach entsprechend verkleinern und fertig?

Weil ich ja wissen um, um wie viel der vector verkleinert werden muss aka wie viele Nullen sich am Ende befinden

[seldon]

@volkard: Du kannst als Zwischenergebnis nehmen, wozu du lustig bist.

@dot: Etwa

v.resize(std::distance(v.begin(), std::find_if(v.rbegin(), v.rend(), std::bind2nd(std::not_equal_to<int>(), 0)).base()));

? Klar, das geht auch. Volkard wird es aber wahrscheinlich aus den gleichen Gründen für eine Parodie halten.

[camper]

boost::algorithm::trim_right_if( v, std::bind2nd( std::equal_to<int>(), 0 ) );

[hustbaer]

Ihr macht wieder alles reichlich kompliziert...

Ich würde das ohne zu überlegen sofort so (ähnlich) schreiben wie cooky451:

while (!vec.empty() && vec.back() == 0)
        vec.pop_back();

Bzw. wenn schon mit Boost, dann gleich so:

boost::trim_right_if(v, boost::lambda::_1 == 0);

Oder so:

boost::trim_right_if(v, [](int i) {return i == 0;} );

[hustbaer]

volkard schrieb:

Der pop_back-Schleife würde ich aber auch nicht trauen.

Wieso nicht?

[volkard]

hustbaer schrieb:

volkard schrieb:

Der pop_back-Schleife würde ich aber auch nicht trauen.

Wieso nicht?

Weil ich viele push_back-Schleifen geschrieben habe und alles war gut. Aber noch nie eine pop_back-Schleife. Darum fühlt sich die für mich komisch an. Und das && in der Laufbedingung scheint mir dann zu einem doppelten Test in der Hauptschleife zu führen, der in find_if nicht steckt.
Andererseits, wenn es typischerweise wenige oder gar keine Nullen sind, drängt sich mir die pop_back-Schleife doch auf.

[volkard]

seldon schrieb:

v.resize(std::distance(v.begin(), std::find_if(v.rbegin(), v.rend(), std::bind2nd(std::not_equal_to<int>(), 0)).base()));

? Klar, das geht auch. Volkard wird es aber wahrscheinlich aus den gleichen Gründen für eine Parodie halten.

Jupp. Weil es drei Aufrufe sind, die nacheinander geschehen und das Ergebnis sukzessive aufbauen.

auto positon_der_ersten_null_am_ende=std::find_if(v.rbegin(), v.rend(), std::bind2nd(std::not_equal_to<int>(), 0)).base();
    auto anzahl_der_nicht_nullen_am_anfang=std::distance(v.begin(),positon_der_ersten_null_am_ende);
    v.resize(anzahl_der_nicht_nullen_am_anfang);