Ist eine ArrayList in Java dasselbe wie eine Deque in C++?



  • Ich denke schon!



  • glaube er das gleiche wie std::list, oder ehr noch std:array



  • Also std::list ist wohl eher LinkedList in Java.



  • BorisDieKlinge schrieb:

    glaube er das gleiche wie std::list, oder ehr noch std:array

    'std::list' ist etwas anderes, wie bereits gesagt wurde, und 'std::array' gibt's nicht.

    Die Java-'ArrayList'-Klasse entspricht von der Implementierung her dem 'std::vector'.



  • Laut Doku von Sun (http://java.sun.com/j2se/1.4.2/docs/api/java/util/ArrayList.html) ist eine ArrayList:

    Resizable-array implementation of the List interface.
    ...
    The size, isEmpty, get, set, iterator, and listIterator operations run in constant time.
    ...
    Each ArrayList instance has a capacity.
    ...

    d.h. es entspricht einem std::vector<>.



  • Zusatz: Eine Deque ist nochmal was anderes, denn sie erlaubt effizientes Hinzufügen und Entfernen von Elementen sowohl vorne als auch hinten. Die 'ArrayList' tut dies nicht, hier ist der Zugriff nur an einer Seite effizient.

    Übrigens ist die 'ArrayList' damit nahezu identisch zur Java-'Vector'-Klasse. Der einzige Unterschied ist, dass 'Vector' Thread-Synchronisation implementiert.



  • Wie verwalten die Container denn die Elemente intern?

    ArrayList speichert sie doch als verlinkte Liste und "führt zusätzlich Buch", damit man relativ schnellen wahlfreien Zugriff hat und Elemente einketten / entfernen kann, ohne das gesamte Array neu aufbauen zu müssen, wie es bei Vektoren der Fall wäre. Und std::vector ist doch genau das, ein einfacher Vektor.

    Bzw. wie sieht dann eigentlich eine Deque aus, wenn man Elemente nur am Anfang und Ende effizient hinzufügen kann?



  • Lister schrieb:

    Wie verwalten die Container denn die Elemente intern?

    Das steht auf der von Th geposteten Seite doch.

    ArrayList speichert sie doch als verlinkte Liste und "führt zusätzlich Buch"

    Nein. Du lässt Dich vom Namen verwirren. Hier wird *nichts* mit einer verketteten Liste gemacht. Die Implementierung ist dieselbe wie die vom Vektor.

    Bzw. wie sieht dann eigentlich eine Deque aus, wenn man Elemente nur am Anfang und Ende effizient hinzufügen kann?

    Da gibt es zwei Möglichkeiten. Die einfachere ist über einen Ringpuffer. Im Prinzip also auch ein dynamisches Array wie beim Vektor, aber man merkt sich zwei Indizes: den Kopf- und den Schwanz-Index. Für eine genauere Erklärung siehe http://en.wikipedia.org/wiki/Circular_buffer.

    Die alternative Implementierung, und unter Umständen geringfügig effizienter, ist die Implementierung über eine Seiten-struktur (pages). Die Implementierung ist leider alles andere als schön, da ihre Effizient auf einer „magischen“ Konstante (und zwar der Page-Größe) beruht, die man durch Benchmarks ermittelt.

    /Edit: Das sieht dann so aus: http://pages.cpsc.ucalgary.ca/~kremer/STL/1024x768/deque.html



  • Lister schrieb:

    ArrayList speichert sie doch als verlinkte Liste und "führt zusätzlich Buch", damit man relativ schnellen wahlfreien Zugriff hat und Elemente einketten / entfernen kann, ohne das gesamte Array neu aufbauen zu müssen, wie es bei Vektoren der Fall wäre.

    Quelle?

    Das ist doch ein Array wie der Name schon sagt, wie bei std::vector.



  • Das Ding heisst ArrayList weil es ein Array verwendet um das List Interface zu implementieren.

    Mit einem STL Container kann man die Java Collections allerdings nicht direkt vergleichen, da Java Collections nur Referenzen speichern, STL Container dagegen Objekte speichern, was ein wichtiger Unterschied ist.



  • STL container können auch 'nur' referenzen speichern.
    🙂



  • Ctullhu schrieb:

    STL container können auch 'nur' referenzen speichern.
    🙂

    Das würde mein Verständnis von den STL Containern widersprechen (zumindestens wenn du von C++ Referenzen sprichst). Den der Kopiekonstruktor sollte da z.B. sehr problematisch werden.

    Wenn man die Java-Referenzen aber als das Interpretiert was sie eher sind (C++ Zeiger mit Referenz-Syntax) hast du recht. Mit Zeigern können die STL-Container natürlich umgehen...

    cu André



  • oh, das wusste ich nicht. ich dachte immer ein STL container würde keine kopie erzeugen, wenn man ihn für referenzen 'konfiguriert' hat. na gut, dann machen wir's eben mit pointern 😉 (schade in dem fall ist nur, dass C++ keinen GC hat).
    🙂



  • Ctullhu schrieb:

    oh, das wusste ich nicht. ich dachte immer ein STL container würde keine kopie erzeugen, wenn man ihn für referenzen 'konfiguriert' hat. na gut, dann machen wir's eben mit pointern 😉 (schade in dem fall ist nur, dass C++ keinen GC hat).
    🙂

    Statt GC kannst du auch Smart-Pointer verwenden (Schau dir mal Boost an [www.boost.org], konkret shared_ptr [http://www.boost.org/libs/smart_ptr/smart_ptr.htm]). Davon abgesehen vermisse ich in C++ den GC nicht wirklich.

    cu André



  • Ctullhu schrieb:

    ...ich dachte immer ein STL container würde keine kopie erzeugen, wenn man ihn für referenzen 'konfiguriert' hat....

    Nunja, da Letzteres nicht geht, ist es sinnfrei, sich über Ersteres den Kopf zu zerbrechen. 😉

    Gruß,

    Simon2.


Anmelden zum Antworten