Aufbau der STL - Teil 1: Container

CStoll

*nachsieht* Du hast recht, da fehl(t)en die schließenden Klammern. Das kommt davon, wenn man den Text blind abtippt und dann als gegeben nimmt.

(*Notiz an mich* Beim nächsten Artikel sage ich den Korrekturlesern, daß sie auch mal die cpp-Teile überfliegen sollen)

aMan

CStoll schrieb:

Ganz einfach: Der letzte Template-Parameter der priority_queue gibt an, nach welchem Verfahren die Elemente einsortiert werden sollen, du brauchst also:
priority_queue<dataT,vector<dataT>,greater<dataT> > my_queue;
(die PQ gibt das "größte" Element nach der angegebenen Sortierung als nächstes heraus - beim normalen less<T> ist das das echt größte Element, mit greater<T> drehst du die Sortierung um und erhältst also das kleinste Element)

Danke, ich hab das jetzt sogar verstanden..

DaRpH

Ich habe mal eine Frage dazu was ist mit Transaktionssicher gemeint?

Ist damit Threadsicher gemeint? Wenn ja werden keine weiteren Syncronisationsmechanismen benötigt bis auf die ausgenommen Funktionen. Ist dies so irgendwo definiert und in der VC++ sowie stlport implementierungen auch wirklich der Fall?

camper

DaRpH schrieb:

Ist damit Threadsicher gemeint?

Nein. Es geht um Exception-Sicherheit. Falls irgendeine der mit einer Funktion verbundenen Operationen (Copy-ctor, Copy-Zuweisung, Vergleichsoperator, Speicheranforderung etc.) fehlschlägt und eine Exception wirft, verändert sich der Inhalt des Containers bei den betreffenden Funktionen nicht. Alle anderen Funktion bieten zumindest die schwache Garantie: der Inhalt eines Containers ist bei Auftreten einer Exception möglicherweise verändert (z.B. ein Element ist plötzlich doppelt vorhanden), aber immer noch gültig (also z.B. keine Löcher im vector oder keine doppelten Elemente in set).

unskilled

Irgendwo hier im Forum war irgendwann auch mal nen Link im Umlauf... Da war ein Bild drauf, wo gezeigt wird, wann welcher Container am besten wäre (schnelle Größenänderung, Einfügen am Anfang, usw.)...
Den Link finde ich leider nicht mehr - wäre toll wenn jmd wüsste wo man so ne Übersicht finden könnte : ]

bb, Tom

michba

http://www.linuxsoftware.co.nz/containerchoice.png?

unskilled

Danke : )

CStoll schrieb:

Container         Vektor          Deque           Liste           Set             Multiset        Map             Multimap
----------------------------------------------------------------------------------------------------------------------------------

Struktur          dynamisches     Array von       verkettete      Binärbaum       Binärbaum       Binärbaum       Binärbaum
                  Array           Arrays          Liste

Elemente          Wert            Wert            Wert            Wert            Wert            Schlüssel+Wert  Schlüssel+Wert

Duplikate         Ja              Ja              Ja              Nein            Ja              Wert            Ja

Direktzugriff     Ja              Ja              Nein            Nein            Nein            über Schlüssel  Nein

Iteratortyp       Random Access   Random Access   Bidirektional   Bidirektional   Bidirektional   Bidirektional   Bidirektional
                                                                  konstant        konstant        Schl. konstant  Schl. konstant
Suche             langsam         langsam         sehr langsam    schnell         schnell         schnell (Schl.) schnell (Schl.)

Einf./Entf.       Ende            Anfang, Ende    überall

invalidiert       Reallocation    immer           nie             nie             nie             nie             nie
Iteratoren etc.

Speicherfreigabe  nie             manchmal        immer           immer           immer           immer           immer

Reservierung      Ja              Nein

Transaktions-     push/pop        push/pop an     alle außer      alle außer      alle außer      alle außer      alle außer
sicher            am Ende         Anfang, Ende    sort            multi-insert    multi-insert    multi-insert    multi-insert

Bei der deque werden die Iteratoren nicht immer ungültig. Beim Löschen am Anfang/Ende werden nur die gelöschten Elemente ungültig, alle anderen auf die deque bleiben aber gültig.

Im vector werden beim Löschen/Einfügen alle iteratoren auf nachfolgenden Elemente ungültig.

Vielleicht kann das jmd. ändern bzw. einbauen, CStoll ist ja ehe nicht mehr da

camper

KasF schrieb:

Bei der deque werden die Iteratoren nicht immer ungültig. Beim Löschen am Anfang/Ende werden nur die gelöschten Elemente ungültig, alle anderen auf die deque bleiben aber gültig.

Um präziser zu sein: Alle Iteratoren werden ungültig beim Einfügen oder Löschen am Anfang bzw. Ende, nicht aber Referenzen (und Zeiger) auf Elemente, die nicht gelöscht wurden.

Bei list könnte man bei Transaktionssicherheit noch erwähnen, dass Exceptions bei sort nur durch das Vergleichsobjekt entstehen können. Aus den Komplexitätsveraussetzungen für list::sort kann man ableiten, dass dieses intern mit splice mit konstanter Komplexität arbeiten muss, und folglich keine Exceptions durch das Herumkopieren entstehen können.

GPC

Okay, danke für eure Anmerkungen. Ich passe es in der kommenden Woche an.