ENIB LANG-CPP 05_Alloc - Allocation individuelle

{} Allocation et libération explicites

Une interprétation naïve de la description précédente pourrait nous conduire à tenter de définir un type de nœud de cette façon :

struct ImpossibleNode
{
  double value_oper;
  ImpossibleNode left;
  ImpossibleNode right;
};

Cette structure sera bien entendu rejetée par le compilateur car la relation

sizeof(ImpossibleNode)>=sizeof(double)+2*sizeof(ImpossibleNode)

(voir cette section du cours S3-PRC) ne peut en aucun cas être respectée !

!!! Avertissement !!!

La démarche d'allocation dynamique suivie au cours de cette étape de l'expérimentation est une très mauvaise pratique qui ne sert qu'à favoriser la bonne compréhension de la solution apportée par l'étape suivante.
Il ne faut en aucun cas la reproduire pour d'autres raisons que l'expérimentation à vocation pédagogique.

Nous sommes contraints de représenter la nature récursive des nœuds par la définition d'une structure auto-référencée :

struct PossibleNode
{
  double value_oper;
  PossibleNode *left;
  PossibleNode *right;
};

Un tel nœud de type PossibleNode ne contient pas deux autres nœuds similaires mais se contente d'y faire référence par l'intermédiaire de deux pointeurs (les pointeurs ont toujours la même taille, quelle que soit celle de la structure).
Contrairement aux références, les pointeurs peuvent être nuls, c'est-à-dire que, si nécessaire, ils peuvent ne désigner aucune donnée utile ; cette propriété nous permettra de représenter les nœuds qui sont des valeurs.

Pour effectivement aborder l'expérimentation, nous devons réaliser un nouveau programme.
Créez alors sur votre poste de travail un répertoire de votre choix dans lequel vous placerez le fichier GNUmakefile, un fichier prog.cpp et un module raw_node.
Le fichier d'en-tête raw_node.hpp doit définir le type structuré RawNode :

class RawNode
{
public:

  RawNode(double value);

  RawNode(char oper,
          RawNode *left,
          RawNode *right);

  std::string
  show() const;

  double
  eval() const;

private:
  double value_oper_;
  RawNode *left_;
  RawNode *right_;
};

dans l'espace de noms s4prc.
La définition de ses fonctions membres prendra place dans le fichier raw_node.cpp :

RawNode::RawNode(double value)
: value_oper_{value}
, left_{nullptr}
, right_{nullptr}
{
  // nothing more to be done
}

RawNode::RawNode(char oper,
                 RawNode *left,
                 RawNode *right)
: value_oper_{double(oper)}
, left_{left}
, right_{right}
{
  if(!left_||!right_)
  {
    throw std::runtime_error{"two child nodes expected"};
  }
}

std::string
RawNode::show() const
{
  std::string result;
  if(left_&&right_) // child nodes, assume an operation
  {
    const auto oper=char(value_oper_);
    result+='(';
    result+=left_->show();
    result+=oper;
    result+=right_->show();
    result+=')';
  }
  else // no child nodes, assume a value
  {
    result+=std::to_string(value_oper_);
  }
  return result;
}

double
RawNode::eval() const
{
  if(left_&&right_) // child nodes, assume an operation
  {
    const auto l=left_->eval();
    const auto r=right_->eval();
    const auto oper=char(value_oper_);
    switch(oper)
    {
      case '+': return l+r;
      case '-': return l-r;
      case '*': return l*r;
      case '/': return l/r;
    }
    throw std::runtime_error{"unexpected operation "+oper};
  }
  else // no child nodes, assume a value
  {
    return value_oper_;
  }
}

Remarquez que, lorsqu'un tel nœud représente une valeur (premier constructeur), ses deux pointeurs sont initialisés à nullptr ; il s'agit de la forme conventionnelle du pointeur nul en C++ moderne et c'est celle que nous utiliserons dorénavant✍.
(https://en.cppreference.com/w/cpp/language/nullptr)
Remarquez également que, lorsqu'un tel nœud représente une opération (second constructeur), le caractère ('+', '-', '*' ou '/' par exemple) qui symbolise cette opération est mémorisé à la place de la valeur (sous la forme d'un réel) ; en effet, la valeur réelle n'a pas d'utilité dans ce cas, elle peut alors être réutilisée à cette fin.
Les fonctions d'affichage et d'évaluation se contentent alors de tester la nullité des pointeurs pour savoir s'il faut considérer le nœud comme une valeur ou bien une opération.

Cherchons maintenant à créer dynamiquement des données de type RawNode.
Nos connaissances antérieures du langage C nous orientent naturellement vers cette formulation :

// WARNING: never use malloc() in real C++ code!
RawNode *n=(RawNode *)std::malloc(sizeof(RawNode)); // only allocate!

(voir cette section du cours S3-PRC) mais ce serait une grave maladresse !
En effet, les fonctionnalités d'allocation dynamique du langage C ne supposent pas que les données obtenues aient besoin d'être initialisées implicitement : ici, la fonction std::malloc() réserve effectivement suffisamment d'octets pour mémoriser une donnée de type RawNode mais ne sait absolument pas qu'ils serviront à ça.
Nous avons défini des constructeurs pour le type RawNode ce qui suppose que toute donnée de ce type a nécessairement été initialisée par l'un d'eux mais ici il n'en est rien : la donnée obtenue dynamiquement et désignée par le pointeur n n'est absolument pas initialisée.
Si nous l'utilisions ainsi nous observerions un comportement indéterminé et probablement un plantage.

En C++ ancien, le moyen d'allouer dynamiquement une donnée individuelle était d'utiliser cette formulation :

// WARNING: never use new in real C++ code!
RawNode *n=new RawNode{10.1}; // allocate and initialise

Puisque le compilateur C++ connaît les détails du type RawNode, il en provoque l'initialisation dès l'allocation, ce qui rend la donnée désignée par n immédiatement utilisable.
Nous ne nous servirons de new, à cette étape de l'expérimentation, que pour justifier l'utilité du mécanisme qui doit désormais lui être substitué ; new est toujours supporté en C++ moderne mais son usage direct doit être proscrit✍.

Le fichier prog.cpp devra contenir une fonction test_RawNode(), qui affichera clairement par des messages son début et sa terminaison (comme nous en avons l'habitude désormais) et qui sera appelée par la fonction principale.
Elle ne contiendra pour l'instant que ces quelques lignes :

using Node = s4prc::RawNode;
// WARNING: never use new in real C++ code!
auto *expr=new Node{'*',
             new Node{10.1},
             new Node{'+',
               new Node{5.2},
               new Node{3.4}}};
std::cout << expr->show() << "="
          << expr->eval() << '\n';

La directive using n'est qu'une facilité d'écriture qui nous permet de désigner le type s4prc::RawNode par le synonyme plus court Node lors des multiples demandes d'allocation.
L'imbrication de ces appels aboutit à l'obtention dans la variable expr d'un pointeur sur RawNode qui désigne l'intégralité de l'arbre de données représenté schématiquement à la fin du paragraphe introductif ; nous le retranscrivons alors dans le terminal ainsi que le résultat de son évaluation.

La fabrication du programme exécutable et son exécution ne doivent rien signaler d'anormal jusqu'à sa terminaison.
Cependant, juste avant que le programme ne soit complètement terminé, l'outil LeakSanitizer qui est incorporé (s'il est disponible sur votre plate-forme d'exécution) lors de sa fabrication pour la mise au point (voir cette section du cours S3-PRC) nous indique des fuites de mémoire dans notre programme.
Un examen attentif des messages produits par cet outil nous indique que le problème se pose pour chacun des cinq nœuds que nous avons fabriqués et précise pour chacun d'eux la pile d'exécution au moment de sa création.
Ces fuites de mémoire étaient tout à fait prévisibles puisque nous n'avons à aucun moment envisagé la libération de la mémoire dynamique que notre programme allouait (voir cette section du cours S3-PRC).
Étudions ce mécanisme sur un cas isolé :

Complément : libération des données allouées dynamiquement

Afin de simplifier l'analyse, commentez dans la fonction principale l'appel à la fonction test_RawNode() et remplacez-le par un appel à une nouvelle fonction test_alloc().
Cette dernière affichera clairement par des messages son début et sa terminaison (comme nous en avons l'habitude désormais) et contiendra ces quelques lignes :

// WARNING: never use new in real C++ code!
auto *raw=new s4prc::Noisy<std::string>{"raw-pointer"};
std::cout << "raw memorises the address " << raw << '\n';
if(raw)
{
  std::cout << "... which contains " << *raw << '\n';
}

Le type Noisy<T> est identique à celui des expérimentations précédentes (fichier noisy.hpp✎

Contenu du fichier noisy.hpp

//----------------------------------------------------------------------------

#ifndef S4PRC_NOISY_HPP
#define S4PRC_NOISY_HPP

#include <iostream>
#include <string>
#include <vector>

namespace s4prc {

inline
std::ostream &
operator<<(std::ostream &output,
           const std::string &s) // display string within quotes
{
  using std::operator<<;
  output << '"';
  if(const auto sz=size(s); sz>20) // prevent from using too much space
  {
    output << s.substr(0, 10) << "..." << s.substr(sz-10);
  }
  else
  {
    output << s;
  }
  return output << '"';
}

template<typename E>
inline
std::ostream &
operator<<(std::ostream &output,
           const std::vector<E> &v) // display vector within braces
{
  output << '{';
  if(const auto sz=size(v); sz>4) // prevent from using too much space
  {
    output << v[0] << ',' << v[1] << ",...," << v[sz-2] << ',' << v[sz-1];
  }
  else
  {
    int count=0;
    for(const auto &elem: v)
    {
      if(count++)
      {
        output << ',';
      }
      output << elem;
    }
  }
  return output << '}';
}

template<typename T>
struct Noisy : T
{
  Noisy()
  : T{}
  {
    std::cout << "construct " << *this
              << " from nothing\n";
  }

  Noisy(const T &t)
  : T{t}
  {
    std::cout << "copy-construct " << *this
              << "\n   ... from " << t << '\n';
  }

  Noisy(T &&t)
  : T{std::move(t)}
  {
    std::cout << "move-construct " << *this
              << "\n   ... from (moved) " << t << '\n';
  }

  Noisy(const Noisy &n)
  : T{static_cast<const T &>(n)}
  {
    std::cout << "copy-construct " << *this
              << "\n   ... from " << n << '\n';
  }

  Noisy(Noisy &&n) noexcept
  : T{std::move(static_cast<T &&>(n))}
  {
    std::cout << "move-construct " << *this
              << "\n   ... from (moved) " << n << '\n';
  }

  Noisy &
  operator=(const T &t)
  {
    T::operator=(t);
    std::cout << "copy-assign " << *this
              << "\n   ... from " << t << '\n';
    return *this;
  }

  Noisy &
  operator=(T &&t)
  {
    T::operator=(std::move(t));
    std::cout << "move-assign " << *this
              << "\n   ... from (moved) " << t << '\n';
    return *this;
  }

  Noisy &
  operator=(const Noisy &n)
  {
    T::operator=(static_cast<const T &>(n));
    std::cout << "copy-assign " << *this
              << "\n   ... from " << n << '\n';
    return *this;
  }

  Noisy &
  operator=(Noisy &&n) noexcept
  {
    T::operator=(std::move(static_cast<T &&>(n)));
    std::cout << "move-assign " << *this
              << "\n   ... from (moved) " << n << '\n';
    return *this;
  }

  ~Noisy()
  {
    std::cout << "destroy " << *this << '\n';
  }

  friend
  std::ostream &
  operator<<(std::ostream &output,
             const Noisy &n)
  {
    return output << "Noisy@" << &n << ":" << static_cast<const T &>(n);
  }
};

} // namespace s4prc

#endif // S4PRC_NOISY_HPP

//----------------------------------------------------------------------------

).
L'opérateur new utilisé ici crée dynamiquement une nouvelle donnée de type

s4prc::Noisy<std::string>

et l'initialise avec un message explicite.
La variable raw est donc un pointeur vers une donnée de ce type qui mémorise l'adresse de la donnée ainsi créée.
Nous produisons l'affichage de messages reportant cette adresse et son contenu.

Après une nouvelle fabrication du programme, les messages apparaissant lors de son exécution doivent nous signifier clairement que, dans la fonction test_alloc(), la donnée de type Noisy<T> créée est bien celle qui est désignée par le pointeur raw.
En revanche, même après la sortie de la fonction, aucun message ne nous indique que cette données est détruite, et c'est ce que confirme à nouveau l'outil LeakSanitizer.

L'opération complémentaire à new en C++ est l'opération delete.
Son rôle est d'exécuter les fonctionnalités de destruction de la donnée désignée par le pointeur avant de libérer la mémoire✍ contenant la donnée en question✍.
Complétez alors les quelques lignes de code précédentes par celle-ci :

// WARNING: never use delete in real C++ code!
delete raw;

puis essayez le programme dans ces nouvelles conditions.
La donnée de type Noisy<T> créée dynamiquement signifie très clairement qu'elle est détruite au moment de l'usage de delete et l'outil LeakSanitizer ne reporte désormais plus aucune fuite de mémoire.

Après cette digression, l'appel à la fonction test_RawNode() depuis la fonction principale peut à nouveau avoir lieu.

Pour tenter de nous débarrasser des fuites de mémoire causées par la fonction test_RawNode(), commençons par y ajouter cette ligne :

// WARNING: never use delete in real C++ code!
delete expr;

Après une nouvelle fabrication du programme exécutable, son exécution devrait malheureusement à nouveau aboutir au signalement de quatre fuites de mémoire par l'outil LeakSanitizer.
En effet, nous avons bien libéré et détruit le nœud désigné par expr mais lui-même en désignait d'autres qui ont alors été “oubliés”.

C'est désormais la bonne occasion de déclarer un destructeur pour notre type ; il sera défini de la façon suivante :

RawNode::~RawNode()
{
  // WARNING: never use delete in real C++ code!
  // mandatory to prevent memory-leak!
  delete left_; // no effect on nullptr
  delete right_; // no effect on nullptr
}

Lorsqu'un nœud est détruit, il invoque lui-même la libération et la destruction des nœuds qu'il désigne✍ ; la destruction du nœud désigné par expr doit donc provoquer par réaction en chaîne✍ la destruction et la libération de tous les nœuds dont il est constitué.
Bien entendu, comme décrit dans cette section, dès lors que nous déclarons une fonction membre spéciale il nous faut considérer l'ensemble des cinq.

  //-- disable copy --
  RawNode(const RawNode &) =delete;
  RawNode & operator=(const RawNode &) =delete;

  //-- disable move --
  RawNode(RawNode &&) =delete;
  RawNode & operator=(RawNode &&) =delete;

  //-- explicitely release internal resources --
  ~RawNode();

Ici, puisque nous maintenons en interne une ressource allouée dynamiquement nous nous contentons d'interdire les recopies et les déplacements✍.
Vérifiez que l'exécution de cette nouvelle version du programme ne provoque plus les fuites de mémoire que nous constations auparavant.

Nous en terminons enfin avec l'usage explicite des opérations new et delete sur lesquelles nous ne reviendrons plus jamais✍.
Il est impératif d'éliminer les fuites mémoire✍, même si dans nos exemples triviaux elles semblent mineures✍.
Seulement, cette précaution demande une très grande attention de la part du programmeur qui doit invoquer les opérations de destruction exactement où et quand elles sont nécessaires sans que le langage n'apporte aucune aide :

certains pointeurs peuvent désigner des données que nous nous contentons de manipuler, ce qui est très légitime, sans pour autant les posséder (donc sans devoir les détruire après usage),
d'autres pointeurs sont propriétaires de la donnée désignée, ce qui implique le besoin d'une opération de destruction explicite de cette dernière dès que le pointeur disparaît,
mais rien dans le langage n'indique cette distinction, c'est donc au programmeur de reconnaître parmi tous ces pointeurs ceux pour lesquels une destruction explicite est nécessaire et ceux pour lesquels elle ne l'est pas !

Nous avons constaté que si des opérations de destruction sont oubliées, alors cette situation donne lieu à des fuites de mémoire ; si au contraire des destructions ont lieu alors que la suite du programme continue à utiliser les données initialement désignées par ces pointeurs, alors son comportement sera indéterminé (il produira des incohérences ou un plantage).
Cette critique est une des plus virulente à l'encontre de C++ ancien et c'est celle qui a conduit un grand nombre de programmeurs à se tourner vers d'autres langages qui contournent automatiquement ce problème au sacrifice des performances✍.
C++ moderne, grâce à sa notion de déplacement, apporte une solution très efficace à la problématique de la gestion des ressources en général et de l'allocation dynamique en particulier.

{} Libération automatique des ressources

L'ambiguïté relevée à la fin de l'étape précédente a conduit le comité de normalisation de C++ à proposer un moyen très clair de distinguer les deux rôles qui peuvent motiver l'usage d'un pointeur :

soit nous ne cherchons qu'à désigner une donnée sans considérer la question de sa création et de sa destruction,
- un simple pointeur, au sens du langage C ou de C++ ancien, est parfaitement suffisant,
- la donnée désignée peut être consultée ou modifiée à travers ce pointeur (selon l'emploi ou non du qualificatif const),
- la donnée peut être optionnelle, dans ce cas le pointeur vaut nullptr (si la donnée ne doit pas être optionnelle, il faut le signifier clairement en utilisant une référence à la place du pointeur),
soit nous cherchons à contrôler la “durée de vie” d'une donnée créée par allocation dynamique individuelle,
- un pointeur élaboré (smart-pointer) doit nécessairement être utilisé,
- il sera en mesure de déterminer automatiquement le moment opportun pour détruire la donnée désignée (plusieurs variantes existent),
- il reste utilisable comme un simple pointeur pour les autres opérations.

Avant d'intervenir sur notre réalisation, il nous faut découvrir le type qui jouera le rôle de smart-pointer :

Complément : le type std::unique_ptr<T>

Le rôle du type std::unique_ptr<T>, exposé par le fichier d'en-tête standard

<memory>

, consiste avant tout à se comporter comme un pointeur sur une donnée de type T.
(https://en.cppreference.com/w/cpp/memory/unique_ptr)
Toutefois, par rapport à un pointeur usuel, un tel smart-pointer suppose que la donnée qu'il désigne est allouée dynamiquement et décidera automatiquement de libérer et détruire (avec delete) cette donnée quand lui-même disparaîtra.

Essayons tout de suite cette fonctionnalité en complétant la fonction test_alloc() du fichier prog.c par les lignes suivantes :

auto smart=std::make_unique<s4prc::Noisy<std::string>>("smart-pointer");
std::cout << "smart memorises the address " << smart.get() << '\n';
if(smart)
{
  std::cout << "... which contains " << *smart << '\n';
}

La fonction std::make_unique<T>(), exposée par le fichier d'en-tête standard

<memory>

, alloue dynamiquement une donnée de type T, l'initialise selon les paramètres qui lui sont transmis et renvoie un smart-pointer de type std::unique_ptr<T> qui désigne cette donnée.
(https://en.cppreference.com/w/cpp/memory/unique_ptr/make_unique)
Le type que le mot-clef auto attribue ici à la variable smart est donc

std::unique_ptr<s4prc::Noisy<std::string>>

.
Sa fonction membre get() nous donne accès au pointeur (usuel) qu'il mémorise en interne ; le test de nullité et le déréférencement sont identiques à ce que nous ferions avec un pointeur usuel.
(https://en.cppreference.com/w/cpp/memory/unique_ptr/get)
(https://en.cppreference.com/w/cpp/memory/unique_ptr/operator_bool)
(https://en.cppreference.com/w/cpp/memory/unique_ptr/operator*)

Une nouvelle exécution de notre programme doit montrer que l'effet obtenu avec le smart-pointer smart est très semblable à celui-que nous obtenions avec le pointeur usuel raw.
Cependant, nulle part nous n'avons envisagé de détruire la donnée désignée par la variable smart, et pourtant la destruction de cette donnée est bien signalée à la sortie de la fonction test_alloc()✍.
Le smart-pointer a joué pleinement son effet ici : lorsque la variable smart a été détruite (parce que la fonction se terminait), elle a également provoqué la libération et la destruction de la donnée qu'elle désignait✍.

Essayons maintenant de recopier ce smart-pointer en ajoutant à la fonction test_alloc() ces quelques nouvelles lignes :

auto smarter=smart; // attempt to copy a smart-pointer
std::cout << "smarter memorises the address " << smarter.get() << '\n';
if(smarter)
{
  std::cout << "... which contains " << *smarter << '\n';
}
std::cout << "then smart memorises the address " << smart.get() << '\n';
if(smart)
{
  std::cout << "... which contains " << *smart << '\n';
}

qui ont beaucoup en commun avec les précédentes.
À la compilation, vous aurez le désagrément de constater que l'opération qui consiste à initialiser la variable smarter par une recopie de la variable smart est rejetée ; ce comportement est tout à fait normal et même très souhaitable.
Comme son nom le suggère, le type std::unique_ptr<T> suppose une notion d'unicité : celle-ci porte sur la propriété de la donnée désignée, c'est-à-dire la responsabilité de la créer et de la détruire.
En effet, si à sa disparition un tel smart-pointer détruit automatiquement la donnée qu'il désigne, il est hors de question qu'un autre smart-pointer puisse désigner la même donnée car il en ferait autant à sa propre disparition✍.
C'est la raison pour laquelle le type std::unique_ptr<T> a été conçu comme non-recopiable mais uniquement déplaçable (move-only), c'est-à-dire que la propriété de la donnée qui leur est confiée est transférable mais non duplicable.

Modifiez alors la ligne qui concerne la création de la variable smarter de cette façon :

auto smarter=std::move(smart); // std::unique_ptr<T> is only movable

et relancez la fabrication du programme exécutable.
Celle-ci doit désormais aboutir à un nouveau programme dont l'exécution nous révélera le transfert de propriété qui vient d'être évoqué.
Les messages nous informent très précisément du fait que la donnée allouée dynamiquement qui était initialement maintenue par la variable smart est dorénavant sous la responsabilité de la variable smarter, et ce faisant, la variable smart est devenue équivalente à un pointeur nul.

Nous venons de constater que les smart-pointers de type std::unique_ptr<T> étaient transférables par une opération de déplacement.
Ceci permet notamment d'envisager de les transmettre en paramètre ou comme valeur de retour dans des fonctions✍.
Quel que soit le chemin emprunté, il n'y a à tout moment qu'un seul de ces smart-pointers qui est propriétaire de la donnée désignée et c'est la disparition du dernier propriétaire qui provoquera la destruction et la libération automatiques de cette donnée.

Dans le problème qui sert de prétexte à notre expérimentation, les nœuds qui sont des opérations sont constitués des nœuds qu'ils désignent, ils doivent donc en avoir la propriété ; les membres left_ et right_ ont alors de bonnes raisons d'être des smart-pointers.
Afin de mettre ceci en application, créez un nouveau module smart_node en vous inspirant très fortement du module raw_node.
Le type SmartNode de l'espace de noms s4prc sera déclaré de cette façon :

class SmartNode
{
public:

  SmartNode(double value);

  SmartNode(char oper,
            std::unique_ptr<SmartNode> left,
            std::unique_ptr<SmartNode> right);

  std::string
  show() const;

  double
  eval() const;

private:
  double value_oper_;
  std::unique_ptr<SmartNode> left_;
  std::unique_ptr<SmartNode> right_;
};

Son constructeur pour les nœuds représentant des opérations devra nécessairement utiliser des opérations de déplacement pour mémoriser les nœuds qui lui sont transmis.
Remarquez qu'il n'est désormais plus nécessaire d'envisager explicitement la destruction, la copie et la destruction pour le type SmartNode.
En effet, le comportement par défaut respecte simplement les contraintes des membres left_ et right_ : la destruction des ressources sera automatique, la copie sera interdite et le déplacement sera correctement réalisé par les smart-pointers eux-mêmes.

Le fichier prog.cpp doit maintenant être complété avec une fonction test_SmartNode(), très similaire à test_RawNode() (mais adaptée au nouveau type de nœud), appelée depuis la fonction principale. La fabrication de l'arbre de données aura désormais cette forme :

  using Node = s4prc::SmartNode;
  auto expr=std::make_unique<Node>('*',
              std::make_unique<Node>(10.1),
              std::make_unique<Node>('+',
                std::make_unique<Node>(5.2),
                std::make_unique<Node>(3.4)));

Les nœuds sont bien entendu crées dynamiquement grâce à la fonction std::make_unique<T>().
Dans cette fonction de test, le maintien de l'arbre de données sur lequel nous travaillons n'est dû qu'à l'existence de la variable expr.
Dès que celle-ci disparaît, le nœud qu'elle désigne est détruit et libéré, ce qui fait disparaître ses membres left_ et right_ qui sont eux-mêmes des smart-pointers.
La réaction en chaîne se poursuit automatiquement jusqu'à avoir détruit et libéré tous les nœuds de l'arbre✍.
C'est très proche dans les faits de ce que nous provoquions explicitement avec delete dans test_RawNode() si ce n'est que tout ça a désormais lieu automatiquement, ce qui limite les risques d'erreurs et d'oublis✍.
Après une nouvelle fabrication du programme, son exécution doit montrer pour la fonction test_SmartNode() un comportement similaire à celui de test_RawNode() et sans fuite de mémoire bien que nous n'ayons pas eu à détruire explicitement l'arbre de données que nous avons fabriqué dynamiquement.

Signalons toutefois qu'il est parfaitement correct d'extraire (avec la fonction membre get()) le pointeur que mémorise chaque smart-pointer car leurs rôles sont très distincts :

les smart-pointer servent à maintenir l'existence des données individuelles allouées dynamiquement,
- ils sont mémorisés dans des variables qui existent pendant toute la durée du traitement qui concerne ces données✍
  Il est incorrect d'utiliser un pointeur extrait d'un smart-pointer après que ce dernier ait disparu.
  En effet, la donnée désignée aura probablement été détruite et le pointeur désignera des données indéfinies.
  ,
- ils peuvent néanmoins exister temporairement pour initialiser ces variables par déplacement,
les pointeurs usuels servent à exprimer les traitements qui portent sur les données désignées,
- ils apparaissent, sont dupliqués et disparaissent pour les besoins des traitements sans que ça ne remette en cause l'existence des données désignées (voir la règle F.7 des CppCoreGuideLines),
- s'ils ne sont pas nuls, de tels pointeurs désignent forcément une donnée existante✍
  L'existence de cette donnée peut être assurée par de multiples moyens :
  
  une simple variable dont on a pris l'adresse,
  
  l'adresse d'un élément dans un tableau dynamique ou non,
  
  une donnée individuelle allouée dynamiquement et maintenue par un smart-pointer,
  
  ...
  ,
- ils doivent être remplacés par des références lorsque dans le traitement il n'est pas question qu'ils puissent être nuls.

Le type std::unique_ptr<T> ne représente qu'une seule variété de smart-pointers parmi ceux qui sont fournis par la bibliothèque standard de C++.
Il existe également le type std::shared_ptr<T> qui, comme son nom le suggère, autorise plusieurs d'entre-eux à se partager la propriété d'une même donnée qu'ils désignent ; il reste toutefois garanti qu'à la disparition du dernier d'entre-eux la donnée sera automatiquement détruite et libérée.
(https://en.cppreference.com/w/cpp/memory/shared_ptr)
En dépit de l'attrait exercé par l'annonce d'un tel type de smart-pointer, il faut savoir qu'il induit un surcoût à l'exécution (contrairement à std::unique_ptr<T> qui n'est pas plus coûteux qu'un pointeur usuel) et que son usage sans discernement peut conduire à des boucles de données auto-référencées qui empêchent leur destruction automatique✍.
En raison de son absence de surcoût et de son rôle très clair vis-à-vis des pointeurs usuels, les experts du langage C++ s'accordent à dire que le type std::unique_ptr<T> est à privilégier en matière de smart-pointer (nous n'aborderons pas dans cet enseignement l'usage des types std::shared_ptr<T> et std::weak_ptr<T>).

Finissons cette section en précisant que les principes sous-jacents à la réalisation du type std::unique_ptr<T> sont utilisés dans d'autres contextes que l'allocation dynamique de données.
En effet, la gestion des ressources en C++ moderne obéit au principe RAII (Resource Acquisition Is Initialisation) qui stipule :

que l'initialisation d'une donnée dédiée à la gestion d'une ressource particulière implique que cette ressource lui sera exclusivement confiée tant que cette donnée existera,
et que la ressource sera automatiquement libérée lorsque cette donnée disparaîtra (quelle que soit la raison de sa disparition).

C'est ce que font par exemple les types std::string et std::vector<T> vis-à-vis de la mémoire dynamique qu'ils utilisent en interne.
De plus, si la ressource concernée n'est pas considérée comme duplicable, cette propriété est généralement liée à l'impossibilité de recopier la donnée qui gère cette ressource : seul le déplacement est autorisé afin de rendre possible le transfert de la gestion de la ressource tout en assurant son exclusivité✍.

{} Évitement de l'allocation dynamique individuelle

En introduction de ce chapitre, nous précisions qu'il fallait éviter autant que possible d'allouer dynamiquement des données individuelles.
Nous avons malgré tout trouvé, à travers l'exploitation d'un arbre, un prétexte permettant d'illustrer raisonnablement ce besoin et les précautions qui s'y rapportent.
Cependant, à bien y réfléchir, il est encore envisageable de s'appuyer exclusivement sur le type std::vector<T> pour assurer l'allocation dynamique des nœuds✍.

La solution alternative proposée ne désigne plus les nœuds par des pointeurs mais simplement par des entiers représentant leur position dans un tableau dynamique.
La création d'un nouveau nœud consiste à l'ajouter au tableau dynamique et à relever sa position dans celui-ci (la taille du tableau dynamique avant l'ajout du nœud).
Par convention, nous pouvons décider qu'une position négative dénote l'absence de nœud comme le ferait un pointeur nul.
Mis à part ces détails, les algorithmes restent similaires si ce n'est qu'ils doivent avoir accès au tableau dynamique (en paramètre par référence, constante ou non selon le cas).

Cette solution offre plusieurs avantages :

la manipulation explicite de pointeurs étant considérée par beaucoup comme une source potentielle de maladresses ; le fait de s'en passer tend à diminuer les risques,
les primitives d'allocation dynamique de mémoire, qui sont réputées pour être très coûteuses en temps d'exécution, sont beaucoup moins fréquemment sollicitées (puisque le tableau dynamique utilise une stratégie d'allocation spéculative),
le stockage contigu des nœuds diminue la fragmentation de la mémoire utilisée, ce qui minimise les risques de perte de performances,
les entiers utilisés pour désigner les nœuds sont probablement moins grands que les pointeurs, ce qui diminue la taille des nœuds et est favorable à une exécution efficace,
l'ensemble de l'arbre forme un tout contigu et simplement référencé dans le tableau dynamique ce qui permet de le dupliquer ou de le sérialiser (le stocker et le relire dans un fichier par exemple) très facilement✍
Les solutions à base de pointeurs (usuels ou smart-pointers) nécessiteraient une phase de réécriture de l'arbre dans une forme semblable à celle du tableau dynamique justement !
Les adresses n'ont en effet plus aucune signification à l'extérieur du programme en cours d'exécution.
.

Puisque cette expérimentation se focalise sur l'allocation dynamique de données individuelles, nous ne détaillerons pas plus cette solution alternative.
Elle est simplement fournie, parmi les fichiers résultants, sous la forme du module compact_node dont le programme principal fait usage.
Une fonction réalise des mesures simples qui montrent que les trois solutions envisagées ont des performances proches dans le cas présent.

Code source de l'expérimentation

Si chaque étape a été respectée scrupuleusement, vous devez obtenir des fichiers de code source semblables à ceux-ci :

Fichier noisy.hpp✎

Contenu du fichier noisy.hpp

//----------------------------------------------------------------------------

#ifndef S4PRC_NOISY_HPP
#define S4PRC_NOISY_HPP

#include <iostream>
#include <string>
#include <vector>

namespace s4prc {

inline
std::ostream &
operator<<(std::ostream &output,
           const std::string &s) // display string within quotes
{
  using std::operator<<;
  output << '"';
  if(const auto sz=size(s); sz>20) // prevent from using too much space
  {
    output << s.substr(0, 10) << "..." << s.substr(sz-10);
  }
  else
  {
    output << s;
  }
  return output << '"';
}

template<typename E>
inline
std::ostream &
operator<<(std::ostream &output,
           const std::vector<E> &v) // display vector within braces
{
  output << '{';
  if(const auto sz=size(v); sz>4) // prevent from using too much space
  {
    output << v[0] << ',' << v[1] << ",...," << v[sz-2] << ',' << v[sz-1];
  }
  else
  {
    int count=0;
    for(const auto &elem: v)
    {
      if(count++)
      {
        output << ',';
      }
      output << elem;
    }
  }
  return output << '}';
}

template<typename T>
struct Noisy : T
{
  Noisy()
  : T{}
  {
    std::cout << "construct " << *this
              << " from nothing\n";
  }

  Noisy(const T &t)
  : T{t}
  {
    std::cout << "copy-construct " << *this
              << "\n   ... from " << t << '\n';
  }

  Noisy(T &&t)
  : T{std::move(t)}
  {
    std::cout << "move-construct " << *this
              << "\n   ... from (moved) " << t << '\n';
  }

  Noisy(const Noisy &n)
  : T{static_cast<const T &>(n)}
  {
    std::cout << "copy-construct " << *this
              << "\n   ... from " << n << '\n';
  }

  Noisy(Noisy &&n) noexcept
  : T{std::move(static_cast<T &&>(n))}
  {
    std::cout << "move-construct " << *this
              << "\n   ... from (moved) " << n << '\n';
  }

  Noisy &
  operator=(const T &t)
  {
    T::operator=(t);
    std::cout << "copy-assign " << *this
              << "\n   ... from " << t << '\n';
    return *this;
  }

  Noisy &
  operator=(T &&t)
  {
    T::operator=(std::move(t));
    std::cout << "move-assign " << *this
              << "\n   ... from (moved) " << t << '\n';
    return *this;
  }

  Noisy &
  operator=(const Noisy &n)
  {
    T::operator=(static_cast<const T &>(n));
    std::cout << "copy-assign " << *this
              << "\n   ... from " << n << '\n';
    return *this;
  }

  Noisy &
  operator=(Noisy &&n) noexcept
  {
    T::operator=(std::move(static_cast<T &&>(n)));
    std::cout << "move-assign " << *this
              << "\n   ... from (moved) " << n << '\n';
    return *this;
  }

  ~Noisy()
  {
    std::cout << "destroy " << *this << '\n';
  }

  friend
  std::ostream &
  operator<<(std::ostream &output,
             const Noisy &n)
  {
    return output << "Noisy@" << &n << ":" << static_cast<const T &>(n);
  }
};

} // namespace s4prc

#endif // S4PRC_NOISY_HPP

//----------------------------------------------------------------------------

Fichier raw_node.hpp✎

Fichier raw_node.cpp✎

Fichier smart_node.hpp✎

Fichier smart_node.cpp✎

Fichier compact_node.hpp✎

Fichier compact_node.cpp✎

Fichier prog.cpp✎

Contenu du fichier prog.cpp

//----------------------------------------------------------------------------

#include <iostream>
#include <chrono>

#include "noisy.hpp"
#include "raw_node.hpp"
#include "smart_node.hpp"
#include "compact_node.hpp"

double // seconds (1e-6 precision) since 1970/01/01 00:00:00 UTC
get_time()
{
  const auto now=std::chrono::system_clock::now().time_since_epoch();
  const auto us=std::chrono::duration_cast<std::chrono::microseconds>(now);
  return 1e-6*double(us.count());
}

void
test_alloc()
{
  std::cout << "\n~~~~ enter " << __func__ << "() ~~~~\n";
  // WARNING: never use new in real C++ code!
  auto *raw=new s4prc::Noisy<std::string>{"raw-pointer"};
  std::cout << "raw memorises the address " << raw << '\n';
  if(raw)
  {
    std::cout << "... which contains " << *raw << '\n';
  }
  // WARNING: never use delete in real C++ code!
  delete raw; // mandatory to prevent memory-leak!
  auto smart=std::make_unique<s4prc::Noisy<std::string>>("smart-pointer");
  std::cout << "smart memorises the address " << smart.get() << '\n';
  if(smart)
  {
    std::cout << "... which contains " << *smart << '\n';
  }
  // auto smarter=smart; // std::unique_ptr<T> cannot be copied!
  auto smarter=std::move(smart); // std::unique_ptr<T> is only movable
  std::cout << "smarter memorises the address " << smarter.get() << '\n';
  if(smarter)
  {
    std::cout << "... which contains " << *smarter << '\n';
  }
  std::cout << "then smart memorises the address " << smart.get() << '\n';
  if(smart)
  {
    std::cout << "... which contains " << *smart << '\n';
  }
  std::cout << "~~~~ leave " << __func__ << "() ~~~~\n";
}

void
test_RawNode()
{
  std::cout << "\n~~~~ enter " << __func__ << "() ~~~~\n";
  using Node = s4prc::RawNode;
  // WARNING: never use new in real C++ code!
  auto *expr=new Node{'*',
               new Node{10.1},
               new Node{'+',
                 new Node{5.2},
                 new Node{3.4}}};
  std::cout << expr->show() << "="
            << expr->eval() << '\n';
  // WARNING: never use delete in real C++ code!
  delete expr; // mandatory to prevent memory-leaks!
  std::cout << "~~~~ leave " << __func__ << "() ~~~~\n";
}

void
test_SmartNode()
{
  std::cout << "\n~~~~ enter " << __func__ << "() ~~~~\n";
  using Node = s4prc::SmartNode;
  auto expr=std::make_unique<Node>('*',
              std::make_unique<Node>(10.1),
              std::make_unique<Node>('+',
                std::make_unique<Node>(5.2),
                std::make_unique<Node>(3.4)));
  std::cout << expr->show() << "="
            << expr->eval() << '\n';
  std::cout << "~~~~ leave " << __func__ << "() ~~~~\n";
}

void
test_CompactNode()
{
  std::cout << "\n~~~~ enter " << __func__ << "() ~~~~\n";
  using Node = s4prc::CompactNode;
  std::vector<Node> nodes;
  auto expr=make(nodes, '*',
              make(nodes, 10.1),
              make(nodes, '+',
                make(nodes, 5.2),
                make(nodes, 3.4)));
  std::cout << nodes[expr].show(nodes) << "="
            << nodes[expr].eval(nodes) << '\n';
  std::cout << "~~~~ leave " << __func__ << "() ~~~~\n";
}

void
test_perf()
{
  std::cout << "\n~~~~ " << __func__ << "() ~~~~\n";
#if !defined NDEBUG
  std::cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
               "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"
               "  Built for debug purpose at first "
               "(measurements will not be relevant).\n"
               "  For an actual experiment, rebuild with: "
               "   make rebuild opt=1\n"
               "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
               "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n";
#endif
  const auto perf_build=
    [&](const auto &value_fnct, const auto &oper_fnct)
    {
      const int node_count=1000;
      auto expr=value_fnct(1.0);
      for(int i=0; i<node_count; ++i)
      {
        expr=oper_fnct('+', value_fnct(0.1), expr);
      }
      return expr;
    };
  const auto perf_run=
    [&](const auto &name, auto &expr, const auto &eval_fnct)
    {
      const int iter_count=100'000;
      for(int i=0; i<10; ++i)
      {
        eval_fnct(expr); // warm-up before measure
      }
      const double t0=get_time();
      double result=0.0;
      for(int i=0; i<iter_count; ++i)
      {
        result+=eval_fnct(expr);
      }
      const double dt=get_time()-t0;
      std::cout << name << " takes " << dt << " s\n";
      std::cout << ">>> result=" << result << '\n';
    };
  if(1)
  {
    using Node = s4prc::RawNode;
    auto expr=perf_build(
      [&](const auto &value)
      {
        // WARNING: never use new in real C++ code!
        return new Node{value};
      },
      [&](const auto &oper, const auto &left, const auto &right)
      {
        // WARNING: never use new in real C++ code!
        return new Node{oper, left, right};
      });
    perf_run("RawNode", expr,
      [&](const auto &expr)
      {
        return expr->eval();
      });
    // WARNING: never use delete in real C++ code!
    delete expr; // mandatory to prevent memory-leak!
  }
  if(1)
  {
    using Node = s4prc::SmartNode;
    auto expr=perf_build(
      [&](const auto &value)
      {
        return std::make_unique<Node>(value);
      },
      [&](const auto &oper, auto &&left, auto &&right)
      {
        return std::make_unique<Node>(oper, std::move(left), std::move(right));
      });
    perf_run("SmartNode", expr,
      [&](const auto &expr)
      {
        return expr->eval();
      });
  }
  if(1)
  {
    using Node = s4prc::CompactNode;
    std::vector<Node> nodes;
    auto expr=perf_build(
      [&](const auto &value)
      {
        return make(nodes, value);
      },
      [&](const auto &oper, const auto &left, const auto &right)
      {
        return make(nodes, oper, left, right);
      });
    perf_run("CompactNode", expr,
      [&](const auto &expr)
      {
        return nodes[expr].eval(nodes);
      });
  }
}

int
main()
{
  test_alloc();
  test_RawNode();
  test_SmartNode();
  test_CompactNode();
  test_perf();
  return 0;
}

//----------------------------------------------------------------------------