Pile générique à capacité statique

Deux petits exemples banals de piles génériques sur la base d'un type T, dont la capacité est déterminée de manière statique, donc à la compilation.

Le premier exemple alloue dynamiquement la zone mémoire dans laquelle la gestion des éléments de la pile sera faite. Cette approche est idéale en général, surtout lorsque les valeurs de N sont « grandes ».

Entendu ici que « grande » est quelque peu subjectif : ce que nous souhaitons est éviter que la véritable pile d'exécution du thread utilisant une instance de cette classe ne soit débordée par l'espace que l'instance en question occupera – ici, en allouant dynamiquement ce vers quoi mènera p_, on garde l'espace occupé par une instance de Pile<T,N> sur la pile d'exécution approximativement à la hauteur de sizeof(T*)+sizeof(int), ce qui est tout petit.

Je vous invite à les raffiner (ajouter la sémantique de copie et la sémantique de mouvement, en particulier).

#ifndef PILE_H
#define PILE_H
#include "incopiable.h"
//
// Version de Pile<T,N> pour de gros N (alloue
// l'espace pour les éléments de manière dynamique)
// Pouvez-vous identifier des invariants?
//
class Pleine {};
class Vide {};
template <class T, int N>
   class Pile
      : Incopiable
   {
   public:
      using value_type = T;
      using size_type = int;
   private:
      value_type *p_;
      size_type tete_;
   public:
      Pile()
         : tete_{}, p_{new value_type[N]}
      {
      }
      bool empty() const noexcept
         { return !tete_; }
      bool full() const noexcept
         { return tete_ == N; }
      void push(const value_type &val)
      {
         if(full()) throw Pleine{};
         p_[tete_] = val;
         ++tete_;
      }
      void pop()
      {
         if(empty()) throw Vide{};
         --tete_;
      }
      value_type& top()
      {
         if(empty()) throw Vide{};
         return p_[tete_-1];
      }
      ~Pile() noexcept
         { delete[] p_; }
   };
#endif

Le deuxième exemple se prête à de « petites » valeurs de N (et à de petits T), et peut être économique en temps d'exécution du fait qu'elle ne requiert pas la gestion de mémoire allouée dynamiquement.

#ifndef PILE_H
#define PILE_H
//
// Version de Pile<T,N> pour de petits N (alloue
// l'espace pour les éléments de manière automatique)
// Pouvez-vous identifier des invariants?
//
class Pleine {};
class Vide {};
template <class T, int N>
   class Pile
   {
   public:
      using value_type = T;
      using size_type = int;
   private:
      value_type p_[N];
      size_type tete_;
   public:
      Pile()
         : tete_{}
      {
      }
      bool empty() const noexcept
         { return !tete_; }
      bool full() const noexcept
         { return tete_ == N; }
      void push(const value_type &val)
      {
         if(full()) throw Pleine{};
         p_[tete_] = val;
         ++tete_;
      }
      void pop()
      {
         if(empty()) throw Vide{};
         --tete_;
      }
      value_type& top()
      {
         if(empty()) throw Vide{};
         return p_[tete_-1];
      }
   };
#endif

Choisir une implémentation

Si vous souhaitez une seule classe Pile<T,N> qui soit capable de choisir son implémentation sous-jacente parmi les deux ci-dessus à partir de sizeof(T) et de N, donc qui utilise la version sans allocation dynamique de mémoire pour de « petits » N*sizeof(T) et qui utilise la version avec allocation dynamique de mémoire lorsque N*sizeof(T) passe un certain seuil, voici comment procéder.

En gros, voici comment procéder :

pour conserver le nom Pile<T,N> à fins d'utilisation dans le code client, ce nom étant celui que le code client voudra utiliser, nous renommons les deux implémentations plus haut;
nous déterminons un seuil à partir duquel il vaut mieux, selon nous, utiliser une implémentation ou l'autre (ici, j'ai mis 4096 bytes, mais c'est absolument arbitraire, rien de scientifique);
le seuil a été déposé dans une classe dont le rôle est de faciliter la sélection d'une implémentation. Ici, cette classe a été nommée pile_impl_selector<T,N> et le type interne type correspond à l'implémentation jugée appropriée;
enfin, on dérive Pile<T,N> de façon publique de pile_impl_selector<T,N>::type. Ceci correspond à choisir une implémentation sur la base de données connues à la compilation. Un charme!

J'utilise une alternative statique, std::conditional, pour implémenter le choix de type d'implémentation. Pour en savoir plus à ce sujet, je vous invite à lire l'article sur la métaprogrammation du présent site.

#ifndef PILE_H
#define PILE_H
#include "incopiable.h"
class Pleine {};
class Vide {};
template <class T, int N>
   class PileAlloc
      : Incopiable
   {
   public:
      using value_type = T;
      using size_type = int;
   private:
      value_type *p_;
      size_type tete_;
   public:
      PileAlloc()
         : tete_{}, p_{new value_type[N]}
      {
      }
      bool empty() const noexcept
         { return !tete_; }
      bool full() const noexcept
         { return tete_ == N; }
      void push(const value_type &val)
      {
         if(full()) throw Pleine{};
         p_[tete_] = val;
         ++tete_;
      }
      void pop()
      {
         if(empty()) throw Vide{};
         --tete_;
      }
      value_type& top()
      {
         if(empty()) throw Vide{};
         return p_[tete_-1];
      }
      ~PileAlloc() noexcept
         { delete[] p_; }
   };
template <class T, int N>
   class PileNoAlloc
   {
   public:
      using value_type = T;
      using size_type = int;
   private:
      value_type p_[N]
      size_type tete_;
   public:
      PileNoAlloc()
         : tete_{}
      {
      }
      bool empty() const noexcept
         { return !tete_; }
      bool full() const noexcept
         { return tete_ == N; }
      void push(const value_type &val)
      {
         if(full()) throw Pleine{};
         p_[tete_] = val;
         ++tete_;
      }
      void pop()
      {
         if(empty()) throw Vide{};
         --tete_;
      }
      value_type& top()
      {
         if(empty()) throw Vide{};
         return p_[tete_-1];
      }
   };
#include <type_traits>
template <class T, int N>
   class pile_impl_selector
   {
      enum { SEUIL = 4096 }; // arbitraire
   public:
      using type = typename
         std::conditional<
           (sizeof(T)*N >= SEUIL),
           PileAlloc<T,N>,
           PileNoAlloc<T,N>
         >::type;
   };
template <class T, int N>
   class Pile
      : public pile_impl_selector<T,N>::type
   {
   };
#endif

Qu'en pensez-vous?