Structures séquentielles avec std::list et std::deque en C++

En C++, std::list et std::deque sont des structures de données séquentielles qui constituent des alternatives à std::vector lorsque différents comportements de performance sont nécessaires. std::list implémente une liste doublement chaînée, tandis que std::deque (double-ended queue) permet des insertions et suppressions rapides aux deux extrémités. Cet article explique quand utiliser l’une ou l’autre, avec des exemples pratiques.

1) Qu’est-ce que std::list ?

std::list est une liste doublement chaînée :

• Chaque élément est stocké dans un nœud séparé.
• Chaque nœud contient un pointeur vers l’élément précédent et suivant.
• L’insertion/suppression au milieu est en O(1).
• Pas d’accès aléatoire (v[i] impossible) → accès uniquement par itération.

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

int main() {
    list<int> lst = {10, 20, 30};

    lst.push_front(5);   // ajouter au début
    lst.push_back(40);   // ajouter à la fin

    auto it = lst.begin();
    advance(it, 2);      // avancer de 2 positions
    lst.insert(it, 25);  // insertion au milieu

    for (int x : lst) cout << x << " ";
}

Cas d'utilisation : lorsque de nombreuses insertions/suppressions au milieu sont nécessaires.

2) Performances de std::list

• Insertion/suppression au milieu : O(1)
• Insertion/suppression au début/à la fin : O(1)
• Tri (list.sort()) : O(n log n) mais très économique en déplacement de données.
• Pas d’accès par indice.
• Consommation mémoire plus élevée (pointeurs supplémentaires).

// tri d’une liste
list<int> lst = {5, 2, 9, 1};
lst.sort();

3) Qu’est-ce que std::deque ?

std::deque est une structure double-ended queue (file à deux extrémités) permettant des opérations rapides aussi bien au début qu’à la fin.

• Insertion/suppression au début : O(1)
• Insertion/suppression à la fin : O(1)
• Accès aléatoire : O(1)
• Insertion/suppression au milieu : O(n)
• Mémoire segmentée, moins contiguë que vector.

#include <deque>
#include <iostream>
using namespace std;

int main() {
    deque<int> dq = {10, 20, 30};

    dq.push_front(5);
    dq.push_back(40);

    dq.pop_front();
    dq.pop_back();

    cout << dq[0] << endl;  // accès indexé possible
}

Cas d'utilisation : lorsque des opérations rapides en tête et en fin de structure sont nécessaires.

4) Performances de std::deque

• Insertion/suppression au début : O(1)
• Insertion/suppression à la fin : O(1)
• Insertion/suppression au milieu : O(n)
• Accès aléatoire : O(1)
• Mémoire segmentée, moins optimisée pour le cache qu’un vector.

5) Comparaison : list vs deque

6) Exemples pratiques : files de tâches et gestion d’entités

a) File de tâches avec deque

#include <deque>
#include <iostream>
using namespace std;

int main() {
    deque<string> tasks;

    tasks.push_back("Download");
    tasks.push_back("Parse");
    tasks.push_front("Init"); // tâche prioritaire

    while (!tasks.empty()) {
        cout << "Tâche: " << tasks.front() << endl;
        tasks.pop_front();
    }
}

b) Gestion d’entités dans un moteur de jeu avec list

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

struct Entity {
    string name;
    Entity(string n) : name(n) {}
};

int main() {
    list<Entity> entities;

    entities.emplace_back("Player");
    entities.emplace_back("Enemy");
    entities.emplace_back("Tree");

    for (auto it = entities.begin(); it != entities.end(); ) {
        if (it->name == "Enemy")
            it = entities.erase(it);  // O(1)
        else
            ++it;
    }

    for (auto& e : entities)
        cout << e.name << endl;
}

7) Quel conteneur choisir ?

• list → si de nombreuses insertions/suppressions au milieu.
• deque → si des opérations rapides en tête et en fin sont essentielles.
• vector → si l’accès aléatoire et l’efficacité cache sont importants.

Règle générale : Essayez d’abord vector. S’il ne répond pas aux besoins, utilisez deque ou list.

8) TL;DR

Articles connexes