Benutzt eigentlich irgendwer std::list?

[volkard]

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.

[c++++]

[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)

[chp++]

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

[mgaeckler]

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.

[volkard]

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.

[mgaeckler]

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

[volkard]

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.

[mgaeckler]

volkard schrieb:

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.

Man sollte das nehmen, was für den jeweiligen Anwendungsfall am besten geeignet ist. Ich weiß nicht, wie deque sich verhält, wenn auch mal 100 000 Objekte und mehr darin sein könnten.

mfg Martin

[volkard]

mgaeckler schrieb:

Ich weiß nicht, wie deque sich verhält, wenn auch mal 100 000 Objekte und mehr darin sein könnten.

deque bleibt immer cool. es ist kein vector an einem stück, sondern aus lauter kleinen (vielleicht 8k) happen. also fast so schnell und speichersparend wie vector aber kein ruckeln beim wachsen.

[mgaeckler]

volkard schrieb:

mgaeckler schrieb:

Ich weiß nicht, wie deque sich verhält, wenn auch mal 100 000 Objekte und mehr darin sein könnten.

deque bleibt immer cool. es ist kein vector an einem stück, sondern aus lauter kleinen (vielleicht 8k) happen. also fast so schnell und speichersparend wie vector aber kein ruckeln beim wachsen.

Dann passt es ja

[EOP]

deque ist manchmal ziemlich cool. man sollte nur immer so ungefähr wissen was man braucht und will

[DocShoe]

volkard schrieb:

mgaeckler schrieb:

Ich weiß nicht, wie deque sich verhält, wenn auch mal 100 000 Objekte und mehr darin sein könnten.

deque bleibt immer cool. es ist kein vector an einem stück, sondern aus lauter kleinen (vielleicht 8k) happen. also fast so schnell und speichersparend wie vector aber kein ruckeln beim wachsen.

Hast du dir deine Implementation von std::deque mal angeschaut? Mein Compiler benutzt die Dinkumware STL, da ist die Blockgröße 16 Byte (!), das fragmentiert und hat einen Speicheroverhead wie hulle. Mir ist es nur ein einziges Mal gelungen, eine bad_alloc auszulösen, und das war im Zusammenhang mit std::deque und einigen zig-tausend Elementen.

Ich hätte es ja schön gefunden, wenn man die Blockgröße irgendwie über ein Template Argument hätte steuern können, um sie seinen Bedürfnissen anzupassen. Gibt´s nicht. Leider.

Mit std::deque bin ich sehr vorsichtig geworden, wenn std::vector nur einen kleinen Performancenachteil mit sich bringt nehme ich lieber den.

[volkard]

DocShoe schrieb:

Hast du dir deine Implementation von std::deque mal angeschaut? Mein Compiler benutzt die Dinkumware STL, da ist die Blockgröße 16 Byte (!), das fragmentiert und hat einen Speicheroverhead wie hulle. Mir ist es nur ein einziges Mal gelungen, eine bad_alloc auszulösen, und das war im Zusammenhang mit std::deque und einigen zig-tausend Elementen.

Ich hätte es ja schön gefunden, wenn man die Blockgröße irgendwie über ein Template Argument hätte steuern können, um sie seinen Bedürfnissen anzupassen. Gibt´s nicht. Leider.

Mit std::deque bin ich sehr vorsichtig geworden, wenn std::vector nur einen kleinen Performancenachteil mit sich bringt nehme ich lieber den.

Ich meine mal 4096 gesehen zu haben auf 32-bitter. Und da wäre es logisch, langsam nach 8192 zu gehen.
Mal in den COde shauen...

GCC sagt

/**
   *  @brief This function controls the size of memory nodes.
   *  @param  __size  The size of an element.
   *  @return   The number (not byte size) of elements per node.
   *
   *  This function started off as a compiler kludge from SGI, but
   *  seems to be a useful wrapper around a repeated constant
   *  expression.  The @b 512 is tunable (and no other code needs to
   *  change), but no investigation has been done since inheriting the
   *  SGI code.  Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what
   *  you are doing, however: changing it breaks the binary
   *  compatibility!!
  */

#ifndef _GLIBCXX_DEQUE_BUF_SIZE
#define _GLIBCXX_DEQUE_BUF_SIZE 512
#endif

  inline size_t
  __deque_buf_size(size_t __size)
  { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
	    ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }

Aha! Nur 512. Könnte mir zwei Gründe denken:
a) Zu viele benutzen deque, ohne zu wissen, was drin stecken sollte. Ein vector<deque<int>> mit 1Mio deques, die je 0-10 ints drin haben, und jemand weint bei 8192. Bei 512 hat man immernoch 128 ints drin und der Speicheroverhead pro int ist echt vernachlässigbar. Und die Cacheline sollte auch nicht größer als 512 sein. Also ganz nette Wahl.
b) Die GCC-Leute kennen genau ihren allocator und der geht mit 512 auch gut ab. Unter Win baute ich mir für Blöcke einen eigenen mit VirtualAlloc&Co.
Aber alles reine Vermutung.

Sicher ist aber, daß Deine 16 von Drinkumware ein schlechter Witz ist.

Ach, die Blockgröße ist bei GCC sogar anpassbar.

[volkard]

DocShoe schrieb:

Mit std::deque bin ich sehr vorsichtig geworden, wenn std::vector nur einen kleinen Performancenachteil mit sich bringt nehme ich lieber den.

Ich hab mal gelernt, daß queue gegenüber vector für die Hauptanwendung push_back keinen merklichen Unterschied macht. Und sogar bei sort auf integers ist sie nur halb so lahm wie der vector, und das ist ganz schön magisch. Kann sein, daß sich das in den letzten Jahren zugunsten von vector verschoben hat, RAM ist ja soo lahm.

[SeppJ]

volkard schrieb:

DocShoe schrieb:

Mit std::deque bin ich sehr vorsichtig geworden, wenn std::vector nur einen kleinen Performancenachteil mit sich bringt nehme ich lieber den.

Ich hab mal gelernt, daß queue gegenüber vector für die Hauptanwendung push_back keinen merklichen Unterschied macht.

Das haben wir hier im Forum doch schon oft gemessen. Das Problem ist halt, das push_back selten die Hauptanwendung ist. Da wäre die deque in der Tat optimal. Bloß wenn später auf die Daten zugegriffen werden soll...

[Marthog]

SeppJ schrieb:

Das haben wir hier im Forum doch schon oft gemessen. Das Problem ist halt, das push_back selten die Hauptanwendung ist. Da wäre die deque in der Tat optimal. Bloß wenn später auf die Daten zugegriffen werden soll...

Das Problem ist, dass der iterator bei jedem Schritt ueberpruefen muss, ob schon zum naechsten Block gesprungen werden muss.
Irgendjemand hier hat mal gemessen, dass eine Implementierung mit

for block in deque:
    for element in block:

ungefaehr mit den Arrays gleich aufliegt.
Ich kann mit vorstellen, dass es irgendwann optimierte Standardfunktionen fuer deque-iteratoren gibt.

[volkard]

Marthog schrieb:

Das Problem ist, dass der iterator bei jedem Schritt ueberpruefen muss, ob schon zum naechsten Block gesprungen werden muss.

Kein Problem!
vector::iterator macht in seinem for innendrin irgendwie

:schleife
if pos==ende then goto fertig
tuwas();
++pos;
goto schleife;

und queue::iterator

:innereSchleife
if pos==blockEnde then goto blockEnde
tuwas();
++pos;
goto innereSchleife;

Die innere Schleife ist also gleich. Bei Blockgrößen von 512 Byte sollte das schnell gehen, weil die äußere Schleife so selten läuft.

[krümelkacker]

Bei der C++Now 2014 gab's nen tollen Talk dazu, wo der Vortragende nochmal ein paar bekannte Benchmarks wiederholt und erweitert hat: mehrere Container (u.a. auch Dinge wie vector<unique_ptr<T>> oder boost::flat_map ) mit unterschiedllichen sizeof(T) Größen. Seine Guidelines bzgl smart pointer use sehen auch vernünftig aus.

TL;DW: Sein Fazit ist so etwas wie "std::list ist überflüssig".

(Die vielen Zwischenfragen nerven nur ein bisschen. John Lakos ist da auch im Publikum und gibt seinen Senf abundzu ab.)

[Ethon]

Wegen Cache-Locality: Teilweise ist es cool sich einen kleinen Pool-Allocator zu basteln und den zu verwenden. Zb ist std::set eine astreine priority queue wenn man die Nodes aus einem Pool zieht und viel, viel schneller als std::priority_queue.
Hatte das mal gemessen.

Bei std::list macht es bestimmt auch gewaltig etwas aus.

[volkard]

Ethon schrieb:

Wegen Cache-Locality: Teilweise ist es cool sich einen kleinen Pool-Allocator zu basteln und den zu verwenden. Zb ist std::set eine astreine priority queue wenn man die Nodes aus einem Pool zieht und viel, viel schneller als std::priority_queue.
Hatte das mal gemessen.

Würde ich als schnellen Hack bezeichnen. Müßte bei längerem Betrieb und ein wenig Füllstand die Lokalität gänzlich verlieren. Heaps kann man auch aus (4k-)Blöcken bauen, die dürften dann astrein sein.