Solidifier le recours aux tableaux bruts

Ce qui suit est essentiellement tiré d'idées proposées par Bjarne Stroustrup dans son récent livre Programming, Principles and Practice Using C++. L'implémentation et les exemples ci-dessous sont écrits par moi et quelque peu adaptés, mais sont pour l'essentiel dérivés directement des siens. Je vous propose tout de même cet article parce que c'est simple et élégant, et parce que cela peut être utile dans plusieurs situations où mes étudiant(e)s se trouvent occasionnellement plongées (en particulier les systèmes embarqués ou ceux soumis à des exigences de temps réel). Cela dit, je vous invite à lire le livre original qui contient plusieurs autres bonnes idées.

Mieux vaut comprendre un soupçon de programmation générique avant de lire ce qui apparaît plus bas.

J'utiliserai ici le trait est_convertible et les assertions statiques, tous deux décrits dans d'autres articles, mais dans leur acception standard que sont le trait std::conditional et le mot clé static_assert (pas les versions maison décrites par les articles susmentionnés). Ces manoeuvres sont un peu subtiles, mais vous pouvez les prendre comme des outils sans chercher à les comprendre en profondeur si elles vous échappe. Le code qui suit demande un compilateur C++ 11 mais peut être adapté pour C++ 03 en écrivant les traits appropriés.

Le langage C++ permet d'écrire du code extrêmement performant à plusieurs points de vue, mais inclut aussi un support significatif des fonctionnalités de l'un de ses ancêtres conceptuels et syntaxiques : le langage C.

Un tableau C (et C++, par la même occasion), rappelons-le, n'est ni plus, ni moins qu'un pointeur sur le premier élément d'une séquence contiguë d'éléments du même type.

En langage C, les tableaux sont une structure de données brute et permettant un seuil d'efficacité très élevé lors des accès aux éléments qu'il « contient », puisque pour accéder à l'élément à l'indice i dans un tableau tab de N éléments, avec 0<=i&&i<N, l'écriture tab[i] équivaut à *(tab+i), donc à une opération artihmétique sur un pointeur suivie d'un déréférencement.

À titre d'exemple, ci-dessous, les fonctions f(), g() et h() font précisément le même travail (la fonction h() possède la signature que je privilégierais, personnellement, puisqu'elle suit la convention des itérateurs et, de ce fait, se prête à une gamme plus vaste d'algorithmes). Notez que les interfaces de ces trois fonctions (surtout celles de f() et de g()) sont problématiques, et que cet article portera sur une approche permettant de les raffiner :

#include <iostream>
#include <algorithm>
using namespace std;
void f(const int tab[], size_t n) {
   for (size_t i = 0; i < n; ++i)
      cout << tab[i] << ' ';
   cout << endl;
}
void g(const int *p, size_t n) {
   for (const int *q = p; q != p + n; ++q)
      cout << *q << ' ';
   cout << endl;
}
void h(const int *debut, const int *fin) {
   for (; debut != fin; ++debut)
      cout << *debut << ' ';
   cout << endl;
}
int main() {
   int prem[] { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
   enum { N = sizeof(prem)/sizeof(*prem) };
   f(&prem[0], N);
   g(&prem[0], N);
   h(&prem[0], &prem[N]);
   h(begin(prem), end(prem));
}

En pratique, les vecteurs standards offrent un seuil de performance essentiellement identique à celui des tableaux bruts de C s'ils sont bien utilisés (ils sont même souvent plus performants que les tableaux bruts). Par contre, pour certaines applications pointues, par exemple dans les systèmes embarqués où la mémoire se fait rare, le recours aux conteneurs standards de C++ (même std::vector) peut être proscrit puisque ceux-ci ont recours, en arrière-plan, à de l'allocation dynamique de mémoire, et il faut alors revenir aux tableaux bruts du langage C pour réaliser des opérations sur des séquences d'éléments d'un type donné.

Les appels polymorphiques sont en général un peu plus lents que ceux qui ne le sont pas. Ils impliquent une indirection supplémentaire et empêchent le compilateur de réaliser certaines optimisations. Cela dit, ils demeurent plus efficaces que la plupart des alternatives que nous pourrions écrire manuellement.

Le problème

Le langage C++ permet d'appliquer des approches OO, même dans un système temps réel ou embarqué. En particulier, les appels polymorphiques font partie de la boîte à outils des programmeurs, du fait qu'ils demeurent déterministes : le temps requis pour invoquer un service polymorphique est le même peu importe le nombre de niveaux entre l'abstraction sur laquelle est réalisée l'appel et l'objet effectivement sollicité.

Sachant cela, en nous basant sur un exemple académique (donc simplifié) et sans lien avec les systèmes embarqués (quoique...). imaginons le code ci-dessous. Notez que les constexpr ne sont pas essentiels; retirez-les si votre compilateur ne supporte pas encore cette fonctionnalité.

Soit la classe Forme, une racine polymorphique classique offrant un service abstrait dessiner() capable de projeter une Forme sur un flux standard en sortie.

L'opérateur de projection sur un flux appliqué à une Forme a pour but d'alléger l'écriture du code client, rendant ainsi équivalentes les écritures f.dessiner(cout); et cout<<f; pour une instance f quelconque d'une classe dérivée de Forme.

#ifndef FORME_H
#define FORME_H
//
// Forme.h
//
#include <iosfwd>
class Forme {
public:
   using value_type = char;
private:
   value_type symbole_;
public:
   Forme() : Forme{'*'} {
   }
   Forme(value_type symbole) : symbole_{symbole} {
   }
   value_type symbole() const {
      return symbole_;
   }
   virtual void dessiner(std::ostream &os) const = 0;
   virtual ~Forme() = default;
};
void afficher_formes(Forme *tab, std::size_t n);
#endif

La fonction vilain(), au nom évocateur, itère à travers un tableau brut de Forme et projette (par polymorphisme) chacune sur un flux (ici, par souci de simplicité, ce flux sera la sortie standard.

Que pensez-vous de cette fonction? Réfléchissez à son écriture, car nous y reviendrons plus bas...

#include "Forme.h"
#include <iostream>
using namespace std;
ostream& operator<<(ostream &os, const Forme &f) {
   return f.dessiner(os), os;
}
void vilain(Forme *tab, size_t n) {
   for (Forme *p = tab; p != tab + n; ++p)
      cout << *p << endl;
}

Un exemple concret de classe dérivée de Forme serait la classique classe Rectangle proposée à droite.

Les classes Rectangle et Forme sont toutes deux correctes et légales. Le problème du code proposé jusqu'ici est ailleurs...

//
// Rectangle.h
//
#ifndef RECTANGLE_H
#define RECTANGLE_H
#include "Forme.h"
template <class T>
   constexpr bool est_entre_inclusif(T candidat, T minVal, T maxVal) {
      return minVal <= candidat && candidat <= maxVal;
   }
class DimensionIncorrecte {};
#include <ostream>
class Rectangle : public Forme {
public:
   using size_type = short;
private:
   static constexpr const size_type MIN_LARGEUR = 1, MAX_LARGEUR = 80;
   static constexpr const size_type MIN_HAUTEUR = 1, MAX_HAUTEUR = 25;
   size_type largeur_,
             hauteur_;
   static constexpr size_type valider_largeur(size_type largeur) {
      return est_entre_inclusif(largeur, MIN_LARGEUR, MAX_LARGEUR)? largeur : throw DimensionIncorrecte{};
   }
   static constexpr size_type valider_hauteur(size_type hauteur) {
      return est_entre_inclusif(hauteur, MIN_HAUTEUR, MAX_HAUTEUR)? hauteur : throw DimensionIncorrecte{};
   }
public:
   Rectangle(size_type largeur, size_type hauteur)
      : largeur_{valider_largeur(largeur)},
        hauteur_{valider_hauteur(hauteur)}
   {
   }
   Rectangle(size_type largeur, size_type hauteur, value_type symbole)
      : Forme{symbole},
        largeur_{valider_largeur(largeur)},
        hauteur_{valider_hauteur(hauteur)}
   {
   }
   size_type largeur() const {
      return largeur_;
   }
   size_type hauteur() const {
      return hauteur_;
   }
   void dessiner(std::ostream &os) const {
      using std::endl;
      for (size_type hau = 0; hau < hauteur(); ++hau) {
         for (size_type lar = 0; lar < largeur(); ++lar)
            os << symbole();
         os << endl;
      }
   }
};
#endif

Enfin, voici un exemple de code client, soit un petit programme principal qui crée un tableau de trois instances de Rectangle et invoque vilain() en lui passant l'adresse du premier d'entre eux et le nombre d'instances dans le tableau.

Le tout compile normalement  : puisque tout Rectangle est publiquement une Forme, passer un Rectangle* à une fonction voulant recevoir une Forme* est légal et, habituellement, correct. Selon toute probabilité, la fonction vilain() plantera après avoir dessiné la première des trois instances de Rectangle.

//
// Principal.cpp
//
#include "Rectangle.h"
#include "Forme.h"
int main()
{
   Rectangle tab[] {
      Rectangle{1, 3}, Rectangle{4, 2}, Rectangle{3, 3}
   };
   enum { N = sizeof(tab) / sizeof(tab[0]) };
   vilain(tab, N); // BOUM!
}

Le problème ici est dans la qualité de l'interface de la fonction vilain(). Réexaminons-la brièvement.

Notre fonction vilain() admet un Forme* comme premier paramètre, et progresse d'un élément à l'autre (jusqu'à concurrence de n éléments) en appliquant l'opérateur ++ sur un pointeur.

Le polymorphisme sur un Forme* s'applique lors de la projection de *p sur un flux en sortie; à l'interne, cela invoque la méthode polymorphique dessiner(cout) de p.

L'arithmétique de pointeurs, cependant, nous joue un tour : si p est un Forme*, alors ++p amène p un total de sizeof(Forme) bytes plus loin en mémoire.

Il se trouve qu'ci, sizeof(Forme)!=sizeof(Rectangle) puisque tout Rectangle est une Forme avec quelques attributs en plus. Après le premier ++p, nous ne sommes donc pas tant à la prochaine Forme que quelque part au milieu du premier Rectangle, ce qui explique le plantage subséquent.

#include <iostream>
using namespace std;
void vilain(Forme *tab, size_t n) {
   for (Forme *p = tab; p != tab + n; ++p)
      cout << *p << endl;
}

Ce bogue est très vilain! En fait, l'interface de notre fonction vilain() n'offre pas un niveau d'abstraction suffisant pour permettre d'écrire du code sécuritaire dans un langage OO. Nous souhaitons une solution à ce problème, mais étant donné le contexte d'utilisation qui nous préoccupe, nous ne souhaitons pas sacrifier de performance pour y arriver.

Une solution charmante : les array_ref

La solution proposée par Bjarne Stroustrup dans son récent livre Programming, Principles and Practice Using C++ est de construire sur demande un type sémantiquement plus riche que les tableaux bruts, mais de manière à ce que les coûts de cet ajout sémantique soient extrêmement faibles (en fait, ils seront pratiquement nuls).

Le type sémantiquement enrichi que nous utiliserons se nommera array_ref, et sera générique sur la base d'un type T donné.

Dans le respect des usages de la bibliothèque standard de C++, un array_ref exposera des types internes et publics, en particulier size_type et value_type (à droite). Cet enrichissement n'entraîne aucun coût à l'exécution et facilite l'écriture du code client.

#include <cassert>
#include <iterator>
#include <type_traits>
template <class T>
   class array_ref {
   public:
      using size_type = std::size_t;
      using value_type = T;

Les attributs d'un array_ref seront très légers; on parle d'un entier et d'un pointeur, rien de plus. Cela signifie que copier un array_ref (le passer par valeur à une fonction, par exemple) sera essentiellement aussi performant que le serait copier une instance d'un type primitif.

Un array_ref aura ce qu'on nomme une sémantique de référence : il ne se montrera pas propriétaire des données qu'il permet de manipuler.

   private:
      value_type *ptr;
      size_type nelems;
   public:
      array_ref(value_type *ptr, size_type nelems) : ptr{ptr}, nelems{nelems} {
         assert(ptr && nelems);
      }
      template <class It>
         array_ref(It debut, It fin)
            : ptr(&(*debut)), nelems(std::distance(debut, fin))
         {
            using std::is_convertible;
            static_assert(
               is_convertible<
                  typename std::iterator_traits<It>::iterator_category,
                  std::random_access_iterator_tag
               >::value,
               "array_ref requiert des random_access_iterators"
            );
         }

Remarquez l'exigence statique selon laquelle seuls des itérateurs à accès directs puissent être utilisés comme structure sous-jacente à un array_ref. Ceci admet en particulier les tableaux bruts, les vecteurs, et peut-être les diverses saveurs de std::basic_string (ceci peut varier d'un compilateur à l'autre). Pourquoi se limiter inutilement? Notre seule exigence est que les données de type T soient contiguës en mémoire.

Ceci explique l'étrange notation ptr_(&(*debut)) utilisée en préconstruction dans le constructeur de séquence d'un array_ref : l'expression *debut obtient une référence sur l'élément pointé par l'itérateur debut et l'opérateur & en saisit l'adresse. Ceci permet de contourner les conteneurs qui exposent des itérateurs se voulant intelligents, comme les Checked Iterators de certaines implémentations un peu lentes mais se voulant gentilles de STL.

À partir de ces quelques enrichissements sémantiques, nous pouvons sans coût exposer une gamme de services de base susceptibles d'aider la rédaction du code client. Ainsi, les types et les méthodes visibles à droite sont toutes optimales de complexité constante; pris ensembles, ils permettent de manipuler directement les données d'un tableau brut à la manière d'un conteneur plus riche comme le sont par exemple les vecteurs standards.

// ...
      size_type size() const noexcept {
         return nelems;
      }
      value_type& operator[](size_type n) {
         assert(n < size());
         return ptr[n];
      }
      value_type operator[](size_type n) const {
         assert(n < size());
         return ptr[n];
      }
      using iterator = value_type*;
      using const_iterator = const value_type*;
      iterator begin() noexcept {
         return ptr;
      }
      const_iterator begin() const noexcept {
         return ptr;
      }
      iterator end() noexcept {
         return begin() + size();
      }
      const_iterator end() const noexcept {
         return begin() + size();
      }
   };

Pour faciliter l'utilisation d'un array_ref, nous offririons les deux déclinaisons de la fonction utilitaire make_array_ref() visibles à droite. La première utilisera une interface proche de celle de vilain() plus haut, alors que la seconde sera plus proche des usages C++ contemporains.

template <class T>
   array_ref<T> make_array_ref(T *ptr, size_t n) {
      return { ptr, n };
   }
template <class It>
   array_ref<typename std::iterator_traits<It>::value_type>
      make_array_ref(It debut, It fin)
   {
      return { debut, fin };
   }

Enfin, nous remplacerons la fonction vilain(), plus haut, par une fonction gentil() qui réalisera la même tâche que son prédécesseur, mais correctement cette fois.

À quoi tient la différence entre vilain() et gentil()? Simplement Au fait qu'un array_ref<T> connaisse le type T!

template <class T>
   void gentil(array_ref<T> tab) {
      using namespace std;
      for (auto p = begin(tab); p != end(tab); ++p)
         cout << *p << endl;
   }

L'exemple à droite montre comment utiliser gentil() pour réaliser la tâche que nous cherchions précédemment à réaliser avec vilain(). Nous sommes passés d'une fonction à deux paramètres (un pointeur et un entier) à une fonction à... un seul paramètre, composé lui-même d'un entier et d'un pointeur!

#include <algorithm>
int main() {
   using namespace std;
   Rectangle tab[] {
      Rectangle{1, 3}, Rectangle{4, 2}, Rectangle{3, 3}
   };
   enum { N = sizeof(tab) / sizeof(tab[0]) };
   // vilain (tab, N);
   gentil(make_array_ref(tab, N));
   gentil(make_array_ref(begin(tab), end(tab)));
}

En pratique, nous avons par cette manoeuvre :

Un bon truc, donc.


Valid XHTML 1.0 Transitional

CSS Valide !