Comment l'algorithme STL fonctionne-t-il indépendamment du type Iterator?

Question

Comment l'algorithme STL fonctionne-t-il indépendamment du type Iterator?

Answer 1

Vraiment, ils fonctionnent juste. Ils utilisent des propriétés assez simples de modèles, parfois appelés polymorphisme statique. Si vous connaissez le terme, c'est essentiellement une forme de ducktyping. (Si ça ressemble à un canard, et ça se transforme en un canard, ça doit être un canard)

L'astuce est simple. Voici un exemple très simple:

template <typename T> 
void say_hello(const T& t) { 
    t.hello(); 
} 

La fonction say_hello ne se soucie pas de quel type de son argument est. Il ne doit pas dériver d'une interface ou faire d'autres sortes de «promesses» sur ce que c'est. Tout ce qui compte, c'est que le type fonctionne dans ce contexte. Tout ce que nous faisons avec le type est appelez sa fonction hello. Ce qui signifie que ce code sera compilé pour tout type qui a une fonction membre hello.

Les algorithmes STL fonctionnent de manière similaire. Voici une implémentation simple de std::for_each:

template <typename iter_type, typename func_type> 
void for_each(iter_type first, iter_type last, func_type f){ 
    for (iter_type cur = first; cur != last; ++cur) { 
    f(*cur); 
    } 
} 

Ce code compilera chaque fois que les types de modèle à la hauteur des exigences qui leur sont imposées; iter_type doit avoir l'opérateur ++-pre-increment. Il doit avoir un constructeur de copie, et il doit avoir l'opérateur! =, Et il doit avoir l'opérateur * -dereference-operator.

func_type doit mettre en œuvre l'opérateur d'appel de fonction, en prenant un argument du même type que vous obtenez par déréférencement un objet de type iter_type. Si j'appelle for_each avec des types qui satisfont ces exigences, le code compilera. iter_type peut être n'importe quel type qui répond à ces exigences. Il n'y a rien dans le code qui dise "cela fonctionnera avec les itérateurs de vecteurs et les itérateurs de liste et les itérateurs de cartes". Mais tant que les itérateurs de vecteurs, de listes ou de cartes implémenteront les opérateurs que nous utilisons, cela fonctionnera.

Answer 2

Polymorphism

Answer 3

Chaque algorithme STL est une fonction de modèle qui prend le type d'itération en tant que paramètre de modèle.

Answer 4

Tout algorithme STL est généré automatiquement par le compilateur pour chaque type d'itérateur avec lequel vous l'utilisez.

Il est appelé modèles C++ ou polymorphisme statique.

Answer 5

Les algorithmes STL sont des fonctions de modèle, ce qui signifie qu'ils peuvent être appelés avec n'importe quel type.

Lorsque vous appelez la fonction avec un type spécifique, le compilateur va essayer de compiler une instance de la fonction de ce type et signaler toute erreur de compilation (méthodes manquantes, des erreurs de contrôle de type, etc.)

STL algorithmes, tant que le type utilisé se comporte comme un itérateur (supporte ++, déréférencement), cela fonctionnera. C'est pourquoi ces algorithmes fonctionnent aussi avec des pointeurs natifs, car ils supportent le même type d'opérations que les itérateurs (c'est ainsi qu'ils ont été conçus en premier lieu).

Answer 6

Tous les algorithmes de conteneur/itérateur STL n'ont pas cette indépendance. Ceux qui le font s'appellent des algorithmes génériques, mais ceux-ci sont habituellement juste appelés des algorithmes de STL.

Avec itérateurs seulement vous pouvez:

• inspecter la séquence de sorte que vous pouvez faire des choses comme trouver, compter, for_each, ...
• changement la valeur des références iterator afin que vous puissiez faire des choses comme transformer, copier, faire pivoter, échanger, remplacer, ...
• réorganiser les valeurs des itérateurs, de sorte que vous pouvez faire des choses comme tri, fusion, nth_element.

Certains algorithmes non génériques peuvent être décomposés en 2 étapes, une partie LIST générique et une partie dépendant du conteneur. Donc, afin de détruire toutes les valeurs supérieures à 7 dans un vecteur, nous pouvons faire un remove_if (la partie générique qui ne fait que trier les éléments) suivi d'un effacement (la partie non générique qui détruit la valeur).