Benutzt eigentlich irgendwer std::list?



  • 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



  • mgaeckler schrieb:

    /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.

    Aber mit deque.



  • [quote="Skym0sh0"]

    Und was ist mit Movable Typen?

    Move zählt hier nicht, weil es ihm um eine stabile Speicheradresse geht, die ja auch bei move nicht mehr gegeben ist außerdem muss man move erstmal ordentlich implementieren.

    Move ist nur ein Cast und der muss nicht moven und bei vielen Implementationen moved er überhaupt nicht.
    Außerdem verlierst du die Strong Exception guarantee, wenn du innerhalb eines Vectors move- verwendest, deswegen wird innerhalb eines Vectors nur gemoved, wenn der Move-Konstructor garantiert keine Exception zu werfen. (vector function: move_if_no_excpt)

    - Move geht nicht bei const Objekten.
    - Move-Konstruktor muss innerhalb eines Vectors garantieren, dass er keine exception wirft. (noexcept)



  • Edit: für den Post oben von C++++++

    Er moved natürlich auch, wenn kein Copy-Constructor verfügbar ist.

    Zu dem Thema gab es einen Vortrag von Scott Meyers:

    http://channel9.msdn.com/Events/GoingNative/2013/An-Effective-Cpp11-14-Sampler



  • volkard schrieb:

    mgaeckler schrieb:

    Eine Warteschlange (Queue) würde ich eher nicht mit einem Vektor implementieren.

    Aber mit deque.

    Witzig, das ist schon eine Warteschlange.



  • mgaeckler schrieb:

    volkard schrieb:

    mgaeckler schrieb:

    Eine Warteschlange (Queue) würde ich eher nicht mit einem Vektor implementieren.

    Aber mit deque.

    Witzig, das ist schon eine Warteschlange.

    Eine vector-artige.



  • volkard schrieb:

    mgaeckler schrieb:

    volkard schrieb:

    mgaeckler schrieb:

    Eine Warteschlange (Queue) würde ich eher nicht mit einem Vektor implementieren.

    Aber mit deque.

    Witzig, das ist schon eine Warteschlange.

    Eine vector-artige.

    Na und? Was willst Du damit sagen? Ich habe nicht behauptet, daß man eine Warteschlange nicht auch mit einem Vektor implementieren kann.

    mfg Martin



  • mgaeckler schrieb:

    volkard schrieb:

    mgaeckler schrieb:

    volkard schrieb:

    mgaeckler schrieb:

    Eine Warteschlange (Queue) würde ich eher nicht mit einem Vektor implementieren.

    Aber mit deque.

    Witzig, das ist schon eine Warteschlange.

    Eine vector-artige.

    Na und? Was willst Du damit sagen? Ich habe nicht behauptet, daß man eine Warteschlange nicht auch mit einem Vektor implementieren kann.
    mfg Martin

    Aber das da klang mir ganz so, als ob man std::list dafür nehmen sollte.

    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.


Anmelden zum Antworten