Liste doublement chaînée avec noeuds sentinelles

Je n'ai pas le temps de documenter ce qui suit pour le moment, mais vous trouverez deux implémentations possibles (et incomplètes) de listes doublement chaînées avec noeuds sentinelles aux extrémités et itérateurs. L'une, la classe noeuds_sentinelles_statiques::Liste, intègre les noeuds sentinelles à la liste, alors que l'autre, noeuds_sentinelles_dynamiques::Liste, alloue ces noeuds sentinelles dynamiquement.

J'ai séparé l'interface de l'implémentation, même si ce n'est pas ce que j'aurais fait normalement. Notez que les listes qui suivent entreposent des std::string, mais que l'usage serait de faire de ces listes des structures de données génériques.

#ifndef LISTE_STR_H
#define LISTE_STR_H
#include <string>
#include <string_view>
class liste_vide {};
namespace noeuds_sentinelles_statiques {
   class Liste {
      struct Noeud {
         std::string valeur;
         Noeud *pred {};
         Noeud *succ {};
         Noeud() = default;
         Noeud(std::string_view) : valeur{ valeur } {
         }
      };
      Noeud sentinelle_debut,
            sentinelle_fin;
      std::size_t nelems{};
   public:
      class iterator {
         Noeud *cur;
      public:
         iterator(Noeud*) noexcept;
         iterator& operator++() noexcept;
         iterator operator++(int) noexcept;
         iterator& operator--() noexcept;
         iterator operator--(int) noexcept;
         bool operator==(iterator) const noexcept;
         bool operator!=(iterator) const noexcept;
         std::string& operator*() noexcept;
         const std::string& operator*() const noexcept;
         // pas besoin de operator->() si on n'a que des string
      };
      iterator begin() noexcept;
      iterator begin() const noexcept;
      iterator end() noexcept;
      iterator end() const noexcept;
      Liste();
      [[nodiscard]] bool empty() const noexcept {
         return !size();
      }
      void clear() noexcept;
      [[nodiscard]] std::size_t size() const noexcept {
         return nelems;
      }
      // Sainte-Trinité
      Liste(const Liste&);
      Liste& operator=(const Liste&);
      ~Liste();
      void swap(Liste&) noexcept;
      // mouvement
      Liste(Liste&&);
      Liste& operator=(Liste&&);
      // opérations aux extrémités
      void push_front(std::string_view);
      void push_back(std::string_view);
      void pop_front();
      void pop_back();
      std::string front();
      std::string back();
      // autres opérations (insert, erase)
   };
}

namespace noeuds_sentinelles_dynamiques {
   class Liste {
      struct Noeud {
         std::string valeur;
         Noeud *pred {};
         Noeud *succ {};
         Noeud() = default;
         Noeud(std::string_view valeur) : valeur{ valeur } {
         }
      };
      Noeud *sentinelle_debut,
            *sentinelle_fin;
      std::size_t nelems{};
   public:
      class iterator {
         Noeud *cur;
      public:
         iterator(Noeud*) noexcept;
         iterator& operator++() noexcept;
         iterator operator++(int) noexcept;
         iterator& operator--() noexcept;
         iterator operator--(int) noexcept;
         bool operator==(iterator) const noexcept;
         bool operator!=(iterator) const noexcept;
         std::string& operator*() noexcept;
         const std::string& operator*() const noexcept;
         // pas besoin de operator->() si on n'a que des string
      };
      iterator begin() noexcept;
      iterator begin() const noexcept;
      iterator end() noexcept;
      iterator end() const noexcept;
      Liste();
      [[nodiscard]] bool empty() const noexcept {
         return !size();
      }
      void clear() noexcept;
      [[nodiscard]] std::size_t size() const noexcept {
         return nelems;
      }
      // Sainte-Trinité
      Liste(const Liste&);
      Liste& operator=(const Liste&);
      ~Liste();
      void swap(Liste&) noexcept;
      // mouvement
      Liste(Liste&&);
      Liste& operator=(Liste&&);
      // opérations aux extrémités
      void push_front(std::string_view);
      void push_back(std::string_view);
      void pop_front();
      void pop_back();
      std::string front();
      std::string back();
      // autres opérations (insert, erase)
   };
}
#endif

L'implémentation (les implémentations!) suit (suivent) :

#include "Liste.h"
#include <string>
#include <string_view>
using namespace std;

namespace noeuds_sentinelles_statiques {
   Liste::Liste() {
      sentinelle_debut.succ = &sentinelle_fin;
      sentinelle_fin.pred = &sentinelle_debut;
   }

   Liste::iterator::iterator(Noeud *p) noexcept : cur{ p } {
   }

   Liste::iterator& Liste::iterator::operator++() noexcept {
      cur = cur->succ;
      return *this;
   }
   Liste::iterator Liste::iterator::operator++(int) noexcept {
      auto temp = *this;
      operator++();
      return temp;
   }

   Liste::iterator& Liste::iterator::operator--() noexcept {
      cur = cur->pred;
      return *this;
   }
   Liste::iterator Liste::iterator::operator--(int) noexcept {
      auto temp = *this;
      operator--();
      return temp;
   }

   bool Liste::iterator::operator==(iterator it) const noexcept {
      return cur == it.cur;
   }
   bool Liste::iterator::operator!=(iterator it) const noexcept {
      return !(*this == it);
   }
   string& Liste::iterator::operator*() noexcept {
      return cur->valeur;
   }
   const string& Liste::iterator::operator*() const noexcept {
      return cur->valeur;
   }

   // itérateurs
   Liste::iterator Liste::begin() noexcept {
      return { sentinelle_debut.succ };
   }
   Liste::iterator Liste::begin() const noexcept {
      return { sentinelle_debut.succ };
   }
   Liste::iterator Liste::end() noexcept {
      return { &sentinelle_fin };
   }
   Liste::iterator Liste::end() const noexcept {
      return { const_cast<Noeud*>(&sentinelle_fin) }; // patch
   }

   // Sainte-Trinité
   Liste::Liste(const Liste &lst) : Liste{} {
      for (auto & val : lst)
         push_back(val);
   }
   Liste& Liste::operator=(const Liste &autre) {
      Liste{ autre }.swap(*this);
      return *this;
   }
   void Liste::clear() noexcept { // peut être optimisé
      while (!empty())
         pop_back();
   }
   Liste::~Liste() {
      clear(); // peut être optimisé
   }
   void Liste::swap(Liste &autre) noexcept {
      using std::swap;
      swap(sentinelle_debut.succ, autre.sentinelle_debut.succ);
      swap(sentinelle_fin.pred, autre.sentinelle_fin.pred);
   }

   // mouvement
   Liste::Liste(Liste &&autre) : Liste{} {
      swap(autre); // discutable
   }
   Liste& Liste::operator=(Liste &&autre) {
      swap(autre); // discutable
      return *this;
   }

   // opérations aux extrémités
   void Liste::push_front(string_view valeur) {
      auto p = new Noeud{ valeur };
      p->succ = sentinelle_debut.succ;
      if (p->succ)
         p->succ->pred = p;
      p->pred = &sentinelle_debut;
      sentinelle_debut.succ = p;
      ++nelems;
   }

   void Liste::push_back(string_view valeur) {
      auto p = new Noeud{ valeur };
      p->pred = sentinelle_fin.pred;
      if (p->pred)
         p->pred->succ = p;
      p->succ = &sentinelle_fin;
      sentinelle_fin.pred = p;
      ++nelems;
   }
   void Liste::pop_front() {
      if (empty()) throw liste_vide{};
      auto p = sentinelle_debut.succ;
      sentinelle_debut.succ = p->succ;
      if (sentinelle_debut.succ)
         sentinelle_debut.succ->pred = &sentinelle_debut;
      delete p;
      --nelems;
   }
   void Liste::pop_back() {
      if (empty()) throw liste_vide{};
      auto p = sentinelle_fin.pred;
      sentinelle_fin.pred = p->pred;
      if (sentinelle_fin.pred)
         sentinelle_fin.pred->succ = &sentinelle_fin;
      delete p;
      --nelems;
   }
   string Liste::front() {
      if (empty()) throw liste_vide{};
      return sentinelle_debut.succ->valeur;
   }
   string Liste::back() {
      if (empty()) throw liste_vide{};
      return sentinelle_fin.pred->valeur;
   }
}

namespace noeuds_sentinelles_dynamiques {
   Liste::Liste() : sentinelle_debut{ new Noeud } {
      try {
         sentinelle_fin = new Noeud;
         sentinelle_debut->succ = sentinelle_fin;
         sentinelle_fin->pred = sentinelle_debut;
      } catch (...) {
         delete sentinelle_debut;
         throw;
      }
   }

   Liste::iterator::iterator(Noeud *p) noexcept : cur{ p } {
   }

   Liste::iterator& Liste::iterator::operator++() noexcept {
      cur = cur->succ;
      return *this;
   }
   Liste::iterator Liste::iterator::operator++(int) noexcept {
      auto temp = *this;
      operator++();
      return temp;
   }

   Liste::iterator& Liste::iterator::operator--() noexcept {
      cur = cur->pred;
      return *this;
   }
   Liste::iterator Liste::iterator::operator--(int) noexcept {
      auto temp = *this;
      operator--();
      return temp;
   }

   bool Liste::iterator::operator==(iterator it) const noexcept {
      return cur == it.cur;
   }
   bool Liste::iterator::operator!=(iterator it) const noexcept {
      return !(*this == it);
   }
   string& Liste::iterator::operator*() noexcept {
      return cur->valeur;
   }
   const string& Liste::iterator::operator*() const noexcept {
      return cur->valeur;
   }

   // itérateurs
   Liste::iterator Liste::begin() noexcept {
      return { sentinelle_debut->succ };
   }
   Liste::iterator Liste::begin() const noexcept {
      return { sentinelle_debut->succ };
   }
   Liste::iterator Liste::end() noexcept {
      return { sentinelle_fin };
   }
   Liste::iterator Liste::end() const noexcept {
      return { sentinelle_fin };
   }

   // Sainte-Trinité
   Liste::Liste(const Liste &lst) : Liste{} {
      for (auto & val : lst)
         push_back(val);
   }
   Liste& Liste::operator=(const Liste &autre) {
      Liste{ autre }.swap(*this);
      return *this;
   }
   void Liste::clear() noexcept { // peut être optimisé
      while (!empty())
         pop_back();
   }
   Liste::~Liste() {
      clear(); // peut ête optimisé
      delete sentinelle_fin;
      delete sentinelle_debut;
   }
   void Liste::swap(Liste &autre) noexcept {
      using std::swap;
      swap(sentinelle_debut, autre.sentinelle_debut);
      swap(sentinelle_fin, autre.sentinelle_fin);
   }

   // mouvement
   Liste::Liste(Liste &&autre) : Liste{} {
      swap(autre); // discutable
   }
   Liste& Liste::operator=(Liste &&autre) {
      swap(autre); // discutable
      return *this;
   }

   // opérations aux extrémités
   void Liste::push_front(string_view valeur) {
      auto p = new Noeud{ valeur };
      p->succ = sentinelle_debut->succ;
      if (p->succ)
         p->succ->pred = p;
      p->pred = sentinelle_debut;
      sentinelle_debut->succ = p;
      ++nelems;
   }

   void Liste::push_back(string_view valeur) {
      auto p = new Noeud{ valeur };
      p->pred = sentinelle_fin->pred;
      if (p->pred)
         p->pred->succ = p;
      p->succ = sentinelle_fin;
      sentinelle_fin->pred = p;
      ++nelems;
   }
   void Liste::pop_front() {
      if (empty()) throw liste_vide{};
      auto p = sentinelle_debut->succ;
      sentinelle_debut->succ = p->succ;
      if (sentinelle_debut->succ)
         sentinelle_debut->succ->pred = sentinelle_debut;
      delete p;
      --nelems;
   }
   void Liste::pop_back() {
      if (empty()) throw liste_vide{};
      auto p = sentinelle_fin->pred;
      sentinelle_fin->pred = p->pred;
      if (sentinelle_fin->pred)
         sentinelle_fin->pred->succ = sentinelle_fin;
      delete p;
      --nelems;
   }
   string Liste::front() {
      if (empty()) throw liste_vide{};
      return sentinelle_debut->succ->valeur;
   }
   string Liste::back() {
      if (empty()) throw liste_vide{};
      return sentinelle_fin->pred->valeur;
   }
}

Un exemple de code de test serait :

#include "Liste.h"
#include <iostream>
using namespace std;

int main() {
   using noeuds_sentinelles_dynamiques::Liste;
   // using noeuds_sentinelles_statiques::Liste;
   Liste lst;
   for (auto &s : { "J'aime", "mon", "prof" })
      lst.push_back(s);
   for (auto & s : lst)
      cout << s << ' ';
   cout << endl;
}

Voilà. J'enrichirai d'explications quand je le pourrai.

Valid XHTML 1.0 Transitional

CSS Valide !