Itérateurs générateurs

Cet article présume chez la lectrice ou le lecteur une compréhension de plusieurs concepts avancés de la POO en général et de C++ en particulier. Si vous avez lu et compris le texte sur les itérateurs de points de vue, vous devriez pouvoir lire et comprendre celui-ci sans problème.

Supposons que nous souhaitions créer un vecteur plein de valeurs pseudo-aléatoires. Traditionnellement, le code pour y arriver ressemblerait à ceci :

#include <vector>
#include <cstdlib>
#include <random>
#include <algorithm>
int main() {
   using namespace std;
   random_device rd;
   mt19937 prng { rd() };
   uniform_int_distribution<> d100{ 1, 100 };
   enum { N = 1000 };
   vector<int> v(N);
   generate(begin(v), end(v), [&](){ return d100(prng); });
   // utiliser v...
}

Remarquez que l'initialisation de v se fait en deux temps, soit (a) une construction du conteneur, avec construction de N éléments, et (b) son remplissage par des valeurs générées pseudo-aléatoirement. Dans un tel cas, la construction initiale est essentiellement inutile, puisque les valeurs construites ne seront jamais utilisées.

Il existe un constructeur pour intialiser un conteneur avec des éléments de même valeur. C'est implicitement celui que nous avons utilisé ci-dessus; en n'indiquant pas de valeur initiale pour les éléments de v, le code généré a laissé les éléments non-initialisés – si v avait été un conteneur d'une classe, alors ses éléments auraient été initialisés avec leur constructeur par défaut. On aurait bien sûr pu initialiser les éléments avec d'autres valeurs, comme par exemple :

#include <vector>
#include <string>
int main()
{
   using namespace std;
   enum { N = 1000 };
   vector<int> v0(N); // N int non-initialisés
   vector<string> v1(N); // N instances de string par défaut
   vector<int> v2(N,int{}); // N int de valeur 0
   vector<int> v3(N,3); // N int de valeur 3
   vector<string> v4(N,"J'aime mon prof"); // N messages significatifs
}

Il est aussi possible d'initialiser un conteneur à partir d'une séquence existante, en lui suppléant à la construction une paire d'itérateurs définissant une séquence à demi-ouverte conforme au standard. Ainsi :

#include <vector>
#include <algorithm>
int main() {
   using namespace std;
   int tab[] = { 2, 3, 5, 7, 11 };
   vector<int> v{ begin(tab), end(tab) }; // 2,3,5,7,11
}

Cependant, ceci n'est pas pratique dans un cas comme celui qui nous intéresse : créer un conteneur avec des valeurs pseudo-aléatoires pour... créer un conteneur avec des valeurs pseudo-aléatoires n'est pas, en soi, très productif.

L'idée : un itérateur evanescent

Ce que je vous propose ici est de construire un itérateur evanescent, qui ne correspond pas à un substrat particulier mais bien à une séquence de valeurs – et dans ce cas-ci, on pourrait écrire « séquence » puisque les valeurs seront pseudo-aléatoires, mais l'approche proposée ratissera plus large que la simple génération de telles valeurs.

Nous concevrons donc un itérateur auquel nous confierons une opération nullaire (à zéro opérandes), comme par exemple la fonction std::rand(). À chaque déréférencement, un tel itérateur retournera la plus récente valeur générée par cette opération. De même, l'opération passage au suivant, représentée par l'opérateur ++ préfixé (ou suffixé, l'un appelant l'autre) générera une nouvelle valeur à l'aide de cette opération.

Pour qu'il soit possible pour un conteneur d'évaluer le nombre de valeurs qui seront générées, nous spécialiserons le concept de distance entre deux itérateurs, tel qu'implémenté par la fonction standard std::distance(). Pour ce faire, nous définirons notre itérateur comme étant un itérateur à accès direct (catégorie std::random_access_iterator_tag), comme le sont les itérateurs sur des substrats contigus en mémoire (tableaux bruts, std::array, std::vector, etc.) et nous spécialiserons l'opérateur de soustraction qui permet de déterminer la distance entre deux itérateurs de cette catégorie en temps constant (complexité ).

L'idée du code client souhaité pour notre itérateur générateur s'exprimerait comme ceci (l'écriture est une sorte de pseudocode, pas du C++ légal) :

vector<int> v(generateur(rand), generateur(rand,10));

Remarquez que nous devons spécifier chaque fois la fonction génératrice puisque celle-ci fera partie du type de l'itérateur générateur. Notez aussi qu'il faut trouver un moyen de spécifier le nombre de valeurs à générer; ici, nous présumerons qu'un générateur sera par défaut la « zéro-ième » valeur de la séquence et que, lorsqu'une valeur n sera spécifiée à la construction, cette valeur représentera la nième valeur générée. Deux itérateurs générateurs seront « égaux » lorsqu'ils représenteront le même nombre de valeurs générées, sans égard aux valeurs elles-mêmes (ce qui permet de travailler avec des générateurs de valeurs pseudo-aléatoires).

Détail technique : pour être en mesure de retenir la dernière valeur générée, il nous faudra conserver un attribut dans notre itérateur, or le type de cette valeur dépend du type de ce que retourne la fonction génératrice. Nous pouvons obtenir cette information par des traits, ou encore par l'opérateur statique decltype de C++ 11. Ici, les traits seront notre outil.

Pour déduire le type d'une fonction nullaire à l'aide de traits, la technique décrite à droite fonctionne bien.

Elle distingue un foncteur nullaire documenté à l'aide du type standard std::unary_function de C++ 03 et une fonction nullaire à proprement dit, et identifie chaque fois le type retourné par result_type.

#include <cstdlib>
#include <functional>
template <class R>
   struct nullary_function : std::unary_function<void,R> {
   };
template <class F>
   struct nullary_function_traits {
      using result_type = typename F::result_type;
   };
template <class R>
   struct nullary_function_traits<R(*)()> {
      using result_type = R;
   };

Nous nommerons notre type generator_iterator et le ferons générique sur la base de la fonction génératrice qu'il encapsule et sur le type des valeurs générées – par défaut, ce type sera celui de ce que retourne la fonction génératrice.

Tel que mentionné plus haut, nous conserverons à titre d'état la fonction génératrice, le nombre de valeur générées et la plus récente valeur générée.

#include <iterator>
template <
   class F,
   class T = typename nullary_function_traits<F>::result_type
>
   class generator_iterator : public std::iterator<std::input_iterator_tag, T> {
   public:
      using size_type = std::size_t;
   private:
      F fct;
      size_type cur;
      value_type val;

Remerciement bien senti à Dominique Toupin, du cours IFT729 offert à l'Université de Sherbrooke à la session H2012, pour m'avoir fait remarquer que j'avais erronément catégorisé cet itérateur comme étant un itérateur à accès direct (Random Access) alors qu'il ne permet pas vraiment de revenir en arrière, n'ayant pas de mémoire des valeurs préalablement générées.

Comme il me l'a gentiment fait remarquer, c'est effectivement un beau cas d'itérateur en entrée seule (Input Iterator) comme le sont par exemple les itérateurs de lecture sur des flux.

La raison de mon écart de conduite tenait du fait que j'ai écrit operator-() pour permettre de définir des séquences de taille finie, mais le contrat sémantique d'un itérateur à accès direct est plus complexe que cela. Ceci met en relief que la catégorisation des itérateurs, et la question des concepts de manière générale, est une chose très complexe et très subtile...

À la construction, nous générons une première valeur. Notez que cela signifie qu'étant donné le code proposé ici, un itérateur générateur représentant une fin de séquence appelle aussi la fonction génératrice.

Cet irritant peut être corrigé relativement aisément, cependant (voyez-vous comment?).

Passer au prochain entraîne une modification au nombre de valeurs générées et la génération d'une nouvelle valeur. La valeur la plus récemment générée est obtenue par déréférencement de l'itérateur.

   public:
      generator_iterator(F fct, size_type init = size_type()) : fct{fct}, cur{init} {
         val = fct();
      }
      value_type operator*() const {
         return val;
      }
      generator_iterator& operator++() {
         val = fct();
         ++cur;
         return *this;
      }
      generator_iterator operator++(int) {
         auto temp = *this;
         operator++();
         return temp;
      }

Enfin, la comparaison se base sur le nombre de valeurs générées, et il en va de même pour l'évaluation de la distance entre deux itérateurs générateurs.

      bool operator==(const generator_iterator &autre) const {
         return cur == autre.cur;
      }
      bool operator!=(const generator_iterator &autre) const {
         return !(*this == autre);
      }
      bool operator<(const generator_iterator &autre) const {
         return cur < autre.cur;
      }
      difference_type operator-(const generator_iterator &autre) const {
         return cur - autre.cur;
      }
   };

La fonction génératrice pour des itérateurs générateurs est très simple, malgré une signature quelque peu laborieuse (le code client n'en verra rien).

template <class T, class F>
   generator_iterator<F,T> make_generator_iterator(
      F f,
      typename generator_iterator<F,T>::size_type init = {}
   )
   {
      return { f, init };
   }

Examinons brièvement un programme de démonstration, pour voir à quel point nous serons proches de nos intentions initiales.

Visiblement, notre code de test est très proche du pseudocode annoncé.

Le vecteur v y est construit à partir d'une séquence de N valeurs pseudo-aléatoires, sans génération de valeurs intermédiaires bidon comme dans le cas initial.

#include <vector>
#include <algorithm>
#include <iostream>
#include <random>
int main() {
   using namespace std;
   random_device rd;
   mt19937 prng { rd() };
   uniform_int_distribution<> d100{ 1, 100 };
   auto gen = [&]() { return d100(prng); };
   enum { N = 10 };
   vector<int> v(make_generator_iterator<int>(gen), make_generator_iterator<int>(gen,N));
   for(auto n : v)
      cout << n << ' ';
   cout << endl;
}

Comment testeriez-vous cet itérateur pour en valider les impacts sur les performances à l'exécution?

Variantes sur le même thème

Le sympathique Benoît Bayol m'a écrit ceci (je paraphrase certains passages pour les besoins de l'article; j'espère qu'il me pardonnera) :

« Bonjour, [...].

À deux reprises, il y a une chose qui m'a interpellé sur les vecteurs. Sur la page CPP--Tableaux-2D.html et la page (celle-ci), vous utilisez soit le constructeur, soit resize() pour définir votre vecteur et en argumentant que le problème de ces deux appels est la création de valeurs bidons non-nécessaires.

Il y a en fait une technique qui permet d'éviter ça : combiner reserve() avec generate_n() et un back_inserter. Par exemple :

class generator {
   int state;
public:
   generator(int state) :state{ state } {
   }
   int operator()() {
      return state++;
   }
};
// ...
#include <vector>
#include <algorithm>
#include <iterator>
int main() {
   using namespace std;
   vector<int> v;
   v.reserve(100);
   generate_n(back_inserter(v), 100, generator{42});
   // ...
}

Suite à cette génération de valeurs, v contiendra 42, 43, 44, 45, ... De cette façon il n'y a pas de création de valeurs bidon, et on peut passer une fonction génératrice à états.

Amicalement, Benoît. »

En effet. Comme je le lui indiquais dans ma réponse, le problème avec un site de l'ampleur de h-deb, c'est que les pages ne sont pas toutes tenues à jour en tout temps. J'enseigne à mes étudiantes et à mes étudiants ce qui sous-tend les vecteurs, incluant l'allocation de mémoire brute, l'initialisation par construction positionnelle – le placement new – avec allocateurs ou non, et ainsi de suite) mais ce n'est pas à la portée de tout le monde, vous le comprendrez, alors les pages sur le site varient en complexité et les considérations plus pointues quant aux performances de niveau professionnel ne sont pas présentes dans tous les articles, dépassant probablement les besoins d'une partie de mon lectorat.

Permettez-moi une parenthèse technique, dans laquelle je me limiterai à un survol de concepts plus complexes. Notez que la proposition de Benoît comporte deux volets :

Ceci fonctionne car les conteneurs standards font une distinction entre allouer (de la mémoire brute, non-initialisée), ce qui modifie la capacité du conteneur, et insérer (une copie d'un élément, par exemple), ce qui accroît la taille exprimée en nombre d'éléments et telle que rapportée par la fonction size(). Lorsque cela s'avère possible, allouer sans initialiser est plus rapide qu'allouer puis initialiser; de même, insérer un élément dans un conteneur dont la capacité est a priori suffisante (donc supérieure à sa taille) peut être très rapide – dans un vecteur standard, une telle insertion se fait en temps constant lorsqu'elle est réalisée en fin de conteneur, d'où l'intérêt de l'opération push_back().

La suggestion de Benoît (une technique que j'applique dans certains programmes de la section Exemples et sources, entre autres) m'a aussi rappelé qu'il y a lieu de présenter des approches alternatives pour initialiser efficacement des séquences. En voici quelques-unes.

L'algorithme std::iota()

Il existe, avec C++ 11, un algorithme standard std::iota(), logé dans <numeric>, qui implémente le concept d'initialiser une séquence avec des valeurs consécutives. Par exemple :

#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>
int main() {
   using namespace std;
   vector<int> v(100);
   iota(begin(v), end(v), 42);
   for(auto n : v)
      cout << n << endl;
}

Ceci n'améliore toutefois pas les « performances », au sens où le conteneur de destination de la fonction iota() doit contenir des éléments au préalable. Toutefois, dans certaines circonstances, cet algorithme peut simplifier les choses.

Un value_iterator

Une autre alternative serait de passer par un itérateur sur des valeurs, que je nommerai ici un value_iterator<T>, et d'insérer les éléments en fin de conteneur avec la méthode insert() avec séquence standard :

#ifndef VALUE_ITERATOR_H
#define VALUE_ITERATOR_H
#include <iterator>
template <class T>
   class value_iterator : public std::iterator<std::random_access_iterator_tag, T, T> {
      T cur;
   public:
      value_iterator(const T &val) : cur{ val } {
      }
      value_iterator& operator++() {
         ++cur;
         return *this;
      }
      value_iterator operator++(int) {
         auto temp = *this;
         operator++();
         return temp;
      }
      value_iterator& operator--() {
         --cur_;
         return *this;
      }
      value_iterator operator--(int) {
         value_iterator temp(*this);
         operator--();
         return temp;
      }
      bool operator==(const value_iterator &vi) const {
          return cur == vi.cur;
      }
      bool operator!=(const value_iterator &vi) const {
         return cur != vi.cur;
      }
      bool operator<(const value_iterator &vi) const {
         return cur < vi.cur;
      }
      bool operator<=(const value_iterator &vi) const {
         return cur <= vi.cur;
      }
      bool operator>(const value_iterator &vi) const {
         return cur > vi.cur;
      }
      bool operator>=(const value_iterator &vi) const {
         return cur >= vi.cur;
      }
      T operator*() const {
         return cur;
      }
      value_iterator& operator+=(int n) {
         cur_ += n;
         return *this;
      }
      value_iterator& operator-=(int n) {
         cur_ -= n;
         return *this;
      }
      friend typename
         std::iterator_traits<value_iterator>::difference_type operator+(value_iterator vi, value_iterator vj) {
            return vi.cur + vj.cur;
         }
      friend typename
         std::iterator_traits<value_iterator>::difference_type operator+(value_iterator vi, int n) {
            return vi.cur + n;
         }
      friend typename
         std::iterator_traits<value_iterator>::difference_type operator+(int n, value_iterator vi) {
            return vi.cur + n;
         }
      friend typename
         std::iterator_traits<value_iterator>::difference_type operator-(value_iterator vi, value_iterator vj) {
            return vi.cur - vj.cur; }
      friend typename
         std::iterator_traits<value_iterator>::difference_type operator-(value_iterator vi, int n) {
            return vi.cur - n;
         }
      friend typename
         std::iterator_traits<value_iterator>::difference_type operator-(int n, value_iterator vi) {
            return vi.cur - n;
         }
   };
//
// Fonction génératrice
//
template <class T>
   value_iterator<T> val_it(const T &val) {
      return { val };
   }
#endif
 
//
//
//
#include "value_iterator.h"
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
   using namespace std;
   vector<int> v;
   v.insert(end(v), val_itt(42), val_it(142)); // bingo!
   for(auto n : v)
      cout << n << endl;
}

Au fond, c'est un « vieux truc » : faire passer un entier comme un itérateur avec une très légère couche de maquillage. L'opération insert() acceptant la séquence à insérer en bloc, le conteneur est en mesure de gérer efficacement sa mémoire, quitte à allouer plus que distance(debut,fin) – en supposant que debut et fin soient les valeurs retournées par les appels à la fonction génératrice val_it() – si le conteneur le juge opportun.

Cette insertion en bloc aurait d'ailleurs pu être appliquée avec les itérateurs générateurs proposés plus haut, mais le constructeur de séquence utilisé dans le programme de test est au moins aussi efficace.

#include "value_iterator.h"
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
   using namespace std;
   vector<int> v(val_it(42), val_it(142)); // bingo!
   for(auto n : v)
      cout << n << endl;
}

Valid XHTML 1.0 Transitional

CSS Valide !