Présentation de std::list

Dans la bibliothèque standard C++ (STL), std::list est un conteneur de séquence implémenté sous la forme d'une liste doublement chaînée. Contrairement aux tableaux dynamiques comme std::vector, les éléments d'une liste ne sont pas stockés de manière contiguë en mémoire. Chaque élément, ou nœud, contient la donnée elle-même ainsi que deux pointeurs : l'un vers l'élément précédent et l'autre vers l'élément suivant.

Les caractéristiques principales sont les suiventes :

• Insertion et suppression : Elles s'effectuent en temps constant O(1) à n'importe quel endroit du conteneur une fois que l'on possède un itérateur sur la position.
• Accès aux données : L'accès direct par index (opérateur []) n'est pas supporté. Pour atteindre le n-ième élément, il faut parcourir la liste depuis le début ou la fin, ce qui prend un temps linéaire O(n).
• Stabilité des itérateurs : Les opérations d'ajout ou de retrait n'invalident pas les itérateurs pointant vers d'autres éléments, contrairement au vecteur où un redimensionnement déplace tout le contenu.

Comparaison technique : list vs vector

Le choix entre std::list et std::vector dépend des besoins algorithmiques :

• Complexité temporelle : Le vecteur excelle dans l'accès aléatoire O(1), mais l'insertion au milieu est coûteuse O(n). La liste est idéale pour les manipulations fréquentes de structure en O(1).
• Gestion de la mémoire : La liste consomme plus de mémoire par élément à cause des pointeurs de chaînage. Le vecteur est plus compact et favorise la localité du cache processeur.
• Invalidation : Dans une liste, seul l'itérateur pointant vers l'élément supprimé devient invalide. Dans un vecteur, une insertion peut invalider tous les itérateurs si la capacité est dépassée.

Fonctionnalités spécifiques de la classe list

Certaines méthodes sont propres à std::list car elles exploitent sa nature chaînée pour manipuler les nœuds sans copier les données.

1. La méthode splice

Cette fonction permet de transférer des éléments d'une liste à une autre sans réallocation mémoire. Les nœuds sont simplement "recâblés".

#include <iostream>
#include <list>

int main() {
    std::list<int> base = {1, 2, 3};
    std::list<int> source = {10, 20};

    auto it = base.begin();
    ++it; // Pointe sur le 2

    // Transférer tout le contenu de 'source' avant le '2'
    base.splice(it, source); 

    for (int n : base) std::cout << n << " "; // Sortie : 1 10 20 2 3
    return 0;
}

2. Tri et Fusion (sort et merge)

Comme std::list ne fournit pas d'itérateurs à accès aléatoire, l'algorithme générique std::sort ne peut pas être utilisé. La classe possède donc sa propre méthode sort().

#include <iostream>
#include <list>

int main() {
    std::list<double> L1 = {3.5, 1.2, 8.9};
    std::list<double> L2 = {2.1, 4.4};

    L1.sort();
    L2.sort();

    // Fusionne L2 dans L1 en conservant l'ordre
    L1.merge(L2);

    for (double d : L1) std::cout << d << " "; // Sortie : 1.2 2.1 3.5 4.4 8.9
    return 0;
}

3. Suppression d'éléments (unique et remove)

• remove(val) : Supprime toutes les occurrences d'une valeur spécifique.
• unique() : Supprime les doublons consécutifs.

Implémentation interne simplifiée

Pour comprendre le fonctionnement de std::list, il est crucial de voir comment l'itérateur est construit. Puisque les nœuds sont dispersés en mémoire, l'itérateur doit surcharger l'opérateur ++ pour passer au pointeur suivant.

namespace CustomSTL {
    template<typename T>
    struct Node {
        T data;
        Node* prev;
        Node* next;

        Node(const T& val = T()) : data(val), prev(nullptr), next(nullptr) {}
    };

    template<typename T>
    struct ListIterator {
        Node<T>* current;

        ListIterator(Node<T>* p) : current(p) {}

        // Déplacement vers le nœud suivant
        ListIterator& operator++() {
            current = current->next;
            return *this;
        }

        // Accès à la donnée
        T& operator*() { return current->data; }

        bool operator!=(const ListIterator& other) { return current != other.current; }
    };

    template<typename T>
    class MyList {
        Node<T>* head;
    public:
        MyList() {
            head = new Node<T>();
            head->next = head;
            head->prev = head;
        }

        void push_back(const T& val) {
            Node<T>* newNode = new Node<T>(val);
            Node<T>* tail = head->prev;

            tail->next = newNode;
            newNode->prev = tail;
            newNode->next = head;
            head->prev = newNode;
        }

        ListIterator<T> begin() { return ListIterator<T>(head->next); }
        ListIterator<T> end() { return ListIterator<T>(head); }
    };
}

Analyse de la gestion des itérateurs

L'implémentation de l'itérateur montre qu'il s'agit d'une encapsulation d'un pointeur vers un nœud. Lors d'une opération comme it++, l'itérateur ne fait pas une simple incrémentation d'adresse (comme pour un tableau), mais suit le lien next. C'est pourquoi la liste est moins performante lors du parcours séquentiel massif, car chaque saut peut provoquer un défaut de cache (cache miss).