Itérateurs générateurs

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 = 1'000 };
   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 = 1'000 };
   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é $O(1)$ ).

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.

#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;
   };

#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;

   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;
      }

      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;
      }
   };

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.

#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) :

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});
   // ...
}

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.

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;
}

#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;
}