Retrouvez cet article dans : Linux Magazine 79

Bibliothèque à vocation de plus en plus généraliste et plus seulement graphique, la dernière version de Qt présente une révision en profondeur de ce qui n’était presque qu’anecdotique jusqu’ici, à savoir les outils et structures de données fondamentales utilisées par la bibliothèque elle-même. Si globalement l’évolution est positive, nous verrons qu’il reste encore quelques défauts ici ou là.

Les outils présentés ici font partie de la « sous-bibliothèque » QtCore (libQtCore.so) : il est donc possible de les utiliser dans un programme en mode texte, sans se « traîner » toute la partie graphique de Qt, ce qui représente tout de même une économie de plus de 5 Mo.

Les chaînes de caractères

Jusqu’à la version 3 de Qt, les chaînes de caractères étaient représentées par les classes QCString et QString, pour faciliter la manipulation des chaînes (respectivement) « normales » et Unicode 16bits – des équivalents des classes standards std::string et std::wstring. Qt4 a conservé QString pour les chaînes Unicode, avec des fonctionnalités accrues. Par contre, les chaînes de caractères ASCII sont désormais représentées par QLatin1String, pour bien signifier que cette classe ne concerne que les chaînes ne contenant que les caractères du jeu Latin-1. Des méthodes et conversions implicites permettent de passer aisément de l’une à l’autre. Toutefois dans la pratique la classe QString est nettement privilégiée : elle est à la base des grandes capacités de Qt à l’internationalisation (i18n en abrégé). La classe QString de Qt4 apporte quelques possibilités par rapport à son ancêtre de Qt3.

Citons par exemple :

• Des méthodes permettent d’ajuster assez finement la gestion de la mémoire de la chaîne de caractères. reserve() permet ainsi de réserver de l’espace, en prévision d’un agrandissement futur de la chaîne. capacity() retourne la taille ainsi réservée, tandis que size() (et son synonyme length()) donne le nombre de caractères effectivement utilisés. resize() (ou setLength()) fixe la taille effective de la chaîne. squeeze() permet de réduire l’espace réservé à juste ce qui est nécessaire.
• Les méthodes statiques fromStdString() et fromStdWString() permettent d’obtenir une QString à partir des types standards std::string et std::wstring ; toStdString() et toStdWString() effectuent la conversion d’une QString vers chacun de ces deux types.
• Les méthodes arg() pour l’insertion de nombre dans une chaîne acceptent désormais un paramètre supplémentaire de type QChar (un caractère Unicode) permettant de définir le caractère de remplissage. Par exemple, QString(«%1»).arg(30, 4, 10, QChar(‘#’)) va donner la chaîne «##30», ou avec une taille négative, QString(«%1»).arg(30, -4, 10, QChar(‘@’)) va donner «30@@».

On trouve également toute une collection de méthodes de découpages, d’insertions, d’extractions ou de conversions : consultez la documentation de la classe QString. Plus que jamais, cette classe s’impose comme un substitut fort appréciable aux chaînes C ou C++ classiques.

Conteneurs linéaires

On retrouve dans Qt4 les conteneurs génériques usuels :

• QLinkedList<> implémente une liste doublement chaînée, l’équivalent de std::list<> ou du QValueList<> de Qt3 ;
• QVector<> est un tableau dynamique, l’équivalent de std::vector<> ou du QValueVector<> de Qt3.

Ces deux types proposent les opérations usuelles, les méthodes offertes reproduisant les interfaces des types standards et des types anciens de Qt3. De même que pour les chaînes de caractères, QVector<> permet en outre les conversion vers (avec toStdVector()) ou depuis (avec fromStdVector()) une instance du type standard std::vector<>.
Plus intéressant est le type QList<>. Son nom pourrait laisser penser qu’il s’agit d’un autre type de liste : en effet il propose les opérations usuelles sur les listes, notamment l’insertion ou la suppression d’éléments à n’importe quel endroit. Mais il propose en plus les opérations disponibles sur les tableaux, notamment l’accès aux éléments par indexation. On considère généralement qu’une telle mixité aboutit à de piètres performances par rapport aux conteneurs plus spécialisés que sont les deux précédents. C’est en réalité à la fois vrai et faux. Comparons diverses opérations sur quelques types :

• std::vector<> et std::list<> fournis par la librairie standard qui accompagne GCC 4.0.1 ;
• QValueVector<> et QValueList<> fournis par Qt3 ;
• QLinkedList<>, QVector<> et QList<> fournis par Qt4, ce dernier type étant comparé à la fois aux vecteurs et aux listes étant donné sa vocation mixte.

Pour commencer, on peut se demander si la création d’une instance de tel ou tel type est coûteuse ou non. Alors créons 10 millions d’instances de chacun de ces types, des instances vides destinées à stocker des entiers. Résultats :
Il est manifeste que TrollTech a considérablement amélioré cet aspect des conteneurs, même s’ils restent plus « lourds » que les types standards. Mais qu’en est-il de l’ajout d’éléments en fin de conteneurs, à l’aide de la méthode push_back() ou une autre équivalente ? Voici, d’abord pour les vecteurs :

...puis pour les listes :

Pour être précis, les tailles correspondent au nombre d’éléments ajoutés, de 50000 à 10 millions, tous les 50000. À noter que tous les conteneurs sont initialement vides, aucune mémoire n’est explicitement pré-allouée.
Là encore, Qt4 apporte une nette amélioration par rapport à Qt3. Le type QList<> semble pour l’instant tenir ses promesses, même s’il est légèrement plus lent qu’un vecteur pour ce qui est de l’ajout.

Mais voyons ce qu’il en est de l’insertion d’éléments. Pour ce test, un certain nombre d’éléments (des int) sont placés dans chaque conteneur, puis ces mêmes éléments sont réinsérés un sur deux. Voici les résultats pour les types de vecteur, pour des tailles allant de 2000 à 100000 éléments par incréments de 2000 :

Comme précédemment, Qt3 semble à la traîne. Le type QList<> se comporte à peu près comme un tableau (ce qu’il est en réalité). On peut dès lors affirmer que si ce type est en effet un excellent compromis pour des quantités de données modérées, il n’apporte aucun avantage pour de grandes quantités – du moins en ce qui concerne l’insertion.
Les résultats du même test avec les trois types de liste (std::list<> de GCC, QValueList<> de Qt3 et QLinkedList de Qt4) ne sont pas présentés ; disons simplement qu’ils sont (évidemment) beaucoup plus rapides et à peu près équivalents en termes de performances, avec un très léger avantage pour le type standard std::list<>.
Naturellement, tous ces tests n’ont pas plus de valeur qu’eux-mêmes, tous ces résultats sont à prendre avec précaution et à relativiser.
On peut tout de même en conclure que les conteneurs de Qt4 sont tout à fait valables et se positionnent bien par rapport aux conteneurs standards comparables. Le type QList<>, qui offre simultanément les services d’un tableau classique et d’une liste chaînée, est fort pratique lorsque la quantité de données à manipuler est limitée.

Les itérateurs

Les conteneurs de Qt4 proposent les mêmes itérateurs que ceux de la bibliothèque standard du C++ (STL), nommément les types iterator et const_iterator, avec les méthodes associées que sont begin(), end(), etc. En plus de ceux-ci, Qt4 propose de nouveaux types d’itérateurs, directement inspirés du langage Java (rappelons s’il en était besoin que la bibliothèque Qt se pose en concurrent direct de Java pour ce qui est du développement multiplateforme), qui se comportent un peu différemment.
Pour mémoire, les itérateurs de la STL sont positionnés « sur » les éléments du conteneur qu’ils parcourent. Par exemple, si iter est un itérateur de type QVector<int>::iterator (donc un itérateur sur les éléments d’un vecteur d’entiers), à une certaine position, la situation peut être schématisée ainsi :

Selon ce principe, le déréférencement *iter donne directement l’élément sur lequel est positionné l’itérateur. Les opérateurs ++ et -- permettent d’avancer et de reculer dans le parcours du conteneur.
Les noms des nouveaux itérateurs sont construits selon le principe suivant :

• Pour les itérateurs constants (ne permettant pas de modifier ni la liste, ni ses éléments), il suffit d’ajouter le mot Iterator à la suite du nom du conteneur, par exemple QListIterator, QVectorIterator...
• Pour les itérateurs autorisant des modifications, il faut en plus intercaler Mutable après le Q, par exemple QMutableLinkedListIterator.

Ces types existent par eux-mêmes, ils ne sont pas déclarés au sein d’une classe conteneur comme le sont les itérateurs de type STL. La construction d’une instance se fait en donnant le type contenu comme paramètre générique et l’instance du conteneur au constructeur.
Par exemple :

QList<QString> liste_chaine ;
// remplissage de la liste...
QMutableListIterator<QString> iter(liste_chaine) ;

Ces itérateurs de style Java pointent « entre » les éléments :

Ils ne surdéfinissent pas d’opérateurs, mais offrent un jeu de méthodes permettant de se déplacer dans le conteneur et d’accéder à ses éléments :

• toBack() et toFront() permettent de placer l’itérateur, respectivement, à la fin et au début du conteneur, c’est-à-dire après le dernier élément et avant le premier ;
• next() et previous() retournent respectivement l’élément suivant et l’élément précédent, et déplacent l’itérateur vers la fin et vers le début ;
• peekNext() et peekPrevious() permettent d’obtenir les éléments suivant et précédent, mais sans déplacer l’itérateur ;
• hasNext() et hasPrevious() retournent true lorsque l’itérateur possède respectivement un élément suivant et un élément précédent, false sinon.

Reprenant les deux déclarations précédentes, voici un exemple de code qui parcourt la liste de chaînes et transforme chacune en majuscules :

while ( iter.hasNext() )
{ QString& s = iter.next() ;
  s = s.toUpper() ;
}

Notez l’utilisation d’une référence pour la variable temporaire s. Si nous avions utilisé un QListIterator<>, donc un itérateur ne permettant pas de modifications, elle aurait du être déclarée const QString& s.

Conteneurs associatifs

Les conteneurs associatifs permettent d’indexer des valeurs d’un type quelconque par des clefs d’un autre type quelconque. On peut les séparer en deux grandes catégories : d’une part, ceux pour lesquels les clefs sont maintenues triées (ordonnées), d’autre part ceux dans lesquels les clefs sont dans un ordre quelconque.
La bibliothèque standard du C++ et Qt3 ne proposent que la première catégorie, par les classes génériques std::map<> et QMap<> (les conteneurs de la famille QDict<> de Qt3 sont ici écartés, car ils ne sont pas vraiment génériques sur le type de la clef). On trouve également dans la STL la classe std::multimap<>, qui permet d’associer plusieurs valeurs à une même clef, sans équivalent dans Qt3. Ces types reposent sur une structure d’arbre.
La version 4 de Qt propose les deux catégories :

• QMap<> et QMultiMap<> sont les équivalents des classes (presque) éponymes de la STL : les clefs sont maintenues triées, elles apparaissent dans l’ordre lors d’un parcours linéaire ;
• QHash<> et QMultiHash<> appartiennent à la deuxième catégorie : les clefs apparaissent dans un ordre quelconque lors d’un parcours linéaire ; la structure interne est celle d’une table de hachage.

Les classes « multi » permettent d’associer une liste de valeurs à une même clef. En pratique, une déclaration comme :

QMultiHash<QString, QString> synonymes ;

est à peu près équivalente à :

QHash<QString, QList<QString> > synonymes ;

Ces deux déclarations permettent d’associer plusieurs chaînes de caractères à une seule, ce qui pourrait servir pour construire un dictionnaire des synonymes.

Au contraire, les classes « non-multi » n’autorisent qu’une seule valeur à être associée à une clef donnée. En cela elles se comportent de manière très similaire à un tableau, aussi proposent-elles un opérateur []. Par exemple, si nous voulions associer des entiers à des chaînes, nous pourrions déclarer une variable comme ceci :

QMap<QString, int> dico ;

Les deux instructions suivantes sont alors parfaitement équivalentes, et ont pour effet d’insérer un couple (clef, valeur) dans le conteneur :

dico[«un»] = 1 ;
dico.insert(«un», 1) ;

Récupérer la valeur associée à une clef est tout aussi simple :

int a = dico[«un»] ;
int a = dico.value(«un») ;

Si aucune valeur n’est associée à la clef demandée, une valeur par défaut est retournée.

Pour être tout à fait honnête, QMap<> et QHash<> possèdent des méthodes insertMulti() et values() qui permettent respectivement d’insérer plusieurs valeurs par clef et d’obtenir la liste des valeurs associées à une clef.

Question performances, on peut comparer le QMap<> de Qt4 avec son ancêtre de Qt3 et avec le conteneur standard std::map<>. Pour cela, on associe des entiers à des entiers, les clefs étant tirées aléatoirement. Voici les résultats selon le nombre de clefs insérées (ici jusqu’à un million) :

Il semble malheureusement que la nouvelle mouture de QMap<> ne soit guère performante. Les temps supérieurs à 2500 millisecondes ont été ignorés.
On peut effectuer la même comparaison entre QHash<> et la classe hash_map<>, issue de l’implémentation de la STL par SGI et que l’on trouve dans l’en-tête <ext/hash_map> fourni par g++ (espace de nommage __gnu_cxx) :

Le résultat est plus mitigé, la table de hachage de Qt4 étant plus performante que celle de g++ jusqu’à environ 750000 éléments. Remarquez également que l’on vérifie qu’une table de hachage est plus efficace qu’un arbre binaire. Il convient toutefois de garder à l’esprit que cette classe hash_map<> ne fait pas (pour l’instant) partie du standard C++, même si on la retrouve fréquemment comme extension au standard.

Itérateurs

De même que les conteneurs linéaires envisagés plus haut, les conteneurs associatifs de Qt4 proposent deux jeux d’itérateurs pour les parcours : un premier équivalent à ceux de la librairie C++ standard, un deuxième inspiré par le langage Java. Les deux modèles partagent toutefois les deux mêmes méthodes pour obtenir la clef et la valeur d’un élément, à savoir key() (pour la clef) et value() (pour la valeur). Cette homogénéité a pour désagréable conséquence de rendre les itérateurs « style STL » incompatibles avec, justement, les itérateurs de la STL : ces derniers utilisent plutôt des membres nommés respectivement first et second, tels que définis dans la classe std::pair<>.
Voici un exemple de parcours d’un QMap<> à l’aide d’un itérateur de type STL :

#include <QString>
#include <QMap>
/*...*/
QMap<QString, QString> dico ;
/* ... */
QMap<QString, QString>::const_iterator iter ;
for (iter = dico.begin() ; iter != dico.end() ; ++iter)
{
   QString s = iter.key() + « -> « + iter.value() ;
   /* ... */
}

Parcourir un QMultiHash<> (ou un QMultiMap<>) peut s’avérer plus problématique. La documentation de la version que j’utilise (4.0.1) fait référence à une méthode findNextKey() supposée être disponible dans la classe d’itérateur QHashIterator<>. Ne la cherchez pas, elle n’existe pas : le problème a été soumis à TrollTech, qui invoque une erreur dans la documentation.
Voici un exemple complet montrant comment s’en sortir, en utilisant un itérateur « style Java » :

 1 #include <iostream>
 2 #include <QMultiHash>
 3 #include <QHashIterator>
 4 int main(int argc, char* argv[])
 5 {
 6    QMultiHash<int, int> h ;
 7    h.insert(1, 10) ;
 8    h.insert(2, 20) ;
 9    h.insert(3, 30) ;
10    h.insert(4, 40) ;
11    h.insert(1, 11) ;
12    h.insert(3, 31) ;
13    h.insert(4, 41) ;
14    h.insert(3, 32) ;
15    QHashIterator<int, int> iter(h) ;
16    while ( iter.hasNext() )
17    {
18       iter.next() ;
19       int clef = iter.key() ;
20       std::cout << iter.key() << „ -> [„ ;
21       bool encore = false ;
22       do
23       {
24          std::cout << iter.value() ;
25          encore = iter.hasNext() && (iter.peekNext().key() == clef) ;
26          if ( encore )
27          {
28             std::cout << „, „ ;
29             iter.next() ;
30          }
31       }
32       while ( encore ) ;
33       std::cout << „]\n“ ;
34    }
35    return 0 ;
36 }

Ce programme peut être compilé à l’aide de l’instruction :

Remarquez que les valeurs apparaissent dans l’ordre inverse où elles ont été insérées.

Conclusion

Malgré quelques défauts, les conteneurs offerts par Qt présentent une alternative intéressante à ceux proposés par la bibliothèque standard du C++.
Ils ne sont toutefois véritablement intéressants que dans les situations où une implémentation correcte de celle-ci n’est pas disponible. Par exemple, la bibliothèque libstdc++ qui accompagne notre bon compilateur GCC offre probablement tout ce qui est souhaitable et même plus, par le biais d’extensions à la bibliothèque standard.
Louons malgré tout l’effort fait par TrollTech pour offrir des passerelles depuis et vers les conteneurs de la STL, par le moyen de méthodes spécialisées à cette fin.
N’ont pas été traités ici les algorithmes proposés par Qt, comme qFill() (pour remplir tout ou partie d’un conteneur) ou forEach() (qui applique un bloc d’instructions à chaque élément d’un conteneur), destinés à simplifier l’écriture de tâches communes.
Ils sont similaires à ceux de la bibliothèque standard, aussi encore une fois, à mon humble avis, ne sont-ils véritablement intéressants que lorsque ceux de la STL ne sont pas disponibles.
La prochaine fois, nous verrons quelques-unes des évolutions dans le système de dessin de Qt.

Retrouvez cet article dans : Linux Magazine 79