Comparatif d'implémentations, classe Liste<T> et itérateurs/ énumérateurs

Si vous souhaitez comparer ce qui suit avec une version plus simple, ne permettant de lister que des entiers et n'offrant pas une interface d'itérateurs (ou d'énumérateurs), jetez un coup d'oeil à ce comparatif d'une classe ListeEntiers.

Ce qui suit montre une implémentation simple d'une classe Liste<T>, représentant une liste simplement chaînée d'instances d'un type T, dans trois langages distincts soit Java, C# et C++, de même que ses itérateurs ou ses énumérateurs (selon le vocabulaire de chacun des langages). Chacune a ses forces, faiblesses et caractéristiques diverses; l'idée ici est de mettre en relief les similitudes et différences entre elles, pas de critiquer ou d'encenser l'une ou l'autre.

Nous débuterons par un comparatif côte à côte des trois implémentations, suite à quoi nous reviendrons sur les détails de chacune (détail de la version C#, détail de la version C++, détail de la version Java). Notez que, contrairement au cas de la liste d'entiers sans itérateurs ni énumérateurs, cette proposition est plus près d'une classe utilisable en pratique et est, par consquent, plus sophistiquée. La version C++, en particulier, sera nettement plus puissante que les versions antérieures – en pratique, on utilisera un tel conteneur plus souvent qu'on ne le programmera, mais vous aurez tout de même un exemple à vous mettre sous la dent si vous le souhaitez. Pour cette raison, les éléments présentés seront identifiés comme étant essentiels (sans quoi la classe n'est pas utilisable) ou souhaitables (sans quoi la classe fonctionne mais n'est pas de calibre commercial).

Comparatif côte à côte

Placées côte à côte, les implémentations que nous examinerons dans ces trois langages vont comme suit.

Implémentation C# Implémentation C++ Implémentation Java 
using System;
namespace Liste
{
   class ListeVide : ApplicationException
   {
   }
   sealed class Liste<T> : IEnumerable<T>
   {
      private sealed class Noeud
      {
         public Noeud Succ { get; set; } = null;
         public T Valeur
         {
            get; private set;
         }
         public Noeud(T val)
         {
            Valeur = val;
         }
         public Noeud(Noeud n)
         {
            Valeur = n.Valeur; // ICI: risqué (partage; espérons T immuable!)
         }
      }
      private Noeud Tete { get; set; } = null;
      private Noeud Fin { get; set; } = null;
      public bool Vide
      {
         get => Tete == null;
      }
      public int Taille { get; private set; } = 0;
      public Liste()
      {
      }
      private Liste(Liste<T> lst)
      {
         for (Noeud p = lst.Tete; p != null; p = p.Succ)
            Ajouter(p.Valeur);
      }
      public Liste<T> Dupliquer() =>
         new Liste<T>(this);
      public void Ajouter(T val)
      {
         Noeud p = new Noeud(val);
         if (Vide)
            Tete = Fin = p;
         else
         {
            Fin.Succ = p;
            Fin = p;
         }
         ++Taille;
      }
      public void Inverser()
      {
         Noeud nouvelleTete = null,
               nouvelleFin = null;
         if (Tete != null)
         {
            Noeud p = new Noeud(Tete);
            p.Succ = nouvelleTete;
            nouvelleFin = nouvelleTete = p;
            p = Tete;
            Tete  = Tete.Succ;
         }
         while (Tete != null)
         {
            Noeud p = new Noeud(Tete);
            p.Succ = nouvelleTete;
            nouvelleTete = p;
            p = Tete;
            Tete = Tete.Succ;
         }
         Tete = nouvelleTete;
         Fin = nouvelleFin;
      }
      public T Extraire()
      {
         if (Vide)
            throw new ListeVide();
         Noeud p = Tete;
         Tete = Tete.Succ;
         T val = p.Valeur;
         if (p == Fin)
         {
            Fin = null;
         }
         --Taille;
         return val;
      }
      private class Énumérateur : IEnumerator<T>
      {
         private Noeud Cur { get; set; } = null;
         private Liste<T> Source
         {
            get; set;
         }
         public Énumérateur(Liste<T> source)
         {
            Source = source;
         }
         public void Reset()
         {
            Cur = null;
         }
         public T Current
         {
            get => Cur.Valeur;
         }
         public bool MoveNext()
         {
            if (Source == null)
               Cur = null;
            else if (Cur == null)
               Cur = Source.Tete;
            else
               Cur = Cur.Succ;
            return Cur != null;
         }
         public void Dispose()
         {
            // j'ai choisi de ne pas l'implémenter
         }
         //
         // Soutien historique...
         //
         object System.Collections.IEnumerator.Current
         {
            get => Cur.Valeur;
         }
      }
      public IEnumerator<T> GetEnumerator() =>
         new Énumérateur(this);
      //
      // Soutien historique...
      //
      System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() =>
         new Énumérateur(this);
   }
   class Program
   {
      static void Main(string[] args)
      {
         //
         // Liste<int>
         //
         const int NB_ENTIERS = 10;
         Liste<int> lst = new Liste<int>();
         for (int i = 0; i < NB_ENTIERS; i++)
         {
            lst.Ajouter(i + 1);
         }
         foreach (int i in lst)
         {
            Console.Write($"{i} ");
         }
         Console.WriteLine();
         Liste<int> lstInv = lst.Dupliquer();
         lstInv.Inverser();
         {
            int nbÉléments = lstInv.Taille;
            for (int i = 0; i < nbÉléments; i++)
            {
               Console.Write($"{lstInv.Extraire()} ");
            }
            Console.WriteLine();
            for (int i = 0; i < nbÉléments; i++)
            {
               Console.Write($"{lst.Extraire()} ");
            }
            Console.WriteLine();
         }
         //
         // Liste<String>
         //
         string [] mots =
         {
            "J'aime", "mon", "prof!"
         };
         Liste<string> lstStr = new Liste<string>();
         for (int i = 0; i < mots.Length; i++)
         {
            lstStr.Ajouter(mots[i]);
         }
         foreach (string s in lstStr)
         {
            Console.Write($"{s} ");
         }
         Console.WriteLine();
         Liste<string> lstStrInv = lstStr.Dupliquer();
         lstStrInv.Inverser();
         {
            int nbÉléments = lstStrInv.Taille;
            for (int i = 0; i < nbÉléments; i++)
            {
               Console.Write($"{lstStrInv.Extraire()} ");
            }
            Console.WriteLine();
            for (int i = 0; i < nbÉléments; i++)
            {
               Console.Write($"{lstStr.Extraire()} ");
            }
            Console.WriteLine();
         }
      }
   }
}
 
#ifndef LISTE_H
#define LISTE_H

#include <cstdlib>
#include <algorithm>
#include <initializer_list>
#include <iterator>

class ListeVide {};

template <class T>
   class Liste final {
   public:
      using value_type = T;
      using size_type = std::size_t;
   private:
      struct Noeud final {
         value_type val;
         Noeud *succ {};
         Noeud (const value_type &val) : val{ val } {
         }
         Noeud (const Noeud &n) : val{ n.val } {
         }
      };
      Noeud *tete {}, *queue {};
      size_type nelems {};
   public:
      Liste() = default;
      Liste(Liste && autre) noexcept
         : tete{ std::exchange(autre.tete, nullptr) },
           queue{ std::exchange(autre.queue, nullptr) },
           nelems{ std::exchange(autre.nelems, 0) } {
      }
      Liste& operator=(Liste && autre) noexcept {
         if (this == &autre) return *this;
         clear();
         tete = std::exchange(autre.tete, nullptr);
         queue = std::exchange(autre.queue, nullptr);
         nelems = std::exchange(autre.nelems, 0);
         return *this;
      }
      bool empty() const noexcept {
         return size() == 0;
      }
      size_type size() const noexcept {
         return nelems;
      }
      template <class It>
         void append(It debut, It fin) {
            if (debut == fin) return;
            push_back(*debut);
            auto p = queue;
            for (++debut; debut != fin; ++debut) {
               queue = new Noeud(*debut);
               p->succ = queue;
               p = queue;
               ++nelems;
            }
         }
      void push_back(const value_type &val) {
         auto p = queue;
         queue = new Noeud(val);
         if (!p)
            tete = queue;
         else
            p->succ = queue;
         ++nelems;
      }
      void clear() noexcept {
         while (!empty()) {
            auto p = tete->succ;
            delete tete;
            tete = p;
         }
         queue = nullptr;
         nelems = 0;
      }
      ~Liste() {
         clear();
      }
   private:
      template <class U, class N>
         class base_iterator {
         public:
            using iterator_category = std::forward_iterator_tag;
            using value_type = typename
               Liste<U>::value_type;
            using pointer = value_type*;
            using reference = value_type&;
            using difference_type = std::ptrdiff_t;
            using node_type = N;
         private:
            node_type *cur;
         public:
            base_iterator(node_type *p) : cur{ p } {
            }
            bool operator==(const base_iterator &it) const noexcept {
               return cur == it.cur;
            }
            bool operator!=(const base_iterator &it) const noexcept {
               return !(*this == it);
            }            
            base_iterator &operator++() {
               cur = cur->succ;
               return *this;
            }
            base_iterator operator++(int) {
               iterator temp {*this };
               operator++();
               return temp;
            }
            value_type &operator*() noexcept {
               return cur->val;
            }
            value_type operator*() const {
               return cur->val;
            }
            value_type* operator->() {
               return &(cur->val);
            }
            const value_type* operator->() const {
               return &(cur->val);
            }
         };
   public:
      using iterator = base_iterator<value_type, Noeud>;
      using const_iterator = base_iterator<const value_type, Noeud>;
      iterator begin() noexcept {
         return { tete };
      }
      const_iterator begin() const noexcept {
         return { tete };
      }
      const_iterator cbegin() const noexcept {
         return { tete };
      }
      iterator end() noexcept {
         return { nullptr };
      }
      const_iterator end() const noexcept {
         return { nullptr };
      }
      const_iterator cend() const noexcept {
         return { nullptr };
      }
      Liste(const Liste &lst) : Liste{} {
         append(lst.begin(), lst.end());
      }
      Liste(std::initializer_list<T> init) : Liste{} {
         append(init.begin(), init.end());
      }
      void swap(Liste &lst) noexcept {
         using std::swap;
         swap(tete, lst.tete);
         swap(queue, lst.queue);
         swap(nelems, lst.nelems);
      }
      Liste &operator=(const Liste& lst) {
         Liste{ lst }.swap(*this);
         return *this;
      }
      template <class U>
         Liste(const Liste<U> &lst) : Liste() {
            append(lst.begin(), lst.end());
         }
      template <class U>
         Liste &operator=(const Liste<U>& lst) {
            Liste{ lst }.swap(*this);
            return *this;
         }
      template<class It>
         Liste(It debut, It fin) : Liste() {
            append(debut, fin);
         }
      bool operator==(const Liste &lst) const {
         return size() == lst.size() && equal(begin(), end(), lst.begin());
      }
      template <class U>
         bool operator==(const Liste<U> &lst) const {
            return size() == lst.size() && equal(begin(), end(), lst.begin());
         }
      bool operator!=(const Liste &lst) const {
         return ! (*this == lst);
      }
      template <class U>
         bool operator!=(const Liste<U> &lst) const {
            return ! (*this == lst);
         }
      void push_back(const value_type &val) {
         auto p = new Noeud { val };
         if (empty())
            tete = queue = p;
         else {
            p->succ = tete;
            tete = p;
         }
         ++nelems;
      }
      void pop_front() {
         if (empty()) throw ListeVide{};
         auto p = tete;
         tete = tete-*gt;succ;
         delete p;
         --nelems;
         if (nelems == 0) queue = nullptr;
      }
      value_type& front() {
         if (empty()) throw ListeVide{};
         return tete->val;
      }
      value_type front() const {
         if (empty()) throw ListeVide{};
         return tete->val;
      }
      value_type& back() {
         if (empty()) throw ListeVide{};
         return queue->val;
      }
      value_type back() const {
         if (empty()) throw ListeVide{};
         return queue->val;
      }
      void inverser() {
         Liste lst;
         for (auto p = tete; p ; p = p->succ)
            lst.push_front(p->val);
         swap(lst);
      }
   };
#endif

//
// Programme de test
//
#include "Liste.h"
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <numeric>
using namespace std;

template <class T>
   void afficher(const Liste<T> &lst, ostream &os) {
      for (const auto & elem : lst)
         os << elem << ' ';
      os << endl;
   }

int main() {
   Liste<float> lstf { 2.0f, 3.0f, 5.0f, 7.0f, 11.0f };
   cout << "Somme des " << lstf.size() << " premiers nombres premiers: "
        << accumulate(begin(lstf), end(lstf), 0.0f) << endl;
   int tab[] = { 1, 2, 3, 4, 5 };
   for (auto i : tab)
      cout << i << ' ';
   cout << endl;
   Liste<int> lst0 (begin(tab), end(tab));
   for (auto i : lst0)
      cout << i << ' ';
   cout << endl;
   Liste<int> lst1 = lst0;
   for (auto i : lst1)
      cout << i << ' ';
   cout << endl;
   lst1.push_back(33);
   lst0 = lst1;
   for (auto i : lst0)
      cout << i << ' ';
   cout << endl;
   Liste<float> lst2 = lst0;
   for (auto & i : lst2)
      i -= 0.5f;
   for (auto i : lst2)
      cout << i << ' ';
   cout << endl;
   lst1 = lst2;
   for (auto i : lst1)
      cout << i << ' ';
   cout << endl;
   Liste<string> lst_str { "J'aime", "mon", "prof!" };
   for (const auto & s : lst_str)
      cout << s << ' ';
   cout << endl;
   auto lst_str_inv = lst_str;
   lst_str_inv.inverser();
   for (const auto & s : lst_str_inv)
      cout << s << ' ';
   cout << endl;
   for (const auto & s : lst_str)
      cout << s << ' ';
   cout << endl;
   afficher(lst_str, cout);
}
 
import java.util.Iterator;
class ListeVide extends Exception {
}
public final class Liste<T> implements Iterable<T> {
   private final class Noeud {
      public Noeud succ = null;
      private T valeur;
      public T getValeur() {
         return valeur;
      }
      public Noeud(T val) {
         valeur = val;
      }
      public Noeud(Noeud n) {
         valeur = n.getValeur(); // ICI: risqué (partage; espérons T immuable!)
      }
   }
   private Noeud tete = null;
   private Noeud fin = null;
   private int taille = 0;
   public boolean estVide() {
      return tete == null;
   }
   public int getTaille() {
      return taille;
   }
   public Liste() {
   }
   private Liste(Liste<T> lst) {
      for (Noeud p = lst.tete; p != null; p = p.succ) {
         ajouter(p.getValeur());
      }
   }
   public Liste<T> dupliquer() {
      return new Liste<T>(this);
   }
   public void ajouter(T val) {
      Noeud p = new Noeud(val);
      if (estVide()) {
         tete = fin = p;
      } else {
         fin.succ = p;
         fin = p;
      }
      ++taille;
   }
   public void inverser() {
      Noeud nouvelleTete = null,
            nouvelleFin = null;
      if (tete != null) {
         Noeud p = new Noeud(tete);
         p.succ = nouvelleTete;
         nouvelleFin = nouvelleTete = p;
         p = tete;
         tete  = tete.succ;
      }
      while (tete != null) {
         Noeud p = new Noeud(tete);
         p.succ = nouvelleTete;
         nouvelleTete = p;
         p = tete;
         tete = tete.succ;
      }
      tete = nouvelleTete;
      fin = nouvelleFin;
   }
   public T extraire() throws ListeVide {
      if (estVide()) {
         throw new ListeVide();
      }
      Noeud p = tete;
      tete = tete.succ;
      T val = p.getValeur();
      if (p == fin) {
         fin = null;
      }
      --taille;
      return val;
   }
   
   private class Itérateur implements Iterator<T> {
      private Noeud cur = null;
      private Liste<T> source;
      public Itérateur(Liste<T> source) {
         this.source = source;
      }
      public boolean hasNext() {
         return source != null && source.tete != null &&
                (cur == null || cur != null && cur.succ != null);
      }
      public T next() {
         if (cur == null) {
            cur = source.tete;
         } else {
            cur = cur.succ;
         }
         return cur.getValeur();
      }
      public void remove() {
         // j'ai choisi de ne pas l'implémenter
      }
   }
   public Iterator<T> iterator() {
      return new Itérateur(this);
   }  
   public static void main(String[] args) {
      //
      // Liste<Integer>
      //
      final int NB_ENTIERS = 10;
      Liste<Integer> lst = new Liste<Integer>();
      for (int i = 0; i < NB_ENTIERS; i++) {
         lst.ajouter(i + 1);
      }
      for (Integer i : lst) {
         System.out.print(i + " ");
      }
      System.out.println();
      Liste<Integer> lstInv = lst.dupliquer();
      lstInv.inverser();
      try {
         int nbÉléments = lstInv.getTaille();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lstInv.extraire() + " ");
         }
         System.out.println();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lst.extraire() + " ");
         }
         System.out.println();
      } catch (ListeVide lv) {
         System.err.println("Très, très suspect...");
      }
      //
      // Liste<String>
      //
      final String [] mots = {
         "J'aime", "mon", "prof!"
      };
      Liste<String> lstStr = new Liste<String>();
      for (int i = 0; i < mots.length; i++) {
         lstStr.ajouter(mots[i]);
      }
      for (String s : lstStr) {
         System.out.print(s + " ");
      }
      System.out.println();
      Liste<String> lstStrInv = lstStr.dupliquer();
      lstStrInv.inverser();
      try {
         int nbÉléments = lstStrInv.getTaille();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lstStrInv.extraire() + " ");
         }
         System.out.println();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lstStr.extraire() + " ");
         }
         System.out.println();
      } catch (ListeVide lv) {
         System.err.println("Très, très suspect...");
      }
   }
}
Exécution, implémentation C# Exécution, implémentation C++ Exécution, implémentation Java 
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10
J'aime mon prof!
prof! mon J'aime
J'aime mon prof!
 
Somme des 5 premiers nombres premiers: 28
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5 33
0.5 1.5 2.5 3.5 4.5 32.5
0 1 2 3 4 32
J'aime mon prof!
prof! mon J'aime
J'aime mon prof!
J'aime mon prof!
 
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10
J'aime mon prof!
prof! mon J'aime
J'aime mon prof!

Ne vous fiez pas au nombre de lignes dans chaque cas pour évaluer la complexité relative de chacune des implémentations (bien que celle en C++ soit plus complexe ici... parce qu'elle en fait beaucoup plus que les deux autres!). J'ai disposé le code dans le respect (à ma connaissance) des pratiques de chaque langage, et certains (C#, par exemple) tendent à générer du code plus « vertical » alors que d'autres (Java, par exemple) mènent à du code plus « horizontal », ne serait-ce que dû aux usages quant à la disposition des accolades.

Quelques notes d'ordre général :

Pour le reste, un sympathique constat nous attend : les similitudes sont de loin plus nombreuses que les différences!

Discussion de l'implémentation C#

Le détail de notre implémentation à l'aide du langage C# suit.

Avec C#, tout type d'exception doit dériver, directement ou non, de la classe Exception, et la plupart des exceptions des programmes que nous écrivons devraient dériver plus précisément de la classe ApplicationException. C'est ce que nous faisons ici.

 
using System;
namespace Liste
{
   class ListeVide : ApplicationException
   {
   }

La classe Liste<T> est terminale. Son interface ne se prête pas à spécialisation sans effets adverses. Pour qu'elle puisse exposer un énumérateur standard sur des T, il faut lui faire implémenter l'interface IEnumerable<T>.

 
   sealed class Liste<T> : IEnumerable<T>
   {

Une liste simplement chaînée se compose typiquement de noeuds, tels que chacun connaît son successeur. Ainsi, de manière minimaliste, connaître le premier noeud (la tête) de la liste donne un accès indirect à tous les autres.

Notre classe Noeud est interne à la classe Liste<T>, comme il se doit (le noeud est un détail d'implémentation et ne concerne pas le code client). Pour cette raison, les accès à la valeur (en lecture, du moins) et au successeur sont publics, n'étant en pratique accessibles qu'aux noeuds et à la liste.

La valeur d'un Noeud est immuable une fois le noeud construit.

Puisque nous sommes ici en C#, les propriétés sont de mise.

N'étant pas vouée à être spécialisée, cette classe est aussi terminale.

Remarquez que le constructeur paramétrique initialise le sucesseur d'un Noeud à null, et que le constructeur « de copie » ne copie pas le successeur; organiser les noeuds est le travail de la liste; les noeuds ont pour mandat d'entreposer les données, pas de s'organiser entre eux.

Une caractéristique de C# est qu'il ne permet la généricité sur sur les types « références ». En pratique, il est possible d'écrire une Liste<int>, mais le code généré utilisera alors de manière sous-jacente du Boxing, instanciant une classe correspondant à int pour chaque int utilisé. Conséquemment, un Noeud ne « possède » pas le T qui y est entreposé; ce T est partagé avec tous les autres objets qui tiennent une référence sur lui.

Ainsi, il est fortement recommandable de n'utiliser une classe telle que Liste<T> que pour des types T immuables (sauf si votre code est écrit pour tenir compte de cette réalité). Cet avertissement est doublement important si vous faites de la multiprogrammation.

 
      private sealed class Noeud
      {
         public Noeud Succ { get; set; } = null;
         public T Valeur
         {
            get; private set;
         }
         public Noeud(T val)
         {
            Valeur = val;
         }
         public Noeud(Noeud n)
         {
            Valeur = n.Valeur;
         }
      }

Les états de notre Liste<T> sont au nombre de trois, soit :

  • Tete, une référence sur le premier Noeud de la liste, pour usage interne seulement
  • Fin, une référence sur le dernier Noeud de la liste, aussi pour usage interne seulement – ceci permet certaines optimisations, en particulier lors des ajouts à la fin, mais n'est pas à strictement parler nécessaire pour définir une liste simplement chaînée), et
  • Taille, un compteur du nombre de noeuds dans la liste (ceci aussi permet d'optimiser le calcul du nombre d'éléments dans la liste, sans toutefois être nécessaire en tant que tel), accessible publiquement en consultation mais pour usage interne en ce qui a trait aux modifications

S'ajoute à ces propriétés la propriété en lecture seulement Vide, prédicat qui s'avère seulement si la liste est vide et dont l'implémentation est de complexité constante, donc .

 
      private Noeud Tete { get; set; } = null;
      private Noeud Fin { get; set; } = null;
      public bool Vide
      {
         get => Tete == null;
      }
      public int Taille { get; private set; } = 0;

Une Liste<T> par défaut sera une liste vide : sa téte et sa fin sont toutes deux des références nulles, et son nombre d'éléments est zéro.

 
      public Liste()
      {
      }

J'ai implémenté un « constructeur de copie » privé, donc un constructeur acceptant en paramètre lst, une référence sur une ListeEntiers, et faisant de la ListeEntiers en cours de construction une copie, noeud par noeud, de la liste lst.

L'optimisation permise par l'utilisation d'une référence sur le dernier noeud, qui donne à la méthode Ajouter() sa complexité constante, , fait de ce constructeur une opération raisonnable (complexité linéaire, ). Sans cette optimisation, la méthode Ajouter() serait de complexité linéaire (il faudrait parcourir la liste entière à chaque fois pour trouver le dernier élément avant de lui apposer un successeur), et ce constructeur serait alors de complexité quadratique, , ce qui la rendrait inutilisable en pratique.

Si la Liste<T> avait été vouée à une spécialisation polymorphique, ce constructeur aurait été protégé et la duplication d'une Liste<T> aurait été faite par clonage. Notez qu'il est difficile de déterminer ce que serait un bon clonage sans savoir quelles sont les caractéristiques de T dans un langage comme C#. J'ai choisi ici d'offrir le constructeur de copie privé et d'exposer un service public de duplication, la méthode Dupliquer(), parce que le recours au constructeur de copie ne fait pas partie des usages en C#.

 
      private Liste(Liste<T> lst)
      {
         for (Noeud p = lst.Tete; p != null; p = p.Succ)
            Ajouter(p.Valeur);
      }
      public Liste<T> Dupliquer() =>
         new Liste<T>(this);

La méthode Ajouter() permet de réaliser une insertion en fin de liste. Cette opération se réalise en temps constant dû à la connaissance a priori du dernier Noeud de la liste; si nous n'avions pas cette information, alors il faudrait de prime abord trouver le dernier noeud de la liste, une opération coûteuse.

Notez que l'on ajoute bel et bien un T à la liste, pas un Noeud. Les noeuds sont des outils organisationnels internes, pas un élément de l'interface d'une Liste<T>.

 
      public void Ajouter(T val)
      {
         Noeud p = new Noeud(val);
         if (Vide)
            Tete = Fin = p;
         else
         {
            Fin.Succ = p;
            Fin = p;
         }
         ++Taille;
      }

La méthode Inverser() est la plus complexe du lot en termes d'écriture (sa complexité algorithmique, elle, est linéaire, ). Il s'agit d'un mutateur : elle inverse l'ordre dans lequel les noeuds de la liste apparaissent, ce qui n'est pas nécessairement une pratique recommandable – il serait en général préférable de retourner une nouvelle liste dont les éléments seraient dans l'ordre inverse de ceux de la liste originale, et de laisser cette dernière inchangée.

Pour une liste de éléments, cette implémentation fait allocations dynamiques de mémoire pour des noeuds. Ici, la présence d'un ramasse-miettes permet de ne pas se préoccuper de la libération des noeuds « périmés », mais accroît la probabilité qu'une collecte d'ordures soit provoquée pendant l'exécution de la méthode, surtout si la liste comprend un nombre élevé de noeuds.

Il existe une solution pour cette méthode qui ne fait aucune allocation de mémoire. La voyez-vous? Serait-elle à privilégier en C#?

 
      public void Inverser()
      {
         Noeud nouvelleTete = null,
               nouvelleFin = null;
         if (Tete != null)
         {
            Noeud p = new Noeud(Tete);
            p.Succ = nouvelleTete;
            nouvelleFin = nouvelleTete = p;
            p = Tete;
            Tete  = Tete.Succ;
         }
         while (Tete != null)
         {
            Noeud p = new Noeud(Tete);
            p.Succ = nouvelleTete;
            nouvelleTete = p;
            p = Tete;
            Tete = Tete.Succ;
         }
         Tete = nouvelleTete;
         Fin = nouvelleFin;
      }

La méthode Extraire() élimine un Noeud de la liste et retourne la valeur que ce Noeud entreposait. C'est aussi une méthode de complexité constante, ou . Cette implémentation dépend d'un ramasse-miettes pour assurer le nettoyage des noeuds périmés.

 
      public T Extraire()
      {
         if (Vide)
            throw new ListeVide();
         Noeud p = Tete;
         Tete = Tete.Succ;
         T val = p.Valeur;
         if (p == Fin)
            Fin = null;
         --Taille;
         return val;
      }

Un énumérateur sur des T en C# est une classe qui implémente l'interface IEnumerator<T>. Ici, cette classe se nomme Énumérateur (en français) et est privée à Liste<T>, puisque ses instances ne seront manipulées qu'à travers l'interface IEnumerator<T>.

Pour des raisons historiques, les énumérateurs de C# traînent avec eux un bagage qui alourdit leur écriture : ils sont inspirés d'une technologie antérieure permettant de parcourir des séquences à distance, ce qui amène les services Dispose() et Reset() qui, sans être essentiels, peuvent permettre d'énumérer des éléments de la séquence parcourue de manière plus efficace dans ce cas, et ils ont d'abord été implémentés (en C# v.1,0) de manière non-générique... L'erreur tactique fut sans doute de dériver les interfaces IEnumerator<T> de l'ancienne interface IEnumerator (non-générique), encore aujourd'hui utilisée par foreach en C#, ce qui nous impose d'implémenter certains services « en double ».

Le contrat de l'interface IEnumerator<T> est :

  • D'exposer un propriété Current donnant accès à l'élément courant dans la séquence parcourue. Cette propriété doit être définie pour retourner un T (version générique) et un object (version non-générique et historique)
  • D'exposer une méthode Reset() pour redémarrer le parcours du début
  • D'exposer une méthode MoveNext() tentant d'avancer au prochain élément dans la séquence parcourue et retournant true seulement si cette tentative de progression fut un succès, et
  • D'exposer une méthode Dispose() qui permet de nettoyer les ressources associées à l'énumérateur. Ici, je l'ai laissée vide

Le reste de l'implémentation est directement reliée au conteneur à parcourir. Une séquence standard en C# débute juste avant le premier élément; l'implémentation de cette fonctionnalité nous appartient.

 
      private class Énumérateur : IEnumerator<T>
      {
         private Noeud Cur { get; set; } = null;
         private Liste<T> Source
         {
            get; set;
         }
         public Énumérateur(Liste<T> source)
         {
            Source = source;
         }
         public void Reset()
         {
            Cur = null;
         }
         public T Current
         {
            get => Cur.Valeur;
         }
         public bool MoveNext()
         {
            if (Source == null)
               Cur = null;
            else if (Cur == null)
               Cur = Source.Tete;
            else
               Cur = Cur.Succ;
            return Cur != null;
         }
         public void Dispose()
         {
         }
         object System.Collections.IEnumerator.Current
         {
            get => Cur.Valeur;
         }
      }

Puisque notre conteneur est un IEnumerable<T>, il doit implémenter le contrat décrit par cette interface, donc offrir la méthodeGetEnumerator() qui retournera un IEnumerator<T> permettant de le parcourir. Ce service doit être offert en deux « saveurs », soit celle susmentionnée qui retourne un IEnumerator<T> et une plus traditionnelle (mais utilisée par foreach) qui retourne un IEnumerator non-générique.

 
      public IEnumerator<T> GetEnumerator() =>
         new Énumérateur(this);
      System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() =>
         new Énumérateur(this);
   }

Le programme de test accomplit la tâche attendue, soit tester de manière directe ou indirecte la plupart des services de la classe Liste<T>. Pour les besoins de la démonstration, il utilise une Liste<int> et une Liste<string>, et réalise à la fois des copies et des mutations des conteneurs.

 
   class Program
   {
      static void Main(string[] args)
      {
         const int NB_ENTIERS = 10;
         Liste<int> lst = new Liste<int>();
         for (int i = 0; i < NB_ENTIERS; i++)
         {
            lst.Ajouter(i + 1);
         }
         foreach (int i in lst)
         {
            Console.Write($"{i} ");
         }
         Console.WriteLine();
         Liste<int> lstInv = lst.Dupliquer();
         lstInv.Inverser();
         {
            int nbÉléments = lstInv.Taille;
            for (int i = 0; i < nbÉléments; i++)
            {
               Console.Write($"{lstInv.Extraire()} ");
            }
            Console.WriteLine();
            for (int i = 0; i < nbÉléments; i++)
            {
               Console.Write($"{lst.Extraire()} ");
            }
            Console.WriteLine();
         }
         string [] mots =
         {
            "J'aime", "mon", "prof!"
         };
         Liste<string> lstStr = new Liste<string>();
         for (int i = 0; i < mots.Length; i++)
         {
            lstStr.Ajouter(mots[i]);
         }
         foreach (string s in lstStr)
         {
            Console.Write($"{s} ");
         }
         Console.WriteLine();
         Liste<string> lstStrInv = lstStr.Dupliquer();
         lstStrInv.Inverser();
         {
            int nbÉléments = lstStrInv.Taille;
            for (int i = 0; i < nbÉléments; i++)
            {
               Console.Write($"{lstStrInv.Extraire()} ");
            }
            Console.WriteLine();
            for (int i = 0; i < nbÉléments; i++)
            {
               Console.Write($"{lstStr.Extraire()} ");
            }
            Console.WriteLine();
         }
      }
   }
}

Discussion de l'implémentation C++

Le détail de notre implémentation à l'aide du langage C++ suit. Notez que dans le code ci-dessous, les clauses throw() devraient être remplacées par des clauses noexcept, mais le compilateur à ma disposition quand j'ai rédigé le tout n'était pas suffisamment à jour pour supporter ce mécanisme de C++ 11. J'indiquerai la complexité algorithmique des opération chaque fois que cela sera possible; j'exprimerai la complexité de T::T(const T&) par , tout comme j'exprimerai la complexité de T::T(const U&) par , dans les deux cas pour des raisons de lisibilité. Nous considérerons aussi les opération d'allocation dynamique de mémoire comme étant de complexité constante, , faute de pouvoir faire mieux – en pratique, le temps requis pour de telles opérations est indéterministe.

Pour les besoins de notre implémentation, nous aurons recours à quelques bibliothèques standards :

  • L'en-tête <cstdlib> déclare le type std::size_t, utilisé par la plupart des outils de C et C++ pour représenter des tailles. Nous utiliserons ce type pour représenter le nombre d'éléments d'une Liste<T>
  • L'en-tête <algorithm>, offrant une vaste gamme d'outils précieux
  • L'en-tête <initializer_list>, qui déclare le type std::initialiser_list permettant d'initialiser n'importe quel objet avec les valeurs placées entre accolades, et
  • L'en-tête <iterator>, qui nous aidera à définir notre propre type d'itérateur pour une Liste<T>

Avec C++, tout type peut servir pour signaler une exception. L'usage est de définir un type dont le nom représente le problème à souligner (ici ListeVide) pour éliminer les nombreux ennuis associés aux messages qu'ont les exceptions « traditionnelles » (internationalisation, langue).

 
#ifndef LISTE_H
#define LISTE_H
#include <cstdlib>
#include <algorithm>
#include <initializer_list>
#include <iterator>

class ListeVide {};

La classe Liste<T> est terminale. Son interface ne se prête pas à spécialisation sans effets adverses.

Elle expose les types pertinents à son utilisation dans son interface, sous la forme de types internes et publics, ce qui permet au code client de s'exprimer d'une manière telle qu'il pourra s'adapter sans réécriture aux changements d'implémentation.

 
template <class T>
   class Liste final {
   public:
      using value_type = T;
      using size_type = std::size_t;

Une liste simplement chaînée se compose typiquement de noeuds, tels que chacun connaît son successeur. Ainsi, de manière minimaliste, connaître le premier noeud (la tête) de la liste donne un accès indirect à tous les autres.

Notre classe Noeud est interne à la classe Liste<T>, comme il se doit (le noeud est un détail d'implémentation et ne concerne pas le code client). Pour cette raison, les accès à la valeur (en lecture, du moins) et au successeur sont publics, n'étant en pratique accessibles qu'aux noeuds et à la liste. Notez que le value_type de Noeud est celui défini plus haut dans Liste<T>, donc T, comme il se doit.

La valeur d'un Noeud devrait être immuable une fois le noeud construit; ici, ce sera assuré par discipline, mais il aurait été possible de faire de val un attribut privé auquel les accès passent par un accesseur pour garantir cela.

N'étant pas vouée à être spécialisée, cette classe est aussi terminale.

Remarquez que le constructeur paramétrique initialise le sucesseur d'un Noeud à nullptr, et que le constructeur de copie ne copie pas le successeur; organiser les noeuds est le travail de la liste; les noeuds ont pour mandat d'entreposer les données, pas de s'organiser entre eux. Complexité : 

   private:
      struct Noeud final {
         value_type val;
         Noeud *succ {};
         Noeud (const value_type &val) : val{ val } {
         }
         Noeud (const Noeud &n) : val{ n.val } {
         }
      };

Les attributs de notre Liste<T> sont au nombre de trois, soit :

  • tete, un pointeur sur le premier Noeud de la liste
  • fin, un pointeur sur le dernier Noeud de la liste – ceci permet certaines optimisations, en particulier lors des ajouts à la fin, mais n'est pas à strictement parler nécessaire pour définir une liste simplement chaînée), et
  • nelems, un compteur du nombre de noeuds dans la liste (ceci aussi permet d'optimiser le calcul du nombre d'éléments dans la liste, sans toutefois être nécessaire en tant que tel)

J'ai choisi ici de les initialiser par défaut au zéro de leur type.

 
      Noeud *tete {}, *queue {};
      size_type nelems {};

Une Liste<T> par défaut sera une liste vide : sa téte et sa fin sont toutes deux des pointeurs nuls, et son nombre d'éléments est zéro. Complexité : 

   public:
      Liste() = default;

Les consignes ne le demandaient pas, mais j'ai implémenté la sémantique de mouvement dans la classe Liste<T>. Après tout, ces méthodes sont simples à écrire, ne lèvent pas d'exceptions, et permettent de nombreuses optimisations. Ce serait fou de s'en passer!

Complexité : pour le constructeur, et pour l'affectation.

 
      Liste(Liste && autre) noexcept
         : tete{ std::exchange(autre.tete, nullptr) },
           queue{ std::exchange(autre.queue, nullptr) },
           nelems{ std::exchange(autre.nelems, 0) } {
      }
      Liste& operator=(Liste && autre) noexcept {
         if (this == &autre) return *this;
         clear();
         tete = std::exchange(autre.tete, nullptr);
         queue = std::exchange(autre.queue, nullptr);
         nelems = std::exchange(autre.nelems, 0);
         return *this;
      }

Deux services clés de la liste sont des accesseurs de premier ordre, soit empty(), prédicat qui s'avère seulement si la liste est vide, et size(), qui donne accès au nombre de noeuds dans la liste.

Complexité : dans chaque cas (la complexité de empty() ici dépend directement de la complexité de size()).

 
      bool empty() const noexcept {
         return size() == 0;
      }
      size_type size() const noexcept {
         return nelems;
      }

La méthode append() permet d'insérer une séquence de valeurs à la fin d'une Liste<T>. Je procède comme suit :

  • Si la séquence est vide, cette fonction est un no-op
  • En général, cette fonction insère un premier élément avec push_back(), qui tient compte de cas relativement rares comme celui de l'insertion d'une valeur dans une liste vide, puis procède à une série d'ajouts plus directs. En ce sens, append() sera en général plus rapide qu'une répétitive appelant plusieurs fois push_back()
  • Il se peut que la compilation signale des avertissements à l'utilisation de cette fonction, dans le cas où le type des les éléments « pointés » par un It provoque un avertissement lors d'une affectation à un value_type (je le signale d'office car le programme de test, plus bas, fait de telles opérations). C'est bien sûr un avertissement destiné au code client, pas un problème structurel pour ce qui a trait à Liste<T>

Complexité : , ce qui signifie si It est un itérateur de type Random Access (un pointeur, un itérateur sur un std::vector, sur une std::string, etc.) et pour une séquence de éléments si It est un itérateur de type Forward Iterator.

 
      template <class It>
         void append(It debut, It fin) {
            if (debut == fin) return;
            push_back(*debut);
            auto p = queue;
            for (++debut; debut != fin; ++debut) {
               queue = new Noeud(*debut);
               p->succ = queue;
               p = queue;
               ++nelems;
            }
         }

La méthode push_back() insère un nouvel élément en fin de liste. Notez que l'on ajoute bel et bien un value_type à la liste, pas un Noeud. Les noeuds sont des outils organisationnels internes, pas un élément de l'interface d'une Liste<T>.

Complexité : dû à la présence de l'attribut queue, qui permet de connaître a priori le point d'insertion dans un tel cas; si nous n'avions pas cette information, alors il faudrait de prime abord trouver le dernier noeud de la liste, une opération coûteuse.

 
      void push_back(const value_type &val) {
         auto p = queue;
         queue = new Noeud{ val };
         if (!p)
            tete = queue;
         else
            p->succ = queue;
         ++nelems;
      }

La méthode clear() vide la liste. Elle est plus rapide que ne le serait une série d'appels successifs à pop_front() du fait qu'elle réalise moins de validations et ne modifie nelems qu'une seule fois en fin de parcours.

Complexité : 

      void clear() noexcept {
         while (!empty()) {
            auto p = tete->succ;
            delete tete;
            tete = p;
         }
         queue = nullptr;
         nelems = 0;
      }

Le destructeur vide la liste, tout simplement.

Complexité : 

      ~Liste() {
         clear();
      }

Pour ce qui est des itérateurs, pour couvrir le cas const (parcourir les éléments sans pouvoir les modifier) et non-const, il serait possible d'écrire deux classes à part entière, mais cela mène à du code quelque peu redondant. J'ai plutôt choisi d'écrire une seule classe, interne et privée, nommée base_iterator<U,N> où U est le type des valeurs et N est le type de noeud à parcourir. Ainsi :

  • Le type interne value_type correspond à Liste<U>::value_type, mais j'aurai probablement pu le faire correspondre à U tout simplement
  • Le type interne node_type correspond au type de noeud à parcourir
  • Un itérateur connaît le noeud vers lequel il mène (nommé cur_) dès la construction, paramétrique et de complexité constante, donc
  • La comparaison de deux itérateurs avec les opérateurs == et != est de complexité constante, donc
  • Passer au noeud suivant avec l'opérateur ++ est une opération de complexité constante, donc , mais la constante cachée est plus élevée dans le cas de l'opérateur ++ suffixé, ce qui suggère qu'il soit préférable en général de privilégier la version préfixée lorsque le choix est possible
  • Déréférencer un itérateur à l'aide de l'opérateur * est une opération de complexité constante, donc , dans le cas non-const, mais de complexité dans le cas const du fait que cette méthode retourne un value_type par copie
  • Enfin, appeler une méthode de l'élément vers lequel mène l'itérateur à partir de l'opérateur -> est une opération de complexité constante, donc ... Dans la mesure où le concepteur de value_type n'a pas eu l'idée saugrenue de surcharger l'opérateur & (l'opérateur « adresse-de »), bien entendu

Notez les quelques alias de types définis au début de cette classe : value_type, iterator_category, pointer, reference et difference_type. Avant C++ 17, une classe nommée std::iterator était typiquement utilisée à titre de parent pour la plupart des types d'itérateurs, et définissait ces types de manière à alléger (légèrement) l'écriture. Cette classe est désormais considérée dépréciée, et il est maintenant préférable de définir ces types nous-mêmes.

 
   private:
      template <class U, class N>
         class base_iterator {
         public:
            using iterator_category = std::forward_iterator_tag;
            using value_type = typename
               Liste<U>::value_type;
            using pointer = value_type*;
            using reference = value_type&;
            using difference_type = std::ptrdiff_t;
            using node_type = N;
         private:
            node_type *cur;
         public:
            base_iterator(node_type *p) : cur{ p } {
            }
            bool operator==(const base_iterator &it) const noexcept {
               return cur == it.cur;
            }
            bool operator!=(const base_iterator &it) const noexcept {
               return !(*this == it);
            }            
            base_iterator &operator++() {
               cur = cur->succ;
               return *this;
            }
            base_iterator operator++(int) {
               iterator temp {*this };
               operator++();
               return temp;
            }
            value_type &operator*() noexcept {
               return cur->val;
            }
            value_type operator*() const {
               return cur->val;
            }
            value_type* operator->() {
               return &(cur->val);
            }
            const value_type* operator->() const {
               return &(cur->val);
            }
         };

Muni du type base_iterator<U,N>, la définition des types iterator et const_iterator devient toute simple : iterator est un base_iterator<value_type,Noeud> alors que const_iterator est un base_iterator<const value_type,Noeud>.

Le caractère const ou non du type pointé par l'itérateur assure la disponibilité des services appropriés et l'indisponibilité des autres services.

 
   public:
      using iterator = base_iterator<value_type, Noeud>;
      using const_iterator = base_iterator<const value_type, Noeud>;

Les itérateurs sur les extrémités de la liste sont exposés à traver les méthodes begin() et end(), en déclinaisons const et non-const, de même qu'à travers les méthodes cbegin() et cend() qui, elles, sont toujours const.

Complexité : dans chaque cas.

 
      iterator begin() noexcept {
         return { tete };
      }
      const_iterator begin() const noexcept {
         return { tete };
      }
      const_iterator cbegin() const noexcept {
         return { tete };
      }
      iterator end() noexcept {
         return { nullptr };
      }
      const_iterator end() const noexcept {
         return { nullptr };
      }
      const_iterator cend() const noexcept {
         return { nullptr };
      }

J'ai implémenté un constructeur de copie public, comme il se doit pour les classes concrètes en C++. Notez le recours à une délégation au constructeur par défaut, pour réduire la redondance d'écriture dans le code; cette manoeuvre sera répétée à plusieurs endroits.

Complexité : 

      Liste(const Liste &lst) : Liste{} {
         append(lst.begin(), lst.end());
      }

J'ai implémenté un constructeur acceptant une séquence d'initialisation en paramètre, donc une expression de la forme où chaque est du même type et peut être utilisé pour initialiser un value_type.

Complexité : 

      Liste(std::initializer_list<T> init) : Liste{} {
         append(init.begin(), init.end());
      }

La méthode swap(), qui facilite entre autres l'expression de l'opérateur d'affectation, s'implémente par des appels à std::swap() (ou à une implémentation plus spécialisée de cet algorithme, si tel est le cas) un attribut à la fois.

Complexité : 

      void swap(Liste &lst) noexcept {
         using std::swap;
         swap(tete, lst.tete);
         swap(queue, lst.queue);
         swap(nelems, lst.nelems);
      }

L'affectation repose sur l'idiome d'affectation sécuritaire, ce qui est sans doute le choix le plus sage ici.

Complexité : 

      Liste &operator=(const Liste& lst) {
         Liste{ lst }.swap(*this);
         return *this;
      }

Le constructeur de conversion permet des constructions covariantes pour une Liste<T>, donc la construction d'une Liste<int> à partir d'une Liste<short>, ou la construction d'une Liste<Parent*> à partir d'une Liste<Enfant*> si Enfant dérive publiquement de Parent.

Complexité : 

      template <class U>
         Liste(const Liste<U> &lst) : Liste() {
            append(lst.begin(), lst.end());
         }

L'affectation covariante est au constructeur de conversion ce que l'affectation usuelle est au constructeur de copie.

Complexité : 

      template <class U>
         Liste &operator=(const Liste<U>& lst) {
            Liste{ lst }.swap(*this);
            return *this;
         }

Le constructeur de séquence permet d'initialiser une Liste<T> avec n'importe quelle séquence standard, dans la mesure où les éléments de la séquence standard peuvent être utilisés pour construire des value_type.

Complexité : 

      template<class It>
         Liste(It debut, It fin) : Liste() {
            append(debut, fin);
         }

La comparaison de deux Liste<T> à l'aide de l'opérateur == aura pour résultat true seulement si les deux listes ont le même nombre d'éléments et si les éléments aux mêmes positions dans chacune des deux listes comparées sont eux aussi égaux au sens de l'opérateur ==. évidemment, ceci suppose que value_type a une valeur exacte; avec des nombres à virgule flottante, cet opérateur est d'une utilité limitée.

Complexité : où vaut size()

 
      bool operator==(const Liste &lst) const {
         return size() == lst.size() && equal(begin(), end(), lst.begin());
      }

La comparaison d'une Liste<T> à une Liste<U> à l'aide de l'opérateur == aura pour résultat true seulement si les deux listes ont le même nombre d'éléments et si les éléments aux mêmes positions dans chacune des deux listes comparées sont eux aussi égaux au sens de l'opérateur ==.

Complexité : où vaut size()

 
      template <class U>
         bool operator==(const Liste<U> &lst) const {
            return size() == lst.size() && equal(begin(), end(), lst.begin());
         }

La comparaison de deux Liste<T> à l'aide de l'opérateur != équivaut à la négation logique de leur comparaison à l'aide de l'opérateur ==.

Complexité : où vaut size()

 
      bool operator!=(const Liste &lst) const {
         return ! (*this == lst);
      }

La comparaison d'une Liste<T> à une Liste<U> à l'aide de l'opérateur != équivaut à la négation logique de leur comparaison à l'aide de l'opérateur ==.

Complexité : où vaut size()

 
      template <class U>
         bool operator!=(const Liste<U> &lst) const {
            return ! (*this == lst);
         }

L'ajout d'un élément en tête de liste se fait avec push_front().

Complexité : 

      void push_front(const T &val) {
         auto p = new Noeud { val };
         if (empty())
            tete = queue = p;
         else {
            p->succ = tete;
            tete = p;
         }
         ++nelems;
      }

La méthode pop_front() élimine un Noeud de la liste. Elle ne retourne rien, comme il se doit, car s'il s'avérait que la copie d'un value_type retourné lève une exception, alors il y aurait perte d'information. Pour cette raison, le code client accédera à la valeur en tête de liste par un autre service (la méthode back()).

Complexité : 

      void pop_front() {
         if (empty()) throw ListeVide{};
         auto p = tete;
         tete = tete-*gt;succ;
         delete p;
         --nelems;
         if (nelems == 0) queue = nullptr;
      }

La méthode front() et retourne la valeur entreposée dans le Noeud en tête de liste.

Complexité : pour la version non-const, pour la version const.

 
      value_type& front() {
         if (empty()) throw ListeVide{};
         return tete->val;
      }
      value_type front() const {
         if (empty()) throw ListeVide{};
         return tete->val;
      }

La méthode back() et retourne la valeur entreposée dans  le Noeud en fin de liste.

Complexité : pour la version non-const, pour la version const.

 

 
      value_type& back() {
         if (empty()) throw ListeVide{};
         return queue->val;
      }
      value_type back() const {
         if (empty()) throw ListeVide{};
         return queue->val;
      }

La méthode inverser() est la plus complexe du lot en termes d'écriture (sa complexité algorithmique, elle, est linéaire, ). Il s'agit d'un mutateur : elle inverse l'ordre dans lequel les noeuds de la liste apparaissent, ce qui n'est pas nécessairement une pratique recommandable – il serait en général préférable de retourner une nouvelle liste dont les éléments seraient dans l'ordre inverse de ceux de la liste originale, et de laisser cette dernière inchangée.

Pour une liste de éléments, cette implémentation fait allocations dynamiques de mémoire pour des noeuds. Chaque noeud est détruit une fois son utilité chose du passé, puisque C++ ne suppose pas un ramasse-miettes. Une alternative aurait été d'utiliser des pointeurs intelligents, mais dans ce cas la gestion à faire était suffisamment simple pour que je me limite à de vulgaires pointeurs bruts.

Complexité :

Il existe une solution pour cette méthode qui ne fait aucune allocation de mémoire. La voyez-vous? Serait-elle à privilégier en C++?

 
      void inverser() {
         Liste lst;
         for (auto p = tete; p ; p = p->succ)
            lst.push_front(p->val);
         swap(lst);
      }
   };
#endif

Le programme de test que j'ai utilisé est proposé à droite. On y trouve :

  • Une fonction afficher() qui a pour but de projeter une const Liste<T>& sur un flux en sortie. Son principal rôle à mes yeux, en fait, est de tester le type Liste<T>::const_iterator (car le compilateur tendra à sélectionner la version non-const pour ses opérations courantes)
  • Une Liste<float> nommée lstf, initialisée par une initializer_list<float> et sur laquelle est calculée une sommation
  • Une Liste<int> nommée lst0, sur laquelle est utilisé le constructeur de séquence
  • Une Liste<ìnt> nommée lst1, sur laquelle est testé le constructeur de copie
  • Un appel à push_back()
  • Un appel à l'opérateur d'affectation
  • Une Liste<float> nommée lst2, sur laquelle est appelé le constructeur de conversion
  • Un appel à l'opérateur d'affectation covariante
  • Une Liste<string> nommée lst_str construite à partir d'une initializer_list<const char*>
  • Un appel à inverser()
  • Quelques utilisations de boucles for sur des intervalles, certaines utilisant des itérateurs et d'autres utilisant des itérateurs const

Cette liste de tests n'est pas exhaustive, mais a pour but de donner quelque peu confiance en l'implémentation proposée.

 
// ...
#include "Liste.h"
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <numeric>
using namespace std;
template <class T>
   void afficher(const Liste<T> &lst, ostream &os) {
      for (const auto & elem : lst)
         os << elem << ' ';
      os << endl;
   }
int main() {
   Liste<float> lstf { 2.0f, 3.0f, 5.0f, 7.0f, 11.0f };
   cout << "Somme des " << lstf.size() << " premiers nombres premiers: "
        << accumulate(begin(lstf), end(lstf), 0.0f) << endl;
   int tab[] = { 1, 2, 3, 4, 5 };
   for (auto i : tab)
      cout << i << ' ';
   cout << endl;
   Liste<int> lst0 (begin(tab), end(tab));
   for (auto i : lst0)
      cout << i << ' ';
   cout << endl;
   Liste<int> lst1 = lst0;
   for (auto i : lst1)
      cout << i << ' ';
   cout << endl;
   lst1.push_back(33);
   lst0 = lst1;
   for (auto i : lst0)
      cout << i << ' ';
   cout << endl;
   Liste<float> lst2 = lst0;
   for (auto & i : lst2)
      i -= 0.5f;
   for (auto i : lst2)
      cout << i << ' ';
   cout << endl;
   lst1 = lst2;
   for (auto i : lst1)
      cout << i << ' ';
   cout << endl;
   Liste<string> lst_str { "J'aime", "mon", "prof!" };
   for (const auto & s : lst_str)
      cout << s << ' ';
   cout << endl;
   auto lst_str_inv = lst_str;
   lst_str_inv.inverser();
   for (const auto & s : lst_str_inv)
      cout << s << ' ';
   cout << endl;
   for (const auto & s : lst_str)
      cout << s << ' ';
   cout << endl;
   afficher(lst_str, cout);
}

Discussion de l'implémentation Java

Le détail de notre implémentation à l'aide du langage Java suit.

Avec Java, tout type d'exception doit dériver, directement ou non, de la classe Exception. C'est ce que nous faisons ici.

 
import java.util.Iterator;
class ListeVide extends Exception {
}

La classe Liste<T> est terminale. Son interface ne se prête pas à spécialisation sans effets adverses. Pour qu'elle puisse exposer un énumérateur standard sur des T, il faut lui faire implémenter l'interface Iterable<T>.

 
public final class Liste<T> implements Iterable<T> {

Une liste simplement chaînée se compose typiquement de noeuds, tels que chacun connaît son successeur. Ainsi, de manière minimaliste, connaître le premier noeud (la tête) de la liste donne un accès indirect à tous les autres.

Notre classe Noeud est interne à la classe ListeEntiers, comme il se doit (le noeud est un détail d'implémentation et ne concerne pas le code client). Pour cette raison, les accès à la valeur (en lecture, du moins) et au successeur sont publics, n'étant en pratique accessibles qu'aux noeuds et à la liste.

La valeur d'un Noeud est immuable une fois le noeud construit.

Notez que dû au rôle circonscrit de cette classe et au fait qu'elle ne peut être utilisée qu'à l'interne par ListeEntiers, j'ai laissé l'attribut succ public (et oui, dans ce cas, c'est légitime).

Remarquez que le constructeur paramétrique initialise le sucesseur d'un Noeud à null, et que le constructeur « de copie » ne copie pas le successeur; organiser les noeuds est le travail de la liste; les noeuds ont pour mandat d'entreposer les données, pas de s'organiser entre eux.

Une caractéristique de Java est qu'il ne permet la généricité sur sur les types « références ». Conséquemment, un Noeud ne « possède » pas le T qui y est entreposé; ce T est partagé avec tous les autres objets qui tiennent une référence sur lui.

Ainsi, il est fortement recommandable de n'utiliser une classe telle que Liste<T> que pour des types T immuables (sauf si votre code est écrit pour tenir compte de cette réalité). Cet avertissement est doublement important si vous faites de la multiprogrammation.

 
   private final class Noeud {
      public Noeud succ = null;
      private T valeur;
      public T getValeur() {
         return valeur;
      }
      public Noeud(T val) {
         valeur = val;
      }
      public Noeud(Noeud n) {
         valeur = n.getValeur();
      }
   }

Les attributs de notre Liste<T> sont au nombre de trois, soit :

  • tete, une référence sur le premier Noeud de la liste
  • fin, une référence sur le dernier Noeud de la liste – ceci permet certaines optimisations, en particulier lors des ajouts à la fin, mais n'est pas à strictement parler nécessaire pour définir une liste simplement chaînée), et
  • taille, un compteur du nombre de noeuds dans la liste (ceci aussi permet d'optimiser le calcul du nombre d'éléments dans la liste, sans toutefois être nécessaire en tant que tel)

Deux services clés de la liste sont des accesseurs de premier ordre, soit estVide(), prédicat qui s'avère seulement si la liste est vide, et getTaille(), qui donne accès au nombre de noeuds dans la liste. Ces deux fonctions sont de complexité constante, donc .

 
   private Noeud tete = null;
   private Noeud fin = null;
   private int taille = 0;
   public boolean estVide() {
      return tete == null;
   }
   public int getTaille() {
      return taille;
   }

Une Liste<T> par défaut sera une liste vide : sa téte et sa fin sont toutes deux des références nulles, et son nombre d'éléments est zéro.

 
   public Liste() {
   }

J'ai implémenté un « constructeur de copie » privé, donc un constructeur acceptant en paramètre lst, une référence sur une Liste<T>, et faisant de la Liste<T> en cours de construction une copie, noeud par noeud, de la liste lst.

L'optimisation permise par l'utilisation d'une référence sur le dernier noeud, qui donne à la méthode ajouter() sa complexité constante, , fait de ce constructeur une opération raisonnable (complexité linéaire, ). Sans cette optimisation, la méthode ajouter() serait de complexité linéaire (il faudrait parcourir la liste entière à chaque fois pour trouver le dernier élément avant de lui apposer un successeur), et ce constructeur serait alors de complexité quadratique, , ce qui la rendrait inutilisable en pratique.

Si la Liste<T> avait été vouée à une spécialisation polymorphique, ce constructeur aurait été protégé et la duplication d'une Liste<T> aurait été faite par clonage. Notez qu'il est difficile de déterminer ce que serait un bon clonage sans savoir quelles sont les caractéristiques de T dans un langage comme Java. J'ai choisi ici d'offrir le constructeur de copie privé et d'exposer un service public de duplication, la méthode dupliquer(), parce que le recours au constructeur de copie ne fait pas partie des usages en Java.

 
   private Liste(Liste<T> lst) {
      for (Noeud p = lst.tete; p != null; p = p.succ) {
         ajouter(p.getValeur());
      }
   }
   public Liste<T> dupliquer() {
      return new Liste<T>(this);
   }

La méthode ajouter() permet de réaliser une insertion en fin de liste. Cette opération se réalise en temps constant dû à la connaissance a priori du dernier Noeud de la liste; si nous n'avions pas cette information, alors il faudrait de prime abord trouver le dernier noeud de la liste, une opération coûteuse.

Notez que l'on ajoute bel et bien un T à la liste, pas un Noeud. Les noeuds sont des outils organisationnels internes, pas un élément de l'interface d'une Liste<T>.

 
   public void ajouter(T val) {
      Noeud p = new Noeud(val);
      if (estVide()) {
         tete = fin = p;
      } else {
         fin.succ = p;
         fin = p;
      }
      ++taille;
   }

La méthode inverser() est la plus complexe du lot en termes d'écriture (sa complexité algorithmique, elle, est linéaire, ). Il s'agit d'un mutateur : elle inverse l'ordre dans lequel les noeuds de la liste apparaissent, ce qui n'est pas nécessairement une pratique recommandable – il serait en général préférable de retourner une nouvelle liste dont les éléments seraient dans l'ordre inverse de ceux de la liste originale, et de laisser cette dernière inchangée.

Pour une liste de éléments, cette implémentation fait allocations dynamiques de mémoire pour des noeuds. Ici, la présence d'un ramasse-miettes permet de ne pas se préoccuper de la libération des noeuds « périmés », mais accroît la probabilité qu'une collecte d'ordures soit provoquée pendant l'exécution de la méthode, surtout si la liste comprend un nombre élevé de noeuds.

Il existe une solution pour cette méthode qui ne fait aucune allocation de mémoire. La voyez-vous? Serait-elle à privilégier en Java?

 
   public void inverser() {
      Noeud nouvelleTete = null,
            nouvelleFin = null;
      if (tete != null) {
         Noeud p = new Noeud(tete);
         p.succ = nouvelleTete;
         nouvelleFin = nouvelleTete = p;
         p = tete;
         tete  = tete.succ;
      }
      while (tete != null) {
         Noeud p = new Noeud(tete);
         p.succ = nouvelleTete;
         nouvelleTete = p;
         p = tete;
         tete = tete.succ;
      }
      tete = nouvelleTete;
      fin = nouvelleFin;
   }

La méthode extraire() élimine un Noeud de la liste et retourne la valeur que ce Noeud entreposait. C'est aussi une méthode de complexité constante, ou . Cette implémentation dépend d'un ramasse-miettes pour assurer le nettoyage des noeuds périmés.

La clause throws ListeVide est obligatoire en Java si extraire() est susceptible de lever ListeVide.

 
   public T extraire() throws ListeVide {
      if (estVide()) {
         throw new ListeVide();
      }
      Noeud p = tete;
      tete = tete.succ;
      T val = p.getValeur();
      if (p == fin) {
         fin = null;
      }
      --taille;
      return val;
   }

Un itérateur sur des T en Java est une classe qui implémente l'interface Iterator<T>. Ici, cette classe se nomme Itérateur (en français) et est privée à Liste<T>, puisque ses instances ne seront manipulées qu'à travers l'interface Iterator<T>.

Le contrat de l'interface Iterator<T> est :

  • D'exposer un prédicat hasNext(), qui ne s'avèrera que s'il est encore possible d'avancer d'au moins un élément dans la séquence parcourue
  • D'exposer une méthode next() avançant au prochain élément dans la séquence parcourue et retournant une référence sur l'objet qui s'y trouve, et
  • D'exposer une méthode remove() qui a pour but de supprimer l'élément sur lequel se trouve l'itérateur et d'avancer au prochain élément s'il y a lieu. Pour les besoins de la cause, j'ai offert une implémentation vide pour cette méthode

Le reste de l'implémentation est directement reliée au conteneur à parcourir. Une séquence standard en Java débute juste avant le premier élément; l'implémentation de cette fonctionnalité nous appartient.

 
   private class Itérateur implements Iterator<T> {
      private Noeud cur = null;
      private Liste<T> source;
      public Itérateur(Liste<T> source) {
         this.source = source;
      }
      public boolean hasNext() {
         return source != null && source.tete != null &&
                (cur == null || cur != null && cur.succ != null);
      }
      public T next() {
         if (cur == null) {
            cur = source.tete;
         } else {
            cur = cur.succ;
         }
         return cur.getValeur();
      }
      public void remove() {
      }
   }

Puisque notre conteneur est un Iterable<T>, il doit implémenter le contrat décrit par cette interface, donc offrir la méthode iterator() qui retournera un Iterator<T> permettant de le parcourir.

 
   public Iterator<T> iterator() {
      return new Itérateur(this);
   }

Le programme de test accomplit la tâche attendue, soit tester de manière directe ou indirecte la plupart des services de la classe Liste<T>. Pour les besoins de la démonstration, il utilise une Liste<Integer> et une Liste<string>, et réalise à la fois des copies et des mutations des conteneurs. Remarquez que le code Java doit insérer une forme de gestion d'exception lors d'appels à extraire(), même s'il est évident à l'oeil nu qu'aucune exception ne sera levée ici.

 
   public static void main(String[] args) {
      final int NB_ENTIERS = 10;
      Liste<Integer> lst = new Liste<Integer>();
      for (int i = 0; i < NB_ENTIERS; i++) {
         lst.ajouter(i + 1);
      }
      for (Integer i : lst) {
         System.out.print(i + " ");
      }
      System.out.println();
      Liste<Integer> lstInv = lst.dupliquer();
      lstInv.inverser();
      try {
         int nbÉléments = lstInv.getTaille();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lstInv.extraire() + " ");
         }
         System.out.println();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lst.extraire() + " ");
         }
         System.out.println();
      } catch (ListeVide lv) {
         System.err.println("Très, très suspect...");
      }
      final String [] mots = {
         "J'aime", "mon", "prof!"
      };
      Liste<String> lstStr = new Liste<String>();
      for (int i = 0; i < mots.length; i++) {
         lstStr.ajouter(mots[i]);
      }
      for (String s : lstStr) {
         System.out.print(s + " ");
      }
      System.out.println();
      Liste<String> lstStrInv = lstStr.dupliquer();
      lstStrInv.inverser();
      try {
         int nbÉléments = lstStrInv.getTaille();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lstStrInv.extraire() + " ");
         }
         System.out.println();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lstStr.extraire() + " ");
         }
         System.out.println();
      } catch (ListeVide lv) {
         System.err.println("Très, très suspect...");
      }
   }
}

Conclusion

Vous remarquerez que les ressemblances sont beaucoup plus nombreuses que les divergencesn en particulier dans les versions Java et C# car ces langages se ressemblent philosophiquement (avec C++, qui se conforme à la STL, on trouve des concepts et des formalismes plus sophistiqués).

Personnellement, j'ai écrit l'une des versions, et la traduction dans les autres langages s'est faite en quelques minutes chaque fois. Les plus importantes différences ont trait à la sémantique d'accès (directe ou indirecte) et à ses conséquences : en C++, écrire la Sainte-Trinité; en Java et en C#, compenser le partage implicite par une duplication manuelle. Les métaphores des itérateurs et des énumérateurs sont teintés de la culture de chacun des langages.

Valid XHTML 1.0 Transitional

CSS Valide !