QVector vs QList

Ich habe eine Liste von Ganzzahlen, über die ich iterieren muss, aber ein Array ist nicht ausreichend. Was sind die Unterschiede zwischen vectorsund listsund gibt es etwas, das ich wissen muss, bevor ich einen Typ auswähle?

Um ganz klar zu sein, ich habe die QT-Dokumente gelesen, aber das ist der Umfang dessen, was ich weiß:

QList<T>, QLinkedList<T>Und QVector<T>bietet eine ähnliche Funktionalität. Hier ist eine Übersicht:

• Für die meisten Zwecke QListist die richtige Klasse zu verwenden. Die indexbasierte API ist praktischer als die QLinkedList'siteratorbasierte API und normalerweise schneller als QVectoraufgrund der Art und Weise, wie die Elemente im Speicher gespeichert werden. Es wird auch auf weniger Code in Ihrer ausführbaren Datei erweitert.
• Wenn Sie eine echte verknüpfte Liste mit Garantien für konstante Zeiteinfügungen in der Mitte der Liste und Iteratoren für Elemente anstelle von Indizes benötigen, verwenden Sie QLinkedList.
• Wenn Sie möchten, dass die Elemente benachbarte Speicherpositionen einnehmen, verwenden Sie QVector.

QVectorist meistens analog zu std::vector, wie Sie aus dem Namen erraten können. QListist näher an boost::ptr_deque, trotz der offensichtlichen Assoziation mit std::list. Objekte werden nicht direkt gespeichert, sondern Zeiger auf sie. Sie profitieren von allen Vorteilen des schnellen Einfügens an beiden Enden, und bei Neuzuweisungen werden Zeiger anstelle von Kopierkonstruktoren gemischt, verlieren jedoch die räumliche Lokalität eines tatsächlichen std::dequeoder std::vectorund erhalten viele Heap-Zuweisungen. Es gibt einige Entscheidungen, um die Heap-Zuweisungen für kleine Objekte zu vermeiden und die räumliche Lokalität wiederzugewinnen, aber soweit ich weiß, gilt dies nur für Dinge, die kleiner als ein sind int.

QLinkedListist analog zu std::listund hat alle Nachteile. Im Allgemeinen sollte dies Ihre letzte Wahl für einen Container sein.

In der QT-Bibliothek wird die Verwendung von QListObjekten stark bevorzugt. Wenn Sie sie also in Ihrem eigenen Code bevorzugen, können Sie manchmal unnötige Langeweile vermeiden. Die zusätzliche Heap-Verwendung und die zufällige Positionierung der tatsächlichen Daten können unter bestimmten Umständen theoretisch schaden, sind jedoch häufig nicht bemerkbar. Daher würde ich vorschlagen, QListbis die Profilerstellung einen Wechsel zu a vorschlägt QVector. Wenn Sie erwarten, dass eine zusammenhängende Zuordnung wichtig ist [lesen Sie: Sie arbeiten mit Code zusammen, der ein T[]statt eines erwartet QList<T>], kann dies auch ein Grund sein, sofort damit zu beginnen QVector.

Wenn Sie allgemein nach Containern fragen und nur die QT-Dokumente als Referenz verwenden, sind die oben genannten Informationen weniger nützlich.

An std::vectorist ein Array, dessen Größe Sie ändern können. Alle Elemente werden nebeneinander gespeichert, und Sie können schnell auf einzelne Elemente zugreifen. Der Nachteil ist, dass Einfügungen nur an einem Ende effizient sind. Wenn Sie etwas in die Mitte oder am Anfang stellen, müssen Sie die anderen Objekte kopieren, um Platz zu schaffen. In der Big-Oh-Notation ist die Einfügung am Ende O (1), die Einfügung an einer anderen Stelle O (N) und der Direktzugriff O (1).

An std::dequeist ähnlich, garantiert jedoch nicht, dass Objekte nebeneinander gespeichert werden, und ermöglicht das Einfügen an beiden Enden als O (1). Es müssen auch kleinere Speicherblöcke gleichzeitig zugewiesen werden, was manchmal wichtig sein kann. Der Direktzugriff ist O (1) und die Einfügung in der Mitte ist O (N), wie bei a vector. Die räumliche Lokalität ist schlechter als std::vector, aber Objekte sind in der Regel gruppiert, sodass Sie einige Vorteile erzielen.

An std::listist eine verknüpfte Liste. Es erfordert den größten Speicheraufwand der drei sequentiellen Standardcontainer, bietet jedoch eine schnelle Einfügung überall ... vorausgesetzt, Sie wissen im Voraus, wo Sie einfügen müssen. Es bietet keinen zufälligen Zugriff auf einzelne Elemente, daher müssen Sie in O (N) iterieren. Dort angekommen ist die tatsächliche Einfügung jedoch O (1). Der größte Vorteil std::listbesteht darin, dass Sie sie schnell zusammenfügen können. Wenn Sie einen gesamten Wertebereich auf einen anderen verschieben std::list, ist die gesamte Operation O (1). Es ist auch viel schwieriger, Verweise in der Liste ungültig zu machen, was manchmal wichtig sein kann.

Als allgemeine Regel gilt, ziehe ich std::dequean std::vector, wenn ich die Daten in eine Bibliothek übergeben müssen in der Lage sein , die ein rohes Array erwartet. std::vectorist garantiert zusammenhängend, &v[0]funktioniert also für diesen Zweck. Ich erinnere mich nicht an das letzte Mal, als ich ein verwendet habe std::list, aber es war fast sicher, weil ich die stärkere Garantie dafür brauchte, dass Referenzen gültig bleiben.

Dinge haben sich geändert

Wir sind jetzt in Qt 5.8 und die Dinge haben sich geändert, also die Dokumentation. Es gibt eine klare und andere Antwort auf diese Frage:

QVector sollte Ihre erste Wahl sein. QVector<T>QList<Tbietet normalerweise eine bessere Leistung als >, da QVector<T>die Elemente immer nacheinander im Speicher gespeichert werden, wobei QList<T>die Elemente auf dem Heap zugewiesen werden, es sei denn, sizeof(T) <= sizeof(void*)T wurde als a Q_MOVABLE_TYPEoder Q_PRIMITIVE_TYPEusing deklariert Q_DECLARE_TYPEINFO.

QListEine Erklärung finden Sie in den Vor- und Nachteilen der Verwendung . Wird QListjedoch in allen Qt-APIs zum Übergeben von Parametern und zum Zurückgeben von Werten verwendet. VerwendenQList diese Schnittstelle, um mit diesen APIs zu kommunizieren.

In QVectorist ähnlich wie std::vector. QLinkedListist ähnlich wie std::list. QListist ein indexbasierter Vektor, aber die Speicherposition ist nicht garantiert (wie std::deque).

Aus dem QtList-Dokument:

• QListe, die in den meisten Fällen verwendet werden soll. Ermöglicht bei Strukturen mit tausend Elementen ein effizientes Einfügen in die Mitte und bietet indizierten Zugriff. prepend()und append()sehr schnell, da der Speicher an beiden Enden des internen Arrays vorbelegt ist. QList<T>ist ein Array von Zeigern vom Typ T. Wenn T einen Zeiger oder einen gemeinsam genutzten Qt-ähnlichen Zeigertyp hat, wird das Objekt direkt im Array gespeichert

• QVectorDies ist vorzuziehen, wenn viele append()oder insert()neue Elemente größer als ein Zeiger sind, da QVectorder Speicher für seine Elemente in einer einzigen Heap-Zuordnung zugewiesen wird. Für das QListEinfügen des Anhängens eines neuen Elements ist die Speicherzuweisung des neuen Elements auf dem Heap erforderlich. Kurz gesagt, wenn Sie möchten, dass die Elemente benachbarte Speicherpositionen einnehmen, oder wenn Ihre Elemente größer als ein Zeiger sind und Sie den Aufwand vermeiden möchten, sie beim Einfügen einzeln auf dem Heap zuzuweisen, verwenden Sie QVector.

QVector ist wie ein Array, dessen Größe sich ändern kann (vergrößert oder verkleinert), das jedoch mit hohen Transaktionen, Berechnungen und Zeit verbunden ist.

Wenn Sie beispielsweise ein Element hinzufügen möchten, wird ein neues Array erstellt, alle Elemente werden in ein neues Array kopiert, das neue Element wird am Ende hinzugefügt und das alte Array wird gelöscht. Und umgekehrt auch zum Löschen.

Funktioniert jedoch QLinkedListmit Zeigern. Wenn also ein neues Element erstellt wird, wird nur ein neuer Speicherplatz zugewiesen und mit dem einzigen Speicherblock verknüpft. Da es mit Zeigern arbeitet, ist es schneller und effizienter.

Wenn Sie eine Liste von Elementen haben, von denen Sie nicht erwarten, dass sie die Größe stark ändern, QVectorist dies wahrscheinlich gut, wird aber normalerweise QLinkedListfür die meisten Zwecke verwendet.