Container-Klassen

Einführung

Die Qt-Bibliothek bietet eine Reihe von schablonenbasierten Containerklassen für allgemeine Zwecke. Diese Klassen können verwendet werden, um Elemente eines bestimmten Typs zu speichern. Wenn Sie zum Beispiel ein größenveränderbares Array von QStringbenötigen, verwenden Sie QList<QString>.

Diese Containerklassen sind leichter, sicherer und einfacher zu verwenden als die STL-Container. Wenn Sie mit der STL nicht vertraut sind oder es vorziehen, Dinge auf die "Qt-Art" zu tun, können Sie diese Klassen anstelle der STL-Klassen verwenden.

Die Containerklassen werden implizit gemeinsam genutzt, sind ablaufinvariant und auf Geschwindigkeit, geringen Speicherverbrauch und minimale Inline-Code-Erweiterung optimiert, was zu kleineren ausführbaren Dateien führt. Darüber hinaus sind sie in Situationen, in denen sie von allen Threads, die auf sie zugreifen, als Nur-Lese-Container verwendet werden , thread-sicher.

Die Container bieten Iteratoren für die Durchquerung. Iteratoren im STL-Stil sind die effizientesten und können zusammen mit den generic algorithms von Qt und STL verwendet werden. Iteratoren im Java-Stil werden aus Gründen der Abwärtskompatibilität bereitgestellt.

QList<int> list = {1, 2, 3, 4, 4, 5};
QSet<int> set(list.cbegin(), list.cend());
/*
    Will generate a QSet containing 1, 2, 3, 4, 5.
*/

Die Container-Klassen

Qt bietet die folgenden sequenziellen Container: QList, QStack, und QQueue. Für die meisten Anwendungen ist QList der am besten geeignete Typ. Er bietet sehr schnelle Anhänge. Wenn Sie wirklich eine verknüpfte Liste benötigen, verwenden Sie std::list. QStack und QQueue sind Komfortklassen, die LIFO- und FIFO-Semantik bieten.

Qt bietet auch diese assoziativen Container: QMap, QMultiMap, QHash, QMultiHash, und QSet. Die "Multi"-Container unterstützen auf bequeme Weise mehrere Werte, die mit einem einzigen Schlüssel verbunden sind. Die "Hash"-Container ermöglichen ein schnelleres Nachschlagen, indem sie eine Hash-Funktion anstelle einer binären Suche in einer sortierten Menge verwenden.

Als Sonderfälle bieten die Klassen QCache und QContiguousCache eine effiziente Hash-Suche von Objekten in einem begrenzten Cache-Speicher.

Container können verschachtelt werden. Es ist zum Beispiel durchaus möglich, ein QMap<QString, QList<int>> zu verwenden, wobei der Schlüsseltyp QString und der Wertetyp QList<int> ist.

Die Container werden in einzelnen Header-Dateien mit demselben Namen wie der Container definiert (z. B. <QList>). Der Einfachheit halber werden die Container in <QtContainerFwd> weiterdeklariert.

Die in den verschiedenen Containern gespeicherten Werte können von jedem zuweisbaren Datentyp sein. Um sich zu qualifizieren, muss ein Typ einen Kopierkonstruktor und einen Zuweisungsoperator bereitstellen. Für einige Operationen ist auch ein Standardkonstruktor erforderlich. Dies deckt die meisten Datentypen ab, die Sie wahrscheinlich in einem Container speichern möchten, einschließlich Basistypen wie int und double, Zeigertypen und Qt-Datentypen wie QString, QDate und QTime, aber es deckt nicht QObject oder jede QObject Unterklasse (QWidget, QDialog, QTimer, etc.). Wenn Sie versuchen, eine QList<QWidget> zu instanziieren, wird sich der Compiler beschweren, dass der Kopierkonstruktor und die Zuweisungsoperatoren von QWidget deaktiviert sind. Wenn Sie diese Art von Objekten in einem Container speichern wollen, speichern Sie sie als Zeiger, zum Beispiel als QList<QWidget *>.

Hier ist ein Beispiel für einen benutzerdefinierten Datentyp, der die Anforderung eines zuweisbaren Datentyps erfüllt:

class Employee
{
public:
    Employee() {}
    Employee(const Employee &other);

    Employee &operator=(const Employee &other);

private:
    QString myName;
    QDate myDateOfBirth;
};

Wenn wir keinen Kopierkonstruktor oder Zuweisungsoperator zur Verfügung stellen, bietet C++ eine Standardimplementierung, die eine Kopie von Mitglied zu Mitglied vornimmt. Im obigen Beispiel wäre das ausreichend gewesen. Wenn Sie keine Konstruktoren bereitstellen, bietet C++ einen Standardkonstruktor, der seine Mitglieder mit Standardkonstruktoren initialisiert. Obwohl C++ keine expliziten Konstruktoren oder Zuweisungsoperatoren bereitstellt, kann der folgende Datentyp in einem Container gespeichert werden:

struct Movie
{
    int id;
    QString title;
    QDate releaseDate;
};

Einige Container haben zusätzliche Anforderungen an die Datentypen, die sie speichern können. Zum Beispiel muss der Typ Key eines QMap<Key, T> operator<() bereitstellen. Solche besonderen Anforderungen sind in der detaillierten Beschreibung einer Klasse dokumentiert. In einigen Fällen haben bestimmte Funktionen besondere Anforderungen; diese werden für jede Funktion einzeln beschrieben. Der Compiler wird immer einen Fehler ausgeben, wenn eine Anforderung nicht erfüllt ist.

Die Container von Qt bieten operator<<() und operator>>(), so dass sie einfach mit QDataStream gelesen und geschrieben werden können. Das bedeutet, dass die im Container gespeicherten Datentypen ebenfalls operator<<() und operator>>() unterstützen müssen. Die Bereitstellung einer solchen Unterstützung ist einfach; hier sehen Sie, wie wir dies für die obige Movie-Struktur tun können:

QDataStream &operator<<(QDataStream &out, const Movie &movie)
{
    out << (quint32)movie.id << movie.title
        << movie.releaseDate;
    return out;
}

QDataStream &operator>>(QDataStream &in, Movie &movie)
{
    quint32 id;
    QDate date;

    in >> id >> movie.title >> date;
    movie.id = (int)id;
    movie.releaseDate = date;
    return in;
}

Die Dokumentation bestimmter Funktionen von Containerklassen verweist auf standardmäßig konstruierte Werte; zum Beispiel initialisiert QList seine Elemente automatisch mit standardmäßig konstruierten Werten, und QMap::value() gibt einen standardmäßig konstruierten Wert zurück, wenn der angegebene Schlüssel nicht in der Map enthalten ist. Für die meisten Wertetypen bedeutet dies einfach, dass ein Wert mit dem Standardkonstruktor erstellt wird (z. B. eine leere Zeichenkette für QString). Aber für primitive Typen wie int und double sowie für Zeigertypen gibt die Sprache C++ keine Initialisierung vor; in diesen Fällen initialisieren die Container von Qt den Wert automatisch auf 0.

Iteration über Containern

Bereichsbasiert für

Die bereichsbasierte for sollte vorzugsweise für Container verwendet werden:

QList<QString> list = {"A", "B", "C", "D"};
for (const auto &item : list) {
   ...
}

Beachten Sie, dass bei der Verwendung eines Qt-Containers in einem nicht-konstanten Kontext die implizite Freigabe zu einem unerwünschten Ablösen des Containers führen kann. Um dies zu verhindern, verwenden Sie std::as_const():

QList<QString> list = {"A", "B", "C", "D"};
for (const auto &item : std::as_const(list)) {
    ...
}

Bei assoziativen Containern führt dies zu einer Schleife über die Werte.

Indexbasiert

Bei sequentiellen Containern, die ihre Elemente zusammenhängend im Speicher speichern (z. B. QList), kann die indexbasierte Iteration verwendet werden:

QList<QString> list = {"A", "B", "C", "D"};
for (qsizetype i = 0; i < list.size(); ++i) {
    const auto &item = list.at(i);
    ...
}

Die Iterator-Klassen

Iteratoren bieten ein einheitliches Mittel zum Zugriff auf Elemente in einem Container. Die Containerklassen von Qt bieten zwei Arten von Iteratoren: Iteratoren im STL-Stil und Iteratoren im Java-Stil. Iteratoren beider Typen werden ungültig, wenn die Daten im Container verändert oder von implizit gemeinsam genutzten Kopien aufgrund eines Aufrufs einer nicht-konstanten Mitgliedsfunktion getrennt werden.

Iteratoren im STL-Stil

STL-ähnliche Iteratoren sind seit der Veröffentlichung von Qt 2.0 verfügbar. Sie sind kompatibel mit der generic algorithms von Qt und STL und sind auf Geschwindigkeit optimiert.

Für jede Containerklasse gibt es zwei STL-ähnliche Iteratortypen: einen, der nur Lesezugriff bietet und einen, der Lese- und Schreibzugriff bietet. Nur-Lese-Iteratoren sollten nach Möglichkeit verwendet werden, da sie schneller sind als Schreib-Lese-Iteratoren.

Die API der STL-Iteratoren ist den Zeigern in einem Array nachempfunden. Der Operator ++ beispielsweise bringt den Iterator zum nächsten Element weiter, und der Operator * gibt das Element zurück, auf das der Iterator zeigt. Für QList und QStack, die ihre Elemente an benachbarten Speicherpositionen speichern, ist der Typ iterator nur ein Typedef für T *, und der Typ const_iterator ist nur ein Typedef für const T *.

In dieser Diskussion werden wir uns auf QList und QMap konzentrieren. Die Iterator-Typen für QSet haben genau die gleiche Schnittstelle wie die Iteratoren von QList; ebenso haben die Iterator-Typen für QHash die gleiche Schnittstelle wie die Iteratoren von QMap.

Hier ist eine typische Schleife, die alle Elemente eines QList<QString> der Reihe nach durchläuft und sie in Kleinbuchstaben umwandelt:

QList<QString> list = {"A", "B", "C", "D"};

for (auto i = list.begin(), end = list.end(); i != end; ++i)
    *i = (*i).toLower();

Iteratoren im STL-Stil zeigen direkt auf Elemente. Die Funktion begin() eines Containers gibt einen Iterator zurück, der auf das erste Element des Containers zeigt. Die Funktion end() eines Containers gibt einen Iterator zurück, der auf das imaginäre Element eine Position hinter dem letzten Element des Containers zeigt. end() markiert eine ungültige Position; sie darf niemals dereferenziert werden. Sie wird normalerweise in der Abbruchbedingung einer Schleife verwendet. Wenn die Liste leer ist, ist begin() gleich end(), so dass wir die Schleife nie ausführen.

Das folgende Diagramm zeigt die gültigen Iteratorpositionen als rote Pfeile für eine Liste mit vier Elementen:

Die Rückwärts-Iteration mit einem STL-artigen Iterator erfolgt mit umgekehrten Iteratoren:

QList<QString> list = {"A", "B", "C", "D"};

for (auto i = list.rbegin(), rend = list.rend(); i != rend; ++i)
    *i = i->toLower();

In den bisherigen Codeschnipseln haben wir den unären Operator * verwendet, um das an einer bestimmten Iteratorposition gespeicherte Element (vom Typ QString) abzurufen, und wir haben dann QString::toLower() dafür aufgerufen.

Für schreibgeschützten Zugriff können Sie const_iterator, cbegin() und cend() verwenden. Ein Beispiel:

for(auto i = list.cbegin(), end = list.cend(); i != end;++i)    qDebug() << *i;

Die folgende Tabelle fasst die API der Iteratoren im STL-Stil zusammen:

Die Operatoren ++ und -- sind sowohl als Präfix- (++i, --i) als auch als Postfix-Operatoren (i++, i--) verfügbar. Die Präfix-Versionen verändern die Iteratoren und geben einen Verweis auf den veränderten Iterator zurück; die Postfix-Versionen nehmen eine Kopie des Iterators, bevor sie ihn verändern, und geben diese Kopie zurück. In Ausdrücken, bei denen der Rückgabewert ignoriert wird, empfehlen wir die Verwendung der Präfix-Operatoren (++i, --i), da diese etwas schneller sind.

Bei nicht-konstanten Iterator-Typen kann der Rückgabewert des unären Operators * auf der linken Seite des Zuweisungsoperators verwendet werden.

Bei QMap und QHash gibt der Operator * die Wertkomponente eines Elements zurück. Wenn Sie den Schlüssel abrufen wollen, rufen Sie key() für den Iterator auf. Aus Gründen der Symmetrie bieten die Iterator-Typen auch eine value()-Funktion zum Abrufen des Wertes. So würden wir zum Beispiel alle Elemente in einer QMap auf der Konsole ausgeben:

QMap<int,  int> map;...for(auto i = map.cbegin(), end = map.cend(); i != end;++i)    qDebug() << i.key() << ':' << i.value();

Dank der impliziten Freigabe ist es für eine Funktion sehr kostengünstig, einen Container pro Wert zurückzugeben. Die Qt-API enthält Dutzende von Funktionen, die pro Wert einen QList oder QStringList zurückgeben (z.B. QSplitter::sizes()). Wenn Sie mit einem STL-Iterator über diese iterieren wollen, sollten Sie immer eine Kopie des Containers nehmen und über die Kopie iterieren. Zum Beispiel:

// RIGHT
const QList<int> sizes = splitter->sizes();
for (auto i = sizes.begin(), end = sizes.end(); i != end; ++i)
    ...

// WRONG
for (auto i = splitter->sizes().begin();
        i != splitter->sizes().end(); ++i)
    ...

Dieses Problem tritt nicht bei Funktionen auf, die eine const- oder non-const-Referenz auf einen Container zurückgeben.

Implizites Iterator-Problem bei der gemeinsamen Nutzung

Implizites Teilen hat eine weitere Konsequenz für STL-artige Iteratoren: Sie sollten es vermeiden, einen Container zu kopieren, während Iteratoren auf diesem Container aktiv sind. Die Iteratoren zeigen auf eine interne Struktur, und wenn Sie einen Container kopieren, sollten Sie sehr vorsichtig mit Ihren Iteratoren sein. Z.B.:

QList<int> a, b;
a.resize(100000); // make a big list filled with 0.

QList<int>::iterator i = a.begin();
// WRONG way of using the iterator i:
b = a;
/*
    Now we should be careful with iterator i since it will point to shared data
    If we do *i = 4 then we would change the shared instance (both vectors)
    The behavior differs from STL containers. Avoid doing such things in Qt.
*/

a[0] = 5;
/*
    Container a is now detached from the shared data,
    and even though i was an iterator from the container a, it now works as an iterator in b.
    Here the situation is that (*i) == 0.
*/

b.clear(); // Now the iterator i is completely invalid.

int j = *i; // Undefined behavior!
/*
    The data from b (which i pointed to) is gone.
    This would be well-defined with STL containers (and (*i) == 5),
    but with QList this is likely to crash.
*/

Das obige Beispiel zeigt nur ein Problem mit QList, aber das Problem besteht für alle implizit gemeinsam genutzten Qt Container.

Iteratoren im Java-Stil

Java-Style Iteratoren sind den Iterator-Klassen von Java nachempfunden. Neuer Code sollte STL-Style Iteratoren bevorzugen.

Qt-Container im Vergleich zu Standard-Containern

Qt-Container und std-Algorithmen

Sie können Qt-Container mit Funktionen von #include <algorithm> verwenden.

QList<int> list = {2, 3, 1};

std::sort(list.begin(), list.end());
/*
    Sort the list, now contains { 1, 2, 3 }
*/

std::reverse(list.begin(), list.end());
/*
    Reverse the list, now contains { 3, 2, 1 }
*/

int even_elements =
        std::count_if(list.begin(), list.end(), [](int element) { return (element % 2 == 0); });
/*
    Count how many elements that are even numbers, 1
*/

Andere Container-ähnliche Klassen

Qt enthält weitere Template-Klassen, die in mancher Hinsicht Containern ähneln. Diese Klassen bieten keine Iteratoren und können nicht mit dem Schlüsselwort foreach verwendet werden.

• QCache<Key, T> bietet einen Cache zum Speichern von Objekten eines bestimmten Typs T, die mit Schlüsseln des Typs Key verbunden sind.
• QContiguousCache<T> bietet eine effiziente Möglichkeit zur Zwischenspeicherung von Daten, auf die normalerweise zusammenhängend zugegriffen wird.

Weitere Nicht-Template-Typen, die mit den Template-Containern von Qt konkurrieren, sind QBitArray, QByteArray, QString und QStringList.

Algorithmische Komplexität

Bei der algorithmischen Komplexität geht es darum, wie schnell (oder langsam) jede Funktion ist, wenn die Anzahl der Elemente im Container wächst. Zum Beispiel ist das Einfügen eines Elements in der Mitte einer std::list eine extrem schnelle Operation, unabhängig von der Anzahl der in der Liste gespeicherten Elemente. Andererseits ist das Einfügen eines Elements in der Mitte einer QList potenziell sehr teuer, wenn die QList viele Elemente enthält, da die Hälfte der Elemente um eine Position im Speicher verschoben werden muss.

Zur Beschreibung der algorithmischen Komplexität verwenden wir die folgende Terminologie, die auf der "Big Oh"-Notation basiert:

• Konstante Zeit: O(1). Eine Funktion läuft in konstanter Zeit ab, wenn sie unabhängig von der Anzahl der Elemente im Container die gleiche Zeit benötigt. Ein Beispiel ist QList::push_back().
• Logarithmische Zeit: O(log n). Eine Funktion, die in logarithmischer Zeit läuft, ist eine Funktion, deren Laufzeit proportional zum Logarithmus der Anzahl der Elemente im Container ist. Ein Beispiel ist der binäre Suchalgorithmus.
• Lineare Zeit: O(n). Eine Funktion, die in linearer Zeit läuft, wird in einer Zeit ausgeführt, die direkt proportional zur Anzahl der im Container gespeicherten Elemente ist. Ein Beispiel dafür ist QList::insert().
• Linear-logarithmische Zeit: O(n log n). Eine Funktion, die in linear-logarithmischer Zeit ausgeführt wird, ist asymptotisch langsamer als eine Funktion mit linearer Zeit, aber schneller als eine Funktion mit quadratischer Zeit.
• Quadratische Zeit: O(n²). Eine Funktion mit quadratischer Zeit wird in einer Zeit ausgeführt, die proportional zum Quadrat der Anzahl der im Container gespeicherten Elemente ist.

Die folgende Tabelle gibt einen Überblick über die algorithmische Komplexität des sequentiellen Containers QList<T>:

In der Tabelle steht "Amort." für "amortisiertes Verhalten". Zum Beispiel bedeutet "Amort. O(1)" bedeutet z. B., dass Sie bei einmaligem Aufruf der Funktion ein Verhalten von O(n) erhalten, bei mehrfachem Aufruf (z. B. n-mal ) jedoch ein durchschnittliches Verhalten von O(1).

Die folgende Tabelle fasst die algorithmische Komplexität der assoziativen Container und Sets von Qt zusammen:

Mit QList, QHash und QSet wird die Leistung des Anhängens von Elementen mit O(log n) amortisiert. Sie kann auf O(1) gesenkt werden, indem Sie QList::reserve(), QHash::reserve() oder QSet::reserve() mit der erwarteten Anzahl von Elementen aufrufen, bevor Sie die Elemente einfügen. Der nächste Abschnitt befasst sich eingehender mit diesem Thema.

Optimierungen für primitive und verschiebbare Typen

Qt-Container können optimierte Codepfade verwenden, wenn die gespeicherten Elemente verschiebbar oder sogar primitiv sind. Ob Typen primitiv oder verschiebbar sind, kann jedoch nicht in allen Fällen erkannt werden. Sie können Ihre Typen als primitiv oder relocatable deklarieren, indem Sie das Q_DECLARE_TYPEINFO Makro mit dem Q_PRIMITIVE_TYPE Flag oder dem Q_RELOCATABLE_TYPE Flag verwenden. Siehe die Dokumentation von Q_DECLARE_TYPEINFO für weitere Details und Anwendungsbeispiele.

Wenn Sie Q_DECLARE_TYPEINFO nicht verwenden, wird Qt std::is_trivial_v<T> verwenden, um primitive Typen zu identifizieren, und es wird sowohl std::is_trivially_copyable_v<T> als auch std::is_trivially_destructible_v<T> benötigen, um verschiebbare Typen zu identifizieren. Dies ist immer eine sichere Wahl, wenn auch mit möglicherweise suboptimaler Leistung.

Wachstums-Strategien

QList<T>, QString und QByteArray speichern ihre Elemente zusammenhängend im Speicher; QHash<Key, T> führt eine Hash-Tabelle, deren Größe proportional zur Anzahl der Elemente im Hash ist. Um zu vermeiden, dass die Daten jedes Mal neu zugewiesen werden, wenn ein Element am Ende des Containers hinzugefügt wird, weisen diese Klassen in der Regel mehr Speicher als nötig zu.

Betrachten Sie den folgenden Code, der eine QString aus einer anderen QString aufbaut:

QString onlyLetters(const QString &in)
{
    QString out;
    for (qsizetype j = 0; j < in.size(); ++j) {
        if (in.at(j).isLetter())
            out += in.at(j);
    }
    return out;
}

Wir bauen die Zeichenkette out dynamisch auf, indem wir jeweils ein Zeichen an sie anhängen. Nehmen wir an, dass wir 15000 Zeichen an die Zeichenfolge QString anhängen. Dann kommt es zu den folgenden 11 Neuzuweisungen (von 15000 möglichen), wenn QString keinen Platz mehr hat: 8, 24, 56, 120, 248, 504, 1016, 2040, 4088, 8184, 16376. Am Ende hat die QString 16376 Unicode-Zeichen zugewiesen, von denen 15000 belegt sind.

Die obigen Werte mögen ein wenig seltsam erscheinen, aber es gibt ein Leitprinzip. Es schreitet voran, indem es die Größe jedes Mal verdoppelt. Genauer gesagt, wird die nächste Zweierpotenz minus 16 Bytes erreicht. 16 Bytes entsprechen acht Zeichen, da QString intern UTF-16 verwendet.

QByteArray verwendet denselben Algorithmus wie QString, aber 16 Bytes entsprechen 16 Zeichen.

QList<T> verwendet ebenfalls diesen Algorithmus, aber 16 Bytes entsprechen 16/sizeof(T)-Elementen.

QHash<Key, T> ist ein völlig anderer Fall. QHash Die interne Hash-Tabelle von <Key, T> wächst mit Zweierpotenzen, und jedes Mal, wenn sie wächst, werden die Elemente in einen neuen Bereich verschoben, der als qHash(Schlüssel) % QHash::capacity() (die Anzahl der Bereiche) berechnet wird. Diese Bemerkung gilt auch für QSet<T> und QCache<Schlüssel, T>.

Für die meisten Anwendungen ist der Standard-Algorithmus von Qt ausreichend. Wenn Sie mehr Kontrolle benötigen, bieten QList<T>, QHash<Key, T>, QSet<T>, QString und QByteArray eine Reihe von Funktionen, mit denen Sie überprüfen und festlegen können, wie viel Speicher für die Speicherung der Elemente verwendet werden soll:

• capacity() gibt die Anzahl der Elemente zurück, für die Speicher zugewiesen wird (für QHash und QSet die Anzahl der Bereiche in der Hashtabelle).
• reserve(size) weist explizit Speicher für size-Elemente vor.
• squeeze() gibt den Speicher frei, der nicht für die Speicherung der Elemente benötigt wird.

Wenn Sie ungefähr wissen, wie viele Elemente Sie in einem Container speichern wollen, können Sie mit dem Aufruf von reserve() beginnen, und wenn Sie mit dem Auffüllen des Containers fertig sind, können Sie squeeze() aufrufen, um den zusätzlichen, vorab zugewiesenen Speicher freizugeben.