Unterschied list, queue, deque?



  • Was ist der Unterschied zwischen list, queue und deque?



  • Was ist der Unterschied zwischen Auto, Pferd und Flugzeug?



  • Die Listen/Kontainer haben alle unterschiedliche Eigenschaften. Ich kann mir die Eigenschaften am besten merken, wenn ich mir vorstelle, dass eine std::list eine einfach verkettete Liste ist, ein std::vector ein einfaches, sich selbst vergrößerndes Array und eine std::dequeue eine verkette Liste von Arrays ist.

    Entsprechend günstig/ungünstig sind z.B. wahlfreier Zugriff und/oder Einfügen/Löschen am Anfang/Ende der Liste.



  • gsfddfsfds schrieb:

    Was ist der Unterschied zwischen list, queue und deque?

    queue ist nur ein Adapter, der dir eine andere Schnittstelle bietet und unter Haube eine bestimmte Datenstruktur nutzt, die man selbst festlegen kann. Per Default ist das eine deque . Du könntest aber auch eine queue erzeugen, die intern eine list statt einer deque benutzt.

    Die Sequenz-Container list , deque und vector unterscheiden sich durch ihre Garantien bzgl. Speicherlayout, Random-Accessibility, der Komplexität für das Einfügen und Löschen sowie ob/wann Iteratoren und Referenzen beim Einfügen/Löschen invalidiert werden. list bietet dann noch ein paar Extra-Operationen an (z.B. splice ).

    Beispielsweise garantiert vector , dass die Elemente alle linear hintereinander im Speicher liegen ohne Lücken, also wie bei einem normalen "Feld" (array). list ist eine doppelt-verkettete Liste. Die Listenelenemte werden einzeln alloziert und miteinander "verpointert". Das Speicherlayout ist also ganz anders und es gibt auch kein Random-Access mehr. deque ist quasi irgendwie zwischen vector und list . Die Elemente stehen kompakter in Blöcken im Speicher, aber nicht alle zusammenhängend. Dafür kann man bei einer deque effizient an beiden Enden Elemente hinzufügen und Löschen, ohne dass Referenzen auf die anderen Elemente ungültig werden oder irgendetwas verschoben werden muss. deque-Iteratoren werden aber gegebenenfalls trotzdem ungültig. Da musst Du einfach mal in eine der Referenzen nachschauen, was die einzelnen Operationen genau versprechen. Die Garantien folgen eigentlich aus der Implementierung.

    list<T> benutze ich so gut wie nie. Ich kann mich jedenfalls nicht an eine Situation erinnern, wo mir list<T> besser geholfen hätte als vector<T> oder deque<T> . Über splice kann man zwar Elemente aus einer Liste in konstanter Zeit in einer anderen Liste einfügen. Aber das brauchte ich nie. Eine list kann auch effizient Elemente aus der Mitte löschen oder dort einfügen. Aber dafür braucht man einen Iterator, der an die richtige Stelle hinzeigt. Den müsste man sich schon irgendwo gemerkt haben, weil das Aufsuchen der Stelle ja wieder Zeit kosten würde.



  • Was für einen Container würdet ihr für Breitensuche benutzen, was für einen für Tiefensuche?


  • Mod

    sdffds schrieb:

    Was für einen Container würdet ihr für Breitensuche benutzen, was für einen für Tiefensuche?

    Welche Hecke würdest du zum Heckenschneiden benutzen?



  • Pack doch gleich die komplette Hausaufgabe rein, dann können wir sie schneller lösen ...



  • sdffds schrieb:

    Was für einen Container würdet ihr für Breitensuche benutzen, was für einen für Tiefensuche?

    Was hindert dich denn dran, diese Frage selbst zu beantworten?


Log in to reply