Structures pair

La structure std::pair permet de grouper deux éléments de types potentiellement différents. Elle est analogue à une structure personnalisée simple. Les éléments sont accessibles via les membres first et second.

Exemple d'utilisation de pair

#include <iostream>
#include <string>
#include <utility> // Nécessaire pour std::pair et std::make_pair

int main() {
    std::pair<int, int> simplePair;
    simplePair.first = 10;
    simplePair.second = 20;
    std::cout << "Simple Pair: " << simplePair.first << " " << simplePair.second << std::endl;

    std::pair<std::string, int> namedPair("Example", 42);
    std::cout << "Named Pair: " << namedPair.first << " " << namedPair.second << std::endl;

    // Utilisation de make_pair pour créer une paire
    std::pair<int, int> assignedPair = std::make_pair(30, 40);
    std::cout << "Assigned Pair: " << assignedPair.first << " " << assignedPair.second << std::endl;

    // Paire imbriquée
    std::pair<int, std::pair<int, int>> nestedPair;
    nestedPair.first = 5;
    nestedPair.second.first = 6;
    nestedPair.second.second = 7;
    std::cout << "Nested Pair: " << nestedPair.first << " " << nestedPair.second.first << " " << nestedPair.second.second << std::endl;

    return 0;
}

Conteneur std::vector

std::vector est un conteneur dynamique qui permet de stocker une séquence d'éléments. Il gère automatiquement l'allocation et la désallocation de mémoire.

Opérations courantes sur vector

• clear() : Supprime tous les éléments.
• empty() : Vérifie si le vecteur est vide.
• erase(iterator pos) : Supprime l'élément à la position spécifiée.
• erase(iterator first, iterator last) : Supprime les éléments dans l'intervalle [first, last).
• front() : Renvoie le premier élément.
• insert(iterator pos, const T& value) : Insère une copie de value avant la position pos.
• pop_back() : Supprime le dernier élément.
• push_back(const T& value) : Ajoute value à la fin.
• resize(size_type count) : Redimensionne le vecteur pour contenir count éléments.
• size() : Renvoie le nombre d'éléments.
• begin() : Renvoie un itérateur vers le premier élément.
• end() : Renvoie un itérateur vers l'élément suivant le dernier.
• shrink_to_fit() : Demande la réduction de la capacité au minimum nécessaire.
• capacity() : Renvoie la capacité actuelle du vecteur.
• reserve(size_type new_cap) : Alloue de la mémoire pour au moins new_cap éléments.

Exemple d'utilisation de vector

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // Pour std::sort

int main() {
    std::vector<int> dataVector;

    // Ajout d'éléments
    for (int i = 0; i < 10; ++i) {
        dataVector.push_back((i * i * i) % 23);
    }

    std::cout << "Capacite initiale: " << dataVector.capacity() << std::endl;
    dataVector.reserve(20); // Augmentation de la capacité réservée
    std::cout << "Capacite apres reserve: " << dataVector.capacity() << std::endl;

    // Suppression d'un élément
    if (dataVector.size() > 5) {
        dataVector.erase(dataVector.begin() + 5);
    }

    // Insertion d'un élément
    dataVector.insert(dataVector.begin() + 5, 114514);

    std::cout << "Elements apres insertion/suppression: ";
    for (int val : dataVector) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Parcours avec itérateur
    std::cout << "Parcours avec iterateur: ";
    for (std::vector<int>::iterator it = dataVector.begin(); it != dataVector.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // Parcours inversé
    std::cout << "Parcours inverse: ";
    for (int i = dataVector.size() - 1; i >= 0; --i) {
        std::cout << dataVector[i] << " ";
    }
    std::cout << std::endl;

    // Parcours avec range-based for loop
    std::cout << "Range-based for loop: ";
    for (const auto& element : dataVector) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    // Suppression du dernier élément
    dataVector.pop_back();
    std::cout << "Apres pop_back: ";
    for (int val : dataVector) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Suppression d'un intervalle
    if (dataVector.size() > 3) {
        dataVector.erase(dataVector.begin() + 3, dataVector.begin() + 4);
    }
    std::cout << "Apres erase(intervalle): ";
    for (int val : dataVector) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Vidage du vecteur
    dataVector.clear();
    std::cout << "Taille apres clear: " << dataVector.size() << std::endl;

    // Redimensionnement
    dataVector.resize(5);
    std::cout << "Taille apres resize(5): " << dataVector.size() << std::endl;

    std::cout << "Taille maximale possible: " << dataVector.max_size() << std::endl;

    // Vecteur de vecteurs (matrice)
    int rows = 5, cols = 6;
    std::vector<std::vector<int>> matrix(rows, std::vector<int>(cols));
    std::cout << "Nombre de lignes: " << matrix.size() << std::endl;
    if (!matrix.empty()) {
        std::cout << "Nombre de colonnes (ligne 0): " << matrix[0].size() << std::endl;
    }

    // Tri du vecteur
    for (int i = 1; i <= 10; ++i) {
        dataVector.push_back((i * i * i * i * i) % 37);
    }
    std::sort(dataVector.begin(), dataVector.end());
    std::cout << "Vecteur apres tri: ";
    for (int val : dataVector) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    std::cout << "Capacite apres ajout et tri: " << dataVector.capacity() << std::endl;
    dataVector.shrink_to_fit(); // Libération de la mémoire inutilisée
    std::cout << "Capacite apres shrink_to_fit: " << dataVector.capacity() << std::endl;

    return 0;
}

Conteneur std::map

std::map est un conteneur associatif qui stocke des paires clé-valeur, triées par clé. Les clés sont uniques.

Exemple d'utilisation de map

#include <iostream>
#include <map>
#include <string>
#include <unordered_map> // Inclus pour la référence, mais non utilisé dans cet exemple map

int main() {
    std::map<std::string, int> wordCounts;

    // Insertion de paires clé-valeur
    wordCounts["apple"] = 5;
    wordCounts.insert(std::map<std::string, int>::value_type("banana", 2));
    wordCounts.insert(std::make_pair("cherry", 8));
    wordCounts["date"] = 1;

    std::cout << "Counts: ";
    std::cout << wordCounts["apple"] << " " << wordCounts["banana"] << " " << wordCounts["cherry"] << " " << wordCounts["date"] << std::endl;

    // Tentative d'insertion d'une clé existante (ne modifie pas si la valeur est différente)
    wordCounts.insert({"banana", 10}); // Cette insertion échouera car "banana" existe déjà
    wordCounts["apple"] = 7;          // Modification de la valeur existante
    std::cout << "Apple count after update: " << wordCounts["apple"] << std::endl;
    std::cout << "Banana count (unchanged by insert): " << wordCounts["banana"] << std::endl;

    // Accès à une clé inexistante (crée la clé avec une valeur par défaut)
    int unknownCount = wordCounts["grape"]; // Crée "grape" avec la valeur 0
    std::cout << "Grape count (default initialized): " << unknownCount << std::endl;
    std::cout << "Map size after accessing grape: " << wordCounts.size() << std::endl;

    // Recherche d'un élément
    auto it = wordCounts.find("cherry");
    if (it != wordCounts.end()) {
        std::cout << "Found cherry: " << it->second << std::endl;
    } else {
        std::cout << "Cherry not found." << std::endl;
    }

    // Vérification de l'existence d'une clé
    if (wordCounts.count("date")) {
        std::cout << "Date key exists." << std::endl;
    } else {
        std::cout << "Date key does not exist." << std::endl;
    }

    // Parcours du map (trié par clé)
    std::cout << "Iterating through map:" << std::endl;
    for (auto const& [key, val] : wordCounts) {
        std::cout << key << ": " << val << std::endl;
    }

    // Autre façon de parcourir avec itérateur
    std::cout << "Iterating with iterator:" << std::endl;
    for (auto iter = wordCounts.begin(); iter != wordCounts.end(); ++iter) {
        std::cout << iter->first << " => " << iter->second << std::endl;
    }

    // Suppression d'un élément par itérateur
    auto erase_it = wordCounts.find("grape");
    if (erase_it != wordCounts.end()) {
        wordCounts.erase(erase_it);
    }

    std::cout << "Map after erasing grape:" << std::endl;
    for (const auto& pair : wordCounts) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    // Vider le map
    wordCounts.clear();
    if (wordCounts.empty()) {
        std::cout << "Map is empty." << std::endl;
    }

    return 0;
}

Conteneur std::set

std::set est un conteneur qui stocke des éléments uniques, triés par ordre croissant. Les opérations d'insertion, de suppression et de recherche ont une complexité logarithmique.

Exemple d'utilisation de set

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<int> numberSet;

    // Insertion d'éléments (les doublons sont ignorés)
    numberSet.insert(114514);
    numberSet.insert(1);
    numberSet.insert(2);
    numberSet.insert(1); // Ignoré
    numberSet.insert(8);

    std::cout << "Set elements (forward): ";
    // Parcours en ordre croissant
    for (int val : numberSet) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    std::cout << "Set elements (reverse): ";
    // Parcours en ordre décroissant
    for (auto rit = numberSet.rbegin(); rit != numberSet.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    std::cout << "Max elements: " << numberSet.max_size() << std::endl;
    std::cout << "Current size: " << numberSet.size() << std::endl;

    // Suppression d'éléments
    numberSet.erase(114514); // Supprime la valeur 114514
    numberSet.erase(99);     // Ne fait rien si la valeur n'existe pas

    std::cout << "Set after erasing: ";
    for (int val : numberSet) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Recherche avec lower_bound et upper_bound
    auto lower = numberSet.lower_bound(3); // Premier élément >= 3
    if (lower != numberSet.end()) {
        std::cout << "Lower bound for 3: " << *lower << std::endl;
    }

    auto upper = numberSet.upper_bound(1); // Premier élément > 1
    if (upper != numberSet.end()) {
        std::cout << "Upper bound for 1: " << *upper << std::endl;
    }

    // Vider le set
    numberSet.clear();
    if (numberSet.empty()) {
        std::cout << "Set is empty." << std::endl;
    }

    return 0;
}

Fonctions algorithmiques

Recherche binaire

Les fonctions std::binary_search, std::lower_bound et std::upper_bound sont efficaces pour rechercher des éléments dans des séquences triées.

• std::binary_search(first, last, value) : Renvoie true si value est trouvé dans l'intervalle [first, last), false sinon.
• std::lower_bound(first, last, value) : Renvoie un itérateur vers le premier élément dans l'intervalle qui n'est pas inférieur à value.
• std::upper_bound(first, last, value) : Renvoie un itérateur vers le premier élément dans l'intervalle qui est supérieur à value.
• std::upper_bound(first, last, value, comp) : Identique à std::upper_bound, mais utilise une fonction de comparaison personnalisée comp. Utile pour les séquences triées dans l'ordre décroissant.

std::unique

std::unique supprime les éléments consécutifs dupliqués dans une plage triée. Il réorganise la plage de sorte que les éléments uniques apparaissent au début, et renvoie un itérateur vers la fin de la plage unique. Il est souvent utilisé en combinaison avec std::sort.

Exemple d'utilisation de std::unique

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath> // Pour std::pow

int main() {
    std::vector<long long> numbers;
    int n = 20; // Taille de l'exemple
    int m = 3;  // Paramètre pour la génération de nombres

    // Génération de nombres potentiellement dupliqués
    for (int i = 1; i <= n; ++i) {
        numbers.push_back(static_cast<long long>(std::pow(i, m)) % 1997);
    }

    std::cout << "Original numbers: ";
    for (long long num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Trier pour que unique fonctionne correctement sur les doublons
    std::sort(numbers.begin(), numbers.end());

    std::cout << "Sorted numbers: ";
    for (long long num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Utilisation de std::unique
    // Il renvoie un itérateur vers le nouvel "end" logique
    auto last_unique = std::unique(numbers.begin(), numbers.end());

    // Suppression physique des éléments dupliqués restants
    numbers.erase(last_unique, numbers.end());

    std::cout << "Numbers after unique: ";
    for (long long num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::next_permutation

std::next_permutation réorganise la plage [first, last) dans l'ordre lexicographique de permutation suivant. Il renvoie true s'il a pu générer la permutation suivante, et false si la permutation actuelle est la dernière possible (l'ordre lexicographique décroissant), auquel cas il réorganise la plage dans le premier ordre (ordre croissant).

Exemple d'utilisation de std::next_permutation

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // Pour std::iota

int main() {
    int count = 5; // Nombre d'éléments pour générer les permutations
    std::vector<int> p(count);

    // Initialiser le vecteur avec les nombres 1 à 'count'
    std::iota(p.begin(), p.end(), 1); // p devient {1, 2, 3, 4, 5}

    std::cout << "Generating permutations for: ";
    for(int x : p) std::cout << x << " ";
    std::cout << std::endl;

    int permutation_count = 0;
    // Générer toutes les permutations
    do {
        permutation_count++;
        std::cout << "Permutation " << permutation_count << ": ";
        for (int i = 0; i < p.size(); ++i) {
            std::cout << p[i] << (&i == &p.size() - 1 ? "" : " ");
        }
        std::cout << std::endl;
    } while (std::next_permutation(p.begin(), p.end()));

    std::cout << "Total permutations generated: " << permutation_count << std::endl;

    // Afficher la dernière permutation (l'ordre initial si on avait commencé par le dernier)
    std::cout << "Final arrangement (lexicographically smallest): ";
    for(int x : p) std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

Conteneur std::list

std::list est une liste doublement chaînée qui permet des insertions et suppressions efficaces en n'importe quelle position, mais un accès aux éléments moins efficace que std::vector.

Opérations courantes sur list

• assign(count, value) : Assigne de nouvelles valeurs, remplaçant le contenu existant.
• back() : Renvoie le dernier élément.
• begin() : Renvoie un itérateur vers le premier élément.
• clear() : Supprime tous les éléments.
• empty() : Vérifie si la liste est vide.
• end() : Renvoie un itérateur vers l'élément suivant le dernier.
• erase(iterator pos) : Supprime l'élément à la position spécifiée.
• erase(iterator first, iterator last) : Supprime les éléments dans l'intervalle [first, last).
• front() : Renvoie le premier élément.
• insert(iterator pos, const T& value) : Insère une copie de value avant la position pos.
• max_size() : Renvoie le nombre maximum d'éléments que la liste peut contenir.
• merge(list& other) : Fusionne la liste other dans la liste actuelle (les deux listes doivent être triées).
• pop_back() : Supprime le dernier élément.
• pop_front() : Supprime le premier élément.
• push_back(const T& value) : Ajoute value à la fin.
• push_front(const T& value) : Ajoute value au début.
• rbegin() : Renvoie un itérateur inversé vers le premier élément (qui est le dernier dans l'ordre normal).
• remove(const T& value) : Supprime toutes les occurrences de value.
• remove_if(Predicate pred) : Supprime tous les éléments pour lesquels le prédicat pred renvoei true.
• rend() : Renvoie un itérateur inversé vers la fin (qui est le début dans l'ordre normal).
• resize(size_type count) : Redimensionne la liste.
• reverse() : Inverse l'ordre des éléments.
• size() : Renvoie le nombre d'éléments.
• sort() : Trie la liste.
• splice(iterator pos, list& other) : Déplace tous les éléments de other dans la liste actuelle avant la position pos.
• swap(list& other) : Échange le contenu des deux listes.
• unique() : Supprime les éléments consécutifs dupliqués.

Exemple d'utilisation de list

#include <iostream>
#include <list>
#include <string>
#include <algorithm> // Pour std::for_each

// Fonction prédicat pour remove_if
bool is_not_two(int val) {
    return val != 2;
}

int main() {
    std::list<int> myList;

    // Ajout d'éléments
    myList.push_back(1);
    myList.push_back(2);

    // Insertion
    auto it = myList.begin();
    myList.insert(it, 114514); // Ajoute avant le premier élément
    myList.insert(it, 114514); // Ajoute encore avant, le premier 114514 est maintenant avant le second

    std::cout << "List after insertions: ";
    for (int val : myList) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Suppression par valeur
    myList.remove(114514); // Supprime toutes les occurrences de 114514

    // Pour insérer après le nouvel 'it', il faut le réactualiser ou avancer
    // Ici, 'it' pointe toujours sur l'ancien début qui est maintenant 1
    // On va insérer après le '1'
    it = myList.begin(); // Réinitialisation de l'itérateur au début (qui est 1)
    std::advance(it, 1); // Avance l'itérateur pour pointer sur le 2
    myList.insert(it, 1919810); // Insère 1919810 avant le 2

    std::cout << "List after remove and insert: ";
    for (int val : myList) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Suppression par itérateur
    it = myList.begin(); // Retourne au début (qui est maintenant 1)
    ++it; // Pointe sur 1919810
    myList.erase(it); // Supprime 1919810

    std::cout << "List after erasing by iterator: ";
    for (int val : myList) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Échange de listes
    std::list<int> otherList(3, 2); // Liste avec 3 éléments, tous valant 2
    myList.swap(otherList);

    std::cout << "List after swap: ";
    for (int val : myList) { // myList contient maintenant {2, 2, 2}
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Tri
    myList.sort(); // Trier {2, 2, 2} n'a pas d'effet visible

    // Fusion (les deux listes doivent être triées)
    // otherList est vide après swap
    // Pour démontrer merge, créons une nouvelle liste triée
    std::list<int> mergeList;
    mergeList.push_back(0);
    mergeList.push_back(3);
    mergeList.sort(); // mergeList est {0, 3}
    myList.sort(); // myList est {2, 2, 2}
    myList.merge(mergeList); // myList devient {0, 2, 2, 2, 3}

    std::cout << "List after merge: ";
    for (int val : myList) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Splice
    std::list<int> spliceSource(3, 5); // {5, 5, 5}
    myList.splice(myList.begin(), spliceSource); // Déplace les éléments de spliceSource au début de myList

    std::cout << "List after splice: ";
    for (int val : myList) { // myList est maintenant {5, 5, 5, 0, 2, 2, 2, 3}
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Parcours inversé
    std::cout << "List reverse iteration: ";
    for (auto rit = myList.rbegin(); rit != myList.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    // Suppression conditionnelle
    myList.push_front(1); // Ajoute 1 au début
    myList.remove_if(is_not_two); // Supprime tout ce qui n'est PAS égal à 2

    std::cout << "List after remove_if(is_not_two): ";
    for (int val : myList) { // Devrait contenir uniquement des 2
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Assigner de nouvelles valeurs
    myList.assign(3, 4); // Remplace le contenu par trois 4

    std::cout << "List after assign(3, 4): ";
    for (int val : myList) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Suppression des doublons consécutifs
    myList.push_back(4);
    myList.unique(); // Supprime le doublon de 4

    std::cout << "List after unique: ";
    for (int val : myList) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Vider la liste
    myList.clear();
    if (myList.empty()) {
        std::cout << "List is empty." << std::endl;
    }

    return 0;
}