Conteneurs Associatifs en C++: `std::map` et `std::set`

Cette section explore l'utilisation des conteneurs associatifs std::map et std::set de la Standard Template Library (STL) en C++.

1. Concepts Fondamentaux

1.1 Conteneurs Séquentiels et Associatifs

La STL C++ inclut deux catégories principales de conteneurs :

Conteneurs Séquentiels : Ils stockent des éléments dans un ordre linéaire et maintiennent leur position relative. L'accès se fait généralement par indice ou itérateur. Exemples : std::vector, std::list, std::deque, std::forward\_list (C++11).
Conteneurs Associatifs : Ils stockent des paires clé-valeur (ou simplement des clés pour std::set) et sont optimisés pour une recherche rapide basée sur la clé. Leur structure logique est généralement non linéaire (arborescente ou hachée). Exemples : std::set, std::map, std::unordered\_set, std::unordered\_map.

Il est à noter que std::stack, std::queue et std::priority\_queue sont des adaptateurs de conteneurs, utilisant par défaut std::deque ou std::vector comme conteneur sous-jacent.

1.2 La Paire Clé-Valeur (`std::pair`)

Une paire clé-valeur est une structure simple pour représenter une relation un-à-un, comprenant généralement deux membres : une clé (key) et une valeur (value). La clé sert à identifier l'information, et la valeur est l'information associée à cette clé.

Imaginez un dictionnaire anglais-français : chaque mot anglais est une clé, et sa traduction française est la valeur correspondante. Chaque clé est unique et est associée à une seule valeur.

En C++, la structure std::pair est utilisée pour cela. Voici une version simplifiée de sa définition :

template <class Type1, class Type2>
struct pair
{
   typedef Type1 first_type;
   typedef Type2 second_type;
   Type1 first;   // Représente la clé
   Type2 second;  // Représente la valeur
   
   // Constructeur par défaut
   pair() : first(Type1()), second(Type2()) {}
   
   // Constructeur avec paramètres
   pair(const Type1& val1, const Type2& val2) : first(val1), second(val2) {}
};

Le membre first correspond à la clé et second à la valeur. Lors de la conception de conteneurs de type clé-valeur, il suffit de définir un objet std::pair pour chaque nœud ou élément.

Pourquoi utiliser std::pair plutôt que de définir directement key et value ? Le C++ ne permet de retourner qu'une seule valeur à la fois. En encapsulant key et value dans une std::pair, on peut retourner l'objet pair entier, puis accéder à first et second séparément.

Fonction std::make\_pair

Étant donné que std::pair est un modèle de classe, son utilisation directe peut être fastidieuse (par exemple, std::pair<:string int=""> monCouple("age", 30);). Pour simplifier, C++ propose la fonction std::make\_pair :</:string>

template <class Type1, class Type2>
pair<Type1, Type2> make_pair(Type1 val1, Type2 val2)
{
   return (pair<Type1, Type2>(val1, val2));
}

make\_pair est un modèle de fonction, ce qui permet au compilateur de déduire automatiquement les types des arguments, évitant ainsi de les spécifier explicitement. Par conséquent, make\_pair est généralement préféré à l'instanciation directe de std::pair.

1.3 Structures Arborescentes et Hachées

Selon leurs cas d'utilisation, les conteneurs associatifs de la STL C++ sont implémentés avec deux types de structures sous-jacentes :

Conteneur Associatif	Structure Logique	Implémentation Sous-jacente
`set`, `map`, `multiset`, `multimap`	Arborescente	Arbre de Recherche Équilibré (Arbre Rouge-Noir)
`unordered\_set`, `unordered\_map`, `unordered\_multiset`, `unordered\_multimap`	Hachée	Table de Hachage

Les conteneurs arborescents stockent les éléments de manière ordonnée, tandis que les conteneurs hachés n'offrent aucune garantie d'ordre.

2. `std::set`

2.1 Introduction à `std::set`

std::set est un conteneur qui stocke des éléments uniques selon un ordre spécifié. Son implémentation sous-jacente est un arbre binaire de recherche équilibré, généralement un arbre Rouge-Noir. Grâce à la propriété des arbres binaires de recherche (valeur du nœud gauche < valeur du nœud racine < valeur du nœud droit) et à l'unicité des nœuds, std::set est idéal pour le tri, la suppression des doublons et la recherche rapide (complexité en temps O(logN)).

std::set est un conteneur de type "clé unique" : il ne stocke que des clés, sans valeur associée, et chaque clé est unique. Les éléments d'un std::set ne peuvent pas être modifiés directement, car cela pourrait briser la structure ordonnée de l'arbre. Cependant, l'insertion et la suppression d'éléments sont autorisées.

Voici la déclaration type de std::set :

template <
   class TypeCle,           // Le type des éléments/clés (set::key_type/value_type)
   class Comparaison = std::less<TypeCle>, // Le comparateur de clés (set::key_compare)
   class Allocateur = std::allocator<TypeCle> // L'allocateur de mémoire (set::allocator_type)
> class set;

En résumé :

std::set est un conteneur de type "clé" ; l'insertion ne nécessite que la clé, pas une paire clé-valeur.
Les éléments de std::set sont uniques, ce qui en fait un outil efficace pour la suppression des doublons.
Grâce à son implémentation en arbre Rouge-Noir, la traversée avec un itérateur parcourt les éléments dans un ordre croissant, permettant ainsi le tri.
Le comparateur par défaut est std::less, ordonnant les éléments par ordre croissant. Un comparateur personnalisé (via un foncteur) peut être fourni pour un ordre différent.
L'allocateur de mémoire par défaut est std::allocator. Un allocateur personnalisé peut être spécifié.
Le paramètre de modèle TypeCle représente le type de la clé (et de la valeur) des éléments.
La complexité de la recherche d'un élément dans std::set est O(logN).
Les éléments d'un std::set ne peuvent pas être modifiés directement pour préserver la structure de l'arbre.
L'implémentation sous-jacente est un arbre binaire de recherche équilibré (arbre Rouge-Noir).

2.2 Utilisation de `std::set`

2.2.1 Construction

std::set supporte plusieurs méthodes de construction :

// Construction par défaut (1)
explicit set (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

// Construction par plage d'itérateurs (2)
template <class InputIterator>
set (InputIterator premier, InputIterator dernier,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

// Constructeur de copie (3)
set (const set& autreSet);

// Construction à partir d'une liste d'initialisation (5) (C++11)
set (std::initializer_list<value_type> listeInit,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

2.2.2 Itérateurs

std::set fournit des itérateurs bidirectionnels. La traversée par défaut se fait dans l'ordre croissant des clés, grâce à la traversée infixe de l'arbre binaire sous-jacent. Les itérateurs iterator et const\_iterator ne permettent pas de modifier les données, car toute modification de clé altérerait la structure de l'arbre.

// Les itérateurs sont bidirectionnels
// iterator pointe vers const value_type
iterator begin();           // Itérateur au début
iterator end();             // Itérateur après la fin

reverse_iterator rbegin();  // Itérateur inverse au début
reverse_iterator rend();    // Itérateur inverse après la fin

2.2.3 Modification

Les principales opérations de modification pour std::set sont l'insertion et la suppression :

// Insertion d'un élément unique
// Retourne une paire : itérateur vers l'élément et booléen (vrai si inséré, faux si existait déjà)
std::pair<iterator,bool> insert (const value_type& val);

// Insertion d'une liste d'initialisation
void insert (std::initializer_list<value_type> il);

// Insertion d'une plage d'itérateurs
template <class InputIterator>
void insert (InputIterator premier, InputIterator dernier);

// Suppression par itérateur
iterator erase (const_iterator position);

// Suppression par valeur (retourne le nombre d'éléments supprimés, 0 ou 1 pour set)
size_type erase (const value_type& val);

// Suppression d'une plage d'itérateurs
iterator erase (const_iterator premier, const_iterator dernier);

Les fonctions swap (échange les racines de deux arbres) et clear (libère tous les nœuds de l'arbre) sont également disponibles.

Insertion (insert)

La méthode insert permet d'ajouter un seul élément, une plage d'éléments ou une liste d'initialisation. La complexité est O(logN). Le retour de l'insertion d'un seul élément est un std::pair<iterator bool="">, où le bool indique si l'insertion a eu lieu (faux si la clé existait déjà).

#include <iostream>
#include <set>
#include <string>
#include <functional> // Pour std::greater

int main()
{
   // set pour des entiers (triés et uniques par défaut)
   std::set<int> mesEntiers; 
   // Ou set<int, std::greater<int>> pour un ordre décroissant
   // std::set<int, std::greater<int>> mesEntiers;

   mesEntiers.insert(5);
   mesEntiers.insert(2);
   mesEntiers.insert(7);
   mesEntiers.insert(5); // Ignoré car 5 existe déjà

   std::cout << "Elements du set (entiers): ";
   for (int valeur : mesEntiers) // Utilisation de la boucle for-range
   {
       // *valeur = 1; // Erreur: impossible de modifier un élément de set
       std::cout << valeur << " ";
   }
   std::cout << std::endl;

   // Insertion d'une liste d'initialisation
   mesEntiers.insert({ 2, 8, 3, 9 }); // Les doublons (2) sont ignorés
   std::cout << "Elements après insertion liste: ";
   for (int valeur : mesEntiers)
   {
       std::cout << valeur << " ";
   }
   std::cout << std::endl;

   // set pour des chaînes de caractères (triées par ordre lexicographique)
   std::set<std::string> mots = { "trier", "inserer", "ajouter" };
   std::cout << "Elements du set (chaînes): ";
   for (const std::string& mot : mots)
   {
       std::cout << mot << " ";
   }
   std::cout << std::endl;

   return 0;
}

Suppression (erase)

erase peut supprimer un élément par son itérateur, par sa valeur ou par une plage d'itérateurs.

#include <iostream>
#include <set>
#include <algorithm> // Pour std::find si nécessaire (mais set::find est meilleur)

int main()
{
   std::set<int> nombres = { 4, 2, 7, 2, 8, 5, 9 }; // 2 sera stocké une seule fois
   std::cout << "Elements initiaux: ";
   for (int n : nombres) {
       std::cout << n << " ";
   }
   std::cout << std::endl;

   // Supprimer le plus petit élément (via l'itérateur au début)
   if (!nombres.empty()) {
       nombres.erase(nombres.begin());
   }
   std::cout << "Après suppression du min: ";
   for (int n : nombres) {
       std::cout << n << " ";
   }
   std::cout << std::endl;

   // Supprimer un élément par sa valeur
   int valeurASupprimer;
   std::cout << "Entrez une valeur à supprimer: ";
   std::cin >> valeurASupprimer;
   size_t nbSupprimes = nombres.erase(valeurASupprimer); // Retourne 0 ou 1
   if (nbSupprimes == 0) {
       std::cout << valeurASupprimer << " n'existe pas dans le set." << std::endl;
   } else {
       std::cout << valeurASupprimer << " a été supprimé." << std::endl;
   }
   std::cout << "Après suppression par valeur: ";
   for (int n : nombres) {
       std::cout << n << " ";
   }
   std::cout << std::endl;

   // Rechercher puis supprimer avec l'itérateur
   std::cout << "Entrez une autre valeur à supprimer: ";
   std::cin >> valeurASupprimer;
   auto it = nombres.find(valeurASupprimer);
   if (it != nombres.end())
   {
       nombres.erase(it);
       std::cout << valeurASupprimer << " a été trouvé et supprimé." << std::endl;
   }
   else
   {
       std::cout << valeurASupprimer << " n'existe pas dans le set." << std::endl;
   }
   std::cout << "Après suppression par itérateur: ";
   for (int n : nombres) {
       std::cout << n << " ";
   }
   std::cout << std::endl;

   return 0;
}

2.2.4 Opérations

std::set propose des fonctions de recherche et de bornage :

// Recherche d'une valeur, retourne un itérateur vers l'élément ou end() si non trouvé
iterator find (const value_type& val);

// Compte le nombre d'occurrences d'une valeur (0 ou 1 pour set)
size_type count (const value_type& val) const;

// Retourne un itérateur vers le premier élément >= val (borne inférieure)
iterator lower_bound (const value_type& val) const;

// Retourne un itérateur vers le premier élément > val (borne supérieure)
iterator upper_bound (const value_type& val) const;

Recherche (find)

La fonction find recherche une clé dans l'arbre et retourne un itérateur vers l'élément si trouvé, ou end() sinon. Sa complexité est O(logN), ce qui est bien plus efficace que le std::find générique de la bibliothèque d'algorithmes (qui serait O(N)).

// std::find de la bibliothèque d'algorithmes (O(N) - à éviter pour set)
// auto pos1 = std::find(monSet.begin(), monSet.end(), maValeur); 

// set::find (O(logN) - recommandé)
// auto pos2 = monSet.find(maValeur);

Comptage (count)

Pour std::set, count renvoie toujours 0 ou 1 puisque les éléments sont uniques. Son utilité est donc limitée, mais elle existe pour maintenir la cohérence avec std::multiset.

#include <iostream>
#include <set>

int main()
{
   std::set<int> monEnsemble = { 4, 2, 7, 8, 5, 9 };
   std::cout << "Elements: ";
   for (int e : monEnsemble) {
       std::cout << e << " ";
   }
   std::cout << std::endl;

   int rechercheVal;
   std::cout << "Entrez une valeur à vérifier: ";
   std::cin >> rechercheVal;
   if (monEnsemble.count(rechercheVal)) // Retourne 1 si présent, 0 sinon
   {
       std::cout << rechercheVal << " est présent dans l'ensemble." << std::endl;
   }
   else
   {
       std::cout << rechercheVal << " n'est pas présent." << std::endl;
   }
   return 0;
}

Bornes (lower\_bound et upper\_bound)

Ces fonctions permettent de définir une plage d'itérateurs [borne_inférieure, borne_supérieure) respectant la convention "intervalle semi-ouvert".

lower\_bound(val) retourne un itérateur vers le premier élément dont la clé est supérieure ou égale à val.
upper\_bound(val) retourne un itérateur vers le premier élément dont la clé est strictement supérieure à val.

#include <iostream>
#include <set>

int main()
{
   std::set<int> ensembleValeurs;
   for (int i = 1; i < 10; ++i)
       ensembleValeurs.insert(i * 10); // 10 20 30 40 50 60 70 80 90

   std::cout << "Elements initiaux: ";
   for (int e : ensembleValeurs) {
       std::cout << e << " ";
   }
   std::cout << std::endl;

   // Trouver l'intervalle [30, 60]
   // itInf pointe vers le premier élément >= 30
   auto itInf = ensembleValeurs.lower_bound(30);
   // itSup pointe vers le premier élément > 60
   auto itSup = ensembleValeurs.upper_bound(60);
   
   std::cout << "Suppression de l'intervalle [" << *itInf << ", " << *itSup << ")" << std::endl;

   // Supprimer cette plage d'éléments
   ensembleValeurs.erase(itInf, itSup);

   std::cout << "Elements après suppression: ";
   for (int e : ensembleValeurs) {
       std::cout << e << " ";
   }
   std::cout << std::endl;

   return 0;
}

3. `std::multiset`

3.1 Introduction à `std::multiset`

std::multiset est un conteneur de type "clé" qui, contrairement à std::set, autorise les clés en double. Il utilise également un arbre Rouge-Noir comme implémentation sous-jacente. std::multiset est utile pour le tri et la recherche, mais pas pour la suppression des doublons.

3.2 Utilisation de `std::multiset`

L'utilisation de std::multiset est très similaire à celle de std::set, avec quelques différences clés dues à la tolérance des clés en double. Les fonctions insert, find, count et erase se comportent différemment.

Tri :

#include <iostream>
#include <set> // multiset est aussi dans l'en-tête <set>

int main()
{
   // multiset trie les éléments mais conserve les doublons
   std::multiset<int> ensembleMultiple = { 4, 2, 7, 2, 4, 8, 4, 5, 4, 9 };
   std::cout << "Elements du multiset: ";
   for (int e : ensembleMultiple)
   {
       std::cout << e << " ";
   }
   std::cout << std::endl;
   
   return 0;
}

Recherche (find) :

Si plusieurs éléments ont la même clé, find retourne un itérateur vers le premier élément trouvé lors de la traversée in-ordre.

#include <iostream>
#include <set>

int main()
{
   std::multiset<int> ensembleMultiple = { 4, 2, 7, 2, 4, 8, 4, 5, 4, 9 };
   std::cout << "Elements du multiset: ";
   for (int e : ensembleMultiple)
   {
       std::cout << e << " ";
   }
   std::cout << std::endl;

   int valRecherchee;
   std::cout << "Entrez une valeur à rechercher: ";
   std::cin >> valRecherchee;
   
   auto it = ensembleMultiple.find(valRecherchee);
   if (it != ensembleMultiple.end()) {
       std::cout << "Occurrences de " << valRecherchee << ": ";
       // Il faut boucler pour trouver toutes les occurrences
       while (it != ensembleMultiple.end() && *it == valRecherchee)
       {
           std::cout << *it << " ";
           ++it;
       }
       std::cout << std::endl;
   } else {
       std::cout << valRecherchee << " n'a pas été trouvé." << std::endl;
   }
   
   return 0;
}

Comptage (count) :

count pour std::multiset renvoie le nombre réel d'occurrences de la clé.

#include <iostream>
#include <set>

int main()
{
   std::multiset<int> ensembleMultiple = { 4, 2, 7, 2, 4, 8, 4, 5, 4, 9 };
   std::cout << "Elements du multiset: ";
   for (int e : ensembleMultiple)
   {
       std::cout << e << " ";
   }
   std::cout << std::endl;

   int valComptee;
   std::cout << "Entrez une valeur à compter: ";
   std::cin >> valComptee;
   std::cout << "Nombre d'occurrences de " << valComptee << ": " << ensembleMultiple.count(valComptee) << std::endl;
   
   return 0;
}

Suppression (erase) :

Si la suppression est faite par valeur (erase(val)), toutes les occurrences de cette valeur sont supprimées.

#include <iostream>
#include <set>

int main()
{
   std::multiset<int> ensembleMultiple = { 4, 2, 7, 2, 4, 8, 4, 5, 4, 9 };
   std::cout << "Elements du multiset initiaux: ";
   for (int e : ensembleMultiple)
   {
       std::cout << e << " ";
   }
   std::cout << std::endl;

   int valASupprimer;
   std::cout << "Entrez une valeur à supprimer: ";
   std::cin >> valASupprimer;
   ensembleMultiple.erase(valASupprimer); // Supprime toutes les occurrences de valASupprimer
   
   std::cout << "Elements du multiset après suppression: ";
   for (int e : ensembleMultiple)
   {
       std::cout << e << " ";
   }
   std::cout << std::endl;

   return 0;
}

5. Questions d'Entretien Impliquant `std::set`

5.1 Intersection de Deux Tableaux

Description du problème (LeetCode 349) : Étant donnés deux tableaux nums1 et nums2, retournez leur intersection. Chaque élément du résultat doit être unique. L'ordre du résultat n'a pas d'importance.

#include <vector>
#include <set>
#include <algorithm> // Pour std::vector::insert

class Solution {
public:
   std::vector<int> intersection(std::vector<int>& nombres1, std::vector<int>& nombres2) {
       // Convertir les vecteurs en sets pour la déduplication et le tri automatique
       std::set<int> ensemble1(nombres1.begin(), nombres1.end());
       std::set<int> ensemble2(nombres2.begin(), nombres2.end());
       
       std::vector<int> resultatIntersection;
       auto it1 = ensemble1.begin();
       auto it2 = ensemble2.begin();

       // Utiliser une approche de deux pointeurs pour trouver l'intersection des sets triés
       while (it1 != ensemble1.end() && it2 != ensemble2.end()) {
           if (*it1 < *it2) {
               ++it1;
           } else if (*it1 > *it2) {
               ++it2;
           } else { // Les éléments sont égaux, c'est une intersection
               resultatIntersection.push_back(*it1);
               ++it1;
               ++it2;
           }
       }
       return resultatIntersection;
   }
};

Analyse : Cette solution exploite les propriétés de std::set : déduplication automatique et maintien de l'ordre. En convertissant les deux tableaux en std::set, nous obtenons deux collections triées et uniques. Ensuite, une technique de "deux pointeurs" est utilisée pour parcourir ces deux sets simultanément et trouver les éléments communs de manière efficace. Si les éléments actuels des deux itérateurs sont inégaux, on avance l'itérateur de l'élément le plus petit. S'ils sont égaux, on ajoute l'élément au résultat et on avance les deux itérateurs.

5.2 Liste Chaînée Circulaire II

Descritpion du problème (LeetCode 142) : Étant donné la tête d'une liste chaînée head, retournez le nœud où le cycle commence. Si la liste n'a pas de cycle, retournez nullptr. Un cycle existe si un nœud de la liste peut être atteint à nouveau en suivant le pointeur next. Vous ne devez pas modifier la liste chaînée.

#include <set> // Pour std::set

// Définition de la structure de nœud (comme sur LeetCode)
struct ListNode {
   int val;
   ListNode *next;
   ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
   ListNode *detectCycle(ListNode *head) {
       std::set<ListNode*> nœudsVisites; // Stocke les adresses des nœuds déjà rencontrés
       ListNode* actuel = head;

       while (actuel != nullptr) {
           // Tenter d'insérer l'adresse du nœud actuel dans le set
           // La méthode insert retourne une pair<iterator, bool>
           // dont le booléen (second) est false si l'élément existait déjà.
           auto resultatInsertion = nœudsVisites.insert(actuel);

           // Si l'insertion a échoué (l'adresse était déjà dans le set)
           if (resultatInsertion.second == false) {
               return actuel; // C'est le nœud de départ du cycle
           }

           actuel = actuel->next; // Avancer au nœud suivant
       }
       return nullptr; // Aucun cycle trouvé
   }
};

Analyse : L'idée centrale est de parcourir la liste chaînée et d'enregistrer l'adresse de chaque nœud visité dans un std::set. Comme un std::set ne peut contenir que des éléments uniques, si nous tentons d'insérer une adresse de nœud qui est déjà présente dans le set, cela signifie que nous avons rencontré ce nœud une seconde fois. Ce nœud est alors le point de départ du cycle. Si le parcours se termine (actuel devient nullptr) sans qu'une adresse dupliquée ne soit trouvée, alors il n'y a pas de cycle.

6. `std::map`

6.1 Introduction à `std::map`

std::map, comme std::set, est un conteneur qui stocke des éléments triés. Cependant, std::map est un conteneur de type "clé-valeur", où chaque élément est une paire (clé, valeur). La clé (Key) est utilisée pour le tri et l'identification unique de l'élément, tandis que la valeur (T) stocke le contenu associé à cette clé. Les types de la clé et de la valeur peuvent être différents. En interne, les paires clé-valeur sont liées ensemble via std::pair et sont organisées dans un arbre Rouge-Noir.

Les éléments d'un std::map sont triés par leurs clés, indépendamment de leurs valeurs. Les clés doivent être uniques. std::map est également adapté pour le tri, la recherche et la déduplication de clés, avec une complexité de recherche de O(logN). La traversée avec un itérateur parcourt les éléments par ordre croissant de clés.

Voici la déclaration type de std::map :

template <
   class TypeCle,           // Le type de la clé (map::key_type)
   class TypeValeur,        // Le type de la valeur (map::mapped_type)
   class Comparaison = std::less<TypeCle>, // Le comparateur de clés (map::key_compare)
   class Allocateur = std::allocator<std::pair<const TypeCle, TypeValeur>> // L'allocateur
> class map;

En résumé :

TypeCle est le type de la clé, et TypeValeur est le type de la valeur associée.
std::map nécessite que les clés supportent une comparaison d'infériorité. Un comparateur personnalisé peut être fourni.
L'allocateur de mémoire par défaut est std::allocator.
Les deux derniers paramètres de modèle sont rarement spécifiés manuellement.
Important : La clé d'un élément dans std::map est const et ne peut pas être modifiée, car cela pourrait rompre la structure ordonnée de l'arbre. Cependant, la valeur associée à une clé peut être modifiée.

6.2 Utilisation de `std::map`

6.2.1 Construction

std::map supporte des constructeurs similaires à std::set :

// Construction par défaut (1)
explicit map (const key_compare& comp = key_compare(),
             const allocator_type& alloc = allocator_type());

// Construction par plage d'itérateurs (2)
template <class InputIterator>
map (InputIterator premier, InputIterator dernier,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

// Constructeur de copie (3)
map (const map& autreCarte);

// Construction à partir d'une liste d'initialisation (5) (C++11)
map (std::initializer_list<value_type> listeInit,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

Exemple de code :

#include <iostream>
#include <map>
#include <string>

int main()
{
   // Construction avec une liste d'initialisation
   std::map<std::string, std::string> dictionnaire = { 
       {"gauche", "left"}, 
       {"droite", "right"},
       {"inserer", "insert"},
       {"chaine", "string"} 
   };

   std::cout << "Elements du dictionnaire (Clé:Valeur):" << std::endl;
   auto it = dictionnaire.begin();
   while (it != dictionnaire.end())
   {
       // Accéder aux membres first et second de la paire via l'itérateur
       std::cout << it->first << ":" << it->second << std::endl;
       ++it;
   }
   std::cout << std::endl;

   return 0;
}

Notes :

La construction via une liste d'initialisation (e.g., {"gauche", "left"}) exploite l'initialisation d'une std::pair à partir d'une liste d'éléments, combinée à des conversions imlpicites (par exemple, de const char\* à std::string).
Lors de l'accès aux éléments d'une std::pair via un itérateur, it->first et it->second sont les méthodes idiomatiques.

6.2.2 Itérateurs

std::map propose des itérateurs bidirectionnels. La traversée se fait dans l'ordre croissant des clés. Les itérateurs et const\_iterator permettent l'accès à la paire (clé, valeur). La clé est const, mais la valeur ne l'est pas.

// Les itérateurs sont bidirectionnels
// iterator pointe vers const std::pair<const Key, T>
iterator begin();
iterator end();

reverse_iterator rbegin();
reverse_iterator rend();

Les boucles for-range sont supportées. Il est recommandé d'utiliser une référence (const auto&) pour éviter des copies coûteuses de paires :

// Boucle for-range classique
for (const auto& entree : dictionnaire)
{
   std::cout << entree.first << ":" << entree.second << std::endl;
}
std::cout << std::endl;

// Liaison structurée (C++17) pour une meilleure lisibilité
for(const auto& [cle, valeur] : dictionnaire)
{
  	std::cout << cle << ":" << valeur << std::endl;  
}
std::cout << std::endl;

6.2.3 Modification

Les opérations de modification principales sont insert et erase.

// Types membres
key_type    // Le premier paramètre de modèle (Key)
mapped_type // Le deuxième paramètre de modèle (T)
value_type  // std::pair<const key_type, mapped_type>

// Insertion d'une paire unique (échec si la clé existe déjà)
std::pair<iterator,bool> insert (const value_type& val);

// Insertion d'une liste d'initialisation
void insert (std::initializer_list<value_type> il);

// Insertion d'une plage d'itérateurs
template <class InputIterator>
void insert (InputIterator premier, InputIterator dernier);

// Suppression par itérateur
iterator erase (const_iterator position);

// Suppression par clé (retourne 1 si trouvée et supprimée, 0 sinon)
size_type erase (const key_type& k);

// Suppression d'une plage d'itérateurs
iterator erase (const_iterator premier, const_iterator dernier);

Insertion (insert)

La fonction insert permet d'ajouter une seule paire clé-valeur, une plage ou une liste d'initialisation. Pour une seule paire, elle retourne un std::pair<iterator bool="">, où bool indique le succès de l'insertion (faux si la clé existait déjà).

#include <iostream>
#include <map>
#include <string>

int main()
{
   std::map<std::string, std::string> monDico = { 
       {"gauche", "left"}, 
       {"droite", "right"}
   };

   // 4 façons d'insérer des paires (key, value)
   // 1. Construire l'objet pair puis l'insérer
   std::pair<std::string, std::string> kv1("premier", "first");
   monDico.insert(kv1);

   // 2. Insérer un objet pair anonyme
   monDico.insert(std::pair<std::string, std::string>("deuxieme", "second"));

   // 3. Utiliser make_pair (déduction de type)
   monDico.insert(std::make_pair("trier", "sort"));

   // 4. Utiliser la liste d'initialisation (méthode préférée depuis C++11)
   monDico.insert({ "auto", "automatic" });
   
   // Tentative d'insertion d'une clé existante (sera ignorée)
   monDico.insert({ "gauche", "left, remaining" });

   std::cout << "Contenu du dictionnaire après insertions:" << std::endl;
   for (const auto& [cle, valeur] : monDico) {
       std::cout << cle << ": " << valeur << std::endl;
   }

   return 0;
}

Suppression (erase)

La fonction erase fonctionne de manière similaire à celle de std::set pour la suppression par itérateur, par clé ou par plage.

6.2.4 Opérations

Les fonctions find, count, lower\_bound et upper\_bound sont également présentes dans std::map.

// Recherche, retourne un itérateur vers la paire (clé, valeur) ou end()
iterator find (const key_type& k);

// Compte le nombre d'occurrences d'une clé (0 ou 1 pour map)
size_type count (const key_type& k) const;

// Retourne un itérateur vers le premier élément dont la clé est >= k
iterator lower_bound (const key_type& k);

// Retourne un itérateur vers le premier élément dont la clé est > k
const_iterator lower_bound (const key_type& k) const; // Surcharge const

Recherche (find)

find est essentiel pour rechercher une clé et récupérer l'itérateur vers la paire correspondante. Si la clé n'est pas trouvée, end() est retourné.

#include <iostream>
#include <map>
#include <string>

int main()
{
	std::map<std::string, std::string> dictionnaireAnglaisFrancais = { 
       {"left", "gauche"}, 
       {"right", "droite"},
       {"insert", "insérer"},
       {"string", "chaîne"} 
   };
   
   std::string motAnglais;
   std::cout << "Entrez un mot anglais (Ctrl+Z pour quitter):" << std::endl;
	while (std::cin >> motAnglais)
	{
		auto itTrouve = dictionnaireAnglaisFrancais.find(motAnglais);
		if (itTrouve != dictionnaireAnglaisFrancais.end())
		{
			std::cout << "Traduction: " << itTrouve->second << std::endl;
		}
		else
		{
			std::cout << "Mot inconnu. Veuillez réessayer." << std::endl;
		}
       std::cout << "Entrez un mot anglais:" << std::endl;
	}
	return 0;
}

Les autres fonctions comme count, lower\_bound et upper\_bound fonctionnent de manière analogue à std::set, avec count retournant 0 ou 1.

6.2.5 Accès aux Éléments (Opérateur `\[\]`)

6.2.5.1 Prototype

L'opérateur \[\] est surchargé pour std::map, permettant un accès direct aux valeurs par leur clé :

// TypeRetour: le type de la valeur (mapped_type)
// TypeCle: le type de la clé (key_type)
mapped_type& operator[] (const key_type& k);

Essentiellement, il permet de récupérer une référence à la valeur associée à une clé. Cette référence peut être utilisée pour lire ou modifier la valeur.

6.2.5.2 Définition Fonctionnelle

L'implémentation de l'opérateur \[\] s'appuie sur la fonction insert :

// Vue simplifiée de l'implémentation de operator[]
mapped_type& operator[] (const key_type& k) 
{
	// Insère une paire {k, mapped_type()} si k n'existe pas.
	// Retourne un pair<iterator, bool>.
	// .first est l'itérateur vers la paire {k, valeur} (existante ou nouvellement insérée).
	// On déréférence l'itérateur pour obtenir la paire, puis on accède à sa 'second' (la valeur).
	return (((this->insert(std::make_pair(k, mapped_type()))).first)->second);
}

Il est crucial de comprendre le comportement de insert :

Si la clé k existe déjà dans le map, insert échoue mais retourne un std::pair<iterator bool=""> où first est un itérateur vers la paire (k, valeur) existante, et second est false.
Si la clé k n'existe pas, insert insère une nouvelle paire (k, valeur\_par\_défaut\_de\_mapped\_type), et retourne un std::pair<iterator bool=""> où first est un itérateur vers la nouvelle paire, et second est true.

Dans tous les cas, le first de la valeur de retour de insert pointe vers la paire (k, valeur). L'opérateur \[\] utilise ceci pour retourner une référence à la second (la valeur) de cette paire.

6.2.5.3 Fonctionnement Interne Simplifié

mapped_type& operator[] (const key_type& k)
{
	// Tente d'insérer {k, mapped_type()} (valeur par défaut)
	std::pair<iterator, bool> resultat_insertion = insert({ k, mapped_type() });
	iterator it = resultat_insertion.first; // Obtient l'itérateur vers l'élément (existante ou nouvelle)
	return it->second; // Retourne la référence à la valeur de cet élément
}

En résumé :

Si la clé k n'est pas dans le map, insert ajoute la paire (k, valeur\_par\_défaut). operator\[\] retourne ensuite une référence à cette nouvelle valeur par défaut. On peut alors modifier cette valeur. Ainsi, \[\] permet l'insertion ET la modification.
Si la clé k est déjà dans le map, insert échoue, mais operator\[\] récupère une référence à la valeur existante. On peut alors lire ou modifier cette valeur. Ainsi, \[\] permet la recherche ET la modification.

6.2.5.4 Exemples de Code

Exemple 1 :

#include <iostream>
#include <map>
#include <string>

int main()
{
	std::map<std::string, std::string> monDico;
	monDico.insert(std::make_pair("trier", "sort"));

	// La clé "inserer" n'existe pas: insertion de {"inserer", "" (string par défaut)}
	monDico["inserer"]; 
   
	// La clé "gauche" n'existe pas: insertion de {"gauche", ""}, puis modification à "left"
	monDico["gauche"] = "left";
   
	// La clé "gauche" existe: modification de sa valeur
	monDico["gauche"] = "left, remaining";
   
	// La clé "gauche" existe: récupération de sa valeur
	std::cout << "Valeur de 'gauche': " << monDico["gauche"] << std::endl;

   // Affichage de tout le map
   std::cout << "Contenu du map:" << std::endl;
   for (const auto& [cle, valeur] : monDico) {
       std::cout << cle << ": " << valeur << std::endl;
   }

	return 0;
}

Exemple 2 : Comptage de fréquences

#include <iostream>
#include <map>
#include <string>
#include <vector>

int main()
{
	std::vector<std::string> fruits = { "pomme", "pastèque", "pomme", "pastèque", "pomme", 
                                         "pomme", "pastèque", "pomme", "banane", "pomme", "banane" };
	std::map<std::string, int> compteFrequence;

	for (const auto& nomFruit : fruits)
	{
		// Si nomFruit n'existe pas, insère {nomFruit, 0}, puis incrémente (devient 1)
		// Si nomFruit existe, retourne la référence à son compteur, puis incrémente
		compteFrequence[nomFruit]++;
	}

   std::cout << "Fréquence des fruits:" << std::endl;
	for (const auto& [fruit, compteur] : compteFrequence)
	{
		std::cout << fruit << ": " << compteur << std::endl;
	}
	std::cout << std::endl;
	return 0;
}

7. `std::multimap`

Comme pour la relation entre std::set et std::multiset, std::multimap est une version de std::map qui autorise les clés en double. Les différences d'utilisation sont analogues : find retourne un itérateur vers la première occurrence, count retourne le nombre réel d'occurrences. Il est important de noter que std::multimap ne surcharge PAS l'opérateur \[\]. En effet, avec des clés dupliquées, il serait ambigu de déterminer quelle valeur \[\] devrait accéder ou créer.

8. Questions d'Entretien Impliquant `std::map`

8.1 Copie d'une Liste Chaînée Aléatoire

Description du problème (LeetCode 138) : Étant donnée une liste chaînée de n nœuds, où chaque nœud contient un pointeur random supplémentaire qui peut pointer vers n'importe quel nœud de la liste ou être null. Construisez une copie profonde de cette liste. La copie profonde doit être composée de n nouveaux nœuds, dont la valeur de chaque nouveau nœud est égale à la valeur de son nœud original correspondant. Les pointeurs next et random des nouveaux nœuds doivent également pointer vers les nouveaux nœuds de la liste copiée, et permettre aux pointeurs des listes originale et copiée de représenter le même état de liste. Aucun des pointeurs de la liste copiée ne doit pointer vers les nœuds de la liste originale.

#include <map> // Pour std::map

// Définition de la structure de nœud (comme sur LeetCode)
class Node {
public:
   int val;
   Node* next;
   Node* random;

   Node(int _val) {
       val = _val;
       next = nullptr;
       random = nullptr;
   }
};

class Solution {
public:
   Node* copyRandomList(Node* head) {
       // Un map pour stocker la correspondance entre les nœuds originaux et leurs copies
       // Clé: pointeur vers un nœud original, Valeur: pointeur vers son nœud copié
       std::map<Node*, Node*> correspondanceNœuds; 
       
       Node* nouvelleTete = nullptr; // Tête de la nouvelle liste
       Node* queueNouvelleListe = nullptr; // Queue de la nouvelle liste
       Node* actuelOriginal = head; // Pointeur pour parcourir la liste originale
       
       // --- Première passe : Création des nœuds et des pointeurs 'next' ---
       while (actuelOriginal != nullptr) {
           Node* nouveauNœud = new Node(actuelOriginal->val);

           if (nouvelleTete == nullptr) {
               nouvelleTete = queueNouvelleListe = nouveauNœud;
           } else {
               queueNouvelleListe->next = nouveauNœud;
               queueNouvelleListe = nouveauNœud;
           }

           // Établir la correspondance : original -> copie
           correspondanceNœuds[actuelOriginal] = nouveauNœud;
           actuelOriginal = actuelOriginal->next;
       }
       
       // --- Deuxième passe : Gestion des pointeurs 'random' ---
       actuelOriginal = head;           // Réinitialiser au début de la liste originale
       Node* actuelCopie = nouvelleTete; // Réinitialiser au début de la liste copiée
       
       while (actuelOriginal != nullptr) {
           if (actuelOriginal->random == nullptr) {
               actuelCopie->random = nullptr; // Si l'original n'avait pas de random, la copie non plus
           } else {
               // Utiliser la map pour trouver le nœud copié correspondant au random de l'original
               actuelCopie->random = correspondanceNœuds[actuelOriginal->random];
           }
           
           actuelOriginal = actuelOriginal->next;
           actuelCopie = actuelCopie->next;
       }
       
       return nouvelleTete; // Retourner la tête de la liste copiée
   }
};

Analyse :

La solution procède en deux étapes principales :

Copie des nœuds et des pointeurs next :
- On parcourt la liste originale. Pour chaque nœud original, un nouveau nœud est créé avec la même valeur.
- Ces nouveaux nœuds sont chaînés pour former la structure de base de la liste copiée, en utilisant les pointeurs next.
- Crucialement, un std::map (appelé correspondanceNœuds) est utilisé pour stocker la relation entre l'adresse du nœud original et l'adresse de son nœud copié (original\_node\_ptr -> copied\_node\_ptr). À la fin de cette étape, la nouvelle liste est formée (avec les bonnes valeurs et next pointeurs), et la map contient toutes les correspondances. Cependant, les pointeurs random des nœuds copiés sont toujours nullptr.
Gestion des pointeurs random :
- On effectue une seconde traversée, simultanément sur la liste originale et la liste copiée.
- Pour chaque nœud original, on examine son pointeur random.
- Si original\_node->random n'est pas nullptr, cela signifie qu'il pointe vers un autre nœud original. On utilise alors la correspondanceNœuds pour trouver l'adresse du nœud copié correspondant à original\_node->random.
- Ce nœud copié trouvé est alors assigné à copied\_node->random.

Cette approche garantit une copie profonde correcte de la liste, gérant les pointeurs random complexes grâce à la map qui établit une liaison entre les adresses de l'ancienne et de la nouvelle liste.

8.2 Les K Mots les Plus Fréquents

Description du problème (LeetCode 692) : Étant donnée une liste de mots words et un entier k, retournez les k mots les plus fréquents. La réponse doit être triée par fréquence décroissante. Si des mots différents ont la même fréquence, ils doivent être triés par ordre lexicographique croissant.

Solution 1 : Tri d'un vecteur avec comparateur stable

#include <vector>
#include <map>
#include <string>
#include <algorithm> // Pour std::stable_sort

class Solution {
public:
   // Foncteur de comparaison pour le tri stable
   struct ComparateurMots {
       bool operator()(const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) const {
           // Trier d'abord par fréquence décroissante
           if (a.second != b.second) {
               return a.second > b.second;
           }
           // Si les fréquences sont égales, trier par ordre lexicographique croissant de la clé (mot)
           return a.first < b.first;
       }
   };

   std::vector<std::string> topKFrequent(std::vector<std::string>& mots, int k) {
       // 1. Comptage des fréquences
       std::map<std::string, int> frequencesMots;
       for (const std::string& mot : mots) {
           frequencesMots[mot]++;
       }

       // 2. Transfert dans un vecteur de paires pour le tri
       // map est déjà trié par clé lexicographiquement.
       // On transfère pour pouvoir utiliser std::stable_sort.
       std::vector<std::pair<std::string, int>> vecteurFrequences(
           frequencesMots.begin(), frequencesMots.end()
       );
       
       // 3. Tri stable du vecteur selon la logique personnalisée
       // stable_sort maintient l'ordre relatif des éléments égaux, ce qui est crucial
       // si notre premier critère de tri (fréquence) est égal, pour que le tri par clé soit maintenu.
       std::stable_sort(vecteurFrequences.begin(), vecteurFrequences.end(), ComparateurMots());

       // 4. Extraction des k premiers mots
       std::vector<std::string> resultat;
       for (int i = 0; i < k; ++i) {
           resultat.push_back(vecteurFrequences[i].first);
       }
       return resultat;
   }
};

Analyse :

Comptage des Fréquences : Un std::map<string int=""> est utilisé pour stocker la fréquence de chaque mot. Le map garantit que les mots sont déjà triés par ordre lexicographique (clé).
Tri : Les paires (mot, fréquence) du map sont transférées dans un std::vector. Ce vecteur est ensuite trié à l'aide de std::stable\_sort et d'un comparateur personnalisé. Le comparateur trie d'abord par fréquence décroissante. Si les fréquences sont égales, il trie par ordre lexicographique croissant des mots (ce qui est important et est soit maintenu par stable\_sort si l'ordre initial était déjà lexicographique, soit explicitement géré par le comparateur).
Extraction : Les k premiers mots du vecteur trié sont ajoutés au vecteur résultat.

Solution 2 : File de Priorité (Priority Queue)

#include <vector>
#include <map>
#include <string>
#include <queue> // Pour std::priority_queue

class Solution {
public:
   // Foncteur de comparaison pour la file de priorité
   // (pour un min-heap, l'opérateur < doit inverser la logique désirée pour le top)
   // Ici, nous voulons que les éléments "plus grands" (moins fréquents ou lexicographiquement plus grands si fréquences égales) soient au sommet du min-heap
   // afin de garder les K plus fréquents.
   struct ComparateurMinHeap {
       bool operator()(const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) const {
           // Si les fréquences sont différentes, le moins fréquent est "plus grand" pour un min-heap
           if (a.second != b.second) {
               return a.second > b.second; // 'a' est "plus grand" si sa fréquence est plus petite
           }
           // Si les fréquences sont égales, le mot lexicographiquement plus grand est "plus grand"
           return a.first < b.first; // 'a' est "plus grand" si son mot est plus petit (pour que les mots lexicographiquement plus petits avec même fréquence restent)
       }
   };

   std::vector<std::string> topKFrequent(std::vector<std::string>& mots, int k) {
       // 1. Comptage des fréquences
       std::map<std::string, int> frequencesMots;
       for (const std::string& mot : mots) {
           frequencesMots[mot]++;
       }

       // 2. Construction d'une file de priorité de taille K (Min-Heap)
       // La file de priorité stockera les K mots les plus fréquents.
       // Si elle dépasse K, l'élément "le moins prioritaire" (moins fréquent ou lexicographiquement plus grand) est retiré.
       std::priority_queue<
           std::pair<std::string, int>,
           std::vector<std::pair<std::string, int>>,
           ComparateurMinHeap
       > pq;

       for (const auto& paire : frequencesMots) {
           pq.push(paire);
           if (pq.size() > k) {
               pq.pop(); // Maintenir la taille à k
           }
       }

       // 3. Extraction des k mots (ils sont maintenant dans l'ordre inverse désiré pour le résultat final)
       std::vector<std::string> resultat;
       while (!pq.empty()) {
           resultat.push_back(pq.top().first);
           pq.pop();
       }

       // Les éléments sont ajoutés dans l'ordre inverse par le pop d'un min-heap.
       // Il faut inverser le vecteur final pour obtenir l'ordre correct (fréquence décroissante, lexicographique croissante).
       std::reverse(resultat.begin(), resultat.end());

       return resultat;
   }
};

Analyse :

Comptage des Fréquences : Identique à la première solution, un std::map est utilisé pour compter les occurrences de chaque mot.
Construction de la File de Priorité : Une std::priority\_queue (min-heap) est construite avec une taille maximale de k. Le comparateur personnalisé (ComparateurMinHeap) est essentiel ici :
- Il donne une priorité plus basse aux mots moins fréquents (pour qu'ils soient au sommet du min-heap et puissent être retirés).
- Si les fréquences sont égales, il donne une priorité plus basse aux mots lexicographiquement plus grands (pour qu'ils soient au sommet du min-heap et puissent être retirés). Ceci garantit que les mots avec la même fréquence mais un ordre lexicographique plus petit restent dans la file.
La file de priorité est remplie. Si sa taille dépasse k, l'élément au sommet (le moins prioritaire) est retiré.
Extraction : Une fois tous les mots traités, la file de priorité contient les k mots les plus fréquents, triés selon les critères définis. Les éléments sont extraits et ajoutés à un vecteur, puis ce vecteur est inversé pour obtenir l'ordre final correct (fréquence décroissante, lexicographique croissante pour les égalités).

Étiquettes: C++ STL map Set Conteneurs Associatifs

Publié le 1 juin à 17h22

L'Atelier Monstre

Conteneurs Associatifs en C++: `std::map` et `std::set`

1. Concepts Fondamentaux

1.1 Conteneurs Séquentiels et Associatifs

1.2 La Paire Clé-Valeur (`std::pair`)

1.3 Structures Arborescentes et Hachées

2. `std::set`

2.1 Introduction à `std::set`

2.2 Utilisation de `std::set`

2.2.1 Construction

2.2.2 Itérateurs

2.2.3 Modification

2.2.4 Opérations

3. `std::multiset`

3.1 Introduction à `std::multiset`

3.2 Utilisation de `std::multiset`

5. Questions d'Entretien Impliquant `std::set`

5.1 Intersection de Deux Tableaux

5.2 Liste Chaînée Circulaire II

6. `std::map`

6.1 Introduction à `std::map`

6.2 Utilisation de `std::map`

6.2.1 Construction

6.2.2 Itérateurs

6.2.3 Modification

6.2.4 Opérations

6.2.5 Accès aux Éléments (Opérateur `\[\]`)

6.2.5.1 Prototype

6.2.5.2 Définition Fonctionnelle

6.2.5.3 Fonctionnement Interne Simplifié

6.2.5.4 Exemples de Code

7. `std::multimap`

8. Questions d'Entretien Impliquant `std::map`

8.1 Copie d'une Liste Chaînée Aléatoire

8.2 Les K Mots les Plus Fréquents

Étiquettes Populaires

L'Atelier Monstre

Conteneurs Associatifs en C++: `std::map` et `std::set`

1. Concepts Fondamentaux

1.1 Conteneurs Séquentiels et Associatifs

1.2 La Paire Clé-Valeur (std::pair)

1.3 Structures Arborescentes et Hachées

2. std::set

2.1 Introduction à std::set

2.2 Utilisation de std::set

2.2.1 Construction

2.2.2 Itérateurs

2.2.3 Modification

2.2.4 Opérations

3. std::multiset

3.1 Introduction à std::multiset

3.2 Utilisation de std::multiset

5. Questions d'Entretien Impliquant std::set

5.1 Intersection de Deux Tableaux

5.2 Liste Chaînée Circulaire II

6. std::map

6.1 Introduction à std::map

6.2 Utilisation de std::map

6.2.1 Construction

6.2.2 Itérateurs

6.2.3 Modification

6.2.4 Opérations

6.2.5 Accès aux Éléments (Opérateur \[\])

6.2.5.1 Prototype

6.2.5.2 Définition Fonctionnelle

6.2.5.3 Fonctionnement Interne Simplifié

6.2.5.4 Exemples de Code

7. std::multimap

8. Questions d'Entretien Impliquant std::map

8.1 Copie d'une Liste Chaînée Aléatoire

8.2 Les K Mots les Plus Fréquents

Étiquettes Populaires

1.2 La Paire Clé-Valeur (`std::pair`)

2. `std::set`

2.1 Introduction à `std::set`

2.2 Utilisation de `std::set`

3. `std::multiset`

3.1 Introduction à `std::multiset`

3.2 Utilisation de `std::multiset`

5. Questions d'Entretien Impliquant `std::set`

6. `std::map`

6.1 Introduction à `std::map`

6.2 Utilisation de `std::map`

6.2.5 Accès aux Éléments (Opérateur `\[\]`)

7. `std::multimap`

8. Questions d'Entretien Impliquant `std::map`