Classes de conteneurs

Introduction

La bibliothèque Qt fournit un ensemble de classes de conteneurs à 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écifié. Par exemple, si vous avez besoin d'un tableau redimensionnable d'QString, 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 ne connaissez pas bien la STL ou si vous préférez adopter l'approche « à la Qt », vous pouvez utiliser ces classes à la place des classes STL.

Les classes de conteneurs sont implicitement partagées, elles sont réentrantes et optimisées pour la vitesse, une faible consommation de mémoire et une expansion minimale du code inline, ce qui se traduit par des exécutables plus légers. De plus, elles sont thread-safe 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 leur parcours. Les itérateurs de type STL sont les plus efficaces et peuvent être utilisés conjointement avec les itérateurs de Qt et de la STL ( generic algorithms). Des itérateurs de type Java sont fournis à des fins de compatibilité ascendante.

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 type le plus adapté. 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 respectivement une sémantique LIFO et FIFO.

Qt fournit également les conteneurs associatifs suivants : QMap, QMultiMap, QHash, QMultiHash et QSet. Les conteneurs « Multi » prennent en charge de manière pratique 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 par hachage efficace d’objets dans un espace de cache limité.

Les conteneurs peuvent être imbriqués. Par exemple, il est tout à fait possible d’utiliser un QMap<QString, QList<int>>, où 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 distincts portant le même nom que le conteneur (par exemple, <QList>). Pour plus de commodité, les conteneurs sont déclarés en 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 êtes susceptible de vouloir stocker dans un conteneur, y compris les types de base tels que int et double, les types de pointeurs, ainsi que les types de données Qt tels que QString, QDate et QTime, mais cela ne couvre pas QObject ni aucune sous-classe de QObject (QWidget, QDialog, QTimer, etc.). Si vous tentez d’instancier un ` QList` <QWidget>, le compilateur 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 en tant que ` 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 vous ne fournissez ni constructeur de copie ni opérateur d’affectation, le C++ fournit une implémentation par défaut qui effectue une copie membre par membre. Dans l’exemple ci-dessus, cela aurait suffi. De même, si vous ne fournissez aucun constructeur, le C++ fournit un constructeur par défaut qui initialise ses membres à l'aide des 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 imposent des exigences supplémentaires concernant les types de données qu’ils peuvent stocker. Par exemple, le type Key d’une QMap<Key, T> doit fournir operator<(). Ces exigences particulières sont documentées dans la description détaillée de la classe. Dans certains cas, des fonctions spécifiques ont des exigences particulières ; celles-ci sont décrites fonction par fonction. Le compilateur génère systématiquement une erreur si une contrainte n’est pas respectée.

Les conteneurs de Qt fournissent les opérateurs <<() et >>() afin de pouvoir ê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 les opérateurs <<() et >>(). La mise en place de cette prise en charge est simple ; voici comment nous pourrions procéder 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 des classes de conteneurs fait référence aux 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 n'est pas présente 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 tels que int et double, ainsi que pour les types de pointeurs, le langage C++ ne spécifie aucune initialisation ; dans ces cas-là, les conteneurs Qt initialisent automatiquement la valeur à 0.

Itération sur les conteneurs

Boucle « for » basée sur une plage

La boucle « for » basée sur une plage est à privilégier pour les conteneurs :

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

Notez que lorsque vous utilisez un conteneur Qt dans un contexte non-const, le partage implicite peut entraîner un détachement indésirable du conteneur. Pour éviter cela, utilisez l’ std::as_const():

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

Pour les conteneurs associatifs, cela effectuera une boucle sur les valeurs.

Basé sur l'index

Pour les conteneurs séquentiels qui stockent leurs éléments de manière contiguë en mémoire (par exemple, QList), on peut utiliser une itération basée sur les indices :

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 proposent deux types d’itérateurs : les itérateurs de type STL et les itérateurs de type 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 à la suite de l’appel d’une fonction membre non const.

Itérateurs de type STL

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

Pour chaque classe de conteneur, il existe deux types d’itérateurs de type STL : l’un offrant un accès en lecture seule et l’autre 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 avancer l’itérateur vers l’élément suivant, et l’opérateur * renvoie l’élément vers lequel pointe l’itérateur. En effet, pour les structures de type « QList » et « QStack », qui stockent leurs éléments à des adresses 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 permettant de parcourir tous les éléments d'un QList<QString> dans l'ordre et de 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 type STL pointent directement vers les éléments. La fonction begin() d’un conteneur renvoie un itérateur qui pointe vers le premier élément du conteneur. La fonction end() d’un conteneur renvoie un itérateur pointant vers l’élément imaginaire situé une position après le dernier élément du conteneur. end() marque une position non valide ; il ne doit jamais être déréférencé. Il est généralement utilisé dans la condition de sortie d’une boucle. Si la liste est vide, begin() est égal à end(), donc la boucle n’est jamais exécutée.

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

Pour itérer en arrière avec un itérateur de type STL, on utilise 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é la méthode QString::toLower() sur celui-ci.

Pour un accès en lecture seule, vous pouvez utiliser `const_iterator`, ` cbegin()` et ` cend()`. Par 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 type STL :

Les opérateurs « ++ » et « -- » sont disponibles à la fois sous forme d’opérateurs préfixés (++i, --i) et postfixés (i++, i--). Les versions préfixées modifient les itérateurs et renvoient une référence à l’itérateur modifié ; les versions postfixées effectuent une copie de l’itérateur avant de le modifier, puis renvoient cette copie. Dans les expressions où la valeur de retour est ignorée, nous vous recommandons d’utiliser les opérateurs préfixés (++i, --i), car ceux-ci sont légèrement plus rapides.

Pour les types d’itérateurs non constants, la valeur de retour de l’opérateur unaire * peut être utilisée à gauche de l’opérateur d’affectation.

Pour les types ` QMap ` et ` QHash`, l’opérateur ` * ` renvoie la composante « valeur » d’un élément. Si vous souhaitez récupérer la clé, appelez la méthode `key()` sur l’itérateur. Par souci de symétrie, les types d’itérateurs fournissent également une fonction `value()` permettant de récupérer la valeur. Par exemple, voici comment afficher tous les éléments d’un ` 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 contient des dizaines de fonctions qui renvoient un « QList » ou un « QStringList » par valeur (par exemple, ` QSplitter::sizes()`). Si vous souhaitez parcourir ces conteneurs à l'aide d'un itérateur STL, vous devez toujours en faire une copie et parcourir cette 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 d’itérateur à partage implicite

Le partage implicite a une autre conséquence sur les itérateurs de type STL : vous devez éviter de copier un conteneur tant que des itérateurs sont actifs sur ce conteneur. Les itérateurs pointent vers une structure interne, et si vous copiez un conteneur, vous devez faire très attention à 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 ce problème existe pour tous les conteneurs Qt à partage implicite.

Itérateurs de type Java

Les itérateurs de type Java s'inspirent des classes d'itérateurs de Java. Dans le nouveau code, il est préférable d'utiliser des itérateurs de type STL.

Comparaison entre les conteneurs Qt et les conteneurs std

Conteneurs Qt et algorithmes std

Vous pouvez utiliser les conteneurs Qt avec les fonctions disponibles sur #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
*/

Algorithmes des conteneurs Qt

Qt fournit également des algorithmes génériques supplémentaires dans <QtAlgorithms> qui fonctionnent avec n'importe quel conteneur prenant en charge les itérateurs de type STL, tels que qJoin() pour regrouper les éléments d'un conteneur en une seule valeur, et qDeleteAll() pour appeler operator delete sur tous les éléments d'un conteneur ou d'une plage donnée.

Autres classes de type conteneur

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 permettant de stocker des objets d’un certain type T associés à des clés de type Key.
• QContiguousCache<T> offre un moyen efficace de mettre en cache des données auxquelles on accède généralement de manière contiguë.

Parmi les autres types non-modèles qui font concurrence aux conteneurs modèles de Qt, on trouve QBitArray, QByteArray, QString et QStringList.

Complexité algorithmique

La complexité algorithmique s'intéresse à la rapidité (ou à la lenteur) de chaque fonction à mesure que le nombre d'éléments du 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’une ` QList ` peut s’avérer très coûteuse si l’` QList ` contient de nombreux éléments, car la moitié des éléments doit être déplacée d’une position en mémoire.

Pour décrire la complexité algorithmique, nous utilisons la terminologie suivante, basée sur la notation « grand O » :

• Temps constant : O(1). On dit qu’une fonction 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. La fonction ` QList::push_back()` en est un exemple.
• Temps logarithmique : O(log n). Une fonction s'exécutant en temps logarithmique est une fonction dont la durée d'exécution est proportionnelle au logarithme du nombre d'éléments contenus dans le conteneur. L'algorithme de recherche binaire en est un exemple.
• Temps linéaire : O(n). Une fonction s'exécutant en temps linéaire s'exécute en un temps directement proportionnel au nombre d'éléments stockés dans le conteneur. Un exemple est la fonction ` QList::insert()`.
• Temps linéaire-logarithmique : O(n log n). Une fonction s'exécutant 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'éléments 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 de l'ordre de O(n), mais si vous l'appelez plusieurs fois (par exemple, n fois), le comportement moyen sera de l'ordre de 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 en 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 plus en détail.

Optimisations pour les types primitifs et relocalisables

Les conteneurs Qt peuvent utiliser des chemins de code optimisés si les éléments stockés sont relocalisables, voire primitifs. Cependant, il n’est pas toujours possible de déterminer si les types sont primitifs ou relocalisables. Vous pouvez déclarer vos types comme primitifs ou relocalisables en utilisant la macro ` Q_DECLARE_TYPEINFO ` avec le drapeau `Q_PRIMITIVE_TYPE` ou le drapeau `Q_RELOCATABLE_TYPE`. Consultez 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. C’est toujours un choix sûr, même si les performances peuvent s’en trouver légèrement réduites.

Stratégies de croissance

QList<T>, QString et QByteArray stockent leurs éléments de manière contiguë en mémoire ; QHash<Key, T> gère une table de hachage dont la taille est proportionnelle au nombre d’éléments qu’elle contient. 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 de manière dynamique en y ajoutant un caractère à la fois. Supposons que nous ajoutions 15 000 caractères à la chaîne « QString ». Les 11 réallocations suivantes (sur un total possible de 15 000) se produisent alors que « QString » manque d’espace : 8, 24, 56, 120, 248, 504, 1 016, 2 040, 4 088, 8 184, 16 376. À la fin, la variable ` QString ` dispose de 16 376 caractères Unicode alloués, dont 15 000 sont occupés.

Les valeurs ci-dessus peuvent sembler un peu étranges, mais il y a un principe directeur. La taille double à chaque fois. Plus précisément, elle passe à la puissance de deux suivante, moins 16 octets. 16 octets correspondent à huit caractères, car QString utilise le codage 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) éléments.

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

Pour la plupart des applications, l’algorithme d’extension par défaut fourni par Qt suffit. Si vous avez besoin d’un contrôle plus précis, QList<T>, QHash<KEY, T>, QSet<T>, QString et QByteArray fournissent un ensemble de trois 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, il s’agit du nombre de compartiments dans la table de hachage).
• reserve(size) préalloue explicitement de la mémoire pour size éléments.
• squeeze() libère toute la mémoire qui n’est pas nécessaire au stockage des éléments.

Si vous connaissez le nombre approximatif d'éléments que vous allez stocker dans un conteneur, vous pouvez commencer par appeler reserve(), puis, une fois le conteneur rempli, appeler squeeze() pour libérer la mémoire préallouée en surplus.