Module 09 : Applications pratiques de la STL

Télécharger le PDF officiel du sujet

Concepts clés :

Choisir le bon conteneur
Analyse de fichiers
Implémentation d’algorithmes
Considérations de performance

Pourquoi c’est important

Ce module concerne les bons choix. Différents conteneurs ont différentes caractéristiques de performance, et choisir judicieusement peut rendre votre programme 10x plus rapide — ou 10x plus lent.

Comprendre la syntaxe STL avancée

Ce module utilise des fonctionnalités STL avancées. Voici la syntaxe expliquée :

L’algorithme `lower_bound`

std::map<std::string, float>::iterator it = db.lower_bound(date);

lower_bound trouve le premier élément PAS INFÉRIEUR à la clé donnée
Il retourne un itérateur vers le premier élément >= la valeur recherchée
Pour les maps, il utilise l’ordre trié des clés
Si tous les éléments sont inférieurs, retourne end()
Utilisé pour trouver des points d’insertion ou rechercher les valeurs les plus proches

L’opération `insert`

v.insert(it, value);   // Insère value à la position it

insert ajoute des éléments à une position d’itérateur spécifique
Pour les vectors, les éléments après la position sont décalés (O(n))
Pour les lists, l’insertion est O(1) mais vous devez d’abord trouver la position (O(n))
Combiné avec lower_bound, insère tout en maintenant l’ordre trié

Le `static_cast<double>` pour le chronométrage

double microseconds = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000000;

static_cast<double> assure une division en virgule flottante
Sans lui, la division entière perdrait la précision
CLOCKS_PER_SEC est généralement un grand entier
Castez avant la division pour préserver les décimales

Les fonctions `std::atoi` et `std::atof`

int n = std::atoi(str.c_str());
float f = std::atof(str.c_str());

atoi = ASCII vers Integer (entier)
atof = ASCII vers Float (flottant)
.c_str() convertit std::string en const char* (requis par ces fonctions C)
Ces fonctions retournent 0 en cas d’erreur, ce qui peut être ambigu

L’`operator[]` avec les maps

ages["Alice"] = 25;   // Insérer ou mettre à jour

[] sur les maps accède ou crée une paire clé-valeur
Si la clé existe, retourne une référence vers la valeur
Si la clé n’existe pas, l’insère avec la valeur par défaut (0 pour les nombres)
map[key] réussit toujours (crée si nécessaire)
Utilisez find() si vous ne voulez pas créer les clés manquantes

1. Règles du module

Restrictions sur les conteneurs

Doit utiliser au moins un conteneur par exercice
L’exercice 02 nécessite DEUX conteneurs différents
Une fois qu’un conteneur est utilisé, il est interdit pour les exercices restants

Allocation suggérée des conteneurs

Exercice	Conteneur(s) suggéré(s)	Pourquoi
ex00	map	Paires clé-valeur (date -> prix)
ex01	stack	RPN utilise naturellement une pile
ex02	vector + deque (ou list)	Comparaison de tri

2. Exercice 00 : Échange Bitcoin

Problème

Lire une base de données de prix Bitcoin et calculer les valeurs pour des montants donnés à des dates spécifiques.

Format d’entrée

// Base de données (CSV) : date,taux_de_change
2009-01-02,0
2011-01-03,0.3
2011-01-09,0.32

// Fichier d'entrée : date | valeur
date | value
2011-01-03 | 3
2011-01-03 | 2

Approche de solution

class BitcoinExchange {
private:
    std::map<std::string, float> _database;  // date -> prix

    bool isValidDate(const std::string& date);
    bool isValidValue(const std::string& value, float& result);
    std::string findClosestDate(const std::string& date);

public:
    BitcoinExchange();
    BitcoinExchange(const BitcoinExchange& other);
    BitcoinExchange& operator=(const BitcoinExchange& other);
    ~BitcoinExchange();

    void loadDatabase(const std::string& filename);
    void processInput(const std::string& filename);
};

### E/S de fichiers avec ifstream
```cpp
#include <fstream>
#include <string>

void BitcoinExchange::loadDatabase(const std::string& filename) {
    // Ouvrir le fichier (.c_str() nécessaire pour la compatibilité C++98)
    std::ifstream file(filename.c_str());

    // Vérifier si le fichier s'est ouvert avec succès
    if (!file.is_open())
        throw std::runtime_error("Cannot open database file");

    std::string line;
    std::getline(file, line);  // Sauter la ligne d'en-tête

    // Lire ligne par ligne
    while (std::getline(file, line)) {
        size_t pos = line.find(',');
        if (pos != std::string::npos) {
            std::string date = line.substr(0, pos);
            float price = std::atof(line.substr(pos + 1).c_str());
            _database[date] = price;
        }
    }

    file.close();  // Optionnel - se ferme automatiquement à la destruction
}

std::getline pour la lecture ligne par ligne

std::ifstream file("input.txt");
std::string line;

// Lire jusqu'à EOF
while (std::getline(file, line)) {
    // Traiter la ligne
    std::cout << line << std::endl;
}

// Vérifier pourquoi la boucle s'est terminée
if (file.eof()) {
    // Fin de fichier normale
}
else if (file.fail()) {
    // Une erreur de lecture s'est produite
}

map::lower_bound pour une recherche efficace

std::string BitcoinExchange::findClosestDate(const std::string& date) {
    // lower_bound retourne un itérateur vers le premier élément >= date
    std::map<std::string, float>::iterator it = _database.lower_bound(date);

    // Cas 1 : Correspondance exacte trouvée
    if (it != _database.end() && it->first == date) {
        return it->first;
    }

    // Cas 2 : date est plus petite que toutes les clés
    if (it == _database.begin()) {
        return "";  // Pas de date antérieure existante
    }

    // Cas 3 : Aller à la date précédente (antérieure)
    --it;
    return it->first;
}

Validation de date avec logique d’année bissextile

bool BitcoinExchange::isValidDate(const std::string& date) {
    // Format : YYYY-MM-DD (exactement 10 caractères)
    if (date.length() != 10)
        return false;
    if (date[4] != '-' || date[7] != '-')
        return false;

    // Vérifier que année, mois, jour sont des chiffres
    for (int i = 0; i < 10; i++) {
        if (i == 4 || i == 7) continue;  // Sauter les tirets
        if (!std::isdigit(date[i]))
            return false;
    }

    int year = std::atoi(date.substr(0, 4).c_str());
    int month = std::atoi(date.substr(5, 2).c_str());
    int day = std::atoi(date.substr(8, 2).c_str());

    // Vérifications de plage de base
    if (year < 1)
        return false;
    if (month < 1 || month > 12)
        return false;
    if (day < 1 || day > 31)
        return false;

    // Jours par mois (index 0 non utilisé)
    int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    // Calcul de l'année bissextile
    // Une année est bissextile si :
    // - Divisible par 4 ET non divisible par 100
    // - OU divisible par 400
    bool isLeapYear = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    if (isLeapYear && month == 2)
        daysInMonth[2] = 29;

    return day <= daysInMonth[month];
}

Exemples d’années bissextiles

// 2000 : divisible par 400 -> ANNÉE BISSEXTILE
// 1900 : divisible par 100 mais pas 400 -> PAS bissextile
// 2024 : divisible par 4, pas par 100 -> ANNÉE BISSEXTILE
// 2023 : pas divisible par 4 -> PAS bissextile

bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

3. Exercice 01 : Notation polonaise inverse (RPN)

Problème

Évaluer des expressions mathématiques en notation postfixe.

Comment fonctionne la RPN

Infixe :  (3 + 4) * 2
Postfixe : 3 4 + 2 *

Évaluation :
- Lire 3, empiler : [3]
- Lire 4, empiler : [3, 4]
- Lire +, dépiler 4,3, empiler 7 : [7]
- Lire 2, empiler : [7, 2]
- Lire *, dépiler 2,7, empiler 14 : [14]
- Résultat : 14

Solution

class RPN {
private:
    std::stack<int> _stack;

    bool isOperator(char c);
    int applyOperator(int a, int b, char op);

public:
    RPN();
    RPN(const RPN& other);
    RPN& operator=(const RPN& other);
    ~RPN();

    int evaluate(const std::string& expression);
};

int RPN::evaluate(const std::string& expression) {
    for (size_t i = 0; i < expression.length(); i++) {
        char c = expression[i];

        if (c == ' ')
            continue;

        if (isdigit(c)) {
            _stack.push(c - '0');
        }
        else if (isOperator(c)) {
            if (_stack.size() < 2)
                throw std::runtime_error("Error");

            int b = _stack.top(); _stack.pop();
            int a = _stack.top(); _stack.pop();

            _stack.push(applyOperator(a, b, c));
        }
        else {
            throw std::runtime_error("Error");
        }
    }

    if (_stack.size() != 1)
        throw std::runtime_error("Error");

    return _stack.top();
}

bool RPN::isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int RPN::applyOperator(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/':
            if (b == 0)
                throw std::runtime_error("Error");
            return a / b;
    }
    throw std::runtime_error("Error");
}

4. Opération vector::insert

Insérer à une position

std::vector<int> v;
v.push_back(10);
v.push_back(30);
v.push_back(40);
// v = {10, 30, 40}

// Insérer 20 à la position 1 (avant 30)
std::vector<int>::iterator it = v.begin() + 1;
v.insert(it, 20);
// v = {10, 20, 30, 40}

Insérer avec lower_bound (insertion triée)

std::vector<int> sorted = {10, 20, 40, 50};

// Insérer 30 à la position triée
std::vector<int>::iterator pos = std::lower_bound(sorted.begin(), sorted.end(), 30);
sorted.insert(pos, 30);
// sorted = {10, 20, 30, 40, 50}

Performance d’insertion

Conteneur	Insertion au début	Insertion à la fin	Insertion au milieu
vector	O(n)	O(1) amorti	O(n)
deque	O(1)	O(1)	O(n)
list	O(1)	O(1)	O(1)*

*Après avoir trouvé la position

5. Opérations sur deque

deque - File à double extrémité

#include <deque>

std::deque<int> dq;

// Ajouter des éléments (efficace aux DEUX extrémités)
dq.push_back(30);   // {30}
dq.push_front(10);  // {10, 30}
dq.push_back(40);   // {10, 30, 40}
dq.push_front(5);   // {5, 10, 30, 40}

// Accès aléatoire (comme vector)
dq[0];              // 5
dq.at(1);           // 10

// Supprimer des deux extrémités
dq.pop_front();     // {10, 30, 40}
dq.pop_back();      // {10, 30}

// Insérer au milieu
std::deque<int>::iterator it = dq.begin() + 1;
dq.insert(it, 20);  // {10, 20, 30}

deque vs vector

Fonctionnalité	vector	deque
push_front	O(n) lent	O(1) rapide
push_back	O(1)	O(1)
Accès aléatoire	O(1)	O(1)
Mémoire	Contiguë	Par blocs
Localité cache	Meilleure	Moins bonne

6. Exercice 02 : PmergeMe (Algorithme Ford-Johnson)

Problème

Implémenter le tri par insertion-fusion en utilisant deux conteneurs différents et comparer les performances.

Vue d’ensemble de l’algorithme Ford-Johnson

Pairer les éléments : Grouper l’entrée en paires
Trier chaque paire : Dans chaque paire, identifier le plus grand et le plus petit élément
Trier récursivement : Trier la séquence des éléments les plus grands
Insertion binaire : Insérer les éléments plus petits en utilisant la recherche binaire (lower_bound)

Pourquoi Ford-Johnson ?

Minimise le nombre de comparaisons
Utilise la séquence de Jacobsthal pour un ordre d’insertion optimal
Amélioration théorique par rapport au simple tri fusion en nombre de comparaisons

Séquence de Jacobsthal (Optimisation optionnelle)

La séquence de Jacobsthal détermine l’ordre d’insertion optimal : 1, 3, 5, 11, 21, 43, …

// J(n) = J(n-1) + 2*J(n-2), J(0)=0, J(1)=1
int jacobsthal(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return jacobsthal(n - 1) + 2 * jacobsthal(n - 2);
}

Implémentation simplifiée

class PmergeMe {
private:
    std::vector<int> _vec;
    std::deque<int> _deq;

    void sortVector();
    void sortDeque();

public:
    PmergeMe();
    PmergeMe(const PmergeMe& other);
    PmergeMe& operator=(const PmergeMe& other);
    ~PmergeMe();

    void parseInput(int argc, char** argv);
    void sort();
    void display() const;
};

// Ford-Johnson pour vector
void PmergeMe::sortVector() {
    if (_vec.size() <= 1)
        return;

    std::vector<int> larger, smaller;

    // Étape 1 : Créer des paires
    for (size_t i = 0; i + 1 < _vec.size(); i += 2) {
        if (_vec[i] > _vec[i + 1]) {
            larger.push_back(_vec[i]);
            smaller.push_back(_vec[i + 1]);
        } else {
            larger.push_back(_vec[i + 1]);
            smaller.push_back(_vec[i]);
        }
    }

    // Gérer l'élément impair
    bool hasOdd = (_vec.size() % 2 != 0);
    int oddElement = hasOdd ? _vec.back() : 0;

    // Étape 2 : Trier récursivement les éléments plus grands
    _vec = larger;
    sortVector();
    larger = _vec;

    // Étape 3 : Insérer les éléments plus petits
    // Le premier élément de smaller va en premier (pairé avec le premier de larger)
    if (!smaller.empty()) {
        std::vector<int>::iterator pos = std::lower_bound(
            larger.begin(), larger.end(), smaller[0]);
        larger.insert(pos, smaller[0]);
    }

    // Insérer le reste en utilisant la séquence de Jacobsthal pour des insertions optimales
    for (size_t i = 1; i < smaller.size(); i++) {
        std::vector<int>::iterator pos = std::lower_bound(
            larger.begin(), larger.end(), smaller[i]);
        larger.insert(pos, smaller[i]);
    }

    // Insérer l'élément impair
    if (hasOdd) {
        std::vector<int>::iterator pos = std::lower_bound(
            larger.begin(), larger.end(), oddElement);
        larger.insert(pos, oddElement);
    }

    _vec = larger;
}

Exemple pas à pas

Entrée : [3, 1, 4, 1, 5, 9, 2, 6]

1. PAIRER ET TRIER LES PAIRES :
   (3,1) -> larger=3, smaller=1
   (4,1) -> larger=4, smaller=1
   (5,9) -> larger=9, smaller=5
   (2,6) -> larger=6, smaller=2

   Plus grands : [3, 4, 9, 6]
   Plus petits : [1, 1, 5, 2]

2. TRIER RÉCURSIVEMENT LES PLUS GRANDS :
   [3, 4, 9, 6] -> [3, 4, 6, 9]

3. INSERTION BINAIRE DES PLUS PETITS :
   Début : [3, 4, 6, 9]
   Insérer 1 (pairé avec 3) : lower_bound trouve 3, insérer avant -> [1, 3, 4, 6, 9]
   Insérer 1 (pairé avec 4) : lower_bound trouve 3, insérer avant -> [1, 1, 3, 4, 6, 9]
   Insérer 5 (pairé avec 9) : lower_bound trouve 6, insérer avant -> [1, 1, 3, 4, 5, 6, 9]
   Insérer 2 (pairé avec 6) : lower_bound trouve 3, insérer avant -> [1, 1, 2, 3, 4, 5, 6, 9]

Résultat : [1, 1, 2, 3, 4, 5, 6, 9]

Utiliser deux conteneurs différents

class PmergeMe {
private:
    std::vector<int> _vec;  // Premier conteneur
    std::deque<int> _deq;   // Second conteneur (doit être différent !)

    void sortVector();
    void sortDeque();       // Même algorithme, conteneur différent
};

// Analyser l'entrée dans les deux conteneurs
void PmergeMe::parseInput(int argc, char** argv) {
    for (int i = 1; i < argc; i++) {
        int num = std::atoi(argv[i]);
        if (num < 0)
            throw std::runtime_error("Error: negative number");
        _vec.push_back(num);
        _deq.push_back(num);  // Mêmes données dans les deux
    }
}

Chronométrage

#include <ctime>

void PmergeMe::sort() {
    // Vector
    clock_t start = clock();
    sortVector();
    clock_t end = clock();
    double vecTime = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000000;

    // Deque
    start = clock();
    sortDeque();
    end = clock();
    double deqTime = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000000;

    std::cout << "Time to process " << _vec.size()
              << " elements with std::vector: " << vecTime << " us" << std::endl;
    std::cout << "Time to process " << _deq.size()
              << " elements with std::deque: " << deqTime << " us" << std::endl;
}

7. Pièges courants

Exercice 00

Ne pas gérer les dates manquantes (utiliser la date antérieure la plus proche)
Ne pas valider le format de date
La valeur doit être positive et <= 1000

Exercice 01

Oublier la vérification de division par zéro
Les nombres doivent être < 10 (un seul chiffre en entrée)
Le résultat peut être de n’importe quelle taille

Exercice 02

Utiliser le même conteneur pour les deux implémentations
Ne pas mesurer le temps correctement
Ne pas implémenter le vrai Ford-Johnson (les tris simplifiés peuvent ne pas passer)

8. Résumé des propriétés des conteneurs

Conteneur	Accès aléatoire	Insertion début	Insertion fin	Insertion milieu	Trié
vector	O(1)	O(n)	O(1)*	O(n)	Non
deque	O(1)	O(1)	O(1)	O(n)	Non
list	O(n)	O(1)	O(1)	O(1)	Non
map	O(log n)	-	-	O(log n)	Oui
set	O(log n)	-	-	O(log n)	Oui
stack	-	-	O(1)	-	Non

*amorti

Exercice 00 : Échange Bitcoin

Analyse du sujet

Créer un programme qui :

Lit un fichier de base de données (CSV : date,taux_de_change)
Lit un fichier d’entrée (CSV : date | valeur)
Pour chaque ligne d’entrée, calcule valeur * taux_de_change
Utilise la date antérieure la plus proche si aucune correspondance exacte n’est trouvée

Contraintes clés :

Format de date : YYYY-MM-DD
Valeur d’entrée : nombre positif entre 0 et 1000
Doit gérer les entrées invalides gracieusement
Fichier de base de données fourni : data.csv

Stratégie d’approche

Réfléchissez avant de coder :

Quel conteneur pour la base de données ?
- std::map<std::string, float> - parfait pour clé-valeur avec clés triées
- Les dates en chaînes se trient correctement lexicographiquement (“2020-01-15” < “2020-02-01”)
Comment trouver la date antérieure la plus proche ?
- map::lower_bound(key) retourne un itérateur vers le premier élément >= clé
- S’il n’y a pas de correspondance exacte, revenir d’une position
Quelles validations sont nécessaires ?
- Format et validité de la date (années bissextiles !)
- La valeur est positive et <= 1000
- Format de ligne (contient |)

Construction progressive du code

Étape 1 : Structure de classe

#ifndef BITCOINEXCHANGE_HPP
#define BITCOINEXCHANGE_HPP

#include <map>
#include <string>

class BitcoinExchange {
private:
    std::map<std::string, float> _database;

    bool isValidDate(const std::string& date) const;
    bool isValidValue(const std::string& value, float& result) const;
    std::string trim(const std::string& str) const;

public:
    BitcoinExchange();
    BitcoinExchange(const BitcoinExchange& other);
    BitcoinExchange& operator=(const BitcoinExchange& other);
    ~BitcoinExchange();

    void loadDatabase(const std::string& filename);
    void processInput(const std::string& filename);
};

#endif

Étape 2 : Charger la base de données

#include "BitcoinExchange.hpp"
#include <fstream>
#include <sstream>
#include <iostream>

void BitcoinExchange::loadDatabase(const std::string& filename) {
    std::ifstream file(filename.c_str());
    if (!file.is_open()) {
        throw std::runtime_error("Error: could not open database file.");
    }

    std::string line;
    std::getline(file, line);  // Sauter l'en-tête

    while (std::getline(file, line)) {
        size_t comma = line.find(',');
        if (comma == std::string::npos) continue;

        std::string date = line.substr(0, comma);
        std::string rateStr = line.substr(comma + 1);

        float rate;
        std::istringstream iss(rateStr);
        if (iss >> rate) {
            _database[date] = rate;
        }
    }
}

Étape 3 : Validation de date

bool BitcoinExchange::isValidDate(const std::string& date) const {
    // Vérifier le format : YYYY-MM-DD (10 caractères)
    if (date.length() != 10) return false;
    if (date[4] != '-' || date[7] != '-') return false;

    // Extraire les parties
    int year, month, day;
    if (sscanf(date.c_str(), "%d-%d-%d", &year, &month, &day) != 3) {
        return false;
    }

    // Valider les plages
    if (year < 1 || month < 1 || month > 12 || day < 1) return false;

    // Jours par mois
    int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    // Vérification année bissextile
    bool isLeap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    if (isLeap) daysInMonth[2] = 29;

    return day <= daysInMonth[month];
}

bool BitcoinExchange::isValidValue(const std::string& value, float& result) const {
    std::istringstream iss(value);
    if (!(iss >> result)) return false;
    if (result < 0) return false;
    return true;
}

Étape 4 : Trouver la date la plus proche et traiter

void BitcoinExchange::processInput(const std::string& filename) {
    std::ifstream file(filename.c_str());
    if (!file.is_open()) {
        std::cerr << "Error: could not open file." << std::endl;
        return;
    }

    std::string line;
    std::getline(file, line);  // Sauter l'en-tête

    while (std::getline(file, line)) {
        size_t pipe = line.find(" | ");
        if (pipe == std::string::npos) {
            std::cerr << "Error: bad input => " << line << std::endl;
            continue;
        }

        std::string date = trim(line.substr(0, pipe));
        std::string valueStr = trim(line.substr(pipe + 3));

        // Valider la date
        if (!isValidDate(date)) {
            std::cerr << "Error: bad input => " << date << std::endl;
            continue;
        }

        // Valider la valeur
        float value;
        if (!isValidValue(valueStr, value)) {
            std::cerr << "Error: bad input => " << valueStr << std::endl;
            continue;
        }
        if (value < 0) {
            std::cerr << "Error: not a positive number." << std::endl;
            continue;
        }
        if (value > 1000) {
            std::cerr << "Error: too large a number." << std::endl;
            continue;
        }

        // Trouver la date la plus proche
        std::map<std::string, float>::iterator it = _database.lower_bound(date);
        if (it == _database.end() || it->first != date) {
            if (it == _database.begin()) {
                std::cerr << "Error: date too early => " << date << std::endl;
                continue;
            }
            --it;  // Aller à la date précédente (antérieure la plus proche)
        }

        float rate = it->second;
        std::cout << date << " => " << value << " = " << (value * rate) << std::endl;
    }
}

Explication ligne par ligne

Comprendre lower_bound :

Scénario	lower_bound retourne
Correspondance exacte	Itérateur vers cet élément
Pas de correspondance	Itérateur vers premier élément > clé
Tous les éléments < clé	Itérateur end()

std::map<std::string, float> db;
db["2020-01-01"] = 100;
db["2020-02-01"] = 200;
db["2020-03-01"] = 300;

// Cas 1 : Correspondance exacte
db.lower_bound("2020-02-01");  // Pointe vers 2020-02-01

// Cas 2 : Entre deux dates
db.lower_bound("2020-02-15");  // Pointe vers 2020-03-01
// On veut 2020-02-01, donc --it

// Cas 3 : Avant toutes les dates
db.lower_bound("2019-01-01");  // Pointe vers 2020-01-01
// Pas de date antérieure - erreur !

Calcul d’année bissextile :

bool isLeap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
// 2000 : bissextile (divisible par 400)
// 1900 : pas bissextile (divisible par 100 mais pas 400)
// 2020 : bissextile (divisible par 4, pas par 100)
// 2021 : pas bissextile

Pièges courants

1. Ne pas gérer le cas “plus tôt que la base de données” :

// FAUX : Suppose qu'il y a toujours une date antérieure
std::map<std::string, float>::iterator it = _database.lower_bound(date);
--it;  // Comportement indéfini si it == begin() !

// CORRECT : Vérifier begin()
if (it == _database.begin()) {
    std::cerr << "Error: date too early" << std::endl;
    continue;
}
--it;

2. Oublier les années bissextiles :

// FAUX : Février toujours 28 jours
int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// CORRECT : Vérifier l'année bissextile
if (isLeap) daysInMonth[2] = 29;

3. Mauvais format de pipe :

// FAUX : Le sujet utilise " | " (avec espaces)
size_t pipe = line.find("|");

// CORRECT : Chercher " | "
size_t pipe = line.find(" | ");

Conseils de test

Créer un fichier d’entrée de test :

date | value
2011-01-03 | 3
2011-01-03 | 2
2011-01-03 | 1
2011-01-03 | 1.2
2011-01-09 | 1
2012-01-11 | -1
2001-42-42
2012-01-11 | 1
2012-01-11 | 2147483648

Script de test :

./btc input.txt

# Sortie attendue :
# 2011-01-03 => 3 = 0.9
# 2011-01-03 => 2 = 0.6
# 2011-01-03 => 1 = 0.3
# 2011-01-03 => 1.2 = 0.36
# 2011-01-09 => 1 = 0.32
# Error: not a positive number.
# Error: bad input => 2001-42-42
# 2012-01-11 => 1 = 7.1
# Error: too large a number.

Code final

#ifndef BITCOINEXCHANGE_HPP
#define BITCOINEXCHANGE_HPP

#include <map>
#include <string>

class BitcoinExchange {
private:
    std::map<std::string, float> _database;

    bool isValidDate(const std::string& date) const;
    std::string trim(const std::string& str) const;

public:
    BitcoinExchange();
    BitcoinExchange(const BitcoinExchange& other);
    BitcoinExchange& operator=(const BitcoinExchange& other);
    ~BitcoinExchange();

    void loadDatabase(const std::string& filename);
    void processInput(const std::string& filename);
};

#endif

Exercice 01 : RPN (Notation polonaise inverse)

Analyse du sujet

Créer un programme qui :

Prend une expression RPN en argument
L’évalue et affiche le résultat
Les nombres sont toujours à un seul chiffre (< 10)
Opérateurs : +, -, *, /

RPN expliquée :

Normal : (3 + 4) * 2
RPN : 3 4 + 2 *
Lire de gauche à droite, pas besoin de parenthèses

Stratégie d’approche

Réfléchissez avant de coder :

Pourquoi utiliser une pile ?
- RPN utilise naturellement l’ordre LIFO
- Empiler les nombres, dépiler pour les opérations, empiler le résultat

Algorithme :

Pour chaque token :
  Si nombre : empiler sur la pile
  Si opérateur : dépiler deux, calculer, empiler le résultat
Réponse finale : seul élément sur la pile

L’ordre compte pour la soustraction/division :
- 5 3 - signifie 5 - 3 = 2, pas 3 - 5
- Dépiler b d’abord, puis a : résultat = a OP b

Construction progressive du code

Étape 1 : Structure de classe

#ifndef RPN_HPP
#define RPN_HPP

#include <stack>
#include <string>

class RPN {
private:
    std::stack<int> _stack;

    bool isOperator(char c) const;

public:
    RPN();
    RPN(const RPN& other);
    RPN& operator=(const RPN& other);
    ~RPN();

    int evaluate(const std::string& expression);
};

#endif

Étape 2 : Évaluation principale

#include "RPN.hpp"
#include <cctype>
#include <stdexcept>

bool RPN::isOperator(char c) const {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int RPN::evaluate(const std::string& expression) {
    // Vider la pile de toute exécution précédente
    while (!_stack.empty()) {
        _stack.pop();
    }

    for (size_t i = 0; i < expression.length(); i++) {
        char c = expression[i];

        // Sauter les espaces
        if (c == ' ') {
            continue;
        }

        // Nombre : empiler sur la pile
        if (std::isdigit(c)) {
            _stack.push(c - '0');
        }
        // Opérateur : dépiler deux, calculer, empiler le résultat
        else if (isOperator(c)) {
            if (_stack.size() < 2) {
                throw std::runtime_error("Error");
            }

            int b = _stack.top(); _stack.pop();
            int a = _stack.top(); _stack.pop();

            int result;
            switch (c) {
                case '+': result = a + b; break;
                case '-': result = a - b; break;
                case '*': result = a * b; break;
                case '/':
                    if (b == 0) {
                        throw std::runtime_error("Error");
                    }
                    result = a / b;
                    break;
                default:
                    throw std::runtime_error("Error");
            }
            _stack.push(result);
        }
        // Caractère invalide
        else {
            throw std::runtime_error("Error");
        }
    }

    // Doit avoir exactement un résultat
    if (_stack.size() != 1) {
        throw std::runtime_error("Error");
    }

    return _stack.top();
}

Explication ligne par ligne

Trace d’évaluation RPN :

Expression : "8 9 * 9 - 9 - 9 - 4 - 1 +"

Étape | Token | Pile (bas->haut) | Action
------|-------|------------------|--------
1     | 8     | [8]              | Empiler 8
2     | 9     | [8, 9]           | Empiler 9
3     | *     | [72]             | Dépiler 9,8; empiler 8*9=72
4     | 9     | [72, 9]          | Empiler 9
5     | -     | [63]             | Dépiler 9,72; empiler 72-9=63
6     | 9     | [63, 9]          | Empiler 9
7     | -     | [54]             | Dépiler 9,63; empiler 63-9=54
8     | 9     | [54, 9]          | Empiler 9
9     | -     | [45]             | Dépiler 9,54; empiler 54-9=45
10    | 4     | [45, 4]          | Empiler 4
11    | -     | [41]             | Dépiler 4,45; empiler 45-4=41
12    | 1     | [41, 1]          | Empiler 1
13    | +     | [42]             | Dépiler 1,41; empiler 41+1=42

Résultat : 42

Pourquoi dépiler b avant a ?

// Pour "5 3 -" :
// Pile après les empilements : [5, 3]  (3 au sommet)
int b = _stack.top(); _stack.pop();  // b = 3
int a = _stack.top(); _stack.pop();  // a = 5
result = a - b;  // 5 - 3 = 2 (correct !)

// Si on faisait a - b dans le mauvais sens :
// result = b - a;  // 3 - 5 = -2 (faux !)

Pièges courants

1. Mauvais ordre des opérandes :

// FAUX : Opérandes inversés
int a = _stack.top(); _stack.pop();
int b = _stack.top(); _stack.pop();
result = a - b;  // Mauvais ordre !

// CORRECT : b est dépilé en premier (était au sommet)
int b = _stack.top(); _stack.pop();
int a = _stack.top(); _stack.pop();
result = a - b;  // Correct !

2. Ne pas gérer la division par zéro :

// FAUX : Crash sur division par zéro
case '/': result = a / b; break;

// CORRECT : Vérifier d'abord
case '/':
    if (b == 0) throw std::runtime_error("Error");
    result = a / b;
    break;

3. Accepter des nombres à plusieurs chiffres :

// FAUX : Le sujet dit un seul chiffre uniquement
if (std::isdigit(c)) {
    // Analyser le nombre complet...
}

// CORRECT : Un seul chiffre seulement
if (std::isdigit(c)) {
    _stack.push(c - '0');  // Seulement 0-9
}

4. Ne pas valider l’état final de la pile :

// FAUX : Accepter n'importe quel état de pile
return _stack.top();

// CORRECT : Doit avoir exactement un résultat
if (_stack.size() != 1) {
    throw std::runtime_error("Error");
}
return _stack.top();

Conseils de test

#include <iostream>
#include "RPN.hpp"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " <expression>" << std::endl;
        return 1;
    }

    RPN calculator;
    try {
        int result = calculator.evaluate(argv[1]);
        std::cout << result << std::endl;
    } catch (std::exception& e) {
        std::cerr << e.what() << std::endl;
        return 1;
    }

    return 0;
}

Cas de test :

./RPN "8 9 * 9 - 9 - 9 - 4 - 1 +"  # 42
./RPN "7 7 * 7 -"                   # 42
./RPN "1 2 * 2 / 2 * 2 4 - +"      # 0
./RPN "(1 + 1)"                     # Error (parenthèses non autorisées)
./RPN "1 2 + +"                     # Error (pas assez d'opérandes)
./RPN "1 2"                         # Error (pas d'opérateur)
./RPN "5 0 /"                       # Error (division par zéro)

Code final

#ifndef RPN_HPP
#define RPN_HPP

#include <stack>
#include <string>

class RPN {
private:
    std::stack<int> _stack;
    bool isOperator(char c) const;

public:
    RPN();
    RPN(const RPN& other);
    RPN& operator=(const RPN& other);
    ~RPN();

    int evaluate(const std::string& expression);
};

#endif

#include "RPN.hpp"
#include <cctype>
#include <stdexcept>

RPN::RPN() {}
RPN::RPN(const RPN& other) : _stack(other._stack) {}
RPN& RPN::operator=(const RPN& other) {
    if (this != &other) _stack = other._stack;
    return *this;
}
RPN::~RPN() {}

bool RPN::isOperator(char c) const {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int RPN::evaluate(const std::string& expression) {
    while (!_stack.empty()) _stack.pop();

    for (size_t i = 0; i < expression.length(); i++) {
        char c = expression[i];

        if (c == ' ') continue;

        if (std::isdigit(c)) {
            _stack.push(c - '0');
        }
        else if (isOperator(c)) {
            if (_stack.size() < 2)
                throw std::runtime_error("Error");

            int b = _stack.top(); _stack.pop();
            int a = _stack.top(); _stack.pop();

            switch (c) {
                case '+': _stack.push(a + b); break;
                case '-': _stack.push(a - b); break;
                case '*': _stack.push(a * b); break;
                case '/':
                    if (b == 0) throw std::runtime_error("Error");
                    _stack.push(a / b);
                    break;
            }
        }
        else {
            throw std::runtime_error("Error");
        }
    }

    if (_stack.size() != 1)
        throw std::runtime_error("Error");

    return _stack.top();
}

Exercice 02 : PmergeMe

Analyse du sujet

Implémenter l’algorithme de tri par insertion-fusion Ford-Johnson :

Prendre des entiers positifs en arguments
Trier en utilisant deux conteneurs différents
Afficher : avant, après, temps pour chaque conteneur
Gérer au moins 3000 nombres

Format de sortie :

Before: 3 5 9 7 4
After:  3 4 5 7 9
Time to process a range of 5 elements with std::vector : 0.00031 us
Time to process a range of 5 elements with std::deque  : 0.00014 us

Stratégie d’approche

Réfléchissez avant de coder :

Qu’est-ce que Ford-Johnson ?
- Aussi appelé “tri par insertion-fusion”
- Minimise les comparaisons par un appariement astucieux
- Utilise l’insertion binaire avec la séquence de Jacobsthal

Algorithme simplifié :

1. Apparier les éléments adjacents
2. Mettre le plus grand dans la "chaîne principale", le plus petit dans "pend"
3. Trier récursivement la chaîne principale
4. Insérer les éléments de pend en utilisant la recherche binaire

Pourquoi deux conteneurs ?
- Le sujet exige une comparaison de performance
- vector : mémoire contiguë, cache-friendly
- deque : insertion rapide aux deux extrémités

Construction progressive du code

Étape 1 : Structure de classe

#ifndef PMERGEME_HPP
#define PMERGEME_HPP

#include <vector>
#include <deque>
#include <string>

class PmergeMe {
private:
    std::vector<int> _vec;
    std::deque<int>  _deq;

    void sortVector();
    void sortDeque();

public:
    PmergeMe();
    PmergeMe(const PmergeMe& other);
    PmergeMe& operator=(const PmergeMe& other);
    ~PmergeMe();

    void parseInput(int argc, char** argv);
    void sort();
    void displayBefore() const;
    void displayAfter() const;
};

#endif

Étape 2 : Analyser et valider l’entrée

#include "PmergeMe.hpp"
#include <cstdlib>
#include <stdexcept>
#include <iostream>

void PmergeMe::parseInput(int argc, char** argv) {
    for (int i = 1; i < argc; i++) {
        char* endptr;
        long num = std::strtol(argv[i], &endptr, 10);

        if (*endptr != '\0') {
            throw std::runtime_error("Error: invalid input.");
        }
        if (num <= 0) {
            throw std::runtime_error("Error: only positive integers.");
        }
        if (num > 2147483647) {
            throw std::runtime_error("Error: integer overflow.");
        }

        _vec.push_back(static_cast<int>(num));
        _deq.push_back(static_cast<int>(num));
    }
}

Étape 3 : Ford-Johnson pour vector

void PmergeMe::sortVector() {
    if (_vec.size() <= 1) return;

    std::vector<int> larger, smaller;
    bool hasOdd = (_vec.size() % 2 != 0);
    int oddElement = hasOdd ? _vec.back() : 0;

    // Étape 1 : Apparier les éléments
    size_t limit = hasOdd ? _vec.size() - 1 : _vec.size();
    for (size_t i = 0; i < limit; i += 2) {
        if (_vec[i] > _vec[i + 1]) {
            larger.push_back(_vec[i]);
            smaller.push_back(_vec[i + 1]);
        } else {
            larger.push_back(_vec[i + 1]);
            smaller.push_back(_vec[i]);
        }
    }

    // Étape 2 : Trier récursivement les éléments plus grands
    _vec = larger;
    sortVector();
    larger = _vec;

    // Étape 3 : Insérer les éléments plus petits en utilisant la recherche binaire
    for (size_t i = 0; i < smaller.size(); i++) {
        std::vector<int>::iterator pos =
            std::lower_bound(larger.begin(), larger.end(), smaller[i]);
        larger.insert(pos, smaller[i]);
    }

    // Étape 4 : Insérer l'élément impair s'il existe
    if (hasOdd) {
        std::vector<int>::iterator pos =
            std::lower_bound(larger.begin(), larger.end(), oddElement);
        larger.insert(pos, oddElement);
    }

    _vec = larger;
}

Étape 4 : Chronométrage

#include <ctime>

void PmergeMe::sort() {
    // Chronométrer le tri vector
    clock_t startVec = clock();
    sortVector();
    clock_t endVec = clock();
    double timeVec = (double)(endVec - startVec) / CLOCKS_PER_SEC * 1000000;

    // Chronométrer le tri deque
    clock_t startDeq = clock();
    sortDeque();
    clock_t endDeq = clock();
    double timeDeq = (double)(endDeq - startDeq) / CLOCKS_PER_SEC * 1000000;

    std::cout << "Time to process a range of " << _vec.size()
              << " elements with std::vector : " << timeVec << " us" << std::endl;
    std::cout << "Time to process a range of " << _deq.size()
              << " elements with std::deque  : " << timeDeq << " us" << std::endl;
}

Explication ligne par ligne

Trace de l’algorithme Ford-Johnson :

Entrée : [3, 5, 9, 7, 4, 1]

Étape 1 : Apparier et séparer
Paires : (3,5) (9,7) (4,1)
Plus grands : [5, 9, 4]
Plus petits : [3, 7, 1]

Étape 2 : Trier récursivement les plus grands
[5, 9, 4] -> [4, 5, 9]  (après récursion)

Étape 3 : Insérer les plus petits en utilisant la recherche binaire
Insérer 3 : [3, 4, 5, 9]
Insérer 7 : [3, 4, 5, 7, 9]
Insérer 1 : [1, 3, 4, 5, 7, 9]

Résultat : [1, 3, 4, 5, 7, 9]

Pourquoi lower_bound pour l’insertion ?

// lower_bound retourne un itérateur vers le premier élément >= valeur
std::vector<int> v = {1, 3, 5, 7};

// Insérer 4 :
std::vector<int>::iterator pos = std::lower_bound(v.begin(), v.end(), 4);
// pos pointe vers 5 (premier élément >= 4)
v.insert(pos, 4);
// v = {1, 3, 4, 5, 7}

Pièges courants

1. Ne pas implémenter le vrai Ford-Johnson :

// FAUX : Utiliser simplement std::sort
void sortVector() {
    std::sort(_vec.begin(), _vec.end());
}

// CORRECT : Implémenter l'appariement et l'insertion-fusion récursive

2. Oublier l’élément impair :

// FAUX : Ignore l'élément impair
for (size_t i = 0; i < _vec.size(); i += 2) {
    // Paires seulement
}

// CORRECT : Gérer l'élément impair séparément
bool hasOdd = (_vec.size() % 2 != 0);
int oddElement = hasOdd ? _vec.back() : 0;
size_t limit = hasOdd ? _vec.size() - 1 : _vec.size();

3. Chronométrer la mauvaise chose :

// FAUX : Inclure l'analyse dans le chronométrage
clock_t start = clock();
parseInput(argc, argv);  // Faux !
sortVector();
clock_t end = clock();

// CORRECT : Chronométrer seulement le tri
parseInput(argc, argv);
clock_t start = clock();
sortVector();
clock_t end = clock();

4. Utiliser le même conteneur :

// FAUX : Le sujet exige DEUX conteneurs différents
std::vector<int> _data1;
std::vector<int> _data2;  // Les deux sont des vectors !

// CORRECT : Types de conteneurs différents
std::vector<int> _vec;
std::deque<int>  _deq;

Conseils de test

# Générer des nombres de test
./PmergeMe 3 5 9 7 4

# Test avec des nombres aléatoires
./PmergeMe `shuf -i 1-100000 -n 3000 | tr "\n" " "`

# Vérifier le tri
./PmergeMe 5 4 3 2 1
# Devrait afficher : Before: 5 4 3 2 1
#                    After:  1 2 3 4 5

Script de vérification :

#!/bin/bash
# Générer des nombres aléatoires, trier, et vérifier
NUMS=$(shuf -i 1-10000 -n 100 | tr "\n" " ")
./PmergeMe $NUMS 2>&1 | head -2

# Comparer avec la commande sort
echo "Attendu : $(echo $NUMS | tr " " "\n" | sort -n | tr "\n" " ")"

Code final

#ifndef PMERGEME_HPP
#define PMERGEME_HPP

#include <vector>
#include <deque>

class PmergeMe {
private:
    std::vector<int> _vec;
    std::deque<int>  _deq;

    void sortVector();
    void sortDeque();

public:
    PmergeMe();
    PmergeMe(const PmergeMe& other);
    PmergeMe& operator=(const PmergeMe& other);
    ~PmergeMe();

    void parseInput(int argc, char** argv);
    void sort();
    void displayBefore() const;
    void displayAfter() const;
};

#endif

#include <iostream>
#include "PmergeMe.hpp"

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "Usage: " << argv[0] << " <numbers...>" << std::endl;
        return 1;
    }

    try {
        PmergeMe sorter;
        sorter.parseInput(argc, argv);
        sorter.displayBefore();
        sorter.sort();
        sorter.displayAfter();
    } catch (std::exception& e) {
        std::cerr << e.what() << std::endl;
        return 1;
    }

    return 0;
}

Résumé du Module 09

Exercice	Conteneur	Algorithme
ex00	`std::map`	lower_bound pour recherche date
ex01	`std::stack`	Évaluation RPN (LIFO)
ex02	`vector` + `deque`	Insertion-fusion Ford-Johnson

Points clés à retenir :

Choisissez les conteneurs judicieusement - chacun a ses forces
Algorithmes STL - lower_bound, sort, find font gagner du temps
La performance compte - mesurez avec clock()
Validez l’entrée - une gestion robuste des erreurs est essentielle

Référence rapide

Conseils d’analyse

// String vers int
int n = std::atoi(str.c_str());

// String vers float
float f = std::atof(str.c_str());

// Diviser une chaîne
size_t pos = str.find(delimiter);
std::string first = str.substr(0, pos);
std::string second = str.substr(pos + 1);

Chronométrage

clock_t start = clock();
// ... code ...
clock_t end = clock();
double microseconds = (double)(end - start) / CLOCKS_PER_SEC * 1000000;

Recherche binaire (pour insertion)

std::vector<int>::iterator pos = std::lower_bound(v.begin(), v.end(), value);
v.insert(pos, value);

Concepts connexes

Vous avez terminé les modules de la Piscine C++ ! Maintenant préparez-vous pour l’examen :

Précédent : Module 08 : Conteneurs STL - Réviser les fondamentaux des conteneurs
Suivant : Exam Rank 04 - Se préparer pour l’examen pratique

Module 09 : Applications pratiques de la STL

Pourquoi c’est important

Comprendre la syntaxe STL avancée

L’algorithme lower_bound

L’opération insert

Le static_cast<double> pour le chronométrage

Les fonctions std::atoi et std::atof

L’operator[] avec les maps

1. Règles du module

Restrictions sur les conteneurs

Allocation suggérée des conteneurs

2. Exercice 00 : Échange Bitcoin

Problème

Format d’entrée

Approche de solution

std::getline pour la lecture ligne par ligne

map::lower_bound pour une recherche efficace

Validation de date avec logique d’année bissextile

Exemples d’années bissextiles

3. Exercice 01 : Notation polonaise inverse (RPN)

Problème

Comment fonctionne la RPN

Solution

4. Opération vector::insert

Insérer à une position

Insérer avec lower_bound (insertion triée)

Performance d’insertion

5. Opérations sur deque

deque - File à double extrémité

deque vs vector

6. Exercice 02 : PmergeMe (Algorithme Ford-Johnson)

Problème

Vue d’ensemble de l’algorithme Ford-Johnson

Pourquoi Ford-Johnson ?

Séquence de Jacobsthal (Optimisation optionnelle)

Implémentation simplifiée

Exemple pas à pas

Utiliser deux conteneurs différents

Chronométrage

7. Pièges courants

Exercice 00

Exercice 01

Exercice 02

8. Résumé des propriétés des conteneurs

Exercice 00 : Échange Bitcoin

Analyse du sujet

Stratégie d’approche

Construction progressive du code

Explication ligne par ligne

Pièges courants

Conseils de test

Code final

Exercice 01 : RPN (Notation polonaise inverse)

Analyse du sujet

Stratégie d’approche

Construction progressive du code

Explication ligne par ligne

Pièges courants

Conseils de test

Code final

Exercice 02 : PmergeMe

Analyse du sujet

Stratégie d’approche

Construction progressive du code

Explication ligne par ligne

Pièges courants

Conseils de test

Code final

Résumé du Module 09

Référence rapide

Conseils d’analyse

Chronométrage

Recherche binaire (pour insertion)

Concepts connexes

L’algorithme `lower_bound`

L’opération `insert`

Le `static_cast<double>` pour le chronométrage

Les fonctions `std::atoi` et `std::atof`

L’`operator[]` avec les maps