La bibliothèque standard de modèles (STL) en C++ est un pilier fondamental pour le développement d'algorithmes efficaces. Elle s'articule autour de trois composants principaux : les conteneurs (structures de données), les algorithmes (opérations de traitement) et les itérateurs (pointeurs intelligents pour parcourir les conteneurs). Cet article explore en détail les conteneurs séquentiels et associatifs les plus couramment utilisés.
Le conteneur vector
Le std::vector est l'équivalent dynamique des tableaux statiques. Contrairement à ces derniers, il ajuste automtaiquement sa capacité en allouant un nouveau bloc de mémoire plus grand et en y copiant les éléments existants lorsque l'espace initial est saturé.
Initialisation et duplication
#include <vector>
#include <iostream>
int main() {
std::vector<int> primaryVec;
for (int idx = 0; idx < 10; ++idx) {
primaryVec.push_back(idx * 2);
}
// Duplication par assignation d'itérateurs
std::vector<int> secondaryVec;
secondaryVec.assign(primaryVec.begin(), primaryVec.end());
// Duplication par constructeur de copie
std::vector<int> tertiaryVec(primaryVec);
return 0;
}
Manipulation de la capacité et des éléments
push_back(val)/pop_back(): Ajout et suppression à la fin.insert(it, val)/erase(it): Insertion et suppression à une position spécifique via itérateur.size()/capacity()/empty(): Enformations sur l'état du conteneur.reserve(n): Préallocation de mémoire pour éviter les réallocations fréquentes.resize(n, val): Modifie la taille logique, en initialisant les nouveaux éléments avecval.
Parcours et accès
#include <vector>
#include <algorithm>
#include <iostream>
void displayElement(int val) {
std::cout << val << " ";
}
int main() {
std::vector<int> dataVec = {10, 20, 30, 40, 50};
// Accès direct
std::cout << "Premier : " << dataVec.front() << ", Dernier : " << dataVec.back() << "\n";
std::cout << "Index 2 : " << dataVec.at(2) << "\n";
// Parcours avec itérateurs
for (auto it = dataVec.begin(); it != dataVec.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n";
// Parcours avec l'algorithme for_each
std::for_each(dataVec.begin(), dataVec.end(), displayElement);
return 0;
}
Le conteneur deque
Le std::deque (double-ended queue) permet des insertions et suppressions rapides aux deux extrémités. Il ne possède pas de notion de capacity comme le vector, car sa structure mémoire est segmentée.
#include <deque>
#include <algorithm>
#include <iostream>
int main() {
std::deque<int> dque;
dque.push_back(15);
dque.push_front(5); // Spécifique au deque
// Tri des éléments
std::sort(dque.begin(), dque.end());
for (const auto& elem : dque) {
std::cout << elem << " ";
}
return 0;
}
La classe string
La classe std::string encapsule la gestion des chaînes de caractères, offrant des méthodes robustes pour la manipulation de texte.
Opérations courantes
#include <string>
#include <iostream>
int main() {
std::string baseStr = "Programmation";
std::string suffix = " C++";
// Concaténation
baseStr += suffix;
baseStr.append(" moderne");
// Recherche
size_t pos = baseStr.find("C++");
if (pos != std::string::npos) {
std::cout << "Trouvé à l'index : " << pos << "\n";
}
// Extraction et modification
std::string sub = baseStr.substr(0, 13);
sub.replace(0, 1, "p"); // Remplace le premier caractère
// Insertion et suppression
sub.insert(5, "xyz");
sub.erase(5, 3); // Supprime 3 caractères à partir de l'index 5
std::cout << sub << "\n";
return 0;
}
Comptage d'occurrences
#include <string>
#include <iostream>
int main() {
std::string text = "algorithmique et algorithmes";
std::string target = "algo";
size_t currentPos = 0;
int occurrences = 0;
while ((currentPos = text.find(target, currentPos)) != std::string::npos) {
occurrences++;
currentPos += target.length();
}
std::cout << "Occurrences : " << occurrences << "\n";
return 0;
}
Les adaptateurs stack et queue
Le std::stack suit le principe LIFO (Last-In, First-Out), tandis que le std::queue suit le principe FIFO (First-In, First-Out).
#include <stack>
#include <queue>
#include <iostream>
int main() {
// Stack (LIFO)
std::stack<int> pile;
for (int i = 1; i <= 3; ++i) pile.push(i * 10);
while (!pile.empty()) {
std::cout << pile.top() << " ";
pile.pop();
}
std::cout << "\n";
// Queue (FIFO)
std::queue<int> file;
for (int i = 1; i <= 3; ++i) file.push(i * 10);
while (!file.empty()) {
std::cout << file.front() << " ";
file.pop();
}
std::cout << "\n";
return 0;
}
Le conteneur list
Le std::list est une liste doublement chaînée. Il ne supporte pas l'accès aléatoire, ce qui implique que l'algorithme std::sort ne peut pas être utilisé directement. Il faut utiliser sa méthode membre sort().
#include <list>
#include <iostream>
int main() {
std::list<int> linkedList = {40, 10, 30, 20, 10};
// Tri et suppression des doublons spécifiques
linkedList.sort();
linkedList.remove(10);
linkedList.reverse();
// Insertion à une position spécifique
auto it = linkedList.begin();
std::advance(it, 2);
linkedList.insert(it, 99);
for (int val : linkedList) {
std::cout << val << " ";
}
return 0;
}
Les conteneurs associatifs set et multiset
Ces conteneurs stockent des éléments uniques (set) ou autorisent les doublons (multiset). Les éléments sont automatiquement triés via une structure d'arbre binaire de recherche (généralement un arbre rouge-noir).
#include <set>
#include <iostream>
// Foncteur (Functor) pour un tri décroissant
struct DescendingOrder {
bool operator()(int a, int b) const {
return a > b;
}
};
int main() {
std::set<int, DescendingOrder> uniqueSet;
uniqueSet.insert(50);
uniqueSet.insert(20);
uniqueSet.insert(80);
std::multiset<int> multiSet;
multiSet.insert(15);
multiSet.insert(15); // Autorisé
// Recherche
if (uniqueSet.find(20) != uniqueSet.end()) {
std::cout << "20 est présent dans le set.\n";
}
// Statistiques
std::cout << "Nombre de 15 dans multiset : " << multiSet.count(15) << "\n";
return 0;
}
Les conteneurs map et multimap
Le std::map associe des clés uniques à des valeurs, tandis que le std::multimap permet plusieurs valeurs pour une même clé. Les éléments sont des paires (std::pair) et sont triés par clé.
#include <map>
#include <string>
#include <iostream>
struct ReverseStringCompare {
bool operator()(const std::string& s1, const std::string& s2) const {
return s1 > s2;
}
};
int main() {
std::map<std::string, int, ReverseStringCompare> scores;
// Insertion de paires
scores.insert(std::make_pair("Alice", 95));
scores["Bob"] = 85;
scores.emplace("Charlie", 90);
// Parcours
for (const auto& pair : scores) {
std::cout << "Joueur : " << pair.first
<< ", Score : " << pair.second << "\n";
}
return 0;
}