sind stl-container in tiefer Schachtelung noch effizient?

hustbaer

Mit C++0x wird das alles (deutlich) besser

Hi volkard,

volkard schrieb:

PhilippM schrieb:

vector<pair<unsigned char, queue<float> > >

das ist kacke.

wenn hier der vector wachsen muß, dann kopiert er tausende von queues, die wiederum innendrin schleifen laufen haben, die kopieren, dazu pro queue-block, der daten bekommen hat, einmal new und einmal delete. das ist eher nicht lecker.

Deine Bedenken kann ich sehr gut verstehen.

Ich bin zwar nur C++-Hobby-Programmierer, aber wenn ich so ein Konstrukt
brauchen würde, dann würde ich es auch so verwenden.

Dazu würde ich std::swap für den Datentyp pair<unsigned char, queue<float> >
implementieren um somit das kopieren zu verhindern.

Würde das nicht den von mir erhofften Erfolg zur Folge haben?

Gruß,
CSpille

volkard

CSpille schrieb:

Dazu würde ich std::swap für den Datentyp pair<unsigned char, queue<float> >
implementieren um somit das kopieren zu verhindern.

Würde das nicht den von mir erhofften Erfolg zur Folge haben?

nein, eher nicht. Draveres swap ist bei Draveres beispiel ok, nicht aber beim wachsen. an sich geht er ja in die richtige richtung, da wollte ich nicht widersprechen.
beim wachsen passiert was anderes.
man hat zum beispiel einen vector mit 1000 elementen. und der ist voll. push_back löst ein wachsen aus. dabei wird an einem neuen ort im ram neuer speicher für 2000 elemente angelegt. dann werden die 1000 bisherigen elemente in den neuen speicher kopiert. mit dem kopierkonstruktor. falls eine exception fliegt beim 567. element, werden die 566 kopierten elemete halt schnell wieder destruiert.
nichsdestotrotz würde was einigermaßen schnelles mit swap gehen. man prüft vor jedem push_back selber, ob noch platz ist. wachsenlassen ginge dann mit: neuen vector mit 1000 leeren queues anlegen. die 1000 elemens vom alten und neuen swappen. dann die vectoren selbst swappen. und den kleinen löschen (fallenlassen). ein vector ist niicht so kompliziert, daß man nicht einfach eine eigene klasse bauen kann, die das macht, statt den std::vector in solcher weise von außen zu managen.

volkard

CSpille schrieb:

Ich bin zwar nur C++-Hobby-Programmierer, aber wenn ich so ein Konstrukt
brauchen würde, dann würde ich es auch so verwenden.

vielleicht würde ich mich einmischen und die sagen, daß du das eben nicht brauchen würdest.

nimm doch einfach statt
vector<pair<unsigned char, queue<float> > >
eine
queue<pair<unsigned char, queue<float> > >

die zugriffszeiten der äußeren queue sind immernoch lecker schnell und die leichte verlangsamung gegenüber vector wird nochmal relativiert, weil die zugriffszeiten der inneren queue noch dazukommen und die äußere queue kann wachsen, ohne was zu kopieren. queues haben doch nen operator[] mit der zeitkomplexität O(1), wenn ich mich recht erinnere.

Hi volkard,

vielen Dank für deine nächtliche Antwort. Hab gerade völlig vergessen,
dass der Copy-Konstruktor aufgerufen wird. Hab durch die swap-Diskussion
gedacht es würde der leere Konstruktor aufgerufen und ein swap. ^^
Naja, ist halt spät

Die Datenstruktur, die ich (unbedingt) verwenden wollte, war unabhängig
von dem Beispiel. Klar kann ich in diesem Beispiel eine sinnvollere verwenden.

volkard schrieb:

queues haben doch nen operator[] mit der zeitkomplexität O(1)

Wirklich? Ich dachte es war O(n)

Dann bleibt als einzige Copy-Prevention (ohne explizite push_back-Behandlung unter
Verwendung der STL) wohl doch nur
vector<pair<unsigned char, queue<float>* > >
bzw.
vector<pair<unsigned char, queue<float> >* >
EDIT: Wenn man also einen Vektor verwenden möchte (ohne Betrachtung alternativer Strukturen)...

Gruß,
CSpille

volkard

CSpille schrieb:

volkard schrieb:

queues haben doch nen operator[] mit der zeitkomplexität O(1)

Wirklich? Ich dachte es war O(n)

queue ist nur ein adapter, drunter liegt normalerweise deque.
ich meinte natürlich deque.
und der op[] hat dabei O(1).
http://www.cplusplus.com/reference/stl/deque/operator[].html

die deque ist nämlich nicht eine doppelt verkettete liste, sondern besteht aus lauter (zum beispiel) 4096 bytes großen seiten, die vollgemacht werden und beim wachsen müssen die seiten nicht umkopiert werden. für den op[] gibt es eine zusätzliche indirektion, also nix schlimmes. und du kannst sie weitgehend verwenden, ohne dran zu denken, daß sie gar kein vector ist.

Dann bleibt als einzige Copy-Prevention (ohne explizite push_back-Behandlung unter
Verwendung der STL) wohl doch nur
vector<pair<unsigned char, queue<float>* > >
bzw.
vector<pair<unsigned char, queue<float> >* >
EDIT: Wenn man also einen Vektor verwenden möchte (ohne Betrachtung alternativer Strukturen)...

an die lösung hab ich auch gedacht, die ist aber nicht gerade exceptionsicher. nimmr man dann smart pointers rein, wird's am ende vielleicht langsamer als die deque und ist vor allem viel schlechter zu bedienen. man müßte ja die ganzen zeiger mit new bestücken.

Dravere

volkard schrieb:

man hat zum beispiel einen vector mit 1000 elementen. und der ist voll. push_back löst ein wachsen aus. dabei wird an einem neuen ort im ram neuer speicher für 2000 elemente angelegt. dann werden die 1000 bisherigen elemente in den neuen speicher kopiert. mit dem kopierkonstruktor. falls eine exception fliegt beim 567. element, werden die 566 kopierten elemete halt schnell wieder destruiert.

Sagt der Standard denn etwas dazu, dass hier der Kopierkonstruktor verwendet werden muss? Ich dachte es wäre auch korrekt, wenn die Implementierung einen swap der einzelnen Elemente ausführt. Was zur Konstruktion und Destruktion von nur sehr kleinen Objekten führt. Also grundsätzlich das, was du sagst, was man selber machen müsse.

Ich würde das grösste Problem eher in std::queue sehen. Queue ist nur ein Adapter, welcher keinen Zugriff auf den inneren Container gibt. Soweit mir bekannt ist, ist auch kein swap für std::queue vorhanden. Man muss diese Struktur somit immer kopieren.
(Bin im übrigen sowieso kein Fan von diesen Adaptern, habe den Vorteil noch nicht entdecken können)

Grüssli

volkard

Dravere schrieb:

Sagt der Standard denn etwas dazu, dass hier der Kopierkonstruktor verwendet werden muss?

nein.

Ich dachte es wäre auch korrekt, wenn die Implementierung einen swap der einzelnen Elemente ausführt. Was zur Konstruktion und Destruktion von nur sehr kleinen Objekten führt. Also grundsätzlich das, was du sagst, was man selber machen müsse.

und die version mit swap ist für PODs großer unfug. der vector müßte mit extrem spaßiger template-metaprogrammierung feststellen, ob die verwaltete klasse swap anbietet und ob das zu nehmen klug wäre. also in diesem falls feststellen: std::pair kann geswapped werden, ob's klug ist hängt aber davon ab, ob die inneren typen das mögen. drinnen sind a) unsigned char. der char mag es nicht. b) queue<float>. die mag es. die queue kann normalerweise viel mehr gewinnen als der bool verliert. also nehmen wir mal die swap-version.
ich bin sicher, daß es noch keine implemetierung der stl gibt, die sowas macht. und ich vermute, die wird es auch nie geben. sich die richtigen datenstrukturen rauszusuchen, bzw wie bei alexandrescu dem vector die grow-with-swap-policy mitzugeben, ist aufgabe des programmierers.

Ich würde das grösste Problem eher in std::queue sehen. Queue ist nur ein Adapter, welcher keinen Zugriff auf den inneren Container gibt. Soweit mir bekannt ist, ist auch kein swap für std::queue vorhanden. Man muss diese Struktur somit immer kopieren.
(Bin im übrigen sowieso kein Fan von diesen Adaptern, habe den Vorteil noch nicht entdecken können)

ich sehe da auch eher keinen vortiel. ich meinte auch die deque. deque hat swap. die queue nicht mehr, vielleicht um mehr innere container für diesen adapter zu erlauben? da wäre SFINAE wohl die wahl gewesen, und zu sagen, daß queue dann swap hat, wenn der innere container swap hat. aber das gab es damals noch nicht.

hustbaer

volkard schrieb:

die queue nicht mehr, vielleicht um mehr innere container für diesen adapter zu erlauben? da wäre SFINAE wohl die wahl gewesen, und zu sagen, daß queue dann swap hat, wenn der innere container swap hat. aber das gab es damals noch nicht.

was hat das mit SFINAE zu tun?
diese dinge löst man doch normalerweise dadurch dass man die funktion einfach implementiert -- solange sie nicht instanziert wird ist alles OK. und wenn man versucht sie zu instanzieren, dann sieht man eh ob es klappt oder nicht.

volkard

hustbaer schrieb:

was hat das mit SFINAE zu tun?
diese dinge löst man doch normalerweise dadurch dass man die funktion einfach implementiert

stimmt. das hab ich gerade verwechselt mit einem eigenen globalen swap, das mit SFINAE geschaut hat, ob die klasse eine memberswap hat und das gegebenenfalls benutzt und anderenfalls nur dreieckstausch macht. jetzt frage ich mich, warum die queue kein swap hat.

Dravere

volkard schrieb:

und die version mit swap ist für PODs großer unfug.

Hmmm, stimmt. Hab die PODs vergessen. Gibt es keine einfachere Lösung, um auch die zu berücksichtigen? *gähnende müde leere im Kopf hat*
Naja, das überleg ich mir nicht mehr um 5 Uhr morgens

volkard schrieb:

jetzt frage ich mich, warum die queue kein swap hat.

Wenn du schon dabei bist, frag gleich mal nach, wieso std::stack und std::priority_queue kein swap haben. Und ein clear wäre auch nicht schlecht. Und noch ein paar andere Dinge. Wozu sind die Dinger überhaupt gut?

Grüssli

volkard

Dravere schrieb:

volkard schrieb:

und die version mit swap ist für PODs großer unfug.

Hmmm, stimmt. Hab die PODs vergessen. Gibt es keine einfachere Lösung, um auch die zu berücksichtigen?

ich sehe keine. aber meiner meinung nach sollte c++ das nicht tun aus ideologischen gründen (sie stehen nicht im standard). c++ darf nicht erkennen, daß ich bubble-sort gebaut habe und es klammheimlich durch intro-sort ersetzen. es kann nämlich sein, daß ich die ausgefallene datenlage habe, daß ich mein telefonbuch sortiert auf platte und im ram halte und sort nach jedem neuladen aufrufe und mit dem benutzer vereinbart habe, daß er nur einträge löschen darf und neue einträge hinten an die datei anhängen darf. da ist bubblesort einfach schneller als die ganzen profi-alternativen. beim
vector<pair<unsigned char, queue<float> > >
mags ja klar sein, aber beim
vector<pair<unsigned char[8192], queue<float> > >
muß einfach der programmierer entscheiden, ob die queues gewöhnlich sehr wenige elemente haben und der POD bestimmt oder ob die queues gewöhnlich sehr viele elemente haben und swap gut ist.
darüberhinaus ist es nicht gut, bloß auf die verbrauchte zeit zu achten, manchmal ist eine langsame lösung besser, weil sie nicht ruckelt. deswegen ist die globale objektliste im 3d-spiel eine verkettete liste, die 150-mal so viel rechenzeit frißt wie der entsprechende vector. aber die liste ruckelt nicht. wenn der vector von 1000000 elementen auf 2000000 mio springt, dann steht der rechner für ein halbes sekündchen und der player ist mausetot. das mag er nicht. lieber gibt er 50€ mehr für hardware aus und nimmt die verkettete liste. hingegen muß im backup-brogramm der vector genommen werden. da will ich ein paar minuten schneller sein und ein ruckeln ist mir egal.
ich möchte keine sprache benutzen, die für mich entscheidet, ob mein programm eher ein backup-programm oder ein spiel ist. ok, wie kopiert werden soll, darf sie entscheiden, solange ich noch ein vetorecht behalte.