La STL (Standard Template Library) est un ensemble de structures de données et d'algorithmes génériques développé à l'origine par les laboratoires Hewlett-Packard. Elle se compose de six composants principaux :

• Conteneurs : structures destinées à stocker des données. On distingue les conteneurs séquentiels (vector, deque, list) où l'ordre des éléments dépend de la séquence d'insertion, et les conteneurs associatifs (set, map) organisés sous forme d'arbres binaires avec une clé d'indexation.
• Algorithmes : fonctions de manipulation de données, divisées en algorithmes modificateurs (copie, suppression, remplacement) et non-moidficateurs (recherche, parcours, extrêmes).
• Itérateurs : ponts entre conteneurs et algorithmes. Ils existent en plusiuers catégories : entrée (lecture seule), sortie (écriture seule), avant (lecture/écriture + avancement), bidirectionnel (avance + recul), et à accès aléatoire (le plus puissant).
• Foncteurs : objets-fonctions fournissant des stratégies aux algorithmes.
• Adaptateurs : offrent des interfaces supplémentaires aux algorithmes.
• Allocateurs : gèrent l'allocation mémoire pour les conteneurs et algorithmes.

La classe string

Le type string encapsule une chaîne de caractères dynamique.

Construction

void demoConstruction()
{
    std::string chaineVide;
    std::cout << "Vide : [" << chaineVide << "]" << std::endl;

    std::string message("Bonjour");
    std::cout << "Message : " << message << std::endl;

    std::string copie = message;
    std::cout << "Copie : " << copie << std::endl;

    std::string repetee(4, 'z');
    std::cout << "Répétée : " << repetee << std::endl;
}

Affectation et assignation

void demoAffectation()
{
    std::string texte;
    texte = "Dupont";
    std::cout << texte << std::endl;

    std::string autre;
    autre = texte;
    std::cout << autre << std::endl;

    std::string init;
    init.assign("programmation", 7); // 7 premiers caractères
    std::cout << init << std::endl;

    std::string extrait;
    extrait.assign(std::string("abcdef"), 2, 3); // à partir de l'index 2, 3 caractères
    std::cout << extrait << std::endl;
}

Taille et accès aux caractères

void demoAcces()
{
    std::string mot = "salut";
    std::cout << "Taille : " << mot.size() << ", Longueur : " << mot.length() << std::endl;

    // [] ne lève pas d'exception si hors limites
    std::cout << mot[2] << std::endl;

    // at() lève out_of_range en cas de dépassement
    std::cout << mot.at(1) << std::endl;
}

Concaténation

void demoConcatenation()
{
    std::string phrase = "Hello";
    phrase += " World";
    phrase += '!';
    std::cout << phrase << std::endl;

    std::string suite;
    suite.append("C++");
    suite.append(" est puissant", 3); // " es"
    suite.append(std::string("langage"), 0, 2); // "la"
    std::cout << suite << std::endl;
}

Recherche et remplacement

void demoRecherche()
{
    std::string contenu = "abc123abc456";
    int premier = contenu.find('a');
    std::cout << "Premier 'a' : " << premier << std::endl;

    int dernier = contenu.rfind("abc");
    std::cout << "Dernier 'abc' : " << dernier << std::endl;

    // Retourne npos (équivalent à -1) si introuvable
    int introuvable = contenu.find("xyz");
    std::cout << "Introuvable : " << (introuvable == std::string::npos) << std::endl;

    contenu.replace(0, 3, "XYZ");
    std::cout << contenu << std::endl;
}

Comparaison, extraction, insertion et suppression

void demoManipulations()
{
    std::string a = "pomme";
    std::string b = "poire";
    // compare : > retourne 1, < retourne -1, == retourne 0
    std::cout << a.compare(b) << std::endl;

    std::string fichier = "document.txt";
    std::string ext = fichier.substr(8, 3);
    std::cout << "Extension : " << ext << std::endl;

    std::string base = "12";
    base.insert(1, "abcd");
    std::cout << base << std::endl;
    base.erase(1, 4);
    std::cout << base << std::endl;
}

Conversion avec char*

void demoConversion()
{
    std::string chaine = "test";
    const char* ptr = chaine.c_str();

    char* brut = (char*)"donnee";
    std::string depuisChar(brut);
}

Le conteneur vector

Le vector est un tableau dynamique unidirectionnel à mémoire contiguë. Il propose un itérateur à accès aléatoire et double sa capacité lors d'un redimensionnement. Sa structure sous-jacente est un tableau.

Construction et parcours

void demoVectorConstruct()
{
    std::vector<int> nombres;
    nombres.push_back(10);
    nombres.push_back(50);
    nombres.push_back(30);

    // Parcours avec itérateur
    for (auto curseur = nombres.begin(); curseur != nombres.end(); ++curseur)
    {
        std::cout << *curseur << std::endl;
    }

    // Construction par intervalle [début, fin)
    std::vector<int> sousEnsemble(nombres.begin(), nombres.begin() + 2);

    // Construction avec valeur répétée
    std::vector<int> rempli(8, 42);
}

Affectation, insertion et suppression

void demoVectorOps()
{
    std::vector<int> source = {2, 4, 6, 8, 10};

    std::vector<int> dest;
    dest.assign(source.begin(), source.begin() + 3);
    dest = source; // opérateur =

    std::vector<int> echange = {1, 3, 5};
    dest.swap(echange);

    // Insertion
    dest.insert(dest.begin(), 2, 0);

    // Suppression
    dest.pop_back();
    dest.erase(dest.begin() + 1, dest.begin() + 3);
    dest.erase(dest.begin());
    dest.clear();
}

Accès et gestion de la taille

void demoVectorTaille()
{
    std::vector<int> donnees = {7, 14, 21, 28, 35};

    std::cout << "at(2) : " << donnees.at(2) << std::endl; // lance out_of_range si hors limites
    std::cout << "[1] : " << donnees[1] << std::endl;   // comportement indéfini si hors limites
    std::cout << "Premier : " << donnees.front() << std::endl;
    std::cout << "Dernier : " << donnees.back() << std::endl;

    std::cout << "Taille : " << donnees.size() << std::endl;
    std::cout << "Capacité : " << donnees.capacity() << std::endl;

    donnees.reserve(20); // pré-alloue de l'espace
    std::cout << "Capacité après reserve : " << donnees.capacity() << std::endl;

    // Technique pour réduire la capacité : swap avec un vecteur temporaire
    std::vector<int>(donnees).swap(donnees);
    std::cout << "Capacité après shrink : " << donnees.capacity() << std::endl;
}

Types personnalisés et imbrication

class Utilisateur
{
public:
    std::string nom;
    Utilisateur(const std::string& n) : nom(n) {}
};

void demoVectorPersonnalise()
{
    std::vector<Utilisateur> liste;
    liste.emplace_back("Alice");
    liste.emplace_back("Bob");
    liste.emplace_back("Charlie");

    for (const auto& u : liste)
    {
        std::cout << u.nom << std::endl;
    }
}

void demoVectorImbrique()
{
    std::vector<std::vector<int>> grille;
    grille.push_back({1, 2, 3});
    grille.push_back({10, 20, 30});
    grille.push_back({100, 200, 300});

    for (const auto& ligne : grille)
    {
        for (int val : ligne)
        {
            std::cout << val << " ";
        }
        std::cout << std::endl;
    }
}

Le contaneur deque

Le deque (double-ended queue) est un espace linéaire bidirectionnel permettant des insertions et suppressions en O(1) aux deux extrémités. Contrairement au vector, il n'a pas de notion de capacité car il est composé de segments de mémoire continue reliés entre eux.

void demoDeque()
{
    std::deque<int> fileDouble;

    fileDouble.push_back(5);
    fileDouble.push_front(1);
    fileDouble.push_back(10);
    fileDouble.push_front(0);

    // Contenu : 0, 1, 5, 10
    std::cout << "Tête : " << fileDouble.front() << std::endl;
    std::cout << "Queue : " << fileDouble.back() << std::endl;

    fileDouble.pop_front();
    fileDouble.pop_back();

    // Accès indexé
    std::cout << fileDouble[0] << std::endl;
    std::cout << fileDouble.at(0) << std::endl;

    // Insertion et suppression
    fileDouble.insert(fileDouble.begin(), 2, 42);
    fileDouble.erase(fileDouble.begin());
    fileDouble.clear();
}

Le conteneur stack

La pile (stack) fonctionne selon le principe LIFO (dernier entré, premier sorti). Elle ne possède pas d'itérateur et n'expose qu'une seule ouverture.

#include <stack>

void demoStack()
{
    std::stack<int> pile;
    pile.push(100);
    pile.push(200);
    pile.push(300);

    while (!pile.empty())
    {
        std::cout << pile.top() << std::endl;
        pile.pop();
    }
    // Affiche : 300, 200, 100
}

Le conteneur queue

La file (queue) fonctionne selon le principe FIFO (premier entré, premier sorti). L'entrée se fait à l'arrière et la sortie à l'avant. Elle ne possède pas non plus d'itérateur.

#include <queue>

void demoQueue()
{
    std::queue<int> file;
    file.push(1);
    file.push(2);
    file.push(3);
    file.push(4);

    while (!file.empty())
    {
        std::cout << file.front() << std::endl;
        file.pop();
    }
    // Affiche : 1, 2, 3, 4
}

Le conteneur list

La list est une liste doublement chaînée à stockage discontinu. Elle fournit un itérateur bidirectionnel (incrément et décrément, mais pas d'addition/soustraction directe). Les éléments peuvent être dupliqués.

#include <list>

void demoList()
{
    std::list<int> liste;
    liste.push_back(30);
    liste.push_back(10);
    liste.push_back(50);
    liste.push_back(20);

    liste.push_front(5);
    liste.pop_back();
    liste.pop_front();

    // Tri et inversion
    liste.sort();
    liste.reverse();

    for (int val : liste)
    {
        std::cout << val << std::endl;
    }

    // Suppression par valeur
    liste.remove(30);
}

Les conteneurs set et multiset

Le set stocke des éléments uniques triés automatiquement par valeur clé. La clé et la valeur sont identiques. L'itérateur est en lecture seule : il est impossible de modifier une clé après insertion. La structure sous-jacente est un arbre rouge-noir.

Le multiset est identique au set, mais autorise les doublons.

#include <set>

void demoSet()
{
    std::set<int> ensemble;
    ensemble.insert(5);
    ensemble.insert(2);
    ensemble.insert(8);
    ensemble.insert(2); // ignoré, doublon

    for (auto val : ensemble)
    {
        std::cout << val << std::endl;
    }
    // Affiche : 2, 5, 8

    // Recherche
    auto trouve = ensemble.find(5);
    if (trouve != ensemble.end())
        std::cout << "Trouvé : " << *trouve << std::endl;

    std::cout << "Compte de 2 : " << ensemble.count(2) << std::endl;

    // Bornes inférieure et supérieure
    auto bas = ensemble.lower_bound(5);
    auto haut = ensemble.upper_bound(5);
    std::cout << "Lower : " << *bas << ", Upper : " << *haut << std::endl;

    auto plage = ensemble.equal_range(5);
    std::cout << "Plage first : " << *plage.first << ", second : " << *plage.second << std::endl;
}

// Tri personnalisé (ordre décroissant)
struct ComparateurDecroissant
{
    bool operator()(int a, int b) const
    {
        return a > b;
    }
};

void demoSetPersonnalise()
{
    std::set<int, ComparateurDecroissant> ensembleTrie;
    ensembleTrie.insert(10);
    ensembleTrie.insert(30);
    ensembleTrie.insert(20);

    for (auto val : ensembleTrie)
    {
        std::cout << val << std::endl;
    }
    // Affiche : 30, 20, 10
}

Les conteneurs map et multimap

Le map stocke des paires clé-valeur (appelées pairs). Chaque paire est accessible via les membres first (clé) et second (valeur). Les clés sont uniques et triées automatiquement. La structure sous-jacente est un arbre rouge-noir.

Le multimap autorise plusieurs valeurs pour une même clé.

#include <map>

void demoMap()
{
    std::map<std::string, int> ages;

    // Insertion
    ages.insert(std::make_pair("Alice", 25));
    ages["Bob"] = 30;
    ages["Charlie"] = 28;

    // Parcours (trié par clé)
    for (const auto& paire : ages)
    {
        std::cout << paire.first << " : " << paire.second << std::endl;
    }

    // Recherche
    auto it = ages.find("Bob");
    if (it != ages.end())
        std::cout << "Age de Bob : " << it->second << std::endl;

    // Suppression par clé
    ages.erase("Alice");

    std::cout << "Taille : " << ages.size() << std::endl;
    std::cout << "Vide : " << ages.empty() << std::endl;
}

Synthèse des cas d'usage

• vector : tableau dynamique, idéal pour l'enregistrement d'historiques d'actions où l'on consulte fréquemment mais où la suppression est rare. Itérateur à accès aléatoire.
• deque : tableau double extrémité, adapté aux files d'attente (ex : système de tickets) nécessitant retrait en tête et ajout en queue rapides.
• stack : pile LIFO sans itérateur, pour des mécanismes de retour-arrière ou d'annulation.
• queue : file FIFO sans itérateur, pour un traitement séquentiel strict.
• list : liste chaînée, recommandée quand les insertions et suppressions sont fréquentes à des positions aléatoires (ex : passagers dans un bus). Itérateur bidirectionnel.
• set/multiset : ensemble trié à clés uniques (ou non), pour des classements automatiques comme des scores de jeu. Itérateur en lecture seule.
• map/multimap : association clé-valeur triée, parfait pour indexer des utilisateurs par identifiant et effectuer des recherches rapides. Itérateur en lecture seule.