Zeile aus Datei in vector<string> schreiben



  • Hallo,
    ich möchte aus einer Datei jede Zeile in ein Element (String) eines Vectors schreiben.
    Mein Code sieht so aus: ("file" ist der Dateiname)

    ...
    while (getline(file, line))
    {
        vector<string> zeile;
        string line;
        unsigned int idx = 0;
        zeile[idx] = line;
        idx++;
    }
    ...
    

    Wenn ich das Programm starte stürzt es ab. Wo liegt mein Fehler?



  • Dein vector ist leer. Mit dem operator[] greifst du auf Elemente zu, die nicht existieren. Benutze push_back um Elemente hinzuzufügen.
    http://www.cplusplus.com/reference/stl/vector/push_back/



  • Und in dem Fall würde ich eher zu std::list oder zu std::deque greifen.



  • EOutOfResources schrieb:

    Und in dem Fall würde ich eher zu std::list oder zu std::deque greifen.

    Wieso das denn?



  • Danke für die schnellen Antworten. Funktioniert super 😃



  • brotbernd schrieb:

    Wieso das denn?

    Weil std::vector bei einer Vergrösserung alles kopieren muss, die beiden Anderen erstellen nur einen neuen Node und verknüpfen dann.


  • Mod

    EOutOfResources schrieb:

    brotbernd schrieb:

    Wieso das denn?

    Weil std::vector bei einer Vergrösserung alles kopieren muss, die beiden Anderen erstellen nur einen neuen Node und verknüpfen dann.

    Der vector hängt bei allen anderen Zugriffen die list und die deque weit ab und beim hinzufügen ist er nur ein genz kleines bisschen langsamer (möglicherweise sogar schneller als list). Man sollte schon deutlich bessere Gründe haben, um von vector abzuraten.



  • ixaM95 schrieb:

    Danke für die schnellen Antworten. Funktioniert super 😃

    Bist Du sicher?
    Ich hätte vermutet, dass in Deinem Code oben der Vektor bei jedem Schleifendurchlauf neu erstellt und zerstört wird, ebenso wie die Variable idx. Weiters hätte ich angenommen, dass die Variable line in der Schleife immer leer ist, weil Du ihr nix zuweist, und weil sie eine andere zu sein scheint, als die, die getline als Parameter bekommt ...

    Aber wenn jetzt alles funktioniert, dann muss ich meine Kenntnisse wohl noch mal auffrischen gehen ...



  • SeppJ schrieb:

    beim hinzufügen ist er nur ein genz kleines bisschen langsamer (möglicherweise sogar schneller als list)

    Wusste ich nicht! Danke 👍



  • EOutOfResources schrieb:

    brotbernd schrieb:

    Wieso das denn?

    Weil std::vector bei einer Vergrösserung alles kopieren muss, die beiden Anderen erstellen nur einen neuen Node und verknüpfen dann.

    Dass der Vector beim Iterieren deutlich schneller ist, ist wohl klar und wurde schon gesagt. Wir lesen hier eine Datei ein, das ist eh langsam im Vergleich zu allen Vorgängen im Speicher. Der Container sollte also passend zu den anschließenden Aufgaben gewählt werden. Wenn wir nicht ständig irgendwas in der Mitte einfügen/löschen wollen ohne die Reihenfolge zu ändern brauchen wir keine Liste. Sie ist in allen anderen Bereichen größer und langsamer. Ja auch beim Befüllen, denn das "Erstellen nur einen neuen Node und verknüpfen dann.." gibt es auch nicht umsonst. Jedes Einfügen eines neuen Elements in einer std::list bedeutet eine zusätzliche dynamische Speicheranforderung. Ich habe das gerade mal gemessen:

    using namespace std;
        typedef list<string> Container;
    
        ifstream file("1.dat");
        string line;
        Container lines;
        {
            HrTimer timer;
            while (getline(file, line))
                lines.push_back(line);
        }
        size_t size = 0;
        {
            HrTimer timer;
            size = std::accumulate(lines.begin(), lines.end(), 0,
                [](size_t n, const string& s) -> size_t {return n + s.size();});
        }
        cout << size << endl;
    

    Bei einer 3mb Text Datei:

    std::vector
    68.684 ms
    0.0725053 ms
    2888293
    
    std::list
    75.9199 ms
    1.62863 ms
    2888293
    

    Sowohl Einlesen als auch Iterieren(!) ist schneller.



  • EOutOfResources schrieb:

    brotbernd schrieb:

    Wieso das denn?

    Weil std::vector bei einer Vergrösserung alles kopieren muss, die beiden Anderen erstellen nur einen neuen Node und verknüpfen dann.

    Annahme: vector verdoppelt seine größe wenn nötig.
    Schluss: Pro push_back muß maximal zweimal kopiert werden. Dabei wird nur ld(n) mal vergrößert.

    Das riecht auf alle Fälle schnell. list muß pro Knozen einmal new aufrufen. Wie schnell ist das heute? 100 Takte? list ist für andere Sachen da. vector ist schnell. Mit C++0x erst recht.



  • Naja, ganz so einfach ist es nun auch nicht. Wenn die Kopie des verwalteten Datentyps teuer ist, schlägt die Relokation in std::vector schon ins Gewicht - fahr mal einen Test mit

    struct A {
      A() { }
      A(A const &) { usleep(1); }
      A &operator=(A const &) { usleep(1); }
    
      ~A() { }
    };
    

    ...und schon braucht std::vector doppelt so lange wie sowohl list als auch deque. Aber damit nicht genug - selbst Folgendes reicht schon aus, um vector hinter deque verschwinden zu lassen:

    #include <cstddef>
    #include <cstdlib>
    #include <ctime>
    #include <deque>
    #include <iostream>
    #include <list>
    #include <vector>
    
    std::size_t const rounds = 100000000;
    
    struct A {
      A() { }
      A(A const &) { std::rand(); } // <-- wirklich nicht teuer!
      A &operator=(A const &) { std::rand(); }
    
      ~A() { }
    };
    
    int main() {
      std::vector<A> vec;
      std::list  <A> ls;
      std::deque <A> deq;
    
      std::clock_t bench[4];
    
      std::srand(std::time(0));
    
      bench[0] = std::clock();
    
      for(std::size_t i = 0; i < rounds; ++i) {
        vec.push_back(A());
      }
    
      bench[1] = std::clock();
    
      for(std::size_t i = 0; i < rounds; ++i) {
        ls.push_back(A());
      }
    
      bench[2] = std::clock();
    
      for(std::size_t i = 0; i < rounds; ++i) {
        deq.push_back(A());
      }
    
      bench[3] = std::clock();
    
      std::cout << "vector: " << static_cast<double>(bench[1] - bench[0]) / CLOCKS_PER_SEC << '\n'
                << "list:   " << static_cast<double>(bench[2] - bench[1]) / CLOCKS_PER_SEC << '\n'
                << "deque:  " << static_cast<double>(bench[3] - bench[2]) / CLOCKS_PER_SEC << '\n';
    }
    

    Ergebnis:

    vector: 2.66
    list:   6.67
    deque:  1.23
    

    Verwendet wurde gcc 4.5.2 mit -O2.

    Die Einstellung "Ach ja, ein bisschen Kopiererei, was macht das schon" halte ich für mehr als blauäugig. std::vector ist gut, wenn man vorher weiß, wie viel Daten man etwa kriegt. Kann man das nicht abschätzen, ist std::deque im Zweifel die bessere Wahl.



  • Kopierkosten werden in der Zukunft keine große Rolle mehr spielen, weil man diese in fast allen Fällen durch Moven eliminieren kann.
    Desweiteren nimmt das Hinzufügen der Daten meistens einen kleinen Zeitanteil gegenüber der Verarbeitung der Daten ein. Und bei Zugriff/Iteration ist vector wieder schneller als deque , so dass dort die erhöhte Zeit beim Einfügen wieder herausgeholt werden kann.

    Natürlich ist vector nicht in allen Situationen ideal, aber man sollte eigentlich immer zuerst vector nehmen und nur dann auf list oder deque wechseln, wenn diese erwiesenermaßen (Messung) schneller sind.



  • ipsec schrieb:

    Kopierkosten werden in der Zukunft keine große Rolle mehr spielen, weil man diese in fast allen Fällen durch Moven eliminieren kann.

    Diese "fast alle Fälle" lassen sich exakt reduzieren zu "wenn die Klassen einen Move Konstruktor oder Zuweisungsoperator haben, der günstiger als der Kopierkonstruktor ist". Das ist bei Containern wie std::string natürlich der Fall, aber bei sehr vielen anderen Klassen eben auch nicht.
    Abschließend kann man vielleicht auch nochmal erwähnen "premature optimization is the root of all evil". Wenn wir keine besonderen Anforderungen haben, nehmen wir das einfachste was verfügbar ist, das ist ein vector. Wenn wir irgendwann merken (und messen) dass der vector hier performancekritisch ist, überlegen wir uns etwas anderes.



  • Dass ein Move-Konstruktor in allen Fällen schneller sein wird als ein Aufruf von rand(), wage ich mal zu bezweifeln, und der Zugriff auf eine deque im Vergleich zu vector ist nicht dermaßen teuer, dass im Falle eines mittelmäßig komplexen Kopier- bzw. Move-Konstruktors davon auszugehen wäre, dass der Zeitnachteil auf jeden Fall wieder herausgeholt werde. Auch werden die Kosten der Umlegung durch Move-Konstruktoren nicht eliminiert, sondern allenfalls gesenkt. Hat man einen teuren Kopierkonstruktor und einen etwas weniger teuren Move-Konstruktor, bleibt std::vector trotzdem auf den Kosten des Move-Konstruktors sitzen. Wie sich all das in der Praxis auswirken wird, kann ich zumindest heute noch nicht sagen.

    Ich halte die Aussage "man sollte eigentlich immer zuerst vector nehmen und nur dann auf list oder deque wechseln, wenn diese erwiesenermaßen (Messung) schneller sind" nicht für zielführend. Seine Containerwahl sollte man nach Sachlage entscheiden; Kernfragen wie diese quasi als Dekoration zu betrachten, ist aus meiner Sicht unsinnig.

    Noch etwas zu "premature optimization is the root of all evil": Das ist ein Knuth-Zitat aus einem Artikel von 1974, betitelt mit "Structured Programming with go to Statements" (Seite 8, rechte Spalte). Lasst den Titel mal einen Moment sacken. Mit Kontext liest sich die Stelle wie folgt:

    Donald E. Knuth schrieb:

    There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified.

    Wie gesagt: Es geht in diesem Artikel um die Benutzung von goto aus Performancegründen. Die Aussage hier ist: Optimierung, die die Handhabung des Codes erschwert, d.h. ihn unübersichtlicher macht, sollte nur dort passieren, wo sie tatsächlich etwas bringt. Auch denkt Knuth generell an sehr viel kleinere Optimierungen - lest euch den Artikel mal durch. Dass Knuth die Auswahl einer Containment-Strategie unter "Kleinkram, um den man sich keine Sorgen machen sollte" eingeordnet hätte, ist nicht plausibel. Mit Sicherheit hat er nicht sagen wollen, dass man sich beim Entwurf seines Programms keine Gedanken um Performance machen sollte.

    Und natürlich ist im Zeitalter optimierender Compiler vieles dessen, was Knuth in diesem Artikel schreibt, inzwischen eh hinfällig.


Anmelden zum Antworten