Classes de conteneurs

Introduction

La bibliothèque Qt fournit un ensemble de classes de conteneurs d'usage général basées sur des modèles. Ces classes peuvent être utilisées pour stocker des éléments d'un type spécifique. Par exemple, si vous avez besoin d'un tableau redimensionnable de QStrings, utilisez QList<QString>.

Ces classes de conteneurs sont conçues pour être plus légères, plus sûres et plus faciles à utiliser que les conteneurs STL. Si vous n'êtes pas familier avec la STL, ou si vous préférez faire les choses "à la manière de Qt", vous pouvez utiliser ces classes à la place des classes STL.

Les classes conteneurs sont implicitement partagées, elles sont réentrantes et elles sont optimisées pour la vitesse, une faible consommation de mémoire et une expansion minimale du code en ligne, ce qui permet d'obtenir des exécutables plus petits. En outre, elles sont sûres pour les threads dans les situations où elles sont utilisées comme conteneurs en lecture seule par tous les threads qui y accèdent.

Les conteneurs fournissent des itérateurs pour la traversée. Les itérateurs de style STL sont les plus efficaces et peuvent être utilisés avec ceux de Qt XML et de STL generic algorithms. Les itérateurs de style Java sont fournis à des fins de rétrocompatibilité.

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.
*/

Les classes de conteneurs

Qt fournit les conteneurs séquentiels suivants : QList, QStack, et QQueue. Pour la plupart des applications, QList est le meilleur type à utiliser. Il permet des ajouts très rapides. Si vous avez vraiment besoin d'une liste chaînée, utilisez std::list. QStack et QQueue sont des classes de commodité qui fournissent une sémantique LIFO et FIFO.

Qt fournit également ces conteneurs associatifs : QMap, QMultiMap, QHash, QMultiHash, et QSet. Les conteneurs "Multi" prennent en charge plusieurs valeurs associées à une seule clé. Les conteneurs "Hash" permettent une recherche plus rapide en utilisant une fonction de hachage au lieu d'une recherche binaire sur un ensemble trié.

Dans des cas particuliers, les classes QCache et QContiguousCache permettent une recherche efficace par hachage d'objets dans une mémoire cache limitée.

Les conteneurs peuvent être imbriqués. Par exemple, il est parfaitement possible d'utiliser un conteneur QMap<QString, QList<int>>, dont le type de clé est QString et le type de valeur QList<int>.

Les conteneurs sont définis dans des fichiers d'en-tête individuels portant le même nom que le conteneur (par exemple, <QList>). Pour des raisons de commodité, les conteneurs sont déclarés à l'avance dans <QtContainerFwd>.

Les valeurs stockées dans les différents conteneurs peuvent être de n'importe quel type de données assignable. Pour être éligible, un type doit fournir un constructeur de copie et un opérateur d'affectation. Pour certaines opérations, un constructeur par défaut est également requis. Cela couvre la plupart des types de données que vous voudrez probablement stocker dans un conteneur, y compris les types de base tels que int et double, les types de pointeurs et les types de données Qt XML tels que QString, QDate et QTime, mais cela ne couvre pas QObject ou toute sous-classe de QObject (QWidget, QDialog, QTimer, etc.). Si vous tentez d'instancier un QList<QWidget>, le compilateur vous signalera que le constructeur de copie et les opérateurs d'affectation de QWidget sont désactivés. Si vous souhaitez stocker ce type d'objets dans un conteneur, stockez-les sous forme de pointeurs, par exemple sous la forme QList<QWidget *>.

Voici un exemple de type de données personnalisé qui répond aux exigences d'un type de données assignable :

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

    Employee &operator=(const Employee &other);

private:
    QString myName;
    QDate myDateOfBirth;
};

Si nous ne fournissons pas de constructeur de copie ou d'opérateur d'affectation, le C++ propose une implémentation par défaut qui effectue une copie membre par membre. Dans l'exemple ci-dessus, cela aurait été suffisant. De même, si vous ne fournissez aucun constructeur, le C++ fournit un constructeur par défaut qui initialise son membre à l'aide de constructeurs par défaut. Bien qu'il ne fournisse aucun constructeur explicite ni opérateur d'affectation, le type de données suivant peut être stocké dans un conteneur :

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

Certains conteneurs ont des exigences supplémentaires concernant les types de données qu'ils peuvent stocker. Par exemple, le type Key d'un QMap<Key, T> doit fournir operator<(). Ces exigences particulières sont documentées dans la description détaillée d'une classe. Dans certains cas, des fonctions spécifiques ont des exigences particulières ; celles-ci sont décrites pour chaque fonction. Le compilateur émettra toujours une erreur si une exigence n'est pas respectée.

Les conteneurs de Qt fournissent operator<<() et operator>>() afin qu'ils puissent être facilement lus et écrits à l'aide d'un QDataStream. Cela signifie que les types de données stockés dans le conteneur doivent également prendre en charge operator<<() et operator>>(). Il est facile de fournir un tel support ; voici comment nous pourrions le faire pour la structure Movie ci-dessus :

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;
}

La documentation de certaines fonctions de classe de conteneur fait référence à des valeurs construites par défaut; par exemple, QList initialise automatiquement ses éléments avec des valeurs construites par défaut, et QMap::value() renvoie une valeur construite par défaut si la clé spécifiée ne se trouve pas dans la carte. Pour la plupart des types de valeurs, cela signifie simplement qu'une valeur est créée à l'aide du constructeur par défaut (par exemple, une chaîne vide pour QString). Mais pour les types primitifs comme int et double, ainsi que pour les types pointeurs, le langage C++ ne spécifie aucune initialisation ; dans ces cas, les conteneurs de Qt XML initialisent automatiquement la valeur à 0.

Itération sur les conteneurs

Basé sur l'intervalle pour

Il est préférable d'utiliser for pour les conteneurs :

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

Notez que lors de l'utilisation d'un conteneur Qt dans un contexte non-const, le partage implicite peut effectuer un détachement indésirable du conteneur. Pour éviter cela, utilisez std::as_const():

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

Pour les conteneurs associatifs, ceci bouclera sur les valeurs.

Basé sur un index

Pour les conteneurs séquentiels qui stockent leurs éléments de manière contiguë en mémoire (par exemple, QList), l'itération basée sur un index peut être utilisée :

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

Les classes d'itérateurs

Les itérateurs fournissent un moyen uniforme d'accéder aux éléments d'un conteneur. Les classes de conteneurs de Qt fournissent deux types d'itérateurs : Les itérateurs de style STL et les itérateurs de style Java. Les itérateurs des deux types sont invalidés lorsque les données du conteneur sont modifiées ou détachées des copies implicitement partagées suite à un appel à une fonction membre non-const.

Itérateurs de style STL

Les itérateurs de type STL sont disponibles depuis la sortie de Qt 2.0. Ils sont compatibles avec Qt XML et STL generic algorithms et sont optimisés pour la vitesse.

Pour chaque classe de conteneur, il existe deux types d'itérateurs de style STL : un qui fournit un accès en lecture seule et un qui fournit un accès en lecture-écriture. Les itérateurs en lecture seule doivent être utilisés dans la mesure du possible, car ils sont plus rapides que les itérateurs en lecture-écriture.

L'API des itérateurs STL s'inspire des pointeurs dans un tableau. Par exemple, l'opérateur ++ fait passer l'itérateur à l'élément suivant, et l'opérateur * renvoie l'élément vers lequel pointe l'itérateur. En fait, pour QList et QStack, qui stockent leurs éléments à des positions mémoire adjacentes, le type iterator n'est qu'un typedef pour T *, et le type const_iterator n'est qu'un typedef pour const T *.

Dans cette discussion, nous nous concentrerons sur QList et QMap. Les types d'itérateurs pour QSet ont exactement la même interface que les itérateurs de QList; de même, les types d'itérateurs pour QHash ont la même interface que les itérateurs de QMap.

Voici une boucle typique pour parcourir tous les éléments d'un QList<QString> dans l'ordre et les convertir en minuscules :

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

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

Les itérateurs de style STL pointent directement sur les éléments. La fonction begin() d'un conteneur renvoie un itérateur qui pointe sur le premier élément du conteneur. La fonction end() d'un conteneur renvoie un itérateur vers l'élément imaginaire situé une position après le dernier élément du conteneur. end() marque une position invalide ; elle ne doit jamais être déréférencée. Elle est généralement utilisée dans la condition de rupture d'une boucle. Si la liste est vide, begin() est égal à end(), de sorte que la boucle n'est jamais exécutée.

Le diagramme ci-dessous montre les positions valides de l'itérateur sous forme de flèches rouges pour une liste contenant quatre éléments :

L'itération vers l'arrière avec un itérateur de style STL se fait avec des itérateurs inversés :

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

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

Dans les extraits de code présentés jusqu'à présent, nous avons utilisé l'opérateur unaire * pour récupérer l'élément (de type QString) stocké à une certaine position de l'itérateur, puis nous avons appelé QString::toLower() sur cet élément.

Pour un accès en lecture seule, vous pouvez utiliser const_iterator, cbegin() et cend(). Voici un exemple :

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

Le tableau suivant résume l'API des itérateurs de style STL :

Les opérateurs ++ et -- sont disponibles à la fois comme opérateurs préfixes (++i, --i) et postfixes (i++, i--). Les versions préfixes modifient les itérateurs et renvoient une référence à l'itérateur modifié ; les versions postfixes prennent une copie de l'itérateur avant de le modifier et renvoient cette copie. Dans les expressions où la valeur de retour est ignorée, nous vous recommandons d'utiliser les opérateurs préfixes (++i, --i), qui sont légèrement plus rapides.

Pour les itérateurs non constants, la valeur de retour de l'opérateur unaire * peut être utilisée du côté gauche de l'opérateur d'affectation.

Pour QMap et QHash, l'opérateur * renvoie la valeur d'un élément. Si vous souhaitez récupérer la clé, appelez key() sur l'itérateur. Par symétrie, les types d'itérateurs fournissent également une fonction value() pour récupérer la valeur. Par exemple, voici comment imprimer tous les éléments d'un site QMap sur la console :

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

Grâce au partage implicite, il est très peu coûteux pour une fonction de renvoyer un conteneur par valeur. L'API Qt XML contient des dizaines de fonctions qui renvoient un QList ou un QStringList par valeur (par exemple, QSplitter::sizes()). Si vous souhaitez itérer sur ces fonctions à l'aide d'un itérateur STL, vous devez toujours prendre une copie du conteneur et itérer sur la copie. Par exemple :

// 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)
    {/*...*/}

Ce problème ne se pose pas avec les fonctions qui renvoient une référence const ou non const à un conteneur.

Problème de partage implicite de l'itérateur

Lepartage implicite a une autre conséquence sur les itérateurs de style STL : vous devez éviter de copier un conteneur lorsque des itérateurs sont actifs sur ce conteneur. Les itérateurs pointent vers une structure interne, et si vous copiez un conteneur, vous devez être très prudent avec vos itérateurs. Par exemple

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.
*/

L'exemple ci-dessus ne montre qu'un problème avec QList, mais le problème existe pour tous les conteneurs Qt implicitement partagés.

Itérateurs de type Java

Lesitérateurs de type Java s 'inspirent des classes d'itérateurs de Java. Le nouveau code devrait préférer les itérateurs de type STL.

Conteneurs Qt comparés aux conteneurs std

Conteneurs Qt et algorithmes std

Vous pouvez utiliser les conteneurs Qt avec les fonctions de #include <algorithm>.

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
*/

Autres classes similaires aux conteneurs

Qt inclut d'autres classes de modèles qui ressemblent à des conteneurs à certains égards. Ces classes ne fournissent pas d'itérateurs et ne peuvent pas être utilisées avec le mot-clé foreach.

• QCache<Key, T> fournit un cache pour stocker des objets d'un certain type T associés à des clés de type Key.
• QContiguousCache<T> constitue un moyen efficace de mettre en cache des données auxquelles on accède généralement de manière contiguë.

D'autres types non modèles qui sont en concurrence avec les conteneurs modèles de Qt sont QBitArray, QByteArray, QString, et QStringList.

Complexité algorithmique

La complexité algorithmique concerne la rapidité (ou la lenteur) de chaque fonction lorsque le nombre d'éléments dans le conteneur augmente. Par exemple, l'insertion d'un élément au milieu d'une std::list est une opération extrêmement rapide, quel que soit le nombre d'éléments stockés dans la liste. En revanche, l'insertion d'un élément au milieu d'un site QList est potentiellement très coûteuse si le site QList contient de nombreux éléments, puisque la moitié des éléments doivent être déplacés d'une position en mémoire.

Pour décrire la complexité algorithmique, nous utilisons la terminologie suivante, basée sur la notation "big Oh" :

• Temps constant : O(1). On dit d'une fonction qu'elle s'exécute en temps constant si elle nécessite le même temps quel que soit le nombre d'éléments présents dans le conteneur. Un exemple est QList::push_back().
• Temps logarithmique : O(log n). Une fonction qui s'exécute en temps logarithmique est une fonction dont le temps d'exécution est proportionnel au logarithme du nombre d'éléments dans le conteneur. L'algorithme de recherche binaire en est un exemple.
• Temps linéaire : O(n). Une fonction qui s'exécute en temps linéaire s'exécutera en un temps directement proportionnel au nombre d'éléments stockés dans le conteneur. Un exemple est QList::insert().
• Temps linéaire-logarithmique : O(n log n). Une fonction qui s'exécute en temps linéaire-logarithmique est asymptotiquement plus lente qu'une fonction en temps linéaire, mais plus rapide qu'une fonction en temps quadratique.
• Temps quadratique : O(n²). Une fonction à temps quadratique s'exécute en un temps proportionnel au carré du nombre d'objets stockés dans le conteneur.

Le tableau suivant résume la complexité algorithmique du conteneur séquentiel QList<T> :

Dans le tableau, "Amort." signifie "comportement amorti". Par exemple, "Amort. O(1)" signifie que si vous appelez la fonction une seule fois, vous pouvez obtenir un comportement O(n), mais si vous l'appelez plusieurs fois (par exemple, n fois), le comportement moyen sera O(1).

Le tableau suivant résume la complexité algorithmique des conteneurs associatifs et des ensembles de Qt :

Avec QList, QHash, et QSet, la performance de l'ajout d'éléments est amortie O(log n). Elle peut être ramenée à O(1) en appelant QList::reserve(), QHash::reserve() ou QSet::reserve() avec le nombre prévu d'éléments avant de les insérer. La section suivante aborde ce sujet de manière plus approfondie.

Optimisations pour les types primitifs et déplaçables

Les conteneurs Qt peuvent utiliser des chemins de code optimisés si les éléments stockés sont relocalisables ou même primitifs. Cependant, il n'est pas toujours possible de savoir si les types sont primitifs ou relocalisables. Vous pouvez déclarer que vos types sont primitifs ou relocalisables en utilisant la macro Q_DECLARE_TYPEINFO avec l'indicateur Q_PRIMITIVE_TYPE ou l'indicateur Q_RELOCATABLE_TYPE. Voir la documentation de Q_DECLARE_TYPEINFO pour plus de détails et des exemples d'utilisation.

Si vous n'utilisez pas Q_DECLARE_TYPEINFO, Qt utilisera std::is_trivial_v<T> pour identifier les types primitifs et exigera à la fois std::is_trivially_copyable_v<T> et std::is_trivially_destructible_v<T> pour identifier les types relocalisables. Il s'agit toujours d'un choix sûr, même si les performances peuvent être sous-optimales.

Stratégies de croissance

QList<T>, QString et QByteArray stockent leurs éléments de manière contiguë en mémoire ; QHash<Key, T> conserve une table de hachage dont la taille est proportionnelle au nombre d'éléments dans le hachage. Pour éviter de réallouer les données à chaque fois qu'un élément est ajouté à la fin du conteneur, ces classes allouent généralement plus de mémoire que nécessaire.

Considérons le code suivant, qui construit un QString à partir d'un autre QString:

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;
}

Nous construisons la chaîne out dynamiquement en y ajoutant un caractère à la fois. Supposons que nous ajoutons 15 000 caractères à la chaîne QString. Les 11 réallocations suivantes (sur un total possible de 15 000) se produisent lorsque QString manque d'espace : 8, 24, 56, 120, 248, 504, 1016, 2040, 4088, 8184, 16376. À la fin, le site QString a 16376 caractères Unicode alloués, dont 15000 sont occupés.

Les valeurs ci-dessus peuvent sembler un peu étranges, mais il y a un principe directeur. Il avance en doublant la taille à chaque fois. Plus précisément, il avance à la puissance deux suivante, moins 16 octets. 16 octets correspondent à huit caractères, car QString utilise UTF-16 en interne.

QByteArray utilise le même algorithme que QString, mais 16 octets correspondent à 16 caractères.

QList<T> utilise également cet algorithme, mais 16 octets correspondent à 16/sizeof(T) elements.

QHash<Key, T> est un cas totalement différent. QHash La table de hachage interne de <T> croît par puissances de deux, et à chaque fois qu'elle croît, les éléments sont déplacés dans un nouveau godet, calculé comme suit : qHash(clé) % QHash::capacity() (le nombre de godets). Cette remarque s'applique également à QSet<T> et QCache<Key, T>.

Pour la plupart des applications, l'algorithme de croissance par défaut fourni par Qt fait l'affaire. Si vous avez besoin de plus de contrôle, QList<T>, QHash<Key, T>, QSet<T>, QString, et QByteArray fournissent un trio de fonctions qui vous permettent de vérifier et de spécifier la quantité de mémoire à utiliser pour stocker les éléments :

• capacity() renvoie le nombre d'éléments pour lesquels de la mémoire est allouée (pour QHash et QSet, le nombre de godets dans la table de hachage).
• reserve(size) pré-alloue explicitement de la mémoire pour les éléments de taille.
• squeeze() libère la mémoire qui n'est pas nécessaire pour stocker les éléments.

Si vous savez approximativement combien d'éléments vous allez stocker dans un conteneur, vous pouvez commencer par appeler reserve(), et lorsque vous avez fini de remplir le conteneur, vous pouvez appeler squeeze() pour libérer la mémoire préallouée supplémentaire.