alphabetisches Sortieren von Wörtern

kaenzign

Nathan der Weise? schrieb:

Nathan schrieb:

Natürlich ist reserve() und push_back() das bester, aber nur push_back() ist ineffizienter als resize() und operator [].

Ah, interessant.

Hast du dazu auch eine Begründung?

Also wenn ich das richtig verstanden habe wird bei push_back() ja immer automatisch der vector vergörssert, bzw. es wird eine "resize-Funktion ausgeführt.
Klingt für mich plausibel, dass es weniger aufwendig ist, wenn man ganz am Anfang nur einmal resize aufruft und die benötigte Grösse definiert. Oder?

Wie dem auch sei, der Tipp mit dem Resize funktioniert, und auf diese Weise werden,wie es aussieht, auch die backslash-characters ignoriert...

liste.resize(8);
for(unsigned int i = 0; i!=lines; i++) //einlesen?????
{
    fin >> liste[i];
}

Damit werden alle acht Zahlen am schluss ausgegeben. (und nicht nur 4 wie bei push_back)
Bleibt also nur noch die Frage, wie ich die backslashs mit der push_back()-Methode ignorieren kann.

Nathan schrieb:

Sage ich.
Natürlich ist reserve() und push_back() das bester[sic!], aber nur push_back() ist ineffizienter als resize() und operator [].

Hier eine Klasse zum testen:

struct X {
  X(){sleep(1);}
};

Nathan

OK, ich gebe zu ich habe ein "unter Umständen" vergessen.
Wenn wegen push_back() neuer Speicher angefordert werden muss, ist das ineffizienter als wenn die Kapazität und die Größe nicht verändert werden muss.

Edit: Ja, ok, bei deiner Klasse ist das vielleicht so, aber wir reden hier von Zahlen nicht von Objekten die komplexe Initialisierungsvorgänge benötigen.
Du musst meine Beiträge auch in einem gewissen Kontext sehen. Und in seiner Situation (von der ich eigentlich auch geredet habe) ist das so.

Edit 2 @TE: Warum hast du den Backslashs in deinem File?

kaenzign schrieb:

Also wenn ich das richtig verstanden habe wird bei push_back() ja immer automatisch der vector vergörssert, bzw. es wird eine "resize-Funktion ausgeführt.
Klingt für mich plausibel, dass es weniger aufwendig ist, wenn man ganz am Anfang nur einmal resize aufruft und die benötigte Grösse definiert. Oder?

Der vector ist schlau und vergrössert sich nicht nur um 1 Element sondern vervielfacht seine Grösse.

Das führt dazu, dass jeder Aufruf von push_back durchschnittlich in konstanter Zeit abläuft, d.h. normalerweise braucht man sich da nicht drum zu kümmern. Mit reserve() wird das ganze noch etwas schneller.

Nathan schrieb:

Du musst meine Beiträge auch in einem gewissen Kontext sehen. Und in seiner Situation (von der ich eigentlich auch geredet habe) ist das so.

Nicht ganz. resize() vergrössert den Vektor und setzt erst einmal alle Elemente auf 0. Dann werden die noch einmal eingelesen und richtig initialisiert. mit push_back() werden die gleich auf den echten Wert gesetzt, dafür muss die Grösse verändert werden.

Ist insgesamt ein Nullsummenspiel (gerade bei ints) und push_back ist um einiges sauberer.

Nathan

Die Frage ist nur: Ohne reserve(), was ist da besser? Und seit wann werden die Werte bei ints ohne weiteres Argument auf 0 gesetzt?

Nathan schrieb:

Und seit wann werden die Werte bei ints ohne weiteres Argument auf 0 gesetzt?

Seit es vector gibt Ist übrigens ein weiterer Vorteil von vector gegenüber einem rohen Array.

Ohne reserve() ist resize() in diesem Fall möglicherweise wirklich schneller, aber trotzdem sollte man resize() nicht empfehlen, wenn es doch auch reserve() gibt.

Nathan

Oh ja, stimmt ja.
Wusste ich gar nicht... Naja, habe es bisher noch nie wirklich gebraucht.^^

Ohne reserve() ist resize() in diesem Fall möglicherweise wirklich schneller

Davon rede ich ja die ganze Zeit.

Nathan schrieb:

Ohne reserve() ist resize() in diesem Fall möglicherweise wirklich schneller

Davon rede ich ja die ganze Zeit.

Ja, aber wayne?
Wenn man kurzen und schönen Code will, nimmt man push_back und wenn man schönen und schnellen Code will nimmt man reserve+push_back. resize hat da gar nichts zu suchen.

Nathan

OK, du hast Recht: TE, verwende reserve() und push_back(), sofern dein Backslash-Problem gelöst ist.
Zufrieden?
Und was hat Sone damit zu tun?

kaenzign

Nathan schrieb:

OK, du hast Recht: TE, verwende reserve() und push_back(), sofern dein Backslash-Problem gelöst ist.
Zufrieden?
Und was hat Sone damit zu tun?

Glaube du hast mich falsch verstanden
Genau dann wenn ich push_back() verwende, gibt mir die Funktion am schluss nur die Hälfte der Liste sortiert aus. Reserve() und Resize() ändern daran irgendwie nichts. Wie gesagt, meine vermutung ist, dass es ein Zusammenhang mit '\n' hat, mir ist jedoch nicht klar, wie ich das Problem umgehen kann.

Nathan

Der Fehler ist seltsam...
Übrigens geht das Bestimmen der Größe auch einfacher:

is.seekg (0, ios::end);
length = is.tellg();
is.seekg (0, ios::beg);

Mit seekg bestimmst du die Leseposition im File, abhängig von der Position, die im zweiten Parameter angegeben wird.

kaenzign

@Nathan

Aber wenn du tellg() auf den Schluss des Files anwendest, gibt er dir die Anzahl Zeichen und nicht die anzahl Zeilen zürich, oder?

Ich habe jetzt mal aus spass die Anzahl der einzulesenden Zahlen im .txt-file geändert. Komischerweise funktioniert die push_back() methode jetzt gar nicht mehr, obwohl ich nichts am Code veränderd habe.
Die Konsole gibt nun nach dem Start des Programms folgendes aus:

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

Process returned 3 (0x3)   execution time : 4.672 s
Press any key to continue.

Die >> Methode mit vorherigem resize() funktioniert aber nach wie vor...
Hier noch mal beides als Vergleich:

for(unsigned int i = 0; i!=lines; i++)
{
    int tmp;
    fin >> tmp;
    liste.push_back(tmp);
    i++;
}

liste.resize(lines);
for(unsigned int i = 0; i!=lines; i++) 
{
    fin >> liste[i];
}

Sollten doch eigentlich letztendlich genau dasselbe tun... Woran kann das liegen?

PS: Zur Erinnerung, der gesamte Code ist auf Seite 2 geposted.

for(unsigned int i = 0; i!=lines; i++)
{
    int tmp;
    fin >> tmp;
    liste.push_back(tmp);
    i++;
}

Schau dir mal ganz genau an, was da mit i passiert.

kaenzign

bist_du_sone? schrieb:

Schau dir mal ganz genau an, was da mit i passiert.

Hmm worauf willst du hinaus. So wie ich das sehe wird die Schleife "lines"-mal durchlaufen bzw. push_back() wird "lines"-mal ausgeführt, und es sollen "lines" Zahlen eingelesen werden, das ist doch in Ordnung?

Nathan

Nein, denn i wird zweimal inkrementiert.

kaenzign

Unglaublich wie ich das übersehen konnte.
Jetzt funktioniert es natürlich, danke dir.

kaenzign schrieb:

Jetzt funktioniert es natürlich

Toll, jetzt kann man nach Alternativen suchen:
1)

int main()
{
  std::ifstream in("data.txt");
  std::vector<std::string> lines;
  for (std::string s; getline(in, s);)
    lines.push_back(s);
  std::sort(lines.begin(), lines.end());
  std::copy(lines.begin(), lines.end(),
            std::ostream_iterator<std::string>(std::cout, "\n"));
}

struct line : std::string {};
std::istream& operator>>(std::istream& in, line& l) { return getline(in, l); }

int main()
{
  std::ifstream in("data.txt");
  std::vector<std::string> lines(std::istream_iterator<line>(in),
                                 std::istream_iterator<line>{});
  std::sort(lines.begin(), lines.end());
  std::copy(lines.begin(), lines.end(),
            std::ostream_iterator<std::string>(std::cout, "\n"));
}

Nathan

zu 1:
Besser wäre es allerdings die Größe zu bestimmen und dann mit resize() und operator[]/at() zu arbeitn. :p

Nathan schrieb:

zu 1:
Besser wäre es allerdings die Größe zu bestimmen und dann mit resize() und operator[]/at() zu arbeitn. :p

Würde mich echt wundern, ob das schneller ist. Misst du das mal?

volkard

Nathan schrieb:

zu 1:
Besser wäre es allerdings die Größe zu bestimmen und dann mit resize() und operator[]/at() zu arbeitn. :p

??

Die Kosten des Wachsens beim push_back werden immer total überschätzt.
Nehmen wir an, daß der vector die Größe des internen Arrays immer verdoppelt, wenn das neue Element nicht reinpaßt. Und nehmen wir an, es werden 1Mio Werte eingetragen.
Startgröße mal 16 nehmen, ist aber recht egal.
Beim 17-te push_back müssen 16 Zahlen geschrieben werden.
Beim 33-ten push_back müssen 32 Zahlen geschrieben werden.
...
Beim 524289-ten push_back müssen 524288 Zahlen geschrieben werden.
Macht zusammen 1048576 Schreibungen. Also bloß eine Schreibungen pro push_back!
Und wenn man Pech hat, bis zu zwei. Aber mehr dann auch nicht. Natürlich macht man reserve, wenn es spürbar was bringt. Aber für so Kinkerlitzchen mache ich es regelmäßig nicht. Erst, wenn der Hauch einen Schimmers einen Verdachts darauf besteht, daß es am Ende spürbar sein könnte. Vorher schmiere ich mir damit meinen Code nicht voll. Und schon gar nicht zwanghaft.

Sobald mit den Daten irgendwas gerechnet wird, überwiegen andere Kosten.

Beim resize hätte man eine nutzlose Schreibung pro push_back, was durchaus vergleichbar mit 1-2 Schreibungen durch push_back ohne reserve ist.