Hmmm ... von der anderen Antwort klingt es so, als ob der Vektor nicht als verknüpfte Liste implementiert ist? Habe ich recht? Ich verwende diese Liste als Sammlung, in der ein ziemlich hoher Umsatz an Objekten hinzugefügt und daraus entfernt wird. Ist dieses Array tatsächlich die beste Implementierung? Oder gibt es eine Version mit verknüpfter Liste?
Interstar
4
@interstar - absolut richtig. Wenn Sie wirklich eine Semantik für verknüpfte Listen wünschen, verwenden Sie diese std::list, aber dann verlieren Sie die Indexierbarkeit (nein operator[]), sodass es sich nicht wirklich um ein Array handelt. listdas hat seine eigenen eigenheiten, so dass vectoroft eine bessere wahl ist. In Standard-C ++ - Containern müssen Sie auf die eine oder andere Weise Kompromisse eingehen. Schauen Sie deque, das könnte eine bessere Leistung für Sie bieten. Es ist (relativ) einfach, vectorvs dequevs zu messen, listda sie im Code weitgehend austauschbar sind - verwenden Sie einfach ein typedef für Ihren Container, z typedef vector<MyObj> MyList.
Steve Townsend
Nun, ich werde zuerst den Vektor versuchen. Weil Index nützlich ist. Wenn es zu langsam ist, kann ich zur verknüpften Liste wechseln. Danke
Interstar
2
@interstar ist ArrayList, wie Sie vielleicht anhand des Namens erraten können, auch nicht als verknüpfte Liste implementiert. Sie könnten daran denken LinkedList. Auch wenn Sie einen relativ hohen Umsatz an Objekten haben, die der Liste hinzugefügt und daraus entfernt wurden, ist dies vectormöglicherweise immer noch schneller als listwenn Sie anfangs genügend Speicherplatz dafür zuweisen, damit es nicht neu zugewiesen werden muss (dh geben Sie ihm die maximaler Platz, den es jemals brauchen sollte).
Kyle Strand
@ KyleStrand Das ist interessant. Ich habe immer angenommen, dass ArrayList "eine arraylike Sache, die als verknüpfte Liste implementiert ist" bedeutet, und nicht "eine verknüpfte Liste, die als Array implementiert ist".
Interstar
62
Ein paar zusätzliche Punkte werden hier wiederverwendet vector.
Im Gegensatz zu ArrayListund Arrayin Java müssen Sie nichts Besonderes tun, um vectorein Array zu behandeln. Der zugrunde liegende Speicher in C ++ ist garantiert zusammenhängend und effizient indizierbar.
Im Gegensatz zu ArrayList, ein vectoreffizienten Urtyp ohne Einkapselung als vollwertiges Objekt halten.
Beachten Sie beim Entfernen von Elementen aus a vector, dass die Elemente über dem entfernten Element nach unten verschoben werden müssen, um die zusammenhängende Speicherung zu erhalten. Dies kann bei großen Containern teuer werden.
Stellen Sie beim Speichern komplexer Objekte sicher, vectordass deren Kopierkonstruktor und Zuweisungsoperatoren effizient sind. Unter der Decke verwendet C ++ STL diese während der Containerverwaltung.
Hinweise zur reserve()Speicherung im Voraus (dh zur Vektorkonstruktion oder zur Initialisierungszeit) zur Minimierung der Speicherumverteilung bei einer späteren Erweiterung werden von Java auf C ++ übertragen.
Antworten:
Verwenden Sie die
std::vectorKlasse aus der Standardbibliothek.quelle
std::list, aber dann verlieren Sie die Indexierbarkeit (neinoperator[]), sodass es sich nicht wirklich um ein Array handelt.listdas hat seine eigenen eigenheiten, so dassvectoroft eine bessere wahl ist. In Standard-C ++ - Containern müssen Sie auf die eine oder andere Weise Kompromisse eingehen. Schauen Siedeque, das könnte eine bessere Leistung für Sie bieten. Es ist (relativ) einfach,vectorvsdequevs zu messen,listda sie im Code weitgehend austauschbar sind - verwenden Sie einfach ein typedef für Ihren Container, ztypedef vector<MyObj> MyList.ArrayList, wie Sie vielleicht anhand des Namens erraten können, auch nicht als verknüpfte Liste implementiert. Sie könnten daran denkenLinkedList. Auch wenn Sie einen relativ hohen Umsatz an Objekten haben, die der Liste hinzugefügt und daraus entfernt wurden, ist diesvectormöglicherweise immer noch schneller alslistwenn Sie anfangs genügend Speicherplatz dafür zuweisen, damit es nicht neu zugewiesen werden muss (dh geben Sie ihm die maximaler Platz, den es jemals brauchen sollte).Ein paar zusätzliche Punkte werden hier wiederverwendet
vector.Im Gegensatz zu
ArrayListundArrayin Java müssen Sie nichts Besonderes tun, umvectorein Array zu behandeln. Der zugrunde liegende Speicher in C ++ ist garantiert zusammenhängend und effizient indizierbar.Im Gegensatz zu
ArrayList, einvectoreffizienten Urtyp ohne Einkapselung als vollwertiges Objekt halten.Beachten Sie beim Entfernen von Elementen aus a
vector, dass die Elemente über dem entfernten Element nach unten verschoben werden müssen, um die zusammenhängende Speicherung zu erhalten. Dies kann bei großen Containern teuer werden.Stellen Sie beim Speichern komplexer Objekte sicher,
vectordass deren Kopierkonstruktor und Zuweisungsoperatoren effizient sind. Unter der Decke verwendet C ++ STL diese während der Containerverwaltung.Hinweise zur
reserve()Speicherung im Voraus (dh zur Vektorkonstruktion oder zur Initialisierungszeit) zur Minimierung der Speicherumverteilung bei einer späteren Erweiterung werden von Java auf C ++ übertragen.quelle