Aufbau der STL - Teil 1: Container



  • *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)



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



  • 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?



  • 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).



  • 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





  • 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 😞



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



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


Anmelden zum Antworten