Introduction à std::list

std::list est un conteneur séquentiel de la bibliothèque standard C++ qui implémente une liste doublement chaînée. Elle permet des insertions et suppressions en temps constant à n'importe quelle position, grâce à sa structure de données où chaque nœud pointe vers le précédent et le suivant.

Contrairement à std::vector, std::list ne supporte pas l'accès aléatoire, mais excelle dans les opérations d'insertion et de suppression, surtout au milieu de la séquence. Elle est similaire à std::forward_list, mais offre une itération bidirectionnelle.

Utilisation de base de std::list

Définition d'une liste

void ExempleListe1() {
    std::list<int> liste1;
    std::list<int> liste2(4, 100);
    std::list<int> liste3(liste2.begin(), liste2.end());
    std::list<int> liste4(liste3);

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

    std::list<int> liste6{ 1, 2, 3, 4, 5 };

    for (auto it = liste5.begin(); it != liste5.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}</int></int></int></int></int></int>

Insertion et suppression d'éléments

Les opérations push_front, pop_front, push_back, et pop_back gèrent respectivement l'ajout et la suppression en tête et en queue de liste.

void AfficherListe(const std::list<int>& liste) {
    for (const auto& elem : liste) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

void ExempleListe2() {
    int donnees[] = { 1, 2, 3 };
    std::list<int> maListe(donnees, donnees + 3);

    maListe.push_front(0);
    AfficherListe(maListe);

    maListe.pop_front();
    AfficherListe(maListe);
}</int></int>

Les fonctions insert et erase permettent des modifications plus granulaires à des positions spécifiques.

void ExempleListe3() {
    std::list<int> maListe = { 1, 2, 3 };
    auto position = std::next(maListe.begin());

    maListe.insert(position, 4);
    maListe.insert(position, 5, 5);
    std::vector<int> source = { 7, 8, 9 };
    maListe.insert(position, source.begin(), source.end());

    maListe.erase(position);
    maListe.erase(maListe.begin(), maListe.end());
}</int></int>

Itérateurs

Les itérateurs begin, end, rbegin, et rend permettent de parcourir la liste dans les deux sens.

void ExempleIterateurs() {
    std::list<int> maListe = { 1, 2, 3, 4, 5 };
    for (auto it = maListe.begin(); it != maListe.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    for (auto rit = maListe.rbegin(); rit != maListe.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;
}</int>

En cas de suppression d'un élément, seul l'itérateur pointant vers ce nœud devient invalide ; les autres restent valides.

Accès aux éléments et gestion de la taille

Les fonctions front et back accèdent au premier et dernier élément. size retourne le nombre d'élémants, resize modifie la taille, et empty vérifie si la liste est vide.

void ExempleAcces() {
    std::list<int> maListe;
    for (int i = 0; i < 5; ++i) maListe.push_back(i);
    std::cout << maListe.front() << " " << maListe.back() << std::endl;
    std::cout << "Taille: " << maListe.size() << std::endl;
    maListe.resize(7, 6);
    maListe.clear();
}</int>

Opérations avancées

Triage et fusion

La méthode sort trie la liste. Pour des performances optimales, il est recommandé d'utiliser sort de la bibliothèque standard sur un vecteur intermédiaire si la liste est volumineuse.

void ComparerTri() {
    srand(time(nullptr));
    const int N = 100000;
    std::vector<int> vec;
    std::list<int> lst;

    for (int i = 0; i < N; ++i) {
        int val = rand();
        vec.push_back(val);
        lst.push_back(val);
    }

    auto debut = clock();
    lst.sort();
    auto fin = clock();
    std::cout << "Temps de tri de la liste: " << fin - debut << std::endl;
}</int></int>

La fonction splice transfère des éléments d'une liste à une autre sans copie. La fonction unique supprime les doublons consécutifs après tri.

void ExempleFusion() {
    std::list<int> listeA = { 3, 1, 8 };
    std::list<int> listeB = { 6, 2, 9, 5 };
    listeA.sort();
    listeB.sort();
    listeA.merge(listeB);
    // listeA contient maintenant les éléments triés des deux listes.
}</int></int>

Cmoparaison avec std::vector