Parcourir une séquence sans itérateurs

Il arrive que l'on souhaite décrire le parcours d'une séquence sans avoir recours à des itérateurs (au sens STL du terme). Par exemple, dans le cas où la séquence à parcourir repose sur une structure polymorphique :

Bien que ces pratiques soient plus idiomatiques de langages comme Java ou C#, dû à la structure et aux contraintes propres à leurs systèmes de types, il arrive que de telles structures surviennent même en C++. Ce qui suit montre brièvement comment on pourrait y parvenir.

Nous utiliserons des outils et des techniques de C++ 11. Si vous utilisez un compilateur C++ 03, il est possible que deviez procéder à quelques ajustements pour que le tout compile (rien d'irrémédiable, cela dit).

Un exemple simple – parcourir une séquence d'entiers pairs

La démarche qui suit montre un exemple d'implémentation d'une énumération ne permettant pas de modifier l'objet sur lequel elle opère. Évidemment, cela ne protège pas le code client contre des accès concurrents sur la séquence en cours d'énumération. Nous utiliserons une interface d'énumération générique sur la base du type des valeurs à énumérer. Les services que nous demanderons aux divers énumérateurs d'implémenter seront les suivants :

  • La méthode current(), qui permettra de retourner une copie de l'élément vers lequel mène actuellement l'énumérateur
  • La méthode has_next(), qui retourne true seulement s'il est possible d'avancer encore d'au moins un élément dans l'énumération, et
  • La méthode next(), qui mène l'énumérateur vers le prochain élément de la séquence
 
template <class T>
   struct IEnumerateur {
      virtual T current() const = 0;
      virtual bool has_next() const = 0;
      virtual void next() = 0;
      virtual ~IEnumerateur() = default;
   };

Quelques remarques à ce sujet :

Examinons maintenant la séquence à parcourir. Pour les besoins de notre exemple, qui se veut simple, la séquence en question sera les entiers pairs entre deux bornes.

Pour les besoins de la cause, nous aurons recours à des traits numériques et à des pointeurs intelligents. Puisque nous ne supportons pas, avec cette implémentation, le parcours de séquences vides, nous représenterons cette réalité par une levée d'exception.

 
#include <limits>
#include <memory>

class SequenceVide {};

Le recours aux traits tient au fait que nous ne permettrons pas de parcourir des séquences de types T non-entiers pour un Pairs<T> donné. Nous vérifions cette caractéristique de T par numeric_limits<T> en y examinant la constante statique is_integer qui ne sera vraie que pour les types entiers comme char, short, long, bool, int, etc. et en vérifiant cet état par une assertion statique (une technique de métaprogrammation devenue concept de langage avec C++ 11 parce que tellement utile!)

J'exposerai le type T sous la forme du type interne et public value_type, que j'utiliserai par la suite dans mon propre code. En particulier, les attributs marquant les bornes minimale et maximale de la plage de nombres pairs à explorer seront de ce type.

 
template <class T>
   class Pairs {
      static_assert(
         std::numeric_limits<T>::is_integer,
         "Seuls les types entiers sont supportés"
      );
   public:
      using value_type = T;
   private:
      value_type min_, max_;

Étant donné que l'énumérateur ne sert qu'à énumérer des entiers pairs entre deux bornes, l'énumérateur sera simple. Comme c'est souvent le cas, j'ai implémenté le tout par une classe interne et privée (le code client ne l'utilisera qu'à travers son interface, alors c'est une implémentation tout à fait convenable).

Pour ce qui est de la validation des bornes, j'ai fait les choix suivants :

  • Je vérifie les bornes illégales (borne inférieure plus grande que borne supérieure) à la construction de l'énumérateur. Du fait que j'accepte des bornes dynamiques, j'ai choisi de lever une exception dans le cas de bornes illégales. Le nom de l'exception est discutable
  • J'ai implémenté has_next() de manière à ce qu'il fonctionne même si maxval vaut numeric_limits<T>::max(), mais il reste un bogue (dans le cas d'un maxval légal mais négatif). Le voyez-vous? Je vous laisse la chose en exercice : quelle est la meilleure manière de le corriger, selon vous?
  • Je présume la valeur initiale paire. C'est un choix de design qui se défend du fait que mon énumérateur est interne à Pairs, donc que j'en contrôle pleinement la construction. Cela simplifie l'implémentation de la méthode next()
 
      class Enumerateur : public IEnumerateur<value_type> {
         value_type val, maxval;
      public:
         Enumerateur(value_type init, value_type maxval)
            : val{init}, maxval{maxval}
         {
            if (val > maxval) throw SequenceVide{};
         }
         value_type current() const {
            return val;
         }
         bool has_next() const {
            return maxval - current() >= 2;
         }
         void next() {
            val += 2;
         }
      };

La valeur initiale d'un parcours sera nécessairement paire pour l'énumérateur (c'est un choix politique que j'ai fait), mais la valeur minimale d'un Pairs peut ne pas l'être. J'utilise la méthode first() pour déterminer quelle devrait être le début d'une énumération d'entiers pairs à partir de la borne minimale fournir à la construction d'un Pairs.

Comprenez-vous l'algorithme? Il se base sur le fait que le reste de la division par 2 d'un entier n...

  • Soit 0 si n est pair (donc rien à ajouter pour avoir un entier pair)
  • Soit -1 si n est impair et négatif, et
  • Soit 1 si n est impair et positif

On peut écrire l'expression autrement, bien sûr.

 
      constexpr value_type first() const {
         return min_ < 0? min_ + -(min_ % 2) : min_ + min_ % 2;
      }

Obtenir un énumérateur peut se faire de plusieurs manière. J'ai choisi de passer par une instanciation dynamique, mais pour éviter de laisser filtrer des pointeurs bruts vers le code client, j'ai eu recours à un pointeur intelligent, responsable de la gestion de la durée de vie du pointé.

Remarquez le recours à la méthode first() pour assurer la parité de la borne minimale d'énumération.

 
   public:
      std::unique_ptr<IEnumerateur<value_type>> enumerateur() const {
         return std::make_unique<Enumerateur>(first(), max_);
      }

J'ai défini deux constructeurs, chacun étant somme toute banal. Par défaut, mes plages vont de 0 à la borne maximale du type T, alors que j'accepte des bornes quelconques dans le constructeur paramétrique.

Normalement, un objet assurera son intégrité dès sa construction; conséquemment, le code à droite manque de rigueur (il est possible d'instancier un Pairs dont les états seraient irrespectueux des invariants de cette classe). À titre d'exercice, corrigez le code à droite pour déplacer la validation requise aux endroits opportuns.

 
// ...
      constexpr Pairs() : min_{}, max_{std::numeric_limits<value_type>::max()} {
      }
      constexpr Pairs(value_type minval, value_type maxval) : min_{minval}, max_{maxval} {
      }
   };

Reste à examiner un code client possible.

Pour le plaisir, j'ai choisi d'écrire un programme qui pourra en surprendre certains. Ainsi :

  • L'entière définition de main() est un bloc try...catch, ce qui est légal pour toute fonction (incluant les méthodes, bien sûr, en particulier les constructeurs)
  • J'ai inséré une boucle infinie (for(;;) qui est communément nommé le for ever) et j'ai choisi de quitter le programme lorsque le code client créera une séquence illégale de pairs
  • Une fois les entrées consommées au clavier, le programme crée une séquence d'entiers pairs, en obtient un énumérateur et parcourt la séquence ainsi représentée, affichant la valeur de chacun de ses éléments

Remarquez que les blocs catch n'ont, dans un cas comme celui-ci, aucun accès à quelque donnée que ce soit locale au bloc try. Conséquemment, si nous souhaitions laisser filtrer les bornes de la séquence erronnée du bloc try vers le bloc catch approprié, il faudrait que les valeurs de ces bornes soient transférées à l'aide de l'exception elle-même (qui est la seule entité percolant de l'un vers l'autre)

 
#include <iostream>
using namespace std;
int main() try {
   for (;;) {
      short minval, maxval;
      cout << "De ... a ...? " << flush;
      if (cin >> minval >> maxval) {
         Pairs<short> p{minval, maxval};
         auto e = p.enumerateur();
         while(e->has_next()) {
            cout << e->current() << ' ';
            e->next();
         }
         cout << e->current() << endl;
      }
   }
} catch (SequenceVide) {
   cerr << "Sequence vide" << endl;
} catch (...) {
   cerr << "Oh. Imprevu..." << endl;
}

Les versions initiales des plateformes Java et .NET offraient des itérateur/ énumérateurs sur des objets au sens large du terme, une sorte d'effacement de types. Bien que cette approche soit possible (nous pourrions le faire aussi en C++), elle n'est pas souhaitable, réduisant la capacité qu'a le système de types d'un langage de nous offrir un soutien adéquat.

Autre exemple – parcourir une séquence de mots

Ce qui suit est un autre exemple, banal, d'énumérateur. Celui-ci permet de parcourir une séquence de mots entreposés dans une instance d'une classe nommée Mots. Pour élargir la discussion, la classe Mots exposera deux sortes d'énumérateurs : l'un (Mots::Enumerateur) permettra de consulter les valeurs entreposées dans un Mots telles quelles; l'autre (Mots::Transformateur<F>) permettra d'appliquer une transformation F aux éléments énumérés lors de leur consultation.

L'interface d'énumération demeurera la même que dans les cas plus banals que nous avons couverts précédemment. Respectant la forme classique des énumérateurs (débuter avant le premier élément), nous allons à l'encontre des idiomes de C++ (arrêter une fois passé le dernier élément) ce qui nous forcera à faire quelques manoeuvres sous-optimales en cours de route.

 
template <class T>
   struct IEnumerateur {
      using value_type = T;
      virtual bool has_next() const = 0;
      virtual void next() = 0;
      virtual value_type current() const = 0; 
      virtual ~IEnumerateur() = default;
   };

La classe Mots entreposera des chaînes de caractères (on présume des mots, mais la classe ne fait rien pour le garantir) dans un vecteur de chaînes de caractères.

La classe interne et privée Enumerateur ne permettra que de parcourir les éléments entreposés dans un Mots donné.

La classe interne et privée Transformateur<F> permettra de parcourir les éléments entreposés dans un Mots donné, et appliquera un F à chaque chaîne de caractères consommé par sa méthode current(). Notez que ceci ne modifiera pas la séquence en cours d'énumération (la transformation n'est appliquée que sur une copie de la donnée lue, pour le bénéfice du code client).

Exercice : pouvez-vous exprimer Enumerateur par un Transformateur<F> pour lequel F ne ferait rien? Quel serait l'impact sur le code de Mots proposé à droite? Serait-ce avantageux?

 
#include <string>
#include <vector>
#include <algorithm>
#include <memory>
class Mots {
public:
   using str_type = std::string;
private:
   std::vector<str_type> elems;
   class Enumerateur : public IEnumerateur<str_type> {
      std::vector<str_type>::const_iterator cur, fin;
      bool debut; // pour le cas bizarre du « avant le début » qui n'arrive qu'une fois
   public:
      Enumerateur(const std::vector<str_type> &source)
         : cur{source.begin()}, fin{source.end()}, debut_{true}
      {
      }
      bool has_next() const {
         return cur != fin &&          // pour le cas pathologique d'une séquence vide
                std::next(cur) != fin; // std::next(It) est facile à coder :)
      }
      void next() {
         if (!debut)
            ++cur;
         debut = {};
      }
      value_type current() const {
         return *cur;
      }
   };
   template <class F>
      class Transformateur : public IEnumerateur<str_type> {
         std::vector<str_type>::const_iterator cur, fin;
         bool debut; // pour le cas bizarre du «avant le début» qui n'arrive qu'une fois
         F fct;
      public:
         Transformateur(F fct, const std::vector<str_type> &source)
            : cur{source.begin()}, fin{source.end()}, debut{true}, fct{fct}
         {
         }
         bool has_next() const {
            return cur != fin &&          // pour le cas pathologique d'une séquence vide
                   std::next(cur) != fin; // std::next(Itt) est facile à coder :)
         }
         void next() {
            if (!debut)
               ++cur;
            debut = false;
         }
         value_type current() const {
            return fct(*cur);
         }
      };
   template <class F>
      std::unique_ptr<Transformateur<F>> creer_transformateur(F fct) const {
         return std::make_unique<Transformateur<F>>(fct, elems);
      }
public:
   std::unique_ptr<IEnumerateur<str_type>> enumerateur() const {
      return std::make_unique<Enumerateur>(elems);
   }
   template <class F>
      std::unique_ptr<IEnumerateur<str_type>> transformateur(F fct) const {
         return creer_transformateur(fct);
      }
   template <class It>
      Mots(It debut, It fin) : elems{debut, fin} {
      }
};

Une opération F possible pour un Mots::Transformateur<F> donné pourrait être une fonction ou un foncteur transformant une chaîne de caractères en son équivalent majuscule. Le foncteur Majusculeur, à droite, fait cela.

Exercice : pouvez-vous modifier légèrement Majusculeur pour que celui-ci accepte aussi des chaînes de types de caractères autres que char (p. ex. : des std::wstring, qui contiennent des wchar_t)?

 
#include <locale>
class Majusculeur {
public:
   using str_type = std::string;
private:
   std::locale loc;
public:
   Majusculeur(const std::locale &loc = std::locale{""})
      : loc{loc}
   {
   }
   str_type operator()(str_type s) const {
      using namespace std;
      transform(begin(s), end(s), begin(s), [&](char c) {
         return toupper(c, loc);
      });
      return s;
   }
};

Enfin, le programme principal parcourt les éléments d'une instance mots de type Mots à l'aide de deux énumérateurs, l'un banal et l'autre avec transformations. Ceci devrait illustrer le principe.

En espérant que le tout vous ait été utile. 

#include <iostream>
#include <algorithm>
int main() {
   using namespace std;
   const char * source [] = { "J'aime", "mon", "prof" };
   Mots mots{begin(source), end(source)};
   auto e = mots.enumerateur();
   while (e->has_next()) {
      e->next();
      cout << e->current() << endl;
   }
   auto t = mots.transformateur(Majusculeur{});
   while (t->has_next()) {
      t->next();
      cout << t->current() << endl;
   }
}

Lectures complémentaires

Pour en savoir plus sur certains pièges des énumérateurs de C#, voir ces textes d'Eric Lippert en 2014 :

Valid XHTML 1.0 Transitional

CSS Valide !