Benutzt eigentlich irgendwer std::list?



  • Mal so gefragt. Ich sehe die std::list fast nirgendwo und auch ich verwende irgendwie immer den std::vector, auch wenn ich gar keinen wahlfreien Zugriff brauche sondern stets nur von A bis Z iteriere. Trotzdem nehme ich irgendwie nie die Liste 🙄



  • Wenn Iteratoren gĂŒltig bleiben mĂŒssen.



  • Ich benutze std::list nie.



  • Noch nie verwendet.



  • aktuell nicht, aber ich könnte mir durchaus Situationen vorstellen, in denen eine list dem vector ĂŒberlegen ist.



  • Wenn du was innerhalb des Containers was raus oder rein nehmen mußt, ist doch list ggĂŒ. vector im Vorteil.



  • Artchi schrieb:

    Wenn du was innerhalb des Containers was raus oder rein nehmen mußt, ist doch list ggĂŒ. vector im Vorteil.

    Theoretisch ja. Praktisch gilt das aber nur, wenn der Zugriff am Anfang stattfindet, HinzufĂŒgen/Löschen ans Ende eines vectors ist unkritisch (size != capacity). Bei Manipulationen in der Mitte muss das Element bei einer list auch erstmal gefunden werden, sofern du keinen iterator hast.



  • Artchi schrieb:

    Wenn du was innerhalb des Containers was raus oder rein nehmen mußt, ist doch list ggĂŒ. vector im Vorteil.

    Dann hab ich vielleicht intrusive doppelt verkettet Listen/Ringe.

    Wenn Objekte umhergeschaukelt werden mĂŒssen und viel zu teuer zum Kopieren sind und ich keinen vector<Ding*> haben mag vielleicht auch. Oder std::forward_list.

    Und std::queue nicht vergessen.



  • daddy_felix schrieb:

    Artchi schrieb:

    Wenn du was innerhalb des Containers was raus oder rein nehmen mußt, ist doch list ggĂŒ. vector im Vorteil.

    Theoretisch ja. Praktisch gilt das aber nur, wenn der Zugriff am Anfang stattfindet,

    Praktisch ist selbst das bei einem vector erstaunlich "billig" gegenĂŒber einer list: der vector benutzt einen zusammenhĂ€ngenden Speicherbereich, der im Cache liegt. Die Daten sind darin schon lĂ€ngst verschoben, wenn eine Liste endlich den verwendeten Speicherbereich geladen hat.

    Bjarne Stroustrup hat dazu mal Messungen gezeigt (goingnative?). Seine Empfehlung: Standard immer Vector, es sei denn, man hat den Vorteil einer anderen Struktur gemessen.



  • std::list benutze ich, wenn ich Objekte an festen Positionen brauche, weil pointer darauf existieren und tausche das beim Optimieren durch eine effiziente Struktur wie boost::container::stable_vector (wobei der beim itererieren langsamer ist als list) aus.



  • Marthog schrieb:

    std::list benutze ich, wenn ich Objekte an festen Positionen brauche, weil pointer darauf existieren und tausche das beim Optimieren durch eine effiziente Struktur wie boost::container::stable_vector (wobei der beim itererieren langsamer ist als list) aus.

    Das versteh ich nicht.
    Warum allozierst du die Objekte dann nicht auf dem heap?
    Also e.g. einen vector auf unique_ptr oder shared_ptr.

    Bei einem vector auf pointern verÀndert sich doch die Adresse der Heap Objekte nicht.

    Da soweit ich mich erinnere alle STL-Container Copy-Operationen beim wachsen verwenden sollte man eigentlich in 99% aller FĂ€lle das Objekt in einem Pointer verpacken.



  • vector of pointer schrieb:

    Marthog schrieb:

    std::list benutze ich, wenn ich Objekte an festen Positionen brauche, weil pointer darauf existieren und tausche das beim Optimieren durch eine effiziente Struktur wie boost::container::stable_vector (wobei der beim itererieren langsamer ist als list) aus.

    Das versteh ich nicht.
    Warum allozierst du die Objekte dann nicht auf dem heap?
    Also e.g. einen vector auf unique_ptr oder shared_ptr.

    Bei einem vector auf pointern verÀndert sich doch die Adresse der Heap Objekte nicht.

    Da soweit ich mich erinnere alle STL-Container Copy-Operationen beim wachsen verwenden sollte man eigentlich in 99% aller FĂ€lle das Objekt in einem Pointer verpacken.

    Ist aber doof wegen Cache und so.



  • std::list ist noch viel dooferer.



  • vector of pointer schrieb:

    Warum allozierst du die Objekte dann nicht auf dem heap?
    Also e.g. einen vector auf unique_ptr oder shared_ptr.

    Bei einem vector auf pointern verÀndert sich doch die Adresse der Heap Objekte nicht.

    Das macht Geschwindigkeitsmaessig glaube ich auch keinen Unterschied, weil auch jedes Objekt abgefruehstueckt wird und auch so wild auf dem Heap herumgesprungen wird. Auf der anderen Seite macht es aber viele Operationen unnoetig unuebersichtlich, weil man immer Funktoren braucht, die erstmal die pointer dereferenzieren und nicht einfach find verwenden kann.
    Ausserdem kann ich bei einer list auch ganz einfach einen anderen Container verwenden, wenn ich feststelle, dass die festen Addressen nicht mehr gebraucht werden.

    vector of pointer schrieb:

    Da soweit ich mich erinnere alle STL-Container Copy-Operationen beim wachsen verwenden sollte man eigentlich in 99% aller FĂ€lle das Objekt in einem Pointer verpacken.

    Nein. Pointer sollte man nur verwenden, wenn es nicht anders geht oder einen messbaren Unterschied gibt (selten), weil es eine zusaetzliche Indirektion bedeutet, was sich negativ auf Uebersichtlichkeit und Cache-locality auswirkt.



  • Jodocus schrieb:

    Ist aber doof wegen Cache und so.

    Hm, ich habe das anders gelernt.
    Ich meine, wenn eure Vector-Container wachsen habt ihr eine heavyweight copy Operation, die um ein vielfaches teurer ist als euch jede Cache Operation schenken könnte. (falls reserve nicht geht)



  • Kellerautomat schrieb:

    std::list ist noch viel dooferer.

    Nö, ich glaube (Achtung, kein Bock auf Messungen), dass dir ein Pointer-Vektor performance-mĂ€ĂŸig keine großartigen Vorteile gegenĂŒber einer Liste gibt. In beiden FĂ€llen versaust du dir Cache-LokalitĂ€t durch Indirektion.



  • Jodocus schrieb:

    Kellerautomat schrieb:

    std::list ist noch viel dooferer.

    Nö, ich glaube (Achtung, kein Bock auf Messungen), dass dir ein Pointer-Vektor performance-mĂ€ĂŸig keine großartigen Vorteile gegenĂŒber einer Liste gibt. In beiden FĂ€llen versaust du dir Cache-LokalitĂ€t durch Indirektion.

    Battle accepted :p

    Ich mach heute Abend ein paar Messungen.



  • vector of pointer schrieb:

    Jodocus schrieb:

    Ist aber doof wegen Cache und so.

    Hm, ich habe das anders gelernt.
    Ich meine, wenn eure Vector-Container wachsen habt ihr eine heavyweight copy Operation, die um ein vielfaches teurer ist als euch jede Cache Operation schenken könnte. (falls reserve nicht geht)

    Und was ist mit Movable Typen?



  • Ich hab auch noch nie std::list wirklich gebraucht. std::vector, std::set und std::map decken so ziemlich alle BedĂŒrfnisse ab.



  • /rant/ schrieb:

    Ich hab auch noch nie std::list wirklich gebraucht. std::vector, std::set und std::map decken so ziemlich alle BedĂŒrfnisse ab.

    Jein. In den meisten FĂ€llen werden die Container nach Art eines Vektors sicherlich ausreichen oder gar am sinnvollsten sein. Listen sind aber dann von Vorteil, wenn eine hohe Fluktuation in Verbindung mit einer großen Datenmenge vorliegt. Eine Warteschlange (Queue) wĂŒrde ich eher nicht mit einem Vektor implementieren.

    mfg Martin


Log in to reply