Introduction à la classe list

La classe list en C++ est un conteneur séquentiel qui permet l'insertion et la suppression d'éléments en temps constant à n'importe quelle position. Elle supporte l'itération bidirectionnelle. Sa structure sous-jacente est une liste doublement chaînée, où chaque élément est stocké dans un nœud indépendant avec des pointeurs vers les nœuds précédent et suivant.

Contrairement à forward_list, qui est une liste simplement chaînée avec une itération uniquement vers l'avant, list offre une plus grande flexibilité. Par rapport à d'autres conteneurs comme vector ou deque, elle excelle dans les opérations d'insertion et de suppression à des positions arbitraires. Cependant, elle ne supporte pas l'accès aléatoire, nécessitant une itération linéaire pour atteindre un élément spécifique, et elle consomme plus de mémoire pour stocker les pointeurs.

Utilisation de la classe list

Construction de la liste

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
using namespace std;
#include <list>
#include <vector>

void TestListe1()
{
    list<int> liste1;                         // Liste vide
    list<int> liste2(4, 100);                 // 4 éléments valant 100
    list<int> liste3(liste2.begin(), liste2.end());  // Construction par intervalle
    list<int> liste4(liste3);                    // Construction par copie

    int tableau[] = { 16,2,77,29 };
    list<int> liste5(tableau, tableau + sizeof(tableau) / sizeof(int));

    list<int> liste6{ 1,2,3,4,5 };  // Initialisation par liste en C++11

    // Parcours avec itérateur
    list<int>::iterator it = liste5.begin();
    while (it != liste5.end())
    {
        cout << *it << " ";
        ++it;
    }       
    cout << endl;

    // Parcours avec boucle for de portée
    for (auto& elem : liste5)
        cout << elem << " ";
    cout << endl;
}</int></int></int></int></int></int></int></vector></list></iostream>

Utilisation des itérateurs

Les itérateurs sont analouges à des pointeurs, permettent de naviguer dans la liste. L'itérateur begin() pointe vers le premier élément, et end() vers la position après le dernier. Les itérateurs inverses, comme rbegin() et rend(), permettent un parcours à l'envers.

void AfficherListe(const list<int>& lst)
{
    for (list<int>::const_iterator it = lst.begin(); it != lst.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
}

void TestListe2()
{
    int tableau[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> lst(tableau, tableau + sizeof(tableau) / sizeof(tableau[0]));

    // Parcours avant
    auto it = lst.begin();
    while (it != lst.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // Parcours arrière avec itérateur inverse
    auto rit = lst.rbegin();
    while (rit != lst.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
}</int></int></int>

Modificateurs et opérations courantes

void TestListe3()
{
    int tableau[] = { 1, 2, 3 };
    list<int> lst(tableau, tableau + sizeof(tableau) / sizeof(tableau[0]));

    lst.push_back(4);   // Ajouter à la fin
    lst.push_front(0);  // Ajouter au début
    AfficherListe(lst);

    lst.pop_back();     // Supprimer le dernier
    lst.pop_front();    // Supprimer le premier
    AfficherListe(lst);
}

void TestListe4()
{
    int tableau[] = { 1, 2, 3 };
    list<int> lst(tableau, tableau + sizeof(tableau) / sizeof(tableau[0]));

    auto pos = ++lst.begin();  // Itérateur vers le deuxième élément
    cout << *pos << endl;

    lst.insert(pos, 4);  // Insérer avant pos
    AfficherListe(lst);

    lst.insert(pos, 5, 5);  // Insérer 5 fois la valeur 5
    AfficherListe(lst);

    vector<int> vec{ 7, 8, 9 };
    lst.insert(pos, vec.begin(), vec.end());  // Insérer à partir d'un vecteur
    AfficherListe(lst);

    lst.erase(pos);  // Supprimer à la position pos
    AfficherListe(lst);

    lst.erase(lst.begin(), lst.end());  // Supprimer tous les éléments
    AfficherListe(lst);
}

void TestListe5()
{
    int tableau[] = { 1, 2, 3 };
    list<int> lst1(tableau, tableau + sizeof(tableau) / sizeof(tableau[0]));
    AfficherListe(lst1);

    list<int> lst2;
    lst1.swap(lst2);  // Échanger les contenus
    AfficherListe(lst1);
    AfficherListe(lst2);

    lst2.clear();  // Vider la liste
    cout << lst2.size() << endl;
}</int></int></int></int></int>

Invalidation des itérateurs

Dans une liste, l'insertion n'invalide pas les itérateurs. La suppression n'invalide que l'itérateur pointant vers l'élément supprimé, les autres restent valides.

void TestIterateur1()
{
    int tableau[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> lst(tableau, tableau + sizeof(tableau) / sizeof(tableau[0]));
    auto it = lst.begin();
    while (it != lst.end())
    {
        lst.erase(it);  // Erreur : it est invalidé après suppression
        ++it;
    }
}

// Version corrigée
void TestIterateur2()
{
    int tableau[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> lst(tableau, tableau + sizeof(tableau) / sizeof(tableau[0]));
    auto it = lst.begin();
    while (it != lst.end())
    {
        lst.erase(it++);  // Supprimer et avancer l'itérateur
    }
}</int></int>

Implémentation simulée de la classe list

Structure de base et implémentation

#pragma once
#include <assert.h>
#include <iostream>

namespace impl
{
    template<class t="">
    struct Noeud
    {
        Noeud(const T& val = T())
            : _prec(nullptr), _suiv(nullptr), _val(val) {}

        Noeud<t>* _prec;
        Noeud<t>* _suiv;
        T _val;
    };

    template<class class="" ptr="" ref="" t="">
    struct IterateurListe
    {
        typedef Noeud<t>* PNoeud;
        typedef IterateurListe<t ptr="" ref=""> Soi;
        IterateurListe(PNoeud noeud = nullptr) : _noeud(noeud) {}

        T& operator*() { return _noeud->_val; }
        T* operator->() { return &(_noeud->_val); }

        Soi& operator++() { _noeud = _noeud->_suiv; return *this; }
        Soi operator++(int) { Soi tmp(*this); _noeud = _noeud->_suiv; return tmp; }
        Soi& operator--() { _noeud = _noeud->_prec; return *this; }
        Soi operator--(int) { Soi tmp(*this); _noeud = _noeud->_prec; return tmp; }

        bool operator==(const Soi& autre) const { return _noeud == autre._noeud; }
        bool operator!=(const Soi& autre) const { return _noeud != autre._noeud; }

        PNoeud _noeud;
    };

    template<class t="">
    class Liste
    {
        typedef Noeud<t> NoeudType;
        typedef NoeudType* PNoeud;
    public:
        typedef IterateurListe<t t=""> iterateur;
        typedef IterateurListe<t const="" t=""> const_iterateur;

    public:
        Liste() { initialiser_vide(); }

        Liste(int n, const T& val = T())
        {
            initialiser_vide();
            for (int i = 0; i < n; ++i) ajouter_fin(val);
        }

        template<class it="">
        Liste(It debut, It fin)
        {
            initialiser_vide();
            while (debut != fin) { ajouter_fin(*debut); ++debut; }
        }

        Liste(const Liste<t>& autre)
        {
            initialiser_vide();
            const_iterateur it = autre.debut();
            while (it != autre.fin()) { ajouter_fin(*it); ++it; }
        }

        ~Liste() { nettoyer(); delete _tete; _tete = nullptr; }

        void nettoyer()
        {
            iterateur it = debut();
            while (it != fin()) it = supprimer(it);
            _tete->_suiv = _tete;
            _tete->_prec = _tete;
        }

        Liste<t>& operator=(const Liste<t>& autre)
        {
            Liste<t> tmp(autre);
            echanger(tmp);
            return *this;
        }

        size_t taille() const { return _taille; }
        bool vide() const { return _taille == 0; }

        T& premier() { return _tete->_suiv->_val; }
        T& dernier() { return _tete->_prec->_val; }

        void ajouter_fin(const T& val) { inserer(fin(), val); }
        void ajouter_debut(const T& val) { inserer(debut(), val); }

        void supprimer_fin() { supprimer(--fin()); }
        void supprimer_debut() { supprimer(debut()); }

        iterateur inserer(iterateur pos, const T& val)
        {
            PNoeud nouveau = new NoeudType(val);
            PNoeud courant = pos._noeud;
            PNoeud prec = courant->_prec;

            prec->_suiv = nouveau;
            nouveau->_prec = prec;
            nouveau->_suiv = courant;
            courant->_prec = nouveau;

            ++_taille;
            return iterateur(nouveau);
        }

        iterateur supprimer(iterateur pos)
        {
            PNoeud aSupprimer = pos._noeud;
            PNoeud suivant = aSupprimer->_suiv;
            PNoeud prec = aSupprimer->_prec;

            prec->_suiv = suivant;
            suivant->_prec = prec;

            delete aSupprimer;
            --_taille;
            return iterateur(suivant);
        }

        iterateur debut() { return _tete->_suiv; }
        iterateur fin() { return _tete; }
        const_iterateur debut() const { return _tete->_suiv; }
        const_iterateur fin() const { return _tete; }

        void echanger(Liste<t>& autre)
        {
            std::swap(_tete, autre._tete);
            std::swap(_taille, autre._taille);
        }

    private:
        void initialiser_vide()
        {
            _tete = new NoeudType;
            _tete->_prec = _tete;
            _tete->_suiv = _tete;
            _taille = 0;
        }

        PNoeud _tete;
        size_t _taille;
    };
}</t></t></t></t></t></class></t></t></t></class></t></t></class></t></t></class></iostream></assert.h>

Implémentation des itérateurs inverses

template<class iter="">
class IterateurInverse
{
public:
    typedef typename Iter::Ref Ref;
    typedef typename Iter::Ptr Ptr;
    typedef IterateurInverse<iter> Soi;

    IterateurInverse(Iter it) : _it(it) {}

    Ref operator*() { Iter tmp(_it); --tmp; return *tmp; }
    Ptr operator->() { return &(operator*()); }

    Soi& operator++() { --_it; return *this; }
    Soi operator++(int) { Soi tmp(*this); --_it; return tmp; }
    Soi& operator--() { ++_it; return *this; }
    Soi operator--(int) { Soi tmp(*this); ++_it; return tmp; }

    bool operator!=(const Soi& autre) const { return _it != autre._it; }
    bool operator==(const Soi& autre) const { return _it == autre._it; }

    Iter _it;
};</iter></class>

Comparaison entre list et vector

vector et list sont des conteneurs séquenteils essentiels en STL. vector offre un accès aléatoire rapide et une bonne localité spatiale, idéal pour les opérations de lecture. En revanche, list excelle dans les insertions et suppressions fréquentes à des positions arbitraires, mais avec un surcoût mémoire et un accès séquentiel plus lent. Le choix dépend des besoins spécifiques de l'application.