[STL] Vector iterator an Position springen

[krümelkacker]

314159265358979 schrieb:

1. Iterator auf das letzte Element holen.
2. Wenn ein Element gelöscht werden soll, Element mit *last tauschen.
3. Last erniedrigen
4. Remove & Erase Idiom

Super Idee. Wobei remove hier dann ja überflüssig ist. Statt swap mag auch einfach ein move-assignment reichen.

Also...

unsigned numelecs = electrons.size();
for (unsigned idx=0; idx<numelecs; /* kein ++idx hier*/)
{
  ...

  if (muss electrons[idx] gelöscht werden?) {
    --numelecs;
    if (idx!=numelecs) { // falls idx nicht schon das letzte gültige war ...
      electrons[idx] = std::move(electrons[numelecs]);
    }
    // kein ++idx, weil an idx-ter Stelle ja
    // jetzt ein neues Electron steht, was wir nicht
    // ueberspringen wollen, oder wir schon am Ende sind
  } else {
    ++idx; // ok, weiter zum nächsten
  }
}
electrons.erase(electrons.begin()+numelecs,electrons.end());

(ungetestet)

Klaus82 schrieb:

[...]
Dies führt dann kurioser Weise schon zu erster Irritation, denn:

#include <iostream>

using namespace std;

void foo(int i)
{
	cout << "Input is : " << i << endl;
}

int main()
{
  double j = 10;

  foo(j);  // <-- funktioniert!!
	
  return 0;
}

Wie gesagt, die Art der Parameterinitialisierung ist äquivalent zu

double j = 10;
int  i = j; // OK: implizite Konvertierung des double-Wertes nach int

int& r = j; // Compile-Error: Auf was soll sich r denn beziehen?
            // Dass das hier nicht klappt ist ein Feature, denn
            // sonst würde das ganz schnell zu Bugs führen, weil
            // Du ggf beim Schreibzugriff über r Änderungen von j
            // erwarten würdest, was gar nicht sein kann.

const int& c = j; // Das ist erlaubt. Hier bezieht sich die Referenz
                  // auf ein temporär erzeugtes int-Objekt. Da du das
                  // wegen const nicht verändern darfst, kannst du auch
                  // nicht in die Falle von oben reinlaufen.

Die Sache hat mit Funktionen also gar nichts zu tun.

Klaus82 schrieb:

[...]
Warum? Das kann ich nur wieder raten.
[...] aber keine Referenzumwandlung.

Zumindest nicht bei nicht-const Referenzen. Sei froh, dass das so ist!

[Klaus82]

Hi,

krümelkacker schrieb:

unsigned numelecs = electrons.size();
for (unsigned idx=0; idx<numelecs; /* kein ++idx hier*/)
{
  ...

  if (muss electrons[idx] gelöscht werden?) {
    --numelecs;
    if (idx!=numelecs) { // falls idx nicht schon das letzte gültige war ...
      electrons[idx] = std::move(electrons[numelecs]);
    }
    // kein ++idx, weil an idx-ter Stelle ja
    // jetzt ein neues Electron steht, was wir nicht
    // ueberspringen wollen, oder wir schon am Ende sind
  } else {
    ++idx; // ok, weiter zum nächsten
  }
}
electrons.erase(electrons.begin()+numelecs,electrons.end());

Ich habe dein Programm versucht nachzubauen und hänge jetzt an der Fehlermeldung

‘move’ is not a member of ‘std’

Eine Suche im Netz ergabe, dass dies scheinbar ein neues Feature von C++ ist? Scheinbar bin ich nicht up to date?
Ein Hinweis ist, dass es in utility zu finden sei - also habe ich dies mit #include <utility> eingefügt. Ich bekomme jetzt keine Fehlermeldung für utility, also scheinbar besitze ich das (?), aber nach wie vor den Kompilerfehler.

Ich verwende den g++ Kompiler:

g++ -v
gcc version 4.4.5 (Debian 4.4.5-8)

Scheinbar muss ich nachrüsten?

Gruß,
Klaus.

[krümelkacker]

<utility> ist ein Standard-Header. Aber std::move gibt es erst ab C++2011. Deine Compilerversion unterstützt das glaub'ich auch. Musst du nur aktivieren per -std=c++0x

Zeig doch mal deine Definition von electron . Möglicherweise bringt std::move an der Stelle eh nichts. Aber das kommt drauf an, wie electron gestrickt ist.

Außerdem würdest du mit der Verwendung von std::move in Kauf nehmen, dass ein C++1998-Compiler deinen Quellcode nicht mehr übersetzen kann. Das sollte dir klar sein.

[Klaus82]

Hi,

krümelkacker schrieb:

<utility> ist ein Standard-Header. Aber std::move gibt es erst ab C++2011. Deine Compilerversion unterstützt das glaub'ich auch. Musst du nur aktivieren per -std=c++0x

also du meinst als Anhang für das Compiler-Kommando? Anstatt normal z.B:

g++ -Wall -pedantic -ansi -c foo.cpp

eben

g++ -Wall -pedantic -ansi -c -std=c++0x foo.cpp

krümelkacker schrieb:

Zeig doch mal deine Definition von electron . Möglicherweise bringt std::move an der Stelle eh nichts. Aber das kommt drauf an, wie electron gestrickt ist.

Eigentlich nichts wildes, ich sammle nur für jedes Elektron seine für mich physikalisch relevanten Eigenschaften:

#ifndef ELECTRON_H
#define ELECTRON_H

class electron{//
public:
	inline	electron(double e, double z, double x, double a);
	double angle;
	double energy;
	double z_coord;
	double x_coord;
};

electron::electron(double e,double z, double x, double a)
{
	energy = e;
	z_coord = z;
	x_coord = x;
	angle = a;
}

#endif

Gruß,
Klaus.

[SeppJ]

Klaus82 schrieb:

also du meinst als Anhang für das Compiler-Kommando? Anstatt normal z.B:

g++ -Wall -pedantic -ansi -c foo.cpp

eben

g++ -Wall -pedantic -ansi -c -std=c++0x foo.cpp

Ja und Nein. Was macht denn wohl das -ansi? Wenn du es nicht weißt, dann schlag es nach. Mach in der Programmierung niemals irgendetwas blind nach ohne genau zu verstehen, was und warum du es tust. Wenn du rausgefunden hast, was -ansi (und die anderen Optionen) genau machen, dann kommst du sicherlich drauf, wie es richtig heißt.

[krümelkacker]

Klaus82 schrieb:

krümelkacker schrieb:

Zeig doch mal deine Definition von electron . Möglicherweise bringt std::move an der Stelle eh nichts. Aber das kommt drauf an, wie electron gestrickt ist.

[c]

Eigentlich nichts wildes, ich sammle nur für jedes Elektron seine für mich physikalisch relevanten Eigenschaften:

#ifndef ELECTRON_H
#define ELECTRON_H

class electron{//
public:
	inline	electron(double e, double z, double x, double a);
	double angle;
	double energy;
	double z_coord;
	double x_coord;
};

electron::electron(double e,double z, double x, double a)
{
	energy = e;
	z_coord = z;
	x_coord = x;
	angle = a;
}
#endif

Ah ok. Wusstest du, dass wenn du Funktionen innerhalb einer Klasse definierst, dass die dann automatisch inline sind? Wusstest du, dass du im Konstruktor die Elemente direkt initialisieren kannst, statt diese Zuweisungen da zu machen? Wusstest du, dass struct und class sich nur dadurch unterscheiden, dass bei struct die Elemente per default public sind und bei class eben private? Ich verwende struct immer dann, wenn es keine privaten Elemente und keine zu schützende Invariante gibt, es sich also nur um eine Ansammlung von Daten handelt.

#ifndef ELECTRON_H
#define ELECTRON_H

struct electron
{
	double angle;
	double energy;
	double z_coord;
	double x_coord;

	electron(double e, double z, double x, double a)
	: angle(a), energy(e), z_coord(z), x_coord(x) {}
};

#endif

Jedenfalls bringt hier in diesem Fall std::move gar nichts. Kannst du also auch ruhigen Gewissens weglassen, ohne dass es irgendeinen Unterschied machen würde.

Ohne dir auf die Füße treten zu wollen: Wie lernst du eigentlich C++? Hast du dir ein schlaues Buch besorgt? (Würde ich nämlich empfehlen, da du dir damit Ärger sparen kannst)

[List-initialization]

...ich würde gar noch auf den C'tor verzichten und mittels braced-init-list initialisieren. Wenn unterstützt...

just
my2ct

[Klaus82]

SeppJ schrieb:

Was macht denn wohl das -ansi? Wenn du es nicht weißt, dann schlag es nach. Wenn du rausgefunden hast, was -ansi (und die anderen Optionen) genau machen, dann kommst du sicherlich drauf, wie es richtig heißt.

Aha,
laut dem gcc Manual (4.7.0) ist -ansi eine Kurzversion von -std=c90 für C nd -std=c++98 für C++. Und -std selbst betrifft macht eine Aussage über den language standard.

Was mich jetzt nur irritiert, dass ich in dem Manual kein -std=c++0x finde. Ich nehme an, dass ich auch nicht explizit nach x suchen soll, sondern das als Platzhalter für insgesamt die Jahre 00 bis 09 gedacht ist? Das aktuellste was sich in der Doku findet ist c++11 .

krümelkacker schrieb:

Wusstest du, dass wenn du Funktionen innerhalb einer Klasse definierst, dass die dann automatisch inline sind? Wusstest du, dass du im Konstruktor die Elemente direkt initialisieren kannst, statt diese Zuweisungen da zu machen? Wusstest du, dass struct und class sich nur dadurch unterscheiden, dass bei struct die Elemente per default public sind und bei class eben private? Ich verwende struct immer dann, wenn es keine privaten Elemente und keine zu schützende Invariante gibt, es sich also nur um eine Ansammlung von Daten
handelt.

Einiges davon kann ich sogar schon mit ja beantworten. Führt das jetzt zu im Sinne von 'ich kanns' oder im Sinne von 'wenn du es weißt, wieso programmierst du es dann nicht so'

krümelkacker schrieb:

Jedenfalls bringt hier in diesem Fall std::move gar nichts.

Okay.

krümelkacker schrieb:

Ohne dir auf die Füße treten zu wollen: Wie lernst du eigentlich C++? Hast du dir ein schlaues Buch besorgt? (Würde ich nämlich empfehlen, da du dir damit Ärger sparen kannst)

Na ja, prinzipiell learning by doing. Ich habe hier schnell gemerkt, dass die Aussage "C++ können" einem ziemlich hohen Anspruch genügen muss. Und ich selbst würde eben C++ gerne mehr verstehen, als lediglich ein Programm zusammenzustricken, dass 'irgendwie geht'.
Und so pendle ich von Baustelle zu Baustelle, einmal hier etwas ausprobieren, dann gesagt bekommen wie es 'richtig' geht, das wieder nachvollziehen, dann wieder neu ausprobieren ...

Und eigentlich ist das alles nur Nebensache, denn primär mache ich Physik und nicht Programmieren, da ist also von Cheffe kein Anspruch dahinter, dass es sauber programmiert ist, sondern die richtige Physik liefert.

Als Bücher habe ich den C++ Primer, C++ von A bis Z und Die C++-Standardbibliothek. Einführung und Nachschlagewerk

Gruß,
Klaus.

[SeppJ]

Klaus82 schrieb:

Was mich jetzt nur irritiert, dass ich in dem Manual kein -std=c++0x finde. Ich nehme an, dass ich auch nicht explizit nach x suchen soll, sondern das als Platzhalter für insgesamt die Jahre 00 bis 09 gedacht ist? Das aktuellste was sich in der Doku findet ist c++11 .

Das liegt da dran, dass du nicht den GCC 4.7 hast. Ab 4.7 heißt der Sprachstandard c++11. Bei älteren Versionen war noch nicht ganz klar, wie der Standard heißen würde, man nahm allgemein an, dass es vor 2010 werden würde, daher c++0x. (Uralter Witz: Das x ist hexadezimal, daher ist c++11 eigentlich c++0b und die Schreibweise c++0x war daher doch richtig)

Als Bücher habe ich den C++ Primer, C++ von A bis Z und Die C++-Standardbibliothek. Einführung und Nachschlagewerk

"C++ von A bis Z" ist Schrott, der dir eher schadet als hilft. Als Insektenklatsche benutzen, aber bloß nicht lesen!
Verwechsele nicht den (ausgezeichneten) C++ Primer C++ Primer | ISBN: 382732274X mit deinem C++ Primer Plus! Über letzteren kann ich nicht viel sagen. Wenn dein Programmierstil hier aktiv kritisiert wird, dann wird er vielleicht nicht so toll sein.
Das Standardbibliotheksbuch kenne ich nicht. Referenzen gibt es normalerweise online (http://www.cplusplus.com für C++98 und http://en.cppreference.com/w/ wenn es auch C++11 sein soll). Englisch muss man ohnehin können.

[krümelkacker]

Klaus82 schrieb:

Einiges davon kann ich sogar schon mit ja beantworten. Führt das jetzt zu im Sinne von 'ich kanns' oder im Sinne von 'wenn du es weißt, wieso programmierst du es dann nicht so'

Ich wollte nur sicher gehen, dass du weißt, dass man das auch anders aufschreiben kann. Kannst natürlich sagen "nee, so wie ich das schreibe, finde ich das schöner" und dagegen ist auch nix einzuwenden -- also in diesem Fall.

Klaus82 schrieb:

Na ja, prinzipiell learning by doing. Ich habe hier schnell gemerkt, dass die Aussage "C++ können" einem ziemlich hohen Anspruch genügen muss.

Naja, wenn du sagen würdest "ich kann Turmspringen", dann gehe ich davon aus, dass du auch Salti und nicht nur gerade runterspringen kannst. Und wenn du es einfach so probierst, ohne dich intensiver mit der Technik auseinanderzusetzen, dann machste halt auch mal eher 'nen Bauchklatscher. Tut dann natürlich weh. Ich bereue die Entscheidung nicht, mir ein schlaues C++ Buch besorgt zu haben. Drauflos hacken, ohne zu verstehen, was ich da eigentlich tue, wäre für mich total unbefriedigend. Ich will mir ja auch relativ sicher sein, dass ich keinen Murks baue ...

Klaus82 schrieb:

Und ich selbst würde eben C++ gerne mehr verstehen, als lediglich ein Programm zusammenzustricken, dass 'irgendwie geht'.

Das ist doch schomma 'ne super Einstellung.

Klaus82 schrieb:

Und so pendle ich von Baustelle zu Baustelle, einmal hier etwas ausprobieren, dann gesagt bekommen wie es 'richtig' geht, das wieder nachvollziehen, dann wieder neu ausprobieren ...

Na, wenn es für dich funktioniert.

Klaus82 schrieb:

Und eigentlich ist das alles nur Nebensache, denn primär mache ich Physik und nicht Programmieren, da ist also von Cheffe kein Anspruch dahinter, dass es sauber programmiert ist, sondern die richtige Physik liefert.

Hmmm ... ich denke mal, das eine bedingt ein bisschen das andere.

Klaus82 schrieb:

Die C++-Standardbibliothek. Einführung und Nachschlagewerk

Nicht übel. Das ist doch eine super Quelle, um nachzuschauen, ob es sowas wie <utility> gibt.

[Klaus82]

SeppJ schrieb:

Verwechsele nicht den (ausgezeichneten) C++ Primer mit deinem C++ Primer Plus! Über letzteren kann ich nicht viel sagen.

Ach verdammt, verwechselt. Von diesem C++ Primer hatte ich schon viel gehört und habe mir den C++ Primer Plus zugelegt (nachdem ich das andere Buch schon hatte und es scheinbar 'Schrott' ist).

Jetzt wähnte ich mich auf der sicheren Seite; dann muss ich mich doch nochmal umsehen.

Hier stand Blödsinn

Gruß,
Klaus.

[Klaus82]

So,
heute kam der C++ Primer. Ich bin gespannt wie ein Flitzebogen. Fragen werden folgen.

Viele Grüße,

Klaus.

[Klaus82]

So ihr Lieben,

314159265358979 schrieb:

1. Iterator auf das letzte Element holen.
2. Wenn ein Element gelöscht werden soll, Element mit *last tauschen.
3. Last erniedrigen
4. Remove & Erase Idiom

ausgehend davon habe ich jetzt ein kleines Programm zusammengestrickt, was die Anforderungen in abgewandelter Form erfüllt.

1. Das Programm prüft, ob ein Element gelöscht werden soll.
2. Das Programm vertauscht dieses Element mit dem letzten des vectors
3. Die Zählung bis und der Iterator auf das letzte Element werden erniedrigt.
4. Das geschieht jetzt dadurch, dass einfach vom Iterator bis zum Ende des Vectors alles Elemente gelöscht werden. Funktioniert, scheint aber nicht ganz dem Prinzip des erase remove idioms zu entsprechen.

seldon schrieb:

Es wäre besser, einen Zufallszahlengenerator zu benutzen, der gleich Integer ausspuckt und ihn durch std::uniform_int_distribution zu pressen.

Ich hatte überlegt den Zufallsgenerator integers von 1 bis vector<T>.size() erstellen zu lassen, nur scheitert es dann am dem std::uniform_int_distribution .
Das scheint erst wieder mit C++11 zu gehen und zumindest hier auf der Arbeit mit Lenny scheint es nicht zu laufen.
Aber wir stellen jetzt ja auf Squeeze um.

Gruß,
Klaus.

[seldon]

Dann nimm's halt aus Boost. Daher kommt der Kram ja ursprünglich.

[krümelkacker]

Klaus82 schrieb:

ein kleines Programm zusammengestrickt, was die Anforderungen in abgewandelter Form erfüllt.

Das ist leider Murks.

Fehler:
- Du überspringst ggf ein Element, ohne es überprüft zu haben.
- Du dekrementierst einen Iterator, der ggf schon auf das erste Element zeigt.

Komisch:
- swap bringt dir in deinem Fall gegenüber einer einfachen Zuweisung nichts.
- Wozu inkludierst du <iterator>?

Schade. Du hast da mit dem Überspringen übrigens einen Fehler gemacht, vor dem ich auf Seite 4 schon am 23.5. um 10:57 Uhr gewarnt habe.

[ananas]

Ich möchte auch nocheinmal den Hinweis von Seite 4 von SeppJ und Seldon zu remove_if erneuern. Das macht genau das, was du versuchst, nur ohne Fehler.

Damit kannst du deine gesamte handgestrickte Schleife in Zeile 43 bis 54 durch einen Einzeiler ersetzen.

[Klaus82]

krümelkacker schrieb:

Fehler:
- Du überspringst ggf ein Element, ohne es überprüft zu haben.

Oh ja! Ich war so auf das move fixiert, dass wir doch nicht benötigen, dass ich dachte es sei jetzt überholt und ich könnte getrost i erhöhen.
Aber ich muss ja noch das Element prüfen, mit dem ich getauscht habe und dazu darf ich erstmal nicht erhöhen!

krümelkacker schrieb:

- swap bringt dir in deinem Fall gegenüber einer einfachen Zuweisung nichts.

Das verstehe ich nicht. Was ist in diesem Zusammenhang eine einfache Zuweisung ?

Schlußendlich muss ich sagen, dass ich nicht mal mehr verstehe, warum wir swappen oder moven [1] wollten. Es reicht doch wirklich folgendes:

iter = v.begin();

for(unsigned int i = 0; i < num_ints;)
{
  if(delete_element(v[i]))
  {
    l.push_back(v[i]);
    v.erase(iter+i);
    --num_ints;
  }
  else
    // do something else with the element v[i]
    ++i;
}

Klappe zu, Affe tot.

Wobei ich hier nochmal konkret nachfragen muss, wie sich das mit dem Indexzugriff verhält. Wenn ich über einen Iterator zugreife, so steht ja zu erase, dass ein Iterator zurückgegeben wird, der auf das folgende Element zeigt.
Wenn ich jetzt aber ein Element lösche, dann müssen die anderen alle 'nach oben nachrücken', oder? D.h. ich habe eine Indexverschiebung $i\longrightarrow i+1$
Wenn ich also i nicht bei jedem Schleifendurchlauf erhöhe, so wird i dadurch 'erhöht', dass ein Element gelöscht wird. Also das Element i+1 ist jetzt i und (ich erhöhe i nicht) so prüfe ich eben das nächste Element.

Gruß,
Klaus.

[1] Immer diese denglischen Begriffsbildungen.

[krümelkacker]

Klaus82 schrieb:

krümelkacker schrieb:

- swap bringt dir in deinem Fall gegenüber einer einfachen Zuweisung nichts.

Das verstehe ich nicht. Was ist in diesem Zusammenhang eine einfache Zuweisung ?

int a = 23;
int b = 42;
//swap(a,b); // <- Vertauschung
a = b;       // <- Zuweisung

Da du b quasi nicht mehr brauchst, reicht die Zuweisung. In beiden Fällen bekommt a den Wert, den b hatte.

Klaus82 schrieb:

Schlußendlich muss ich sagen, dass ich nicht mal mehr verstehe, warum wir swappen oder moven [1] wollten. Es reicht doch wirklich folgendes:

iter = v.begin();

for(unsigned int i = 0; i < num_ints;)
{
  if(delete_element(v[i]))
  {
    l.push_back(v[i]);
    v.erase(iter+i);
    --num_ints;
  }
  else
    // do something else with the element v[i]
    ++i;
}

Klappe zu, Affe tot.

Klaus82 schrieb:

Wenn ich jetzt aber ein Element lösche, dann müssen die anderen alle 'nach oben nachrücken', oder?

Ja sicher. Deswegen ist das Löschen eines einzelnen Elements aus der Mitte auch eine doofe Idee und deswegen hast du ja auch Tipps bekommen, wie du es besser machen könntest!

[Klaus82]

Hi,

krümelkacker schrieb:

Klaus82 schrieb:

Wenn ich jetzt aber ein Element lösche, dann müssen die anderen alle 'nach oben nachrücken', oder?

Ja sicher. Deswegen ist das Löschen eines einzelnen Elements aus der Mitte auch eine doofe Idee und deswegen hast du ja auch Tipps bekommen, wie du es besser machen könntest!

Ich glaube das bringt bei mir zur Zeit noch nichts, da ich einfach zu wenig Ahnung von STL habe.

Ich kann z.B. überhaupt nicht abschätzen, wieviel Aufwand etwas darstellt. Wenn z.B. löschen in der Mitte eines Vektors eine doofe Idee ist, wieso ist es dann weniger umständlich das Element ans Ende zu verschieben und dann alle Elemente gesammelt am Ende zu löschen.
Sicher, das Löschen am Ende erscheint mir kompakter, aber allein das Verschieben ist doch auch Aufwand.

Aus dem Grund muss ich erstmal viel lesen gehen ... hab ja jetzt den C++ Primer und laut Vorwort, wird auch direkt auf die STL eingegangen. Schließlich sei es unsinnig alles primitiv zu programmieren, nur um dann am Ende zu sagen: Wir müssen das Rad nicht neu erfinden, sondern uns lediglich der STL bedienen.

Vielleicht sehe ich dann klarer.

Momentan habe ich nur das Gefühl ich drehe mich im Kreis.

Auf jeden Fall danke an alle, die so lange durchgehalten haben.

Viele Grüße,
Klaus.

[krümelkacker]

Klaus82 schrieb:

Ich kann z.B. überhaupt nicht abschätzen, wieviel Aufwand etwas darstellt. Wenn z.B. löschen in der Mitte eines Vektors eine doofe Idee ist, wieso ist es dann weniger umständlich das Element ans Ende zu verschieben und dann alle Elemente gesammelt am Ende zu löschen.

Ans Ende schieben sollst du sie gar nicht. Das war nur eine Idee vom Pi mit dem swap. Sagte ich ja, dass das unnötig ist. Das Ding ist, wenn du erase für ein einziges Element in der Mitte durchführst, müssen die dahinter liegenden nachrücken und das kostet. Da die Reihenfolge im Vektor bei dir aber gar nicht wichtig zu sein scheint, kannst du auch einfach das letzte Element an die Stelle kopieren, die du sonst gelöscht hättest. Also, statt

soll weg
      |
      V
+---+---+---+---+---+
| H | e | l | l | o |
+---+---+---+---+---+
         /   /   /
        /   /   /
       /   /   /
+---+---+---+---+
| H | l | l | o |
+---+---+---+---+

machst du einfach

|<- gültig bis
+---+---+---+---+---+
| H | e | l | l | o |
+---+---+---+---+---+
                  |
      +-----------+
      |
      V         |<- gültig bis
+---+---+---+---+---+
| H | o | l | l | o |
+---+---+---+---+---+

Hinterher dann die Dinger am Ende, die eh nicht mehr gültig sind, mit einem Rutsch entfernen und fertig ist die Laube.