Un type maybe<T>

Il arrive que l'on souhaite représenter une donnée qui peut être présente ou non (qui est peut-être là), sans toutefois vouloir recourir à de l'allocation dynamique de mémoire. Ce besoin est bien connu des tenants de la programmation fonctionnelle, où il arrive souvent que l'on enchaîne des fonctions de telle sorte qu'il devienne important de formaliser le concept de « cette fonction n'a rien retourné » pour que les autres puissent le comprendre sans recourir à du cas par cas. Des algorithmes de la forme suivante :

calcul_complique(x)
   y ← f(x)
   si (y < 0)
      erreur // quoi faire?
   retourner y

... soulèvent la question de « quoi faire » dans le cas d'une erreur. Lever une exception peut être convenable dans un appel isolé, mais si calcul_complique() est appelé dans une répétitive sur une vaste gamme de valeurs, il peut être préférable de ne pas interrompre le cacul et de constater a posteriori que le calcul a échoué dans certains cas, de manière repérable.

Les pointeurs résolvent de facto ce problème de « là, pas là » : la convention veut que le pointeur nul représente le concept de « n'est pas là », comme dans l'exemple de code à droite.

template<class T, int N>
   T* trouver_element(T (&arr)[N], const T &val) {
      for(auto p = &arr[0]; p != &arr[N]; ++p)
         if (*p == val)
            return p;
      return nullptr; // pas trouvé
   }

En généralisant la question aux itérateurs représentant, par paire, un intervalle à demi-ouvert où le début est inclus et la fin est exclue, on arrive au même résultat, au sens où retourner la fin signifie donner au code client un signal que rien n'a été trouvé.

template<class T, class It>
   It trouver_element(It debut, It fin, const T &val) {
      for(; debut != fin; ++debut)
         if (*debut == val)
            return debut;
      return fin; // pas trouvé
   }

Imaginons toutefois une structure de données exotique et contenant des T. Si nous voulons offrir des services spécialisés pour retrouver un T dans un conteneur, et s'il on doit parfois signaler que ce T n'a pas été trouvé, alors quelques options classiques s'offrent à nous.

Nous pourrions retourner un pointeur potentiellement nul. À l'usage, on aurait :

TrucComplique<string> truc;
// ...
auto p = truc.trouver("J'aime mon prof");
if (p) {
   // utiliser *p
}

Le risque ici est de donner au code client l'adresse d'un élément dont le conteneur est responsable. Sans ce que ne soit illégal en soi, il s'agit d'une pratique qui demande du doigté.

template<class T>
   class TrucComplique {
      // ...
   public:
      T* trouver(const T&);
      const T* trouver(const T&) const;
   };

Nous pourrions retourner un pair<bool,T> dont l'attribut first indiquerait la pertinence de l'attribut second. À l'usage, on aurait :

TrucComplique<string> truc;
// ...
auto p = truc.trouver("J'aime mon prof");
if (p.first) {
   // utiliser p.second
}

Ceci ressemble à l'approche suivie par Go, qui permet de multiples types de retour par fonction et utilise une combinaison de valeur de retour et de code d'erreur, tout en permettant de ne pas tenir compte de l'un ou de l'autre.

#include <utility>
template<class T>
   class TrucComplique {
      // ...
   public:
      std::pair<bool,T> trouver(const T&) const;
   };

Nous pourrions lever une exception dans le cas où la valeur cherchée ne se trouve pas dans le conteneur. À l'usage, on aurait :

TrucComplique<string> truc;
// ...
try {
   auto p = truc.trouver("J'aime mon prof");
   // utiliser p
} catch (...) {
   // la valeur cherchée n'est pas trouvée
}

Ceci serait quelque peu suspect, cependant, à moins que le fait de ne pas trouver ce que l'on cherche soit une situation véritablement exceptionnelle. Dans la plupart des cas, ne pas trouver ce qu'on cherche est une situation normale, après tout.

class pas_trouve{};
template<class T>
   class TrucComplique {
      // ...
   public:
      T& trouver(const T&);
      const T& trouver(const T&) const;
   };

L'option que nous examinerons ici sera celle de définir un type maybe<T> qui aura les caractéristiques suivantes :

L'implémentation proposée va comme suit.

Un maybe<T> sera constitué de deux états :

  • Un tampon de mémoire brute, buf, capable d'accueillir un T, et
  • Un booléen, vide, qui sera true seulement si le maybe<T> est vide

C'est la présence de ce booléen qui fait que :

sizeof(T) < sizeof(maybe<T>)

Ce que nous allons faire est administrer buf en y plaçant un T au besoin, à l'aide du new positionnel (le Placement New), et nous allons tenir à jour vide pour savoir comment buf est administré.

Notez l'importance de respecter, pour buf, l'alignement d'un T si cette zone mémoire est destinée à entreposer un T en pratique. Ceci explique le recours à std::aligned_storage ici. Une écriture alternative et équivalente aurait été :

alignas(T) unsigned char buf[sizeof(T)];
#ifndef MAYBE_H
#define MAYBE_H
#include <cassert>
#include <iosfwd>
#include <memory>
template <class T>
   class maybe {
      bool vide;
      std::aligned_storage_t<sizeof(T), alignof(T)> buf;

Trois services privés seront utilisés pour mentir (de manière contextuelle et contrôlée, évidemment) sur la nature de buf, soit :

  • La méthode as_raw(), pour traiter buf comme une adresse brute. La signature officielle du new positionnel accepte un void* en tant que deuxième paramètre donc considérer &buf comme un void* permet de l'utiliser comme adresse de destination pour un new positionnel sans ambiguïté

Ceci n'est pas à strictement parler nécessaire, car il est peu probable que quelqu'un spécialise l'opérateur new de manière à prendre un char* en tant que deuxième paramètre, mais pourquoi courir le risque?

  • La méthode as_pointer(), dans ses déclinaisons const et non-const, permet de traiter &buf comme un T* ou un const T*, selon le cas. Elle sera utilisée quand le maybe<T> n'est pas vide pour accéder au T localisé dans buf

Techniquement, nous trichons ici, mais je ne veux pas m'étaler sur le sujet

      constexpr void* as_raw() {
         return static_cast<void*>(&buf);
      }
      T* as_pointer() {
         return reinterpret_cast<T*>(&buf);
      }
      const T* as_pointer() const {
         return reinterpret_cast<const T*>(&buf);
      }

La gestion du concept « être vide » est une clé du bon fonctionnement de notre type maybe<T>, l'autre étant la saine gestion du T encapsulé par le maybe<T> quand celui-ci n'est pas vide.

La méthode empty() d'un maybe<T> permettra au code client de vérifier s'il est bel et bien vide. L'opérateur de conversion en bool aura le même effet.

J'ai fait du constructeur par défaut et du constructeur acceptant nullptr deux manières distinctes de créer un maybe<T> vide. Ceci permet diverses manières de construire un maybe<T> vide, incluant celles-ci :

template <class T>
void creer_quelques_maybe_vides() {
   maybe<T> m0; // constructeur par défaut
   maybe<T> m1{}; // constructeur par défaut
   auto m2 = maybe<T>{}; // constructeur par défaut
   maybe<T> m3 = nullptr; // constructeur prenant un nullptr_t
}

L'affectation d'un nullptr à un maybe<T> fait de ce dernier un objet « vide ».

   public:
      constexpr bool empty() const noexcept {
         return vide;
      }
      constexpr operator bool() const noexcept {
         return !empty();
      }
      constexpr maybe() : vide{ true } {
      }
      constexpr maybe(std::nullptr_t) : vide{ true } {
      }
      maybe& operator=(std::nullptr_t) {
         if (!empty()) as_pointer()->~T();
         vide = true;
         return *this;
      }

Initialiser un maybe<T> avec un T est acceptable, évidemment. Les constructeurs présentés à droite permettent d'entreposer un T accepté par copie ou par mouvement.

Dans les deux cas, le T est entreposé dans buf par voie de new positionnel, et l'attribut vide témoigne du fait que le maybe<T> n'est pas vide.

Ces constructeurs sont Exception-Safe; si la construction positionnelle échoue, le maybe<T> n'a pas été construit et aucune ressource ne fuit.

L'affectation d'un T à un maybe<T> telle que proposée ici n'est pas Exception-Safe, car si la construction de copie d'un T échoue, nous avons détruit l'original.

      constexpr maybe(const T &val) : vide{ false } {
         new (as_raw()) T(val);
      }
      constexpr maybe(T &&val) : vide{ false } {
         new (as_raw()) T(std::move(val));
      }
      maybe& operator=(const T &val) {
         if (!empty()) as_pointer()->~T();
         new (as_raw()) T(val);
         vide = {};
         return *this;
      }

La Sainte-Trinité est évidemment importante ici, du fait que nous construisons un type dont la principale raison d'être est « être correctement ». C'est ces fonctions qui sont les plus importantes pour notre type.

L'affectation proposée ici n'est pas Exception-Safe, et il serait ardu de l'amener à ce niveau sans avoir recours à de l'allocation dynamique de mémoire. Étant donné que l'un de nos objectifs initiaux était d'éviter ce recours, nous gagnons en vitesse mais nous perdons en sécurité.

      maybe(const maybe &val)
         : vide{ val.empty() }
      {
         if (!empty())
            new (as_raw()) T(static_cast<const T&>(val));
      }
      maybe& operator=(const maybe &other) {
         if (!empty()) as_pointer()->~T();
         if (other.empty())
            vide = true;
         else {
            new (as_raw()) T(static_cast<const T&>(other));
            vide = {};
         }
         return *this;
      }
      ~maybe() {
         if (!empty())
            as_pointer()->~T();
      }

L'une des fonctionnalités importantes d'un maybe<T> est l'accès au T qu'il encapsule. Nous offrons ici deux services de conversion explicite en T& et en const T&. Ces services sont somme toute simples. mais les offrir est un atout.

      constexpr explicit operator T&() {
         assert(!empty());
         return *as_pointer();
      }
      constexpr explicit operator const T&() const {
         assert(!empty());
         return *as_pointer();
      }

De la même manière, offrir un accès aux membres du T encapsulé par un maybe<T> est une fonctionnalité très utile, que nous obtenons ici par l'implémentation de l'opérateur ->.

      constexpr T* operator->() {
         assert(!empty());
         return as_pointer();
      }
      constexpr const T* operator->() const {
         assert(!empty());
         return as_pointer();
      }

Pour faciliter le débogage, nous exposons un opérateur de projection sur un flux quelque peu simpliste. Vous pouvez le raffiner pour tenir compte du cas où m.empty() si cela rejoint vos besoins.

      friend std::ostream& operator<<(std::ostream &os, const maybe<T> &m) {
         return os << static_cast<const T&>(m);
      }
   };
#endif

Comment utilise-t-on un maybe<T>? Si nous reprenons l'idée d'une structure de données exotique et contenant des T, exploitée plus haut, et si nous voulons offrir des services spécialisés pour retrouver un T dans un conteneur, devant parfois signaler que ce T n'a pas été trouvé, maybe<T> devient une option intéressante : il se comporte syntaxiquement comme un pointeur, testable pour voir s'il est utilisable, mais ne requiert pas d'allocation dynamique de mémoire.

À l'usage, on aurait :

TrucComplique<string> truc;
// ...
auto p = truc.trouver("J'aime mon prof");
if (p) {
   // utiliser *p
}

Le code client obtenu est identique à celui que nous avions avec des pointeurs, mais sans les risques et les coûts qui leur sont associés.

#include "maybe.h"
template<class T>
   class TrucComplique {
      // ...
   public:
      maybe<T> trouver(const T&) const;
   };

Voilà!

À titre illustratif, voici une autre implémentation possible, avec code de test (simpliste). Je vous laisse explorer les similitudes et les différences avec la proposition précédente :

template <class T>
   class maybe {
      alignas(T) char buf[sizeof(T)];
      T *p;
   public:
      maybe() : p{ } {
      }
      maybe(const T &obj) {
         p = new(static_cast<void*>(buf)) T(obj);
      }
      maybe(T &&obj) {
         p = new(static_cast<void*>(buf)) T(std::move(obj));
      }
      maybe& operator=(const T &obj) {
         if (p) p->~T();
            p = new(static_cast<void*>(buf)) T(obj);
         return *this;
      }
      maybe& operator=(T &&obj) {
         if (p) p->~T();
            p = new(static_cast<void*>(buf)) T(std::move(obj));
         return *this;
      }
      ~maybe() {
         if (p) p->~T();
      }
      maybe(const maybe &autre) : maybe() {
         if (autre)
            p = new(static_cast<void*>(buf)) T(autre.value());
      }
      maybe& operator=(const maybe &autre) {
         if (this != &autre) {
            if (p) p->~T();
            p = new(static_cast<void*>(buf)) T(autre.value());
         }
         return *this;
      }
      operator bool() const noexcept {
         return !!p;
      }
      T & value() noexcept {
         return *p;
      }
      const T & value() const noexcept {
         return *p;
      }
   };

maybe<int> div_ent(int num, int denom) {
  if (!denom) return{};
    return{ num / denom };
}

#include <iostream>
using namespace std;
int main() {
   int n, d;
   if (cin >> n >> d) {
      auto res = div_ent(n, d);
      if (res)
         cout << res.value() << endl;
   }
}

Pas mal, non?

Lectures complémentaires

Quelques liens pour enrichir le propos.


Valid XHTML 1.0 Transitional

CSS Valide !