La STL fournit une collection impressionnante de structures de données génériques. La plupart des bibliothèques s'arrêtent là. Cependant, La STL contient un assortiment supplémentaire d'algorithmes génériques qui peuvent, à quelques exceptions près, être appliqués aux éléments de n'importe quel conteneur. À l'aide de ces algorithmes, de manière optimisée, vous pouvez rechercher des éléments dans des conteneurs, trier des éléments dans des conteneurs, traiter des éléments dans des conteneurs et effectuer toute une série d'autres opérations. La beauté des algorithmes est qu'ils sont indépendants non seulement des types d'éléments sous-jacents, mais aussi des types de conteneurs sur lesquels ils opèrent. Les algorithmes effectuent leur travail en utilisant uniquement les interfaces des itérateurs. De nombreux algorithmes acceptent les fonctions de rappel: un pointeur de fonction ou quelque chose qui se comporte comme un pointeur de fonction, comme un objet avec une surcharge de l'operateur(). Idéalement, la STL fournit un ensemble de classes qui peuvent être utilisées pour créer des objets de rappel pour les algorithmes. Ces objets de rappel sont appelés objets fonction, ou simplement foncteurs.

Introduction

L'algorithme find() recherche un élément spécifique dans une plage d'itérateur. Vous pouvez l'utiliser sur des éléments de n'importe quel type de conteneur. Il renvoie un itérateur faisant référence à l'élément trouvé, ou à l'itérateur de fin de la plage. Notez que la plage spécifiée dans l'appel à find() ne doit pas nécessairement correspondre à la totalité de la plage des éléments d'un conteneur; cela pourrait être un sous-ensemble.

Recherche d'un élément dans un tableau

Exemple:

//===============================================
void GFind::run() {
    int lTab[] = {10, 20, 30, 40};
    int* p;

    p = std::find (lTab, lTab + 4, 30);
    if (p != lTab + 4)
        std::cout << "Element found: " << *p << '\n';
    else
        std::cout << "Element not found.\n";
}
//===============================================

Résultat:

//===============================================
Element found: 30
//===============================================

Recherche d'un élément dans un vecteur

Exemple:

//===============================================
void GFind::run() {
    std::vector<int> lVector = {10, 20, 30, 40};
    std::vector<int>::iterator it;

    it = std::find (lVector.begin(), lVector.end(), 30);
    if(it != lVector.end())
        std::cout << "Element found: " << *it << '\n';
    else
        std::cout << "Element not found.\n";
}
//===============================================

Résultat:

//===============================================
Element found: 30
//===============================================

Introduction

L'algorithme find_if() est similaire à l'algorithme find(), sauf qu'il accepte un rappel de fonction de prédicat au lieu d'un simple élément à faire correspondre. Un prédicat renvoie vrai ou faux. L'algorithme find_if() appelle le prédicat sur chaque élément de la plage jusqu'à ce que le prédicat renvoie vrai. L'algorithme find_if() renvoie ensuite un itérateur faisant référence à cet élément.

Recherche d'un élément dans un vecteur

Le programme suivant lit les résultats des tests de l'utilisateur, puis vérifie si l'un des scores est « parfait ». Un score parfait est un score de 100 ou plus.

Exemple:

//===============================================
void GFind::run() {
    std::vector<int> lVector = {10, 20, 200, 30, 250, 40};
    std::vector<int>::iterator it;

    it = std::find_if (lVector.begin(), lVector.end(), perfectScore);
    if(it != lVector.end())
        std::cout << "Element found: " << *it << '\n';
    else
        std::cout << "Element not found.\n";
}
//===============================================

Résultat:

//===============================================
Element found: 200
//===============================================

Ce programme a transmis un pointeur vers la fonction perfectScore(), que l'algorithme find_if() a ensuite appelé sur chaque élément jusqu'à ce qu'il renvoie true. Malheureusement, la STL ne fournit pas d'algorithme find_all() ou d'algorithme équivalent qui renvoie toutes les instances correspondant à un prédicat. Nous vous montrerons dans les sections suivantes comment écrire votre propre algorithme find_all().

Introduction

Il est souvent utile de calculer la somme, ou une autre quantité arithmétique, de tous les éléments d'un conteneur. C'est exactement ce que fait l'algorithme accumulate(). Dans sa forme la plus élémentaire, il calcule la somme des éléments dans une plage spécifiée.

Calcul de la somme des éléments d'un vecteur

La fonction suivante calcule la moyenne arithmétique d'une séquence d'entiers dans un vecteur. La moyenne arithmétique est simplement la somme de tous les éléments divisée par le nombre d'éléments.

Exemple:

//===============================================
void GAccumulate::run() {
    std::vector<int> lVector = {10, 20, 30, 40, 50, 60};
    std::cout << "arithmeticMean: " << arithmeticMean(lVector) << '\n';
}
//===============================================
double GAccumulate::arithmeticMean(const std::vector<int>& nums) {
    double sum = accumulate(nums.begin(), nums.end(), 0);
    return (sum / nums.size());
}
//===============================================

Résultat:

//===============================================
arithmeticMean: 35
//===============================================

Notez que l'algorithme accumulate() est déclaré dans , pas dans . Notez également que l'algorithme accumulate() prend comme troisième paramètre une valeur initiale pour la somme, qui dans ce cas doit être 0 (l'identité de l'addition) pour démarrer une nouvelle somme.

Calcul du produit des éléments d'un vecteur

La deuxième forme de l'algorithme accumulate() permet à l'appelant de spécifier une opération à effectuer au lieu d'une addition. Cette opération prend la forme d'une fonction de rappel binaire. Supposons que vous souhaitiez calculer la moyenne géométrique, qui est le produit de tous les nombres de la séquence à la puissance l'inverse de la taille. Dans ce cas, vous souhaiterez utiliser l'algorithme accumulate() pour calculer le produit au lieu de la somme. Vous pourriez l'écrire ainsi:

Exemple:

//===============================================
void GAccumulate::run() {
    std::vector<int> lVector = {10, 20, 30, 40, 50, 60};
    std::cout << "geometricMean: " << geometricMean(lVector) << '\n';
}
//===============================================
int GAccumulate::product(int num1, int num2) {
    return (num1 * num2);
}
//===============================================
double GAccumulate::geometricMean(const std::vector<int>& nums) {
    double mult = std::accumulate(nums.begin(), nums.end(), 1, product);
    return (pow(mult, 1.0 / nums.size()));
}
//===============================================

Résultat:

//===============================================
geometricMean: 29.938
//===============================================

Notez que la fonction product() est transmise en tant que fonction de rappel à l'algorithme accumulate() et que la valeur initiale de l'accumulation est 1 (l'identité de la multiplication) au lieu de 0.

La section suivante vous montre comment utiliser l'algorithme accumulate() dans la fonction géométriqueMean() sans écrire de fonction de rappel.

Introduction

Vous avez vu quelques algorithmes STL, vous êtes en mesure d'apprécier les objets fonction. Vous pouvez surcharger l'opérateur d'appel de fonction dans une classe de telle sorte que les objets de la classe puissent être utilisés à la place des pointeurs de fonction.

Ces objets sont appelés objets fonction, ou simplement foncteurs. De nombreux algorithmes STL, tels que find_if() et la deuxième forme de l'algorithme accumulate(), nécessitent un pointeur de fonction comme l'un des paramètres. Lorsque vous utilisez ces fonctions, vous pouvez transmettre un foncteur au lieu d'un pointeur de fonction.

Ce fait, en soi, n'est pas nécessairement une raison pour sauter de joie. Bien que vous puissiez certainement écrire vos propres classes de foncteurs, le véritable attrait est que C++ fournit plusieurs classes de foncteurs prédéfinies qui effectuent les opérations de rappel les plus couramment utilisées. Cette section décrit ces classes prédéfinies et vous montre comment les utiliser.

Toutes les classes d'objets fonction prédéfinies se trouvent dans le fichier d'en-tête <functional>.

Objets fonction arithmétiques

C++ fournit des modèles de classes de foncteurs pour les cinq opérateurs arithmétiques binaires: plus (plus), moins (minus), multiplie (multiplies), divise (divides) et modulo (modulus). De plus, une négation unaire est fournie (negate). Ces classes fournissent un modèle générique sur le type des opérandes et sont des wrappers pour les opérateurs réels. Ils prennent un ou deux paramètres du type de modèle, effectuent l'opération et renvoient le résultat.

L'avantage des objets fonctions arithmétiques est que vous pouvez les transmettre sous forme de fonctions de rappel aux algorithmes, ce que vous ne pouvez pas faire directement avec les opérateurs arithmétiques.

Objets fonction de comparaison

En plus des classes d'objets fonctions arithmétiques, le langage C++ fournit toutes les comparaisons standards: equal_to, not_equal_to, less, greater, less_equal et greater_equal.

Utilisation de la classe plus

Exemple:

//===============================================
void GPlus::run() {
    std::plus<int> myPlus;
    int res = myPlus(4, 5);
    std::cout << res << std::endl;
}
//===============================================

Résultat:

//===============================================
9
//===============================================

Utilisation d'un objet fonction dans un algorithme

Par exemple, l'implémentation de la fonction géométriqueMean() utilisait l'algorithme accumulate() avec une fonction de rappel pour multiplier deux entiers. Vous pouvez le réécrire pour utiliser l'objet fonction multiplie (multiplies):

Exemple:

//===============================================
void GMultiplies::run() {
    std::vector<int> lVector = {10, 20, 30, 40, 50, 60};
    std::cout << "geometricMean: " << geometricMean(lVector) << '\n';
}
//===============================================
double GMultiplies::geometricMean(const std::vector<int>& nums) {
    double mult = std::accumulate(nums.begin(), nums.end(), 1, std::multiplies<int>());
    return (pow(mult, 1.0 / nums.size()));
}
//===============================================

Résultat:

//===============================================
geometricMean: 29.938
//===============================================

L'expression multiplies<int>() crée un nouvel objet de la classe multiplies, en l'instanciant avec le type int. Les autres objets fonction arithmétiques se comportent de la même manière.

Utilisation de l'objet fonction de comparaison (less)

L'objet fonction de comparaison (less) est celui utilisé par défaut par les éléments de la file d'attente prioritaire (priority_queue) et des conteneurs associatifs. Voici un exemple de file d'attente prioritaire utilisant l'opérateur de comparaison par défaut (less).

Exemple:

//===============================================
void GPriority::run() {
    std::priority_queue<int> myQueue;
    myQueue.push(3);
    myQueue.push(4);
    myQueue.push(2);
    myQueue.push(1);

    while (!myQueue.empty()) {
        std::cout << myQueue.top() << std::endl;
        myQueue.pop();
    }
}
//===============================================

Résultat:

//===============================================
4
3
2
1
//===============================================

Comme vous pouvez le constater, les éléments de la file d'attente prioritaire (priority_queue) sont supprimés par ordre décroissant, selon l'opérateur de comparaison (less). Vous pouvez modifier la comparaison en la spécifiant comme argument du modèle de comparaison.

La définition du modèle de la file d'attente prioritaire (priority_queue) ressemble à ceci:

//===============================================
template <typename T
, typename Container = vector<T>
, typename Compare = less<T> >;
//===============================================

Utilisation de l'objet fonction de comparaison (greater)

Le paramètre de type Compare est le dernier, ce qui signifie que pour spécifier la comparaison, vous devez également spécifier le conteneur. Voici un exemple du programme ci-dessus modifié pour que la file d'attente prioritaire (priotity_queue) trie les éléments par ordre croissant en utilisant l'opérateur plus grand (greater):

Exemple:

//===============================================
void GPriority::run() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> myQueue;
    myQueue.push(3);
    myQueue.push(4);
    myQueue.push(2);
    myQueue.push(1);

    while (!myQueue.empty()) {
        std::cout << myQueue.top() << std::endl;
        myQueue.pop();
    }
}
//===============================================

Résultat:

//===============================================
1
2
3
4
//===============================================

Plusieurs algorithmes nécessitent des fonctions de rappel de comparaison, pour lesquels les comparateurs prédéfinis sont utiles.

À suivre...