Itérateurs de points de vue (ou de filtrage)

Imaginons un problème simple : afficher tous les éléments pairs d'un tableau d'entiers. Ou, plus généralement : appliquer une opération à tous les éléments d'une séquence pour lesquels un certain prédicat s'avère.

Écrit à la main, la solution à ce problème dans sa version spécifique (afficher les entiers pairs) est somme tout simple :

#include <iostream>
// le prédicat qui nous servira ici
bool est_pair(int n) noexcept {
   return n % 2 == 0;
}
// programme de démonstration
int main() {
   using namespace std;
   const int N = 10;
   int tab[N];
   // remplir le tableau de valeurs distinctes
   for (int i = 0; i < N; ++i)
      tab[i] = i;
   // pour chaque élément du tableau
   for (int i = 0; i < N; ++i)
      // si le prédicat choisi est vrai lorsque appliqué à l'élément
      if (est_pair(tab[i])
         // opérer sur l'élément
         cout << tab[i] << ' ';
   cout << endl;
}

Malheureusement, elle est à réécrire chaque fois que nous avons à résoudre un problème semblable. De même, elle peut se compliquer si les données du problème se compliquent elles aussi (forme de la boucle, complexité du test, richesse des opérations à réaliser, etc.).

On peut réécrire le tout de manière manuelle mais modulaire, ce qui facilite la construction rapide de solutions à des problèmes semblables :

#include <iostream>
#include <algorithm>
using namespace std;
// le prédicat qui nous servira ici
bool est_pair(int n) noexcept {
   return n % 2 == 0;
}
// initialiser la séquence dans le tableau
template <class It, class T>
   void initialiser_sequence(It debut, It fin, class T) {
      for (; debut != fin; ++i, ++debut)
         *debut = init++;
   }
// opérer sur un élément
void operation(int n) {
   cout << n << ' ';
}
// programme de démonstration
int main() {
   const int N = 10;
   int tab[N];
   // remplir le tableau de valeurs distinctes
   initialiser_sequence(begin(tab), end(tab), 0);
   // pour chaque élément du tableau
   for(auto n : tab)
      if (est_pair(tab[i])
         operation(tab[i]);
   cout << endl;
}

La bibliothèque standard de C++, en particulier à travers les algorithmes standards de la STL, propose aussi une solution simple et élégante (et nettement plus générique, donc plus réutilisable). Notre version proposera plus de code mais l'essentiel de ce qui sera écrit ici sera pleinement réutilisable dans de multiples projets :

#include <iostream>
#include <algorithm>
using namespace std;
//
// la classe Naturels est un foncteur générant à chaque appel le
// prochain entier naturel d'une séquence d'entiers naturels
//
class Naturels {
public:
   using value_type = unsigned int;
private:
   value_type cur;
public:
   Naturels(value_type init = {}) : cur{init} {
   }
   value_type operator()() noexcept {
      return cur++;
   }
};
bool est_pair(int n) noexcept {
   return n % 2 == 0;
}
void operation(int n) {
   cout << n << ' ';
}
void operation_potentielle(int n) {
   if (est_pair(n)) operation(n);
}
int main() {
   const int N = 10;
   int tab[N];
   // générer une séquence d'entiers naturels
   generate(begin(tab), end(tab), Naturels{});
   // opérer sur chaque élément de la séquence
   for_each(begin(tab), end(tab), operation_potentielle);
}

Contrairement aux croyances, la version STL sera (lorsque compilée en mode Release) plus rapide que les versions programmées manuellement. Notez qu'il aurait été possible d'écrire operation_potentielle() de manière beaucoup plus générique, mais je vous laisse y réfléchir (c'est divertissant). Une λ aurait aussi été à propos ici, de même qu'un appel à l'algorithme std::iota().

Remarquez l'optique choisie :

• Examiner tous les éléments
• Appliquer un prédicat à chaque élément
• Si le prédicat s'avère pour un élément, alors lui appliquer une opération

C'est là presque une démarche philosophique : écrire une opération contenant son propre code de validation à travers un prédicat et l'appliquer à tous les éléments d'une séquence.

Une autre approche, que j'aimerais explorer ici, est de considérer la séquence comme un point de vue sur les données et de faire de l'action passer à l'élément suivant une opération capable de filtrer les éléments de manière telle que seuls les éléments pertinents à une recherche soient examinés. Cette approche sera parfois préférable, parfois pire qu'une approche STL classique^[1].

L'idée : un pattern_iterator

Je vous propose donc une classe que je nommerai pattern_iterator. Il s'agira d'une classe d'enrobage (d'une Wrapper Class) capable de :

• Comprendre la structure d'une séquence à l'aide d'itérateurs plus primitifs
• Implémenter l'opération passer au prochain (ou, en termes techniques, l'opération ++) par une combinaison des opérateurs ++ des itérateurs effectifs et d'un prédicat, et
• De se comporter comme un itérateur traditionnel sur la séquence effective pour l'ensemble des autres opérations

Nous pourrons donc définir un itérateur qui n'ira que d'un élément valide à l'autre (le terme valide étant pris ici au sens de respectant la contrainte exprimée par le prédicat) plutôt que d'un élément à l'autre tout simplement.

Avantage de cette stratégie : imaginons une masse de personnages dans un jeu vidéo (tiens : des instances de la classe Orque et des instances de la classe Elfe, par exemple). Tout à coup, un sorcier lance un sort tel que tous les méchants sont frappés par la foudre. Parmi les options possibles pour implémenter un tel effet :

• Une répétitive écrite manuellement
• Une stratégie avec un itérateur classique, un algorithme std::for_each() et une opération (fonction ou foncteur, λ incluses, selon le cas) qui examine chaque élément et décide s'il y a lieu de le frapper ou non d'un éclair, et
• Une stratégie ou un itérateur de point de vue (un pattern_iterator) n'accède qu'aux méchants (décrits par un prédicat), ce qui permet d'écrire une simple opération frappant un élément d'un éclair sans se préoccuper de savoir si cet élément représente un méchant ou non.

Il est probable que les deux dernières options offrent un niveau de performance comparable (ou identique), mais si un pattern_iterator est bien écrit une fois, la solution à tous les problèmes de ce genre sera de facto simplifiée. Viser la dernière option signifie chercher à la fois performance à l'exécution et économie (à moyen terme) en temps de développement.

La difficulté : ne pas dépasser la fin de la séquence

Tel que proposé, un pattern_iterator doit connaître non seulement sa position courante mais aussi la fin de la séquence. La raison pour cela est que le parcours filtré de la séquence implique une logique partielle de parcours de séquence à même l'opération passage au suivant; négliger d'informer l'itérateur de la fin de la séquence à parcourir mènerait la plupart des parcours à des débordements de séquences.

Sachant cela, il est important d'implémenter passage au suivant de manière efficace pour éviter de dégrader la performance d'ensemble. J'aurai pour ce faire recours à un algorithme standard (std::find_if()) offrant les garanties de performance attendues.

Implémentation opérationnelle de pattern_iterator

Ce qui suit détaille une implémentation opérationnelle du type pattern_iterator tel que proposé plus haut. Nous mettrons en place quelques outils qui nous permettront d'écrire du code plus élégant, puis nous montrerons comment mettre en place une première implémentation de notre classe. Par la suite, nous examinerons quelques raffinements possibles à cette implémentation dans le but d'en accroître la convivialité sans en diminuer la vitesse.

#include <iostream>
#include <algorithm>
#include <iterator>
// using...
class Naturels {
   // ...
};

template <class, class>
   class pattern_iterator;
namespace std {
   template <class It, class P>
      struct iterator_traits<pattern_iterator<It, P>> : iterator_traits<It> {
      };
}
template <class It, class P>
   class pattern_iterator
      : public std:iterator<
           typename iterator_traits<It>::value_type,
           typename iterator_traits<It>::iterator_category
        >
   {

   private:
      It cur, fin;
      P patt;
      void seek_next() {
         cur_ = std::find_if(cur, fin, patt);
      }

Les constructeurs dont nous avons besoin ici sont la version paramétrique et la version par copie, mais la Sainte-Trinité générée par le compilateur nous sufit amplement du fait que pattern_iterator est un simple type valeur.

   public:
      pattern_iterator(It cur, It fin, P pattern) : cur{cur}, fin{fin}, patt{pattern} {
         seek_next();
      }

      bool operator==(const pattern_iterator &p) const {
         return cur == p.cur;
      }
      bool operator!=(const pattern_iterator &p) const {
         return !(*this == p);
      }
      bool operator<(const pattern_iterator &p) const {
         return cur < p.cur;
      }

      pattern_iterator& operator++() {
         ++cur;
         seek_next();
         return *this;
      }
      pattern_iterator operator++(int) {
         pattern_iterator temp(*this);
         operator++();
         return temp;
      }

      value_type& operator*() {
         return *cur;
      }
      value_type operator*() const {
         return *cur;
      }
   };

bool est_pair(int n) noexcept {
   return n % 2 == 0;
}
int main() {
   const int N = 10;
   int tab[N];
   generate(begin(tab), end(tab), Naturels{});
   copy(
      pattern_iterator<int*, bool(*)(int)>
         (begin(tab), end(tab), est_pair),
      pattern_iterator<int*, bool(*)(int)>
         (begin(tab), end(tab), est_pair),
      ostream_iterator<int>{cout, " "}
   );
}

Chaque pattern_iterator doit être spécifié à partir de deux types (dont l'un des deux est un type de pointeur de fonction, rien de moins!) et de trois paramètres. C'est clairement une approche déraisonnable : on ne peut faire reposer sur les épaules du code client une stratégie d'écriture aussi lourde car personne ne voudra se servir de notre itérateur dans un tel cas.

Nous procéderons donc maintenant par ajout de quelques outils qui nous permettront de raffiner la convivialité de notre pattern_iterator du point de vue du code client. Comme c'est notre habitude, nous chercherons à atteindre ce raffinement à coût zéro dans le code une fois celui-ci compilé.

Première simplification : une fonction de fabrication

Remarquons tout d'abord un détail important en programmation générique (du moins en C++) quant aux fonctions en comparaison avec les types.

En effet, examinons un premier exemple de code tout simple. Cet exemple déclarera un pointeur intelligent standard capable de contenir un pointeur sur un int, d'en garantir la libération et de permettre une indirection intelligente vers le pointé.

#include <iostream>
#include <memory>
int main() {
   using namespace std;
   unique_ptr<int> p{new int{3}};
   cout << *p;
}

Cette restriction explique la lourdeur de notre déclaration de pattern_iterator : si nous reprenons la déclaration de ceux utilisés dans l'invocation de std::copy(), plus haut, nous constatons que les deux types impliqués doivent être indiqués pour chaque itérateur :

pattern_iterator<int*, bool(*)(int)>(begin(tab), end(tab), est_pair)
pattern_iterator<int*, bool(*)(int)>(end(tab), end(tab), est_pair)

Maintenant, examinons un exemple fonctionnellement identique mais structurellement différent.

#include <iostream>
#include <memory>
using namespace std;
template <class T>
   unique_ptr<T> creer(T *p) {
      return unique_ptr<T>{p};
   }
int main() {
   cout << *creer(new int{3});
}

Pour distinguer une fonction d'une autre en C++, il faut examiner leur signature qui comprend, entre autres choses, le type et le nombre de ses paramètres. Dans la déduction des types d'une fonction générique, le compilateur évalue donc le type de ses paramètres et fait, au besoin, les liens qui s'imposent.

Pour alléger la construction de nos itérateurs, nous utiliserons donc ici cette technique et nous passerons par une fonction de création de pattern_iterator que nous nommerons make_pattit(). Dans la mesure où notre programme principal n'a pas besoin de déclarer de variables pour contenir les instances de pattern_iterator ainsi générées, le code en sera quelque peu allégé.

Le code modifié ou ajouté suit. Je ne répéterai pas tout ce qui a déjà été exprimé par souci d'économie; référez-vous aux sections précédentes pour le reste du code.

// ...
template <class It, class P>
   pattern_iterator<It,P> make_pattit(It debut, It fin, P pattern) {
      return { debut, fin, pattern};
   }
// ...
int main() {
   const int N = 10;
   int tab[N];
   generate(begin(tab), end(tab), Naturels{});
   copy(make_pattit(begin(tab), end(tab), est_pair),
        make_pattit(end(tab), end(tab), est_pair),
        ostream_iterator<int>{cout, " "});
}

Pour bien isoler le gain de lisibilité obtenu ici, comparez la syntaxe associée à l'instanciation du pattern_iterator sur le début de la séquence sans utiliser make_pattitt() (à gauche) avec celle obtenue en utilisant cet outil (à droite). La simplification de l'écriture n'est assurément pas négligeable.

pattern_iterator<int*, bool(*)(int)> {begin(tab), end(tab), est_pair}

make_pattit(begin(tab), end(tab), est_pair)

Deuxième simplification : un type général de type

Autre élément caractéristique de la lourdeur syntaxique de notre écriture permettant d'instancier un type : elle est très répétitive. Pour chaque paire d'itérateurs, il est nécessaire d'exprimer deux fois l'itérateur de fin de séquence et il est aussi nécessaire d'exprimer deux fois le prédicat de filtrage. Pour cet irritant, une fonction ne sera pas la solution (il faudrait l'invoquer deux fois elle aussi et le problème demeurerait entier).

Une solution simple est de définir un type dont le rôle est de décrire à la fois le début et la fin d'une séquence déterminée par un pattern_iterator. Un tel type, portant le nom un peu long de pattern_iterator_descriptor, suit. À partir des trois paramètres usuels, il définit deux constantes représentant le début et la fin de la séquence et permet donc, à travers une même variable, d'obtenir sous forme compacte et allégée les deux extrémités de la séquence.

// ...
template <class It, class P>
   struct pattern_iterator_descriptor {
      using iterator_type = It;
      using pattern_type = P;
      pattern_iterator<iterator_type, pattern_type> debut;
      pattern_iterator<iterator_type, pattern_type> fin;
      pattern_iterator_descriptor(iterator_type debut, iterator_type fin, pattern_type patt) : debut{debut, fin, patt}, fin{fin, fin, patt} {
      }
      pattern_iterator<iterator_type, pattern_type> begin() {
         return debut;
      }
      pattern_iterator<iterator_type, pattern_type> end() {
         return fin;
      }
   };
template <class It, class P>
   pattern_iterator_descriptor<It, P>
      make_pattern_iterator_descriptor(It debut, It fin, P patt) {
         return { debut, fin, patt };
      } 
// ...
int main() {
   const int N = 10;
   int tab[N];
   generate(begin(tab), end(tab), Naturel{}));
   auto pidp = make_pattern_iterator_descriptor(begin(tab), end(tab), est_pair);
   copy(begin(pidp), end(pidp), ostream_iterator<int>{cout, " "});
}

L'invocation de std::copy() est encore une fois allégée, au prix d'avoir au préalable instancié un pattern_iterator_descriptor. L'exemple ci-dessous montre l'invocation de std::copy() avant (à gauche) et après (à droite) application de cette technique.

copy (
   make_pattit(begin(tab), end(tab), est_pair),
   make_pattit(end(tab), end(tab), est_pair),
   ostream_iterator<int>(cout, " ")
);

copy (
   begin(pidp),
   end(pidp),
   ostream_iterator<int>{cout, " "}
);

On peut encore simplifier le tout, mais ça devient plus subtil.

Spécialiser dans un algorithme

Revenons maintenant aux premières manipulations faites dans le but de simplifier le tout et souvenons-nous que le recours au mécanisme permettant de déduire automatiquement les types requis à partir du type des paramètres dans le cas où une fonction est générique.

L'opération d'itérer à travers une séquence et de filtrer les éléments peut se représenter sous la forme d'une fonction, qu'on pourrait nommer afficher_si(). Ce faisant, les descripteurs d'itérateurs peuvent être définis dans la fonction à partir des types des paramètres, élaguant complètement les déclarations de types complexes dans le code client.

Une application de cette stratégie suit. Notez que nous construisons ici encore sur les résultats des simplifications précédentes. Chaque étape était un gain en soi.

// ...
template <class It, class P>
   void afficher_si(It debut, It fin, P patt) {
      using value_type = typename iterator_traits<It>::value_type;
      auto pid = make_pattern_iterator_descriptor(debut, fin, patt);
      copy(begin(pid), end(pid), ostream_iterator<value_type>{cout, " "});
   }
int main() {
   const int N = 10;
   int tab[N];
   generate(begin(tab), end(tab), Naturels{});
   afficher_si(begin(tab), end(tab), est_pair);
}

Raffinements

Pour représenter habilement un itérateur de filtrage applicable à une séquence, notre petite classe pattern_iterator devrait aussi implémenter un certain nombre d'opérations telles que, dans le respect de SFINAE bien entendu :

• L'opérateur + prenant en paramètre un entier, pour permettre le recours à un algorithme comme random_shuffle() (à titre d'exemple, car cet algorithme est déprécié)
• L'opérateur - prenant en paramètre un pattern_iterator sur la même séquence, pour permettre le recours à la déclinaison efficace de l'algorithme std::distance() et pour permettre le recours à un algorithme comme std::sort()
• Investiguer l'implémentation de l'opérateur -- sur un pattern_iterator et voir les impacts que cela aurait sur sa structure et sa taille
• examiner la question de l'implémentation d'un reverse_iterator sur un pattern_iterator quelconque, etc.

Sachant que certaines de ces opérations ne sont permises que sur quelques catégories d'itérateurs, pas tous^[3], il faudrait aussi examiner la question suivante : que faire dans un pattern_iterator dans le cas où l'itérateur sous-jacent (le type It) ne permet pas certaines opérations.

Il est possible de détecter (par des traits d'itérateurs) le support ou non de certaines opérations par le type d'itérateur sous-jacent. Cela dit, devrait-on :

• Mettre ces opérations en place malgré tout dans la classe pattern_iterator, quitte à ce que ces opérations soient inefficaces?
• Mettre ces opérations en place mais seulement pour le type d'itérateur en fonction duquel ce serait efficace, faisant par exemple le choix de n'implémenter l'opérateur -- dans un pattern_iterator que par l'opérateur -- de son type It, et laisser le compilateur indiquer les messages d'erreur lui semblant appropriés si quelqu'un cherche, par exemple, à itérer à rebours sur un pattern_iterator autour d'un itérateur de liste simplement chaînée? ou encore
• Implémenter ces opérations pour un type d'itérateur sur lesquelles elles sont efficaces et mettre en place des mécanismes de génération de messages d'erreurs explicites?

Un chic exercice de programmation pour les intéressé(e)s.

^[1]Si le critère est trouver le prochain élément en ordre croissant, par exemple, chaque passage au prochain élément aura une complexité linéaire et un affichage complet d'une séquence sera de complexité quadratique, bien pire qu'un tri fait au préalable.

^[2]Avec C++ 11, il est possible, à l'aide d'applications novatrices du mot clé auto, qui existe depuis les années '70 mais dont personne ne se sert vraiment, et d'un nouveau mot clé (decltype), d'automatiser certaines déductions de types à la compilation... mais pas celles-ci.

^[3]Par exemple, l'opérateur --, au sens de passage au précédent, n'a de sens que sur un itérateur bidirectionnel.