Algorithmes génériques de Qt

Qt Quarterly est une revue trimestrielle électronique proposée par Nokia à destination des développeurs et utilisateurs de Qt. Vous pouvez trouver les versions originales.

Nokia, Qt, Qt Quarterly et leurs logos sont des marques déposées de Nokia Corporation en Finlande et/ou dans les autres pays. Les autres marques déposées sont détenues par leurs propriétaires respectifs.

Cet article est la traduction de l'article http://qt.nokia.com/doc/qq/qq15-qalgorithms.html, de Morten Sørvig, paru dans la Qt Quarterly Issue 15.

Cet article est une traduction d'un des tutoriels écrits par Nokia Corporation and/or its subsidiary(-ies) inclus dans la documentation de Qt, en anglais. Les éventuels problèmes résultant d'une mauvaise traduction ne sont pas imputables à Nokia.

Qt fournit ses propres algorithmes car certaines plates-formes (par exemple, Linux embarqué) ne fournissent pas une implémentation de la STL. Les algorithmes sont utilisés intérieurement par Qt et sont disponibles aux utilisateurs de Qt.

Il est tout à fait possible de d'utiliser conjointement les implémentations des conteneurs et algorithmes de la STL et de Qt. Par exemple, vous pouvez utiliser l'algorithme std::find() sur une QList<T>, ou qSort() sur un std::vector<T>. C'est possible car les algorithmes sont basés sur des itérateurs correspondant au style STL, et les itérateurs des conteneurs Qt remplissent les prérequis de la STL.

Les algorithmes qSort() et qStableSort() peuvent être utilisés pour trier les éléments d'une QList<T>, d'un QVector<T>, ou encore d'un tableau C++ basique de façon croissante. Avec Qt 4, il est aussi possible de spécifier un opérateur de comparaison personnalisé (en lieu et place de operator<()).

Un tri stable a pour propriété de conserver l'ordre des éléments égaux pendant un tri. C'est utile pour comparer des éléments qui sont considérés "égaux" quand bien même ils ne seraient pas totalement équivalents. Par exemple, si vous trier une liste d'adresses selon le nom de famille, vous pouvez utiliser qStableSort() pour préserver l'ordre initial des gens possédant le même nom de famille. Le tri normal ne présente pas cette garantie.

Les algorithmes qFind() et qBinaryFind() prennent une paire d'itérateurs ainsi qu'une valeur et renvoie un itérateur vers l'élément correspondant à la valeur demandée, ou l'itérateur "end" si cette valeur n'est pas trouvée. L'algorithme de recherche par dichotomie est nettement plus rapide que l'algorithme linéaire, mais il ne peut agir que sur un ensemble trié.

Si la valeur apparaît plusieurs fois, qFind() renvoie un itérateur vers la première occurrence, tandis que qBinaryFind() pointera vers une occurrence arbitraire.

Pour plus de flexibilité, Qt 4 fournit aussi qLowerBound() et qUpperBound(). Tout comme qBinaryFind(), ils agissent sur un ensemble trié. Si la valeur est trouvée, qLowerBound() renvoie un itérateur sur le premier élément qui correspond et qUpperBound() renvoie un itérateur sur le dernier élément qui correspond "plus un". Si la valeur n'est pas trouvée, ils renvoient un itérateur vers la position où la valeur aurait dû être si elle était présente. Vous pouvez ensuite utiliser cet itérateur pour insérer la valeur, par exemple.

Un usage commun de qLowerBound()qUpperBound() est d'itérer sur toutes les occurrences d'une valeur :

QStringList list;
QStringList::iterator i, j;
// ...
i = qLowerBound(list.begin(), list.end(), value);
j = qUpperBound(list.begin(), list.end(), value);

while (i != j)
{
    processItem(*i);
    ++i;
}

Dans cette section, nous allons utiliser la recherche par dichotomie pour implémenter une table de correspondance static const. La structure de données est entièrement stockée dans une mémoire en lecture seule et est constituée de paires sous la forme "nom de famille, prénom" triées par nom de famille. En comparaison avec QMap et QHash, cette approche est économe en mémoire et a du sens dans les applications ou bibliothèques très optimisées.

Premièrement, nous définissons une structure pour contenir un nom, ainsi qu'un opérateur de comparaison "plus petit que" afin de rechercher une entrée par le nom de famille :

struct Entry
{
    const char *familyName;
    const char *givenName;
};

bool operator<(const Entry &entry, const QString &family)
{
    return entry.familyName < family;
}

bool operator<(const QString &family, const Entry &entry)
{
    return family < entry.familyName;
}

Ensuite, nous déclarons nos données :

static const int NumEntries = 4;
static const Entry entries[NumEntries] = 
{
    { "Deitel", "Harvey" },
    { "Deitel", "Paul" },
    { "Jobs", "Steve" },
    { "Torvalds", "Linus" }
};
static const Entry * const end = entries + NumEntries;

Le pointeur end indique la fin du tableau.

bool contains(const QString &family)
{
    return qBinaryFind(entries, end, family) != end;
}

Maintenant que tout est en place, implémenter contains() est trivial. Puisque les pointeurs C++ correspondent aux critères d'un itérateur en accès aléatoire de la STL, nous pouvons les utiliser conjointement à qBinaryFind().

QString givenName(const QString &family)
{
    const Entry *i = qBinaryFind(entries, end, family);
    if (i == end)
        return "";
    return i->givenName;
}

La fonction givenNames() renvoie le prénom d'une personne correspondant au nom de famille donné. Par exemple, si nous passons "Torvalds" comme argument, nous obtenons "Linus" ; si nous passons "Deitel", la fonction nous renvoie alors soit "Harvey", soit "Paul".

QStringList givenNames(const QString &family)
{
    const Entry *i = qLowerBound(entries, end, family);
    const Entry *j = qUpperBound(entries, end, family);
    QStringList result;
    while (i != j)
        result += (i++)->givenName + (" " + family);
    return result;
}

La fonction givenNames() renvoie une liste des personnes appartenant à une certaine famille. Elle illustre l'usage de qLowerBound() et qUpperBound().

Au nom de toute l'équipe Qt, j'aimerais adresser le plus grand remerciement à Nokia pour nous avoir autorisé la traduction de cet article !

J'aimerais aussi adresser un immense merci à dourouc05 pour ses relectures et corrections !