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

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

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

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.

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.

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?

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

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

hustbaer

volkard schrieb:

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.

Ich gehe davon aus dass
a) der Code der pop_back() Schleife sowieso nahezu ideal wird (wieso sollte es da zu einem doppelten Test kommen - .back() ist ja unchecked)
und
b) es völlig egal wäre, selbst wenn die Schleife 10x so lange brauchen würde wie optimal möglich