Module 08 : Conteneurs, itérateurs et algorithmes STL

Télécharger le PDF officiel du sujet

Prérequis

Complétez d’abord les Modules 00-07. Les conteneurs STL sont construits avec les templates du Module 07.

Concepts clés :

• Conteneurs (vector, list, map, stack, etc.)
• Itérateurs
• Algorithmes
• Objets fonctionnels (foncteurs)

---

Pourquoi c’est important

La STL fournit des structures de données éprouvées pour que vous n’ayez pas à les implémenter vous-même. Choisir le bon conteneur pour votre problème est crucial pour les performances.

Analogie du monde réel

Les conteneurs STL sont comme différentes solutions de rangement. Un vector est comme une rangée de casiers — accès rapide à n’importe quel casier par numéro. Une list est comme une chaîne de trombones — facile d’insérer ou de retirer au milieu. Une map est comme un annuaire téléphonique — trouve les entrées par nom rapidement.

Analogie du monde réel

Les itérateurs sont comme des marque-pages. Ils pointent vers une position spécifique dans un conteneur et peuvent avancer (et parfois reculer). Tout comme vous pouvez utiliser un marque-page dans n’importe quel livre, les itérateurs fournissent une manière uniforme de parcourir n’importe quel conteneur.

---

Comprendre la syntaxe des itérateurs STL

Ce module introduit les conteneurs et itérateurs STL. Voici la syntaxe expliquée :

La syntaxe ::iterator

std::vector<int>::iterator it = vec.begin();
std::map<string, int>::iterator it = map.begin();

• ::iterator est un type imbriqué défini à l’intérieur des classes de conteneurs
• Il représente une “position” dans le conteneur (comme un index, mais plus général)
• Différents conteneurs ont différents types d’itérateurs
• vector<int>::iterator est différent de list<int>::iterator

L’opérateur -> avec les itérateurs

it->first;   // Accède à la clé dans un itérateur de map
it->second;  // Accède à la valeur dans un itérateur de map

• -> avec les itérateurs déréférence l’itérateur ET accède à un membre
• Pour les itérateurs de map, it->first obtient la clé, it->second obtient la valeur
• Équivalent à (*it).first mais plus concis
• Utilisez -> quand l’itérateur contient des objets avec des membres

L’opérateur * avec les itérateurs

*it;  // Déréférence pour obtenir la valeur

• * avec les itérateurs obtient l’élément réel à cette position
• Pour les vectors, *it donne la valeur de l’élément
• Pour les lists, *it donne la valeur de l’élément
• Pour les maps, *it donne un objet pair (utilisez ->first et ->second à la place)

Les opérateurs ++ et -- avec les itérateurs

++it;   // Passe à l'élément suivant
--it;   // Passe à l'élément précédent

• ++ avance l’itérateur à la position suivante
• -- déplace l’itérateur à la position précédente
• Pour les itérateurs bidirectionnels (list, map, set), les deux fonctionnent
• Pour les itérateurs forward-only, seul ++ fonctionne
• La pré-incrémentation (++it) est préférée à la post-incrémentation (it++) pour l’efficacité

Les méthodes begin() et end()

it = vec.begin();  // Itérateur vers le premier élément
it != vec.end();   // Condition de boucle - end est "après le dernier"

• begin() retourne un itérateur vers le premier élément
• end() retourne un itérateur vers “après le dernier” élément (pas un élément valide !)
• end() agit comme une sentinelle - vous utilisez != end() pour vérifier si vous avez terminé
• L’intervalle [begin, end) est “semi-ouvert” - inclut le premier, exclut le dernier

Le mot-clé typename avec les types de conteneurs

typename T::iterator easyfind(T& container, int value);

• typename indique au compilateur que T::iterator est un type, pas un membre statique
• Requis lors de l’écriture de templates qui fonctionnent avec des conteneurs
• Sans typename, le compilateur ne sait pas si iterator est un type imbriqué ou un membre

L’accès container_type::

typename std::stack<T>::container_type::iterator iterator;

• container_type est un typedef à l’intérieur de std::stack qui révèle le conteneur sous-jacent
• Les chaînes :: accèdent aux types imbriqués : stack<T> -> container_type (qui est deque<T>) -> iterator
• Utilisé lors de l’héritage de conteneurs STL pour exposer leurs types internes

---

1. Vue d’ensemble de la STL

Trois composants

1. Conteneurs : Stockent des collections d’objets
2. Itérateurs : Accèdent aux éléments dans les conteneurs
3. Algorithmes : Effectuent des opérations sur les conteneurs

#include <vector>      // conteneur vector
#include <algorithm>   // algorithmes
#include <iterator>    // utilitaires d'itérateurs

---

2. Conteneurs séquentiels

vector - Tableau dynamique

#include <vector>

std::vector<int> v;

// Ajouter des éléments
v.push_back(10);
v.push_back(20);
v.push_back(30);

// Accéder aux éléments
v[0];           // 10 (pas de vérification des limites)
v.at(0);        // 10 (avec vérification des limites)
v.front();      // 10 (premier élément)
v.back();       // 30 (dernier élément)

// Taille
v.size();       // 3
v.empty();      // false
v.capacity();   // Défini par l'implémentation

// Supprimer
v.pop_back();   // Supprime le dernier
v.clear();      // Supprime tout

// Itérer
for (size_t i = 0; i < v.size(); i++)
    std::cout << v[i] << std::endl;

list - Liste doublement chaînée

#include <list>

std::list<int> lst;

lst.push_back(10);
lst.push_front(5);   // Peut ajouter au début efficacement

lst.front();         // 5
lst.back();          // 10

// Pas d'accès aléatoire !
// lst[0];           // ERREUR - list ne supporte pas []

// Itérer
std::list<int>::iterator it;
for (it = lst.begin(); it != lst.end(); ++it)
    std::cout << *it << std::endl;

deque - File à double extrémité

#include <deque>

std::deque<int> dq;

dq.push_back(10);
dq.push_front(5);    // Insertion efficace au début
dq[0];               // Accès aléatoire supporté

---

3. Conteneurs associatifs

map - Paires clé-valeur (triées)

#include <map>

std::map<std::string, int> ages;

// Insérer
ages["Alice"] = 25;
ages["Bob"] = 30;
ages.insert(std::make_pair("Charlie", 35));

// Accéder
ages["Alice"];       // 25
ages.at("Alice");    // 25 (lance une exception si non trouvé)

// Vérifier l'existence
if (ages.find("David") != ages.end())
    std::cout << "Trouvé" << std::endl;

// Compter (0 ou 1 pour map)
ages.count("Alice"); // 1

// Itérer (trié par clé !)
std::map<std::string, int>::iterator it;
for (it = ages.begin(); it != ages.end(); ++it)
    std::cout << it->first << ": " << it->second << std::endl;

set - Valeurs uniques triées

#include <set>

std::set<int> s;

s.insert(10);
s.insert(5);
s.insert(10);  // Ignoré - existe déjà

s.size();      // 2
s.count(10);   // 1
s.find(5);     // Itérateur vers l'élément

---

4. Adaptateurs de conteneurs

stack - LIFO

#include <stack>

std::stack<int> st;

st.push(10);
st.push(20);

st.top();     // 20 (consulter)
st.pop();     // Supprime le sommet
st.top();     // 10
st.empty();   // false
st.size();    // 1

// NOTE : stack n'a PAS d'itérateurs par défaut !

Détails internes de Stack : container_type et c

std::stack est un adaptateur de conteneur - il enveloppe un autre conteneur :

// définition de stack (simplifiée)
template <typename T, typename Container = std::deque<T> >
class stack {
protected:
    Container c;  // Le conteneur sous-jacent

public:
    typedef Container container_type;  // Expose le type du conteneur

    void push(const T& x) { c.push_back(x); }
    void pop() { c.pop_back(); }
    T& top() { return c.back(); }
    bool empty() const { return c.empty(); }
    size_t size() const { return c.size(); }
};

Points clés :

• c : Membre protégé contenant les données réelles (par défaut : std::deque<T>)
• container_type : Typedef pour le type du conteneur sous-jacent
• Pas d’itérateurs : Stack cache intentionnellement l’itération pour imposer le LIFO

queue - FIFO

#include <queue>

std::queue<int> q;

q.push(10);
q.push(20);

q.front();    // 10 (premier entré)
q.back();     // 20 (dernier entré)
q.pop();      // Supprime le premier

---

5. Itérateurs

Types d’itérateurs

Type	Opérations	Conteneurs exemples
Input	Lecture seule, passage unique	istream
Output	Écriture seule, passage unique	ostream
Forward	Lecture/écriture, multi-pass	forward_list
Bidirectional	+/-, multi-pass	list, map, set
Random Access	+/-, +n, -n, []	vector, deque

Utilisation basique des itérateurs

std::vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);

// Déclaration d'itérateur
std::vector<int>::iterator it;

// Parcourir le conteneur
for (it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << std::endl;  // Déréférencement
}

// Parcours inverse
std::vector<int>::reverse_iterator rit;
for (rit = v.rbegin(); rit != v.rend(); ++rit) {
    std::cout << *rit << std::endl;
}

// Itérateur const (lecture seule)
std::vector<int>::const_iterator cit;
for (cit = v.begin(); cit != v.end(); ++cit) {
    // *cit = 100;  // ERREUR - itérateur const
    std::cout << *cit << std::endl;
}

---

6. Algorithmes

Inclure l’en-tête

#include <algorithm>

Algorithmes de recherche

std::vector<int> v;
// ... remplir v ...

// find - recherche linéaire
std::vector<int>::iterator it = std::find(v.begin(), v.end(), 42);
if (it != v.end())
    std::cout << "Trouvé à l'index : " << (it - v.begin()) << std::endl;

// count - compter les occurrences
int n = std::count(v.begin(), v.end(), 42);

// binary_search - nécessite un conteneur trié
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 42);

Tri

// sort - ordre croissant
std::sort(v.begin(), v.end());

// sort - comparateur personnalisé
bool compareDesc(int a, int b) { return a > b; }
std::sort(v.begin(), v.end(), compareDesc);

Min/Max

std::vector<int>::iterator minIt = std::min_element(v.begin(), v.end());
std::vector<int>::iterator maxIt = std::max_element(v.begin(), v.end());

Transform

std::vector<int> src;
std::vector<int> dst(src.size());

// Appliquer une fonction à chaque élément
int square(int x) { return x * x; }
std::transform(src.begin(), src.end(), dst.begin(), square);

---

7. Exercices du Module 08

ex00 : easyfind

// Trouver un entier dans n'importe quel conteneur
template <typename T>
typename T::iterator easyfind(T& container, int value) {
    typename T::iterator it = std::find(container.begin(), container.end(), value);
    if (it == container.end())
        throw std::runtime_error("Value not found");
    return it;
}

// Utilisation
std::vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);

try {
    std::vector<int>::iterator it = easyfind(v, 20);
    std::cout << "Trouvé : " << *it << std::endl;
}
catch (std::exception& e) {
    std::cout << e.what() << std::endl;
}

ex01 : Span

class Span {
private:
    std::vector<int> _numbers;
    unsigned int     _maxSize;

public:
    Span(unsigned int n);
    Span(const Span& other);
    Span& operator=(const Span& other);
    ~Span();

    void addNumber(int n);

    // Ajouter une plage de nombres
    template <typename Iterator>
    void addNumber(Iterator begin, Iterator end) {
        while (begin != end) {
            addNumber(*begin);
            ++begin;
        }
    }

    int shortestSpan() const;
    int longestSpan() const;
};

// Implémentation
void Span::addNumber(int n) {
    if (_numbers.size() >= _maxSize)
        throw std::runtime_error("Span is full");
    _numbers.push_back(n);
}

int Span::shortestSpan() const {
    if (_numbers.size() < 2)
        throw std::runtime_error("Not enough numbers");

    std::vector<int> sorted = _numbers;
    std::sort(sorted.begin(), sorted.end());

    int minSpan = sorted[1] - sorted[0];
    for (size_t i = 2; i < sorted.size(); i++) {
        int span = sorted[i] - sorted[i-1];
        if (span < minSpan)
            minSpan = span;
    }
    return minSpan;
}

int Span::longestSpan() const {
    if (_numbers.size() < 2)
        throw std::runtime_error("Not enough numbers");

    int min = *std::min_element(_numbers.begin(), _numbers.end());
    int max = *std::max_element(_numbers.begin(), _numbers.end());
    return max - min;
}

ex02 : MutantStack (Hériter des conteneurs templates)

// Rendre std::stack itérable en héritant et en exposant c
template <typename T>
class MutantStack : public std::stack<T> {
public:
    MutantStack() {}
    MutantStack(const MutantStack& other) : std::stack<T>(other) {}
    MutantStack& operator=(const MutantStack& other) {
        std::stack<T>::operator=(other);
        return *this;
    }
    ~MutantStack() {}

    // Exposer les types d'itérateurs du conteneur sous-jacent avec typedef
    // std::stack<T>::container_type est std::deque<T> par défaut
    typedef typename std::stack<T>::container_type::iterator iterator;
    typedef typename std::stack<T>::container_type::const_iterator const_iterator;
    typedef typename std::stack<T>::container_type::reverse_iterator reverse_iterator;
    typedef typename std::stack<T>::container_type::const_reverse_iterator const_reverse_iterator;

    // Transmettre l'accès aux itérateurs au conteneur sous-jacent
    iterator begin() { return this->c.begin(); }
    iterator end() { return this->c.end(); }
    const_iterator begin() const { return this->c.begin(); }
    const_iterator end() const { return this->c.end(); }

    // Accès aux itérateurs inverses
    reverse_iterator rbegin() { return this->c.rbegin(); }
    reverse_iterator rend() { return this->c.rend(); }
    const_reverse_iterator rbegin() const { return this->c.rbegin(); }
    const_reverse_iterator rend() const { return this->c.rend(); }
};

Pourquoi ça fonctionne :

• std::stack a un membre protégé c (le conteneur sous-jacent)
• En tant que classe dérivée, MutantStack peut accéder à this->c
• Nous exposons les types d’itérateurs en utilisant container_type::iterator
• Le mot-clé typename est requis car le type dépend du paramètre template T

Comprendre le mot-clé typename

// Lors de l'accès aux types imbriqués dans les templates, utilisez typename :
typedef typename std::stack<T>::container_type::iterator iterator;
//      ^^^^^^^^ Requis ! Indique au compilateur que c'est un type, pas une valeur

// Sans typename, le compilateur pourrait penser que container_type::iterator est une valeur

Itérateurs inverses (rbegin/rend)

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

// Itération normale : 1, 2, 3
for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    std::cout << *it << " ";

// Itération inverse : 3, 2, 1
for (std::vector<int>::reverse_iterator rit = v.rbegin(); rit != v.rend(); ++rit)
    std::cout << *rit << " ";

Algorithme lower_bound

Trouve la première position où un élément pourrait être inséré tout en maintenant l’ordre trié :

#include <algorithm>

std::vector<int> v;  // Doit être trié !
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);

// Trouver où 25 irait
std::vector<int>::iterator it = std::lower_bound(v.begin(), v.end(), 25);
// it pointe vers 30 (premier élément >= 25)

// Insérer tout en maintenant l'ordre trié
v.insert(it, 25);  // v est maintenant : 10, 20, 25, 30, 40

// Si l'élément existe, lower_bound retourne un itérateur vers lui
it = std::lower_bound(v.begin(), v.end(), 20);
// it pointe vers 20

lower_bound vs upper_bound

std::vector<int> v = {10, 20, 20, 20, 30};

std::lower_bound(v.begin(), v.end(), 20);  // Pointe vers le premier 20
std::upper_bound(v.begin(), v.end(), 20);  // Pointe vers 30 (premier > 20)

---

8. Guide de sélection des conteneurs

Besoin	Conteneur
Accès aléatoire rapide	vector, deque
Insertion rapide début/fin	deque, list
Insertion rapide au milieu	list
Clés uniques triées	set
Paires clé-valeur	map
Opérations LIFO	stack
Opérations FIFO	queue

---

Exercice 00 : Easy Find

Analyse du sujet

Créer un template de fonction easyfind qui :

• Prend un conteneur d’entiers (type T)
• Prend une valeur entière à rechercher
• Retourne un itérateur vers l’élément trouvé
• Gère le cas “non trouvé” de manière appropriée

Contraintes clés :

• Fonctionne avec n’importe quel conteneur séquentiel (vector, list, deque)
• N’a PAS besoin de fonctionner avec les conteneurs associatifs (map, set)
• Le sujet laisse la gestion du “non trouvé” à votre discrétion

Stratégie d’approche

Réfléchissez avant de coder :

1. Avec quels conteneurs doit-il fonctionner ?

   • std::vector<int>
   • std::list<int>
   • std::deque<int>
   • PAS std::map (stocke des paires, pas des entiers simples)

2. Quel algorithme STL devons-nous utiliser ?

   • std::find(begin, end, value) - retourne un itérateur vers l’élément ou end()

3. Comment gérer “non trouvé” ?

   • Option A : Retourner container.end() (l’appelant vérifie)
   • Option B : Lancer une exception (plus propre pour cet exercice)

4. Pourquoi typename T::iterator ?

   • T::iterator est un “type dépendant” (dépend du paramètre template T)
   • Le compilateur a besoin de l’indication typename pour l’analyser correctement

Construction progressive du code

Étape 1 : Structure de base avec std::find

easyfind.hpp

#ifndef EASYFIND_HPP
#define EASYFIND_HPP

#include <algorithm>  // std::find

template <typename T>
typename T::iterator easyfind(T& container, int value) {
    return std::find(container.begin(), container.end(), value);
}

#endif

Étape 2 : Ajouter une exception pour “non trouvé”

easyfind.hpp - avec exception

#include <algorithm>
#include <stdexcept>

template <typename T>
typename T::iterator easyfind(T& container, int value) {
    typename T::iterator it = std::find(container.begin(), container.end(), value);
    if (it == container.end()) {
        throw std::runtime_error("Value not found in container");
    }
    return it;
}

Explication ligne par ligne

Le mot-clé typename :

Code	Pourquoi
typename T::iterator	Indique au compilateur que T::iterator est un type, pas un membre statique
Sans typename	Erreur de compilation : “expected ’;’ before ‘it’”

// FAUX : Le compilateur pense que T::iterator est une valeur
T::iterator it = ...;  // Erreur !

// CORRECT : Marquer explicitement comme type
typename T::iterator it = ...;  // OK

Comportement de std::find :

Trouvé	Retourne
Oui	Itérateur pointant vers l’élément
Non	Itérateur égal à container.end()

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

std::vector<int>::iterator it = std::find(v.begin(), v.end(), 2);
// it pointe maintenant vers l'élément de valeur 2

it = std::find(v.begin(), v.end(), 99);
// it == v.end() (non trouvé)

Pièges courants

1. Oublier typename :

// FAUX : Erreur de compilation
template <typename T>
T::iterator easyfind(T& container, int value) { ... }

// CORRECT : Marquer le type dépendant
template <typename T>
typename T::iterator easyfind(T& container, int value) { ... }

2. Prendre le conteneur par valeur :

// FAUX : Copie tout le conteneur, l'itérateur pointe vers la copie
template <typename T>
typename T::iterator easyfind(T container, int value) { ... }

// CORRECT : Référence au conteneur original
template <typename T>
typename T::iterator easyfind(T& container, int value) { ... }

3. Ne pas gérer “non trouvé” :

// PROBLÉMATIQUE : L'appelant pourrait déréférencer end()
template <typename T>
typename T::iterator easyfind(T& container, int value) {
    return std::find(container.begin(), container.end(), value);
}

int main() {
    std::vector<int> v;
    std::cout << *easyfind(v, 42);  // UB si non trouve (dereferencer end() est invalide)
}

// MIEUX : Lancer une exception
if (it == container.end())
    throw std::runtime_error("Not found");

4. Essayer avec des conteneurs associatifs :

// NE FONCTIONNERA PAS comme prévu
std::map<int, std::string> m;
m[1] = "one";
easyfind(m, 1);  // std::find cherche std::pair<int,string>, pas int !

Conseils de test

main.cpp

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include "easyfind.hpp"

int main() {
    // Test avec vector
    std::vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(4);
    vec.push_back(5);

    try {
        std::vector<int>::iterator it = easyfind(vec, 3);
        std::cout << "Trouvé dans vector : " << *it << std::endl;
    } catch (std::exception& e) {
        std::cout << "Vector : " << e.what() << std::endl;
    }

    try {
        easyfind(vec, 99);
    } catch (std::exception& e) {
        std::cout << "Vector (99) : " << e.what() << std::endl;
    }

    // Test avec list
    std::list<int> lst;
    lst.push_back(10);
    lst.push_back(20);
    lst.push_back(30);

    try {
        std::list<int>::iterator it = easyfind(lst, 20);
        std::cout << "Trouvé dans list : " << *it << std::endl;
    } catch (std::exception& e) {
        std::cout << "List : " << e.what() << std::endl;
    }

    // Test avec deque
    std::deque<int> deq;
    deq.push_back(100);
    deq.push_front(50);

    try {
        std::deque<int>::iterator it = easyfind(deq, 50);
        std::cout << "Trouvé dans deque : " << *it << std::endl;
    } catch (std::exception& e) {
        std::cout << "Deque : " << e.what() << std::endl;
    }

    return 0;
}

Code final

easyfind.hpp

#ifndef EASYFIND_HPP
#define EASYFIND_HPP

#include <algorithm>
#include <stdexcept>

template <typename T>
typename T::iterator easyfind(T& container, int value) {
    typename T::iterator it = std::find(container.begin(), container.end(), value);
    if (it == container.end()) {
        throw std::runtime_error("Value not found in container");
    }
    return it;
}

#endif

---

Exercice 01 : Span

Analyse du sujet

Créer une classe Span qui :

• Stocke jusqu’à N entiers (N donné dans le constructeur)
• addNumber(int) - ajouter un seul nombre
• addNumber(begin, end) - ajouter une plage de nombres
• shortestSpan() - retourner la plus petite différence entre deux nombres quelconques
• longestSpan() - retourner la plus grande différence entre deux nombres quelconques
• Lance des exceptions quand c’est approprié

Contraintes clés :

• Doit tester avec un minimum de 10 000 nombres
• Utiliser des conteneurs STL en interne
• Ajout de plage requis (itérateurs)

Stratégie d’approche

Réfléchissez avant de coder :

1. Quel conteneur en interne ?

   • std::vector<int> - taille dynamique, accès aléatoire rapide, tri efficace

2. Comment trouver le span le plus court ?

   • Trier les nombres
   • Le span le plus court est entre éléments adjacents
   • Comparer chaque paire de voisins

3. Comment trouver le span le plus long ?

   • Simplement max - min
   • Pas besoin de trier

4. Quelles exceptions lancer ?

   • addNumber : Span est plein
   • shortestSpan/longestSpan : Moins de 2 nombres

Construction progressive du code

Étape 1 : Structure de classe de base

Span.hpp

#ifndef SPAN_HPP
#define SPAN_HPP

#include <vector>
#include <stdexcept>

class Span {
private:
    std::vector<int> _numbers;
    unsigned int     _maxSize;

public:
    Span(unsigned int n);
    Span(const Span& other);
    Span& operator=(const Span& other);
    ~Span();

    void addNumber(int n);
    int shortestSpan() const;
    int longestSpan() const;
};

#endif

Étape 2 : Opérations de base

Span.cpp

#include "Span.hpp"
#include <algorithm>

Span::Span(unsigned int n) : _maxSize(n) {}

Span::Span(const Span& other) : _numbers(other._numbers), _maxSize(other._maxSize) {}

Span& Span::operator=(const Span& other) {
    if (this != &other) {
        _numbers = other._numbers;
        _maxSize = other._maxSize;
    }
    return *this;
}

Span::~Span() {}

void Span::addNumber(int n) {
    if (_numbers.size() >= _maxSize) {
        throw std::runtime_error("Span is full");
    }
    _numbers.push_back(n);
}

Étape 3 : Calculs de span

Span.cpp - spans

int Span::shortestSpan() const {
    if (_numbers.size() < 2) {
        throw std::runtime_error("Not enough numbers for span");
    }

    // Trier une copie
    std::vector<int> sorted = _numbers;
    std::sort(sorted.begin(), sorted.end());

    // Trouver la différence minimale entre éléments adjacents
    int minSpan = sorted[1] - sorted[0];
    for (size_t i = 2; i < sorted.size(); i++) {
        int span = sorted[i] - sorted[i - 1];
        if (span < minSpan) {
            minSpan = span;
        }
    }
    return minSpan;
}

int Span::longestSpan() const {
    if (_numbers.size() < 2) {
        throw std::runtime_error("Not enough numbers for span");
    }

    int min = *std::min_element(_numbers.begin(), _numbers.end());
    int max = *std::max_element(_numbers.begin(), _numbers.end());
    return max - min;
}

Étape 4 : Ajout de plage (membre template)

Span.hpp - ajout de plage

class Span {
    // ... code existant ...

public:
    // Fonction membre template pour l'ajout de plage
    template <typename Iterator>
    void addNumber(Iterator begin, Iterator end) {
        while (begin != end) {
            addNumber(*begin);  // Réutilise l'ajout simple (inclut la vérification de plein)
            ++begin;
        }
    }
};

Explication ligne par ligne

Pourquoi trier pour le span le plus court ?

// Non trié : [5, 1, 9, 3, 7]
// Toutes les paires : (5,1)=4, (5,9)=4, (5,3)=2, (5,7)=2, (1,9)=8, ...
// O(n²) comparaisons !

// Trié : [1, 3, 5, 7, 9]
// Vérifier seulement les voisins : (1,3)=2, (3,5)=2, (5,7)=2, (7,9)=2
// O(n log n) tri + O(n) parcours

min_element et max_element :

Algorithme	Retourne
std::min_element(begin, end)	Itérateur vers le plus petit élément
std::max_element(begin, end)	Itérateur vers le plus grand élément

std::vector<int> v;
v.push_back(5);
v.push_back(1);
v.push_back(9);

int min = *std::min_element(v.begin(), v.end());  // 1
int max = *std::max_element(v.begin(), v.end());  // 9

Pièges courants

1. Modifier l’original pour le span le plus court :

// FAUX : Trie les nombres réellement stockés
int Span::shortestSpan() const {
    std::sort(_numbers.begin(), _numbers.end());  // Modifie _numbers !
}

// CORRECT : Trier une copie
int Span::shortestSpan() const {
    std::vector<int> sorted = _numbers;  // Copie
    std::sort(sorted.begin(), sorted.end());  // Trier la copie
}

2. Pas d’ajout de plage :

// FAUX : Le sujet exige d'ajouter plusieurs nombres à la fois
// Avoir seulement addNumber(int n)

// CORRECT : Template pour n'importe quel type d'itérateur
template <typename Iterator>
void addNumber(Iterator begin, Iterator end);

3. Ne pas tester avec de grandes données :

// FAUX : Tester seulement avec 5 nombres
Span sp(5);

// CORRECT : Le sujet exige 10 000+
Span sp(10000);
for (int i = 0; i < 10000; i++) {
    sp.addNumber(i);
}

4. Dépassement d’entier dans le calcul de span :

// PROBLÈME POTENTIEL avec des valeurs extrêmes
int span = sorted[i] - sorted[i - 1];  // Pourrait dépasser

// Pour plus de sécurité, pourrait utiliser unsigned ou long
// Mais pour cet exercice, int est généralement suffisant

Conseils de test

main.cpp

#include <iostream>
#include <cstdlib>
#include "Span.hpp"

int main() {
    // Test de base du sujet
    Span sp = Span(5);
    sp.addNumber(6);
    sp.addNumber(3);
    sp.addNumber(17);
    sp.addNumber(9);
    sp.addNumber(11);

    std::cout << "Plus court : " << sp.shortestSpan() << std::endl;  // 2
    std::cout << "Plus long : " << sp.longestSpan() << std::endl;    // 14

    // Test des exceptions
    try {
        sp.addNumber(42);  // Devrait lancer - plein
    } catch (std::exception& e) {
        std::cout << "Plein : " << e.what() << std::endl;
    }

    Span empty(5);
    try {
        empty.shortestSpan();  // Devrait lancer - pas assez
    } catch (std::exception& e) {
        std::cout << "Vide : " << e.what() << std::endl;
    }

    // Grand test (10 000+ nombres)
    Span big(10000);
    std::vector<int> manyNumbers;
    for (int i = 0; i < 10000; i++) {
        manyNumbers.push_back(i);
    }
    big.addNumber(manyNumbers.begin(), manyNumbers.end());

    std::cout << "Grand plus court : " << big.shortestSpan() << std::endl;  // 1
    std::cout << "Grand plus long : " << big.longestSpan() << std::endl;    // 9999

    return 0;
}

Script de test bash :

c++ -Wall -Wextra -Werror -std=c++98 main.cpp Span.cpp -o span
./span

# Attendu :
# Plus court : 2
# Plus long : 14
# Plein : Span is full
# Vide : Not enough numbers for span
# Grand plus court : 1
# Grand plus long : 9999

Code final

Span.hpp

#ifndef SPAN_HPP
#define SPAN_HPP

#include <vector>
#include <stdexcept>

class Span {
private:
    std::vector<int> _numbers;
    unsigned int     _maxSize;

public:
    Span(unsigned int n);
    Span(const Span& other);
    Span& operator=(const Span& other);
    ~Span();

    void addNumber(int n);
    int shortestSpan() const;
    int longestSpan() const;

    template <typename Iterator>
    void addNumber(Iterator begin, Iterator end) {
        while (begin != end) {
            addNumber(*begin);
            ++begin;
        }
    }
};

#endif

Span.cpp

#include "Span.hpp"
#include <algorithm>

Span::Span(unsigned int n) : _maxSize(n) {}

Span::Span(const Span& other)
    : _numbers(other._numbers), _maxSize(other._maxSize) {}

Span& Span::operator=(const Span& other) {
    if (this != &other) {
        _numbers = other._numbers;
        _maxSize = other._maxSize;
    }
    return *this;
}

Span::~Span() {}

void Span::addNumber(int n) {
    if (_numbers.size() >= _maxSize) {
        throw std::runtime_error("Span is full");
    }
    _numbers.push_back(n);
}

int Span::shortestSpan() const {
    if (_numbers.size() < 2) {
        throw std::runtime_error("Not enough numbers for span");
    }

    std::vector<int> sorted = _numbers;
    std::sort(sorted.begin(), sorted.end());

    int minSpan = sorted[1] - sorted[0];
    for (size_t i = 2; i < sorted.size(); i++) {
        int span = sorted[i] - sorted[i - 1];
        if (span < minSpan) {
            minSpan = span;
        }
    }
    return minSpan;
}

int Span::longestSpan() const {
    if (_numbers.size() < 2) {
        throw std::runtime_error("Not enough numbers for span");
    }

    int min = *std::min_element(_numbers.begin(), _numbers.end());
    int max = *std::max_element(_numbers.begin(), _numbers.end());
    return max - min;
}

---

Exercice 02 : Abomination mutante

Analyse du sujet

Créer MutantStack qui :

• Hérite de std::stack
• Ajoute le support des itérateurs (begin, end, rbegin, rend)
• Se comporte exactement comme une stack mais peut être itéré

Idée clé : std::stack est un adaptateur de conteneur. Il enveloppe un autre conteneur (par défaut : std::deque) et restreint son interface. Le conteneur sous-jacent est accessible via le membre protégé c.

Stratégie d’approche

Réfléchissez avant de coder :

1. Qu’est-ce que std::stack en interne ?

   template <typename T, typename Container = std::deque<T>>
   class stack {
   protected:
       Container c;  // Le conteneur sous-jacent !
   public:
       void push(const T& val) { c.push_back(val); }
       void pop() { c.pop_back(); }
       T& top() { return c.back(); }
       // ...
   };

2. Comment ajouter des itérateurs ?

   • Accéder au membre protégé c
   • Exposer ses itérateurs via notre interface publique

3. Quels types d’itérateurs avons-nous besoin ?

   • iterator - itération normale
   • const_iterator - itération const normale
   • reverse_iterator - itération inverse
   • const_reverse_iterator - itération inverse const

Construction progressive du code

Étape 1 : Héritage de base

MutantStack.hpp

#ifndef MUTANTSTACK_HPP
#define MUTANTSTACK_HPP

#include <stack>

template <typename T>
class MutantStack : public std::stack<T> {
public:
    MutantStack();
    MutantStack(const MutantStack& other);
    MutantStack& operator=(const MutantStack& other);
    ~MutantStack();
};

#endif

Étape 2 : Implémenter OCF

MutantStack.hpp - OCF

template <typename T>
MutantStack<T>::MutantStack() : std::stack<T>() {}

template <typename T>
MutantStack<T>::MutantStack(const MutantStack& other) : std::stack<T>(other) {}

template <typename T>
MutantStack<T>& MutantStack<T>::operator=(const MutantStack& other) {
    std::stack<T>::operator=(other);
    return *this;
}

template <typename T>
MutantStack<T>::~MutantStack() {}

Étape 3 : Ajouter les types d’itérateurs

MutantStack.hpp - typedefs

template <typename T>
class MutantStack : public std::stack<T> {
public:
    // Alias de types pour les itérateurs
    typedef typename std::stack<T>::container_type::iterator iterator;
    typedef typename std::stack<T>::container_type::const_iterator const_iterator;
    typedef typename std::stack<T>::container_type::reverse_iterator reverse_iterator;
    typedef typename std::stack<T>::container_type::const_reverse_iterator const_reverse_iterator;

    // ... reste de la classe
};

Étape 4 : Ajouter les méthodes d’itérateurs

MutantStack.hpp - itérateurs

// Accéder aux itérateurs du conteneur sous-jacent
iterator begin() { return this->c.begin(); }
iterator end() { return this->c.end(); }
const_iterator begin() const { return this->c.begin(); }
const_iterator end() const { return this->c.end(); }
reverse_iterator rbegin() { return this->c.rbegin(); }
reverse_iterator rend() { return this->c.rend(); }
const_reverse_iterator rbegin() const { return this->c.rbegin(); }
const_reverse_iterator rend() const { return this->c.rend(); }

Explication ligne par ligne

Comprendre container_type :

Expression	Signification
std::stack<T>	Le template de classe stack
std::stack<T>::container_type	Le type du conteneur sous-jacent (défaut : std::deque<T>)
container_type::iterator	Type d’itérateur de ce conteneur

// std::stack est défini approximativement comme :
template <typename T, typename Container = std::deque<T>>
class stack {
public:
    typedef Container container_type;  // Expose le type du conteneur
protected:
    Container c;  // L'instance réelle du conteneur
};

Pourquoi this->c ?

// Sans 'this->', le compilateur ne regarde pas dans la classe de base
iterator begin() { return c.begin(); }  // Peut ne pas compiler

// Avec 'this->', indique explicitement au compilateur de regarder dans la classe de base
iterator begin() { return this->c.begin(); }  // Fonctionne toujours

Pourquoi typedef typename ?

// container_type::iterator est un type dépendant
// Doit utiliser 'typename' pour indiquer au compilateur que c'est un type

// FAUX
typedef std::stack<T>::container_type::iterator iterator;

// CORRECT
typedef typename std::stack<T>::container_type::iterator iterator;

Pièges courants

1. Oublier typename dans typedef :

// FAUX : Erreur de compilation
typedef std::stack<T>::container_type::iterator iterator;

// CORRECT : typename requis pour le type dépendant
typedef typename std::stack<T>::container_type::iterator iterator;

2. Oublier this-> pour c :

// FAUX : Sur certains compilateurs/standards
iterator begin() { return c.begin(); }

// CORRECT : Fonctionne toujours
iterator begin() { return this->c.begin(); }

3. Versions const manquantes :

// FAUX : Seulement les itérateurs non-const
iterator begin() { return this->c.begin(); }

// CORRECT : Const et non-const
iterator begin() { return this->c.begin(); }
const_iterator begin() const { return this->c.begin(); }

4. Ne pas tester la comparaison avec std::list :

// Le sujet exige : la sortie doit être la même que std::list
// (avec les changements de noms de méthodes appropriés : push_back -> push, etc.)

Conseils de test

main.cpp

#include <iostream>
#include <list>
#include "MutantStack.hpp"

int main() {
    // Test du sujet
    MutantStack<int> mstack;

    mstack.push(5);
    mstack.push(17);

    std::cout << "Top : " << mstack.top() << std::endl;

    mstack.pop();

    std::cout << "Size : " << mstack.size() << std::endl;

    mstack.push(3);
    mstack.push(5);
    mstack.push(737);
    mstack.push(0);

    MutantStack<int>::iterator it = mstack.begin();
    MutantStack<int>::iterator ite = mstack.end();

    ++it;
    --it;

    std::cout << "Contenu de la stack :" << std::endl;
    while (it != ite) {
        std::cout << *it << std::endl;
        ++it;
    }

    // Test de copie
    std::stack<int> s(mstack);

    // Comparer avec std::list
    std::cout << "\n--- Comparaison std::list ---" << std::endl;
    std::list<int> lst;

    lst.push_back(5);
    lst.push_back(17);

    std::cout << "Back : " << lst.back() << std::endl;

    lst.pop_back();

    std::cout << "Size : " << lst.size() << std::endl;

    lst.push_back(3);
    lst.push_back(5);
    lst.push_back(737);
    lst.push_back(0);

    std::list<int>::iterator lit = lst.begin();
    std::list<int>::iterator lite = lst.end();

    std::cout << "Contenu de la list :" << std::endl;
    while (lit != lite) {
        std::cout << *lit << std::endl;
        ++lit;
    }

    return 0;
}

Tester les itérateurs inverses :

// Itération inverse
MutantStack<int>::reverse_iterator rit = mstack.rbegin();
MutantStack<int>::reverse_iterator rite = mstack.rend();

std::cout << "Inversé :" << std::endl;
while (rit != rite) {
    std::cout << *rit << std::endl;
    ++rit;
}

Code final

MutantStack.hpp

#ifndef MUTANTSTACK_HPP
#define MUTANTSTACK_HPP

#include <stack>

template <typename T>
class MutantStack : public std::stack<T> {
public:
    MutantStack();
    MutantStack(const MutantStack& other);
    MutantStack& operator=(const MutantStack& other);
    ~MutantStack();

    // Types d'itérateurs
    typedef typename std::stack<T>::container_type::iterator iterator;
    typedef typename std::stack<T>::container_type::const_iterator const_iterator;
    typedef typename std::stack<T>::container_type::reverse_iterator reverse_iterator;
    typedef typename std::stack<T>::container_type::const_reverse_iterator const_reverse_iterator;

    // Accesseurs d'itérateurs
    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;
    reverse_iterator rbegin();
    reverse_iterator rend();
    const_reverse_iterator rbegin() const;
    const_reverse_iterator rend() const;
};

// Implémentation OCF
template <typename T>
MutantStack<T>::MutantStack() : std::stack<T>() {}

template <typename T>
MutantStack<T>::MutantStack(const MutantStack& other) : std::stack<T>(other) {}

template <typename T>
MutantStack<T>& MutantStack<T>::operator=(const MutantStack& other) {
    std::stack<T>::operator=(other);
    return *this;
}

template <typename T>
MutantStack<T>::~MutantStack() {}

// Méthodes d'itérateurs
template <typename T>
typename MutantStack<T>::iterator MutantStack<T>::begin() {
    return this->c.begin();
}

template <typename T>
typename MutantStack<T>::iterator MutantStack<T>::end() {
    return this->c.end();
}

template <typename T>
typename MutantStack<T>::const_iterator MutantStack<T>::begin() const {
    return this->c.begin();
}

template <typename T>
typename MutantStack<T>::const_iterator MutantStack<T>::end() const {
    return this->c.end();
}

template <typename T>
typename MutantStack<T>::reverse_iterator MutantStack<T>::rbegin() {
    return this->c.rbegin();
}

template <typename T>
typename MutantStack<T>::reverse_iterator MutantStack<T>::rend() {
    return this->c.rend();
}

template <typename T>
typename MutantStack<T>::const_reverse_iterator MutantStack<T>::rbegin() const {
    return this->c.rbegin();
}

template <typename T>
typename MutantStack<T>::const_reverse_iterator MutantStack<T>::rend() const {
    return this->c.rend();
}

#endif

main.cpp

#include <iostream>
#include <list>
#include "MutantStack.hpp"

int main() {
    MutantStack<int> mstack;

    mstack.push(5);
    mstack.push(17);
    std::cout << mstack.top() << std::endl;
    mstack.pop();
    std::cout << mstack.size() << std::endl;

    mstack.push(3);
    mstack.push(5);
    mstack.push(737);
    mstack.push(0);

    MutantStack<int>::iterator it = mstack.begin();
    MutantStack<int>::iterator ite = mstack.end();

    ++it;
    --it;
    while (it != ite) {
        std::cout << *it << std::endl;
        ++it;
    }

    std::stack<int> s(mstack);
    return 0;
}

---

Résumé du Module 08 : STL

Concept	Point clé
Conteneurs	vector, list, deque, stack, map, set
Itérateurs	Pointeurs vers les éléments des conteneurs
Algorithmes	find, sort, min_element, max_element
typename	Requis pour les types dépendants dans les templates

Quand utiliser quel conteneur :

Conteneur	Idéal pour
vector	Accès aléatoire, mémoire contiguë
list	Insertions/suppressions fréquentes au milieu
deque	Insertion rapide aux deux extrémités
stack	Opérations LIFO uniquement
map	Paires clé-valeur avec recherche rapide
set	Éléments uniques avec recherche rapide

---

Référence rapide

// Opérations vector
v.push_back(x);    v.pop_back();
v[i];              v.at(i);
v.begin();         v.end();
v.size();          v.empty();

// Opérations map
m[key] = value;    m.at(key);
m.find(key);       m.count(key);
m.insert(pair);    m.erase(key);

// Algorithmes
std::find(begin, end, value);
std::sort(begin, end);
std::count(begin, end, value);
std::min_element(begin, end);
std::max_element(begin, end);

---

Concepts connexes

Continuez votre parcours C++ :

• Précédent : Module 07 : Templates - Révisez comment la STL est construite
• Suivant : Module 09 : STL Pratique - Appliquez la STL à des problèmes réels

Termes clés de ce module

Visitez le Glossaire pour les définitions de :

• Conteneur
• Itérateur