Connaître le minimum du C++
pour utiliser les bibliothèques standards

Guillaume Ryder pour www.france-ioi.org

Le but de ce cours est de vous expliquer l'utilisation de la bibliothèque standard C++ afin de faciliter l'implémentation de problèmes d'algorithmique. Nous étudierons tout ce qu'il faut ajouter au C pour pouvoir utiliser la bibliothèque C++.

Cette présentation n'est donc pas un cours de C++ dans les règles de l'art, on passera volontairement à côté de nombreux concepts importants du C++, notamment la programmation orientée objet.

On supposera dans toute la suite que vous connaissez déjà le C. Dans la dernière partie, on supposera également que vous connaissez la théorie des structures de données telles que le tas ou la table de hachage. Si vous avez déjà programmé à la main (et dans la douleur) de telles structures, vous comprendrez vite l'intérêt de ce cours.

Vous trouverez sur www.cppreference.com une référence abrégée des structures de données utilisées dans ce cours.

Le document est divisé en trois grandes parties :

1. Bases du C++
   Rapide récapitulatif technique, pour ceux qui n'ont jamais codé en C++
2. Classes
   Comment déclarer et implémenter une classe en algorithmique
3. Utilisation de la STL
   Structures de données prêtes à l'emploi de la bibliothèque C++

Bases du C++

Compilation

Les fichiers sources doivent porter l'extension .cpp (éviter .cc dans la mesure du possible, cette extension est moins répandue). Le compilateur n'est plus gcc mais g++. Le C++ est une amélioration du C, donc une majorité de programmes C compilent sans aucune modification en C++. Les options du compilateur sont les mêmes, les messages d'erreur aussi.

Améliorations pratiques du C++

Le C est un langage très ancien, scotché à une norme draconienne difficile à faire évoluer. Avec la création du C++, on en a profité pour corriger d'un seul coup de nombreux défauts :

• Type booléen. Le C++ comporte un type booléen spécifique, nommé bool, stocké sur un octet et prenant les valeurs true et false.
• Commentaires. La syntaxe //, à placer en début de ligne, est autorisée en plus de /* ... */.
• Déclaration de variables :
  • Le C++ autorise la déclaration de variables n'importe où dans le code : plus besoin de regrouper toutes les déclarations au début de chaque bloc.
  • On peut aussi déclarer des variables dans des for, par exemple : for (int col = 0; col < nbCols; col++). Cette syntaxe a le mérite d'éviter certains bugs dus à la réutilisation de variables.
• Déclaration de fonctions : il est maintenant obligatoire de déclarer une fonction avant de l'utiliser. Les compilateurs C généraient un simple warning, en C++ c'est une erreur fatale.
• Overloading. Il est autorisé de créer plusieurs fonctions différentes portant le même nom, du moment qu'elles n'ont pas exactement les mêmes arguments.

  Autorisé:

  void appliquerZoom(int zoom);
  void appliquerZoom(int zoomX, int zoomY);
  void appliquerZoom(float zoomPrecis);
  
  appliquerZoom(3);           // Appelle la première fonction
  appliquerZoom(4, 2);        // Appelle la deuxième fonction
  appliquerZoom(3.0f);        // Appelle la troisième fonction
  appliquerZoom((int)3.0f);   // Appelle la première fonction
  

  Interdit:

  void appliquerZoom(int zoom);
  void appliquerZoom(int zoomArriere); // Prototype identique
  

  Autorisé:

  int   valeurAbsolue(int valeur);
  float valeurAbsolue(float valeur);
  

  Interdit : ne marche pas si seul le type de retour change

  int   calculerUnivers(int ageDuCapitaine);
  float calculerUnivers(int ageDuCapitaine);   // Arguments identiques
  

• Types. Les mots-clés struct et enum n'ont pas besoin d'être réutilisés à chaque utilisation du type. En C, on contournait cela avec un (très laid) typedef, ce n'est plus nécessaire en C++ :

  // En C, on écrivait ceci :
  typedef struct
  {
     int x,y;
  } Point;
  
  // En C++, ceci suffit :
  struct Point
  {
     int x,y;
  };
  
  Point pt = { 4, 2 };   // Pas besoin d'écrire "struct Point pt";
  

• Valeur par défaut des arguments. Un exemple suffit pour comprendre :

  void afficherUnivers(int reponse = 42)
  {
     printf("Univers = %d\n", reponse);
  }
  
  afficherUnivers(1664);   // Affiche 1664
  afficherUnivers();       // Affiche 42
  

Les #include

Tous les #include du C sont utilisables en C++. Cependant, pour utiliser les nouveaux #include spécifiques au C++, on doit souvent enlever le .h à la fin et ajouter la ligne using namespace std;. Pour les #include de la bibliothèque C, la syntaxe habituelle fonctionne, mais on préférera la notation C++ sans le .h, et avec un c devant le nom. Par exemple :

#include <priority_queue>   // Pas de .h, c'est un #include C++
#include <stack>            // Là non plus
#include <cstdio>           // Equivalent au #include <stdio.h>
using namespace std;        // Ligne importante !

Les classes

En résumé, une classe est une structure C avec des fonctions dedans (ou pas). En fait, en C++, même les struct sont des classes. Dans ce cours, on n'emploiera même jamais le mot-clé class car struct suffit et s'avère plus simple à utiliser.

Déclaration et implémentation

Variables membres

Une classe est en particulier une structure, et peut donc contenir des variables.

struct Vector
{
   int x, y;
};

// Utilisation : comme une structure C.
Vector v;
v.x = 3;
v.y = 5;

Méthodes

Jusque-là, rien de bien extraordinaire. Mais une classe peut aussi contenir des fonctions, que l'on appelle méthodes.

// En C, on écrirait par exemple :
typedef struct { int x, y; } Vector;

int lengthSquare(Vector* pVector)
{
   return pVector->x * pVector->x + pVector->y * pVector->y;
}

Vector universe = { 4, 2 };
printf("%d\n", lengthSquare(&universe));


// En C++, on préfère :
struct Vector
{
   int x, y;

   int lengthSquare()
   {
      return x * x + y * y;
   }
};

Vector universe = { 4, 2 };
printf("%d\n", universe.lengthSquare());

À l'intérieur d'une méthode, les variables membres de la structure sont accessibles comme des variables locales.

Pour appeler une méthode, il suffit de faire comme s'il s'agissait d'une variable membre (nom de la variable et opérateur . ou ->), puis de mettre les parenthèses et les arguments, comme pour un appel de fonction normal :

Vector universe = ...;
universe.lengthSquare();

Vector *pUniverse = ...;
pUniverse->lengthSquare();

Constructeur

Le constructeur est une fonction appelée lors d'une instanciation de la classe. L'instanciation est l'opération consistant à créer un objet ayant pour type la classe :

Vector v;          // Ceci est une instanciation : 
                   // on crée un nouveau vecteur.
Vector *pv = &v;   // Ceci n'est pas une instanciation : on ne crée pas
                   // de nouveau vecteur, mais juste un pointeur
                   // sur une instance existante.

Tous les constructeurs portent le même nom, qui est celui de la classe. Ils n'ont pas de type de retour. Grâce à l'overloading, il est possible de créer plusieurs constructeurs pour une classe, du moment que cela n'introduit pas d'ambiguïté.

Constructeur avec arguments

La création d'un constructeur permet d'initialiser la classe avec certaines valeurs. Par exemple :

struct Vector
{
   int x, y;

   Vector(int initX, int initY)
   {
      x = initX;
      y = initY;
   }
};

// Utilisation :
Vector universe(4, 2);   // initX == 4, initY == 2

Vous pouvez voir sur l'exemple qu'on a été obligé de donner un autre nom aux arguments du constructeur. Si on avait écrit Vector(int x, int y), les lignes suivantes auraient été x = x; et y = y;, ce qui n'aurait pas fonctionné.

Plutôt que de changer le nom, on peut utiliser l'une des deux astuces suivantes :

// Solution verbeuse :
Vector(int x, int y)
{
   this->x = x;   // this est un pointeur automatique
                  // sur la structure que l'on crée
   this->y = y;   // this->x est la variable membre x,
                  // x est le premier paramètre du constructeur
}

// Solution concise :
Vector(int x, int y) : x(x), y(y)
{
}

Dans la dernière solution, dans x(x), le x de gauche est celui de la structure, celui de droite est l'argument du constructeur. On aurait aussi pu écrire :

Vector(int initX, int initY) : x(initX), y(initY)
{
}

Constructeur vide

Lorsque vous ne créez pas de constructeur dans une classe, le compilateur en ajoute un par défaut, qui ne prend pas d'arguments et ne fait rien de particulier. Si vous créez un constructeur qui prend des arguments, le compilateur n'ajoute plus ce constructeur par défaut. Il devient alors impossible de ne pas appeler votre propre constructeur lors d'une instanciation, sous peine d'erreur de compilation. Exemple :

struct Vector
{
   int x, y;
   Vector(int x, int y) : x(x), y(y) {}
};

Vector universe(4, 2);  // OK
Vector v;               // Erreur ici : g++ dit qu'il ne trouve pas 
                        // de constructeur vide

Pour corriger ce problème, il faut créer vous-mêmes un constructeur sans arguments :

struct Vector
{
   int x, y;
   Vector(int x, int y) : x(x), y(y) {}
   Vector() {}
};

Vector universe(4, 2);  // OK
Vector v;               // OK

Autre solution : mettre des valeurs par défaut sur le premier constructeur :

struct Vector
{
   int x, y;
   Vector(int x = 0, int y = 0) : x(x), y(y) {}
};

Vector v;   // Équivalent à : Vector v(0, 0);

Références

Pointeurs vs. références

Les références permettent de remplacer les pointeurs dans de nombreux cas, en apportant de la simplicité. Comparons avec les pointeurs, sur cet exemple :

Vector *pVector = &v;
pVector->x = 42;
pVector->lengthSquare();
Vector copy = *pVector;

Les références simplifient le code : pas de changement de syntaxe entre valeur et référence sur une valeur. Pas de * partout, pas de ->. Il faut seulement ajouter & au type pour indiquer que c'est une référence, de même que * signale un pointeur.

Vector &vector = v;
vector.x = 42;
vector.lengthSquare();
Vector copy = vector;

On voit donc que, syntaxiquement, vector et v sont équivalents : on ne peut pas deviner que vector est une référence sans regarder sa déclaration.

Passage par référence

Il arrive qu'une fonction ait besoin de modifier un de ses arguments, souvent pour retourner une valeur. Prenons par exemple la fonction suivante :

void add(Vector v1, Vector v2)
{
   v1.x += v2.x;
   v1.y += v2.y;
}

Vector v1(3, 1);
Vector v2(1, 1);
add(v1, v2);
// Ici, v1 n'a pas changé

Cette fonction ne fournit pas le résultat souhaité. On voudrait que v1 ait changé de valeur après l'appel de fonction. Mais comme il a été passé par valeur, la fonction a modifié une copie de v1 et non v1 lui-même : la fonction ne fait donc strictement rien.

Pour résoudre ce problème, il faut passer v1 par référence, en utilisant les pointeurs (on dit aussi par pointeur dans ce cas). La fonction peut suivre la référence et ainsi modifier la valeur de la variable. Cela permet de créer des fonctions du genre :

void add(Vector* v1, Vector v2)
{
   v1->x += v2.x;
   v1->y += v2.y;
}

Vector v1(3, 1);
Vector v2(1, 1);
add(&v1, v2);
// Ici, v1 == Vector(4, 2)

L'inconvénient des pointeurs est syntaxique : on est obligé de mettre plein de * et de -> dans le code, ce qui alourdit inutilement la syntaxe. De plus, v1 et v2 sont traités différemment dans le code, ce qui n'est pas joli. Les références permettent de faire la même chose plus simplement, en ajoutant & au type des arguments à passer par référence :

void add(Vector& v1, Vector v2)
{
   v1.x += v2.x;
   v1.y += v2.y;
}

Vector v1(3, 1);
Vector v2(1, 1);
add(v1, v2);
// Ici, v1 == Vector(4, 2)

On notera que ce code est quasi-identique au tout premier code qui passait v1 par valeur. On a simplement rajouté un &amp. Mais en fait, il vaut mieux créer cette fonction dans la classe Vector :

struct Vector
{
   // ...
   
   void add(Vector v)
   {
      x += v.x;
      y += v.y;
   }
};

Le passage par référence permet aussi d'économiser la mémoire si l'on a besoin de fournir de grosses structures à une fonction. Exemple :

struct BigData
{
   int values[100000];
   int count;
};

void displayData(BigData data)
{
   for (int i = 0; i < data.count; i++)
      printf("%d ", data.values[i]);
}

BigData data;
data.values[0] = 4;
data.values[1] = 2;
data.count = 2;
displayData(data);

Ce code fonctionne, mais au moment où l'on appelle displayData(), le programme fait une copie complète de l'objet data pour la donner à la fonction. Cette copie est non seulement inutile mais coûteuse : la structure BigData contient presque 100 ko de données ! Pour éviter cela, il suffit de passer data par référence, en écrivant void displayData(BigData& data).

Restrictions pour éviter les bugs

Les références sont moins permissives que les pointeurs. Une fois qu'une référence a été affectée, on ne peut pas la changer.

Vector *pVector = &v1;
...
pVector = &v2;
// pVector pointe sur v2

Vector &vRef = v1;
...
// Comme vRef pointe sur v1, ceci est équivalent à v1 = v2 :
vRef = v2;
// vRef pointe toujours sur v1,
// mais les champs de v2 ont été copiés dans v1

Dans le même ordre d'idée, on ne peut pas manipuler le pointeur sous-jacent à la référence : il n'y a pas d'arithmétique des références. L'exemple suivant montre les dangers de l'arithmétique des pointeurs :

Vector *pVector = &v1;
pVector++;        // Autorisé, mais dangereux : 
                  // pVector pointe vers une donnée invalide
*pVector = 3;     // Plantage
pVector[2] = 5;   // Plantage

Les références ne permettent pas de faire ces opérations dangereuses, ce qui peut éviter certains bugs.

Mot clé const

Arguments constants

Le mot clé const existait déjà en C. Par exemple, dans fonction strlen(const char* string), le const indique que la chaîne n'est pas modifiée par la fonction. Formellement, le const empêche la fonction de modifier ce qui est pointé par le pointeur (mais on peut toujours modifier le pointeur lui-même, pour le faire pointer sur autre chose).

En C++, const est aussi applicable aux références. Par exemple :

// Dans la classe Vector:
// La fonction add() ne modifie pas le vecteur v
int add(const Vector& v)
{
   x += v.x;
   y += v.y;
}

const peut sembler gadget au point où nous en sommes, mais quand nous utiliserons les structures de données du C++, il faudra y faire très attention sous peine de messages d'erreur.

Méthodes constantes

L'idée est ici d'appliquer const à une fonction toute entière, pour dire que la fonction n'a pas le droit de modifier les variables membres de la classe, ni d'appeler des méthodes non-const.

// La fonction lengthSquare() utilise mais ne modifie pas x et y
int lengthSquare() const
{
   return x * x + y * y;
}

// Interdit : la fonction add() modifie les variables membres x et y
void add(const Vector& v) const
{
   x += v.x;
   y += v.y;
}

Opérateurs

Définition

Un opérateur est un symbole spécial qui joue le rôle d'une fonction. Par exemple + (fonction addition), *= (fonction multiplication + affectation), < (fonction de comparaison par infériorité stricte), && (fonction de calcul du ET logique), etc.

Déclaration

Tous les opérateurs du C++ sont redéfinissables, par exemple donner un sens à Vector + Vector, ou à Vector *= float. Certaines structures de données du C++ exigent que l'on définisse des opérateurs, notamment pour comparer des objets (utilisé par le tas).

La définition d'opérateurs est également utile pour la géométrie : ajout de vecteurs, calcul de produit scalaire, etc.

// Syntaxe de déclaration :
typeRetour operator nom(arguments)

Le nombre d'arguments des opérateurs est fixé (sauf pour certains opérateurs dont nous ne parlerons pas ici). Par exemple, l'opérateur + prend un argument, qui est la valeur située à droite du +. La valeur située à gauche est la classe elle-même (le this). Même chose pour +=, &&, =, <, etc. En fait, tous les opérateurs que vous aurez à redéfinir s'écriront de la manière suivante :

struct MyStruct
{
   ...
   typeRetour operator nom(const MyStruct& value) const
   {
      ...
   }
};

En effet, les opérateurs ne modifient pas leurs arguments, d'où le const devant l'argument, et un passage par référence permet d'éviter de copier l'argument quand le programme appelle l'opérateur. Le const situé en bout de déclaration ne doit pas être mis pour les opérateurs qui modifient les membres de la classe. Cependant, dans les faits, la plupart des opérateurs que vous définirez ne seront pas dans ce cas.

Pièges à éviter

• Ne pas oublier de const, que ce soit sur les références ou sur la fonction, sous peine de messages d'erreur à la pelle.
• Seuls les opérateurs C/C++ valides sont redéfinissables, il est impossible d'en ajouter.
• Utiliser au maximum les références, pour éviter les passages par valeur.

Exemples

// Ne pas oublier le "const" au bout
Vector operator + (const Vector& v) const
{
   // Création d'un object par appel du constructeur
   return Vector(x + v.x, y + v.y);
}

// Pas de "const" au bout : cet opérateur modifie la classe
void operator += (const Vector& v)
{
   x += v.x;
   y += v.y;
}

// Utilisation du type "bool"
bool operator == (const Vector& v) const
{
   return x == v.x && y == v.y;
}

Exercice : coder un opérateur < pour la classe Vector, selon le tri lexicographique.

Correction :

bool operator < (const Vector& v) const
{
   return (x < v.x) || (x == v.x && y < v.y);
}

Exercice : coder une classe Vector avec les opérateurs soustraction (symbole -=), produit scalaire (symbole *), produit vectoriel (symbole ^).

Utilisation de la STL

La STL, acronyme de Standard Template Libary, est la bibliothèque de classes C++ standard. Elle offre le support de nombreuses structures de données, dont certaines compliquées à coder telles que les tables de hachage. La STL étant standardisée, vous la retrouverez sur tout compilateur C++ récent, sans changement de syntaxe.

Les templates permettent d'écrire du code générique, indépendant d'un type de données particulier. Par exemple, si vous avez codé une structure de pile d'entiers et que vous avez besoin d'une pile de chaînes de caractères, il est dommage d'avoir à tout recoder ou de faire un gros copier-coller. En effet, le code de gestion de la pile est le même dans les deux cas, seul le type des éléments change. Le C++ permet de créer ses propres templates, mais dans ce cours nous ne ferons qu'utiliser des templates déjà existants.

Pour nous, les templates seront comme des classes paramétrées. Il s'agit en général du type des éléments contenus dans le template. Pour utiliser un template, on doit toujours indiquer la valeur des paramètres sinon le compilateur génère une erreur. Par exemple, on doit préciser une pile d'entiers, un tableau de nombres flottants, etc. Les paramètres sont ajoutés au nom de la classe du template, entre chevrons : NomClasse<paramètre1, paramètre2, ..., paramètreN>. Par exemple stack<int> ou vector<float>.

Les paramètres peuvent être aussi bien des types de base (int, float, char*) que des structures ou des classes.

Pile : classe stack

La plupart du temps, vous coderez vos piles avec un tableau de taille fixée et un entier contenant sa taille. Cependant, dans de rares cas, par exemple lorsque la taille maximale de la pile n'est pas connue à l'avance, un tableau dynamique peut être nécessaire.

Déclaration

#include <stack>
using namespace std;

stack<int> pile;

Opérations

void pile.push(valeur);   // Empiler
TYPE pile.top();          // Récupérer la valeur du haut
void pile.pop();          // Dépiler sans rien retourner
bool pile.empty();        // Regarder si la pile est vide
void pile.clear();        // Tout vider

Exemple

// Affiche 1 5 3
stack<int> pile;
pile.push(3);
pile.push(5);
pile.push(1);
while (!pile.empty())
{
   printf("%d\n", pile.top());
   pile.pop();
}

Tableau : classe vector

De même que pour les piles, les tableaux statiques suffisent dans la plupart des cas. Cependant, lorsque la taille du tableau ne peut pas être bornée, il faut utiliser en C malloc() et free() pour gérer la mémoire. Le C++ nous évite cette corvée grâce au template vector.

Déclaration

#include <vector>
using namespace std;

vector<int> tableau;

Opérations

TYPE tab[index];                // Lecture
tab[index] = valeur;            // Modification
size_t tab.size();              // Taille du tableau
void tab.push_back(valeur);     // Ajout à la fin
void tab.pop_back();            // Supprimer dernier élément
void tab.assign(nb, valeur);    // Mettre nb élts de valeur donnée
tab.erase(tab.begin() + index); // Supprimer un élément
bool tab.empty();               // Regarder si le tableau est vide
void tab.clear();               // Tout vider
TYPE tab.front();                 // Récupérer la première valeur
TYPE tab.back();                // Récupérer la dernière valeur

Le type des index est size_t (entier positif). On peut aussi utiliser int mais le compilateur risque de générer des warnings.

L'opérateur crochet ne fonctionne que si l'élément indexé existe :

stack<int> tableau;
printf("%d\n", tableau[3]);   // Interdit
tableau.assign(4, 42);
printf("%d\n", tableau[3]);   // Affiche "42"

Exemple

// Affiche 42 5 42 42 3
vector<int> tableau;
tableau.assign(5, 42);
tableau.push_back(3);
tableau.erase(tableau.begin() + 2);
tableau[1] = 5;
for (size_t i = 0; i < tableau.size(); i++)
   printf("%d\n", tableau[i]);

File à priorité : classe priority_queue

Note : si vous ne savez pas ce qu'est une file à priorité ou un tas, vous pouvez passer cette partie et revenir dessus plus tard.

Déclaration

#include <queue>
using namespace std;

priority_queue<int> tas;

Opérations

void tas.push(valeur); // Empiler
TYPE tas.top();        // Récupérer la + gde valeur selon l'opérateur <
void tas.pop();        // Dépiler la + gde valeur sans rien retourner
bool tas.empty();      // Regarder si le tas est vide

Exemple avec type de base

// Affiche 5 3 1
tas.push(3);
tas.push(5);
tas.push(1);
while (!tas.empty())
{
   printf("%d\n", tas.top());
   tas.pop();
}

Exemple avec type personnalisé

Pour créer une file à priorité de structures, il faut définir un opérateur <. Attention ! Le sommet du tas contient le plus grand élément. Pour obtenir le plus petit, il faut inverser la signification de l'opérateur <.

struct Vector
{
   int x, y;
   Vector(int x, int y) : x(x), y(y) {}
   
   // Constructeur vide requis par priority_queue
   Vector() {}
   
   // Comparaison inversée
   // Les "const" sont obligatoires, sous peine
   // de messages d'erreur à foison
   bool operator < (const Vector& v) const
   {
      return (x > v.x) || (x == v.x && y > v.y);
   }
};

// Affiche 2,2 3,3 4,1 4,2
priority_queue<Vector> heap;
heap.push(Vector(4,2));
heap.push(Vector(2,2));
heap.push(Vector(4,1));
heap.push(Vector(3,3));
while (!heap.empty())
{
   const Vector &v = heap.top();
   printf("%d,%d\n", v.x, v.y);
   heap.pop();
}

Exercice : coder un algorithme de plus court chemin à la Dijkstra, en utilisant priority_queue.

Table de hachage : classes hash_set et hash_map

Note : si vous ne savez pas ce qu'est une table de hachage, vous pouvez passer cette partie et revenir dessus plus tard.

Il existe deux types de tables de hachage dans la STL :

• hash_set<K> : table de hachage simple, stocke seulement des clés de type K.
• hash_map<K,T> : table de hachage double : stocke des clés de type K associées à des valeurs de type T. À une clé donnée ne peut être stockée qu'une seule valeur.

Déclaration

Malheureusement, les classes hash_set et hash_map ne sont pas standardisées, d'où des déclarations un peu exotiques et dépendant étroitement du compilateur.

Avec g++ 3.2.3 ou plus récent (compilateur des IOI) :

#include <ext/hash_map> // l'un
#include <ext/hash_set> // ou l'autre ou les deux, au choix
using namespace __gnu_cxx;

Avec g++ anciennes versions et les autres compilateurs (Borland, Microsoft) :

#include <hash_map> // l'un
#include <hash_set> // ou l'autre ou les deux, au choix
using namespace std;

La suite ne change pas :

hash_set<int> simpleHashTable;
hash_map<int, char *> doubleHashTable;   // clé = int, valeur = char *

Opérations

hashtable.erase(clé);      // Suppression
hashtable.clear();         // Vidage

// Test de présence : true si clé est contenue, false sinon
hashtable.find(clé) != hashtable.end()

// hash_set seulement
hashtable.insert(clé);     // Insertion

// hash_map seulement
hashtable[clé] = valeur;   // Insertion ou modification
hashtable[clé]             // Accès

Exemple avec type de base

hash_map<int, char *> hashtable;
hashtable[3] = "trois";
hashtable[5] = "CINQ";
hashtable[5] = "cinq";
hashtable[42] = "quarante-deux";

// Affiche 5 -> cinq
printf("5 -> %s\n", hashtable[5]);

// Affiche 5 -> (null)
hashtable.erase(5);
printf("5 -> %s\n", hashtable[5]);

// Affiche "Contient 42"
if (hashtable.find(42) != hashtable.end())
   puts("Contient 42");
else
   puts("Ne contient pas 42");

Exemple avec type personnalisé, hash_set

Pour utiliser une structure ou une classe comme clé, il faut définir un opérateur ==, ainsi qu'un opérateur () chargé de calculer la valeur de hachage d'une clé donnée, de type size_t. Cet opérateur est la fonction de hachage.

struct KeyStruct
{
   char* key;
   
   KeyStruct() {} // Nécessaire
   KeyStruct(char* key) : key(key) {}
   
   bool operator == (const KeyStruct &other) const
   {
      return !strcmp(key, other.key);
   }
   
   // Calculer la valeur de hachage
   size_t operator () (const KeyStruct& k) const
   {
      size_t value = 0;
      for (int i = 0; k.key[i] && i < sizeof(size_t); i++)
         value = (value << 8) | k.key[i];
      return value;
   }
};


int main()
{
   // Premier argument : le type de clé à stocker
   // Second argument (si type personnalisé seulement) :
   // la structure contenant la fonction de hachage,
   // sous la forme d'un opérateur ()
   hash_set<KeyStruct, KeyStruct> dict;
   dict.insert(KeyStruct("universe"));
   dict.insert(KeyStruct("forty-two"));
   printf("contains universe? %x\n",
          dict.find(KeyStruct("universe")) != dict.end());
   printf("contains world? %x\n",
          dict.find(KeyStruct("world")) != dict.end());
   
   return 0;
}

Exemple avec type personnalisé, hash_map

Cette fois on veut associer une fréquence à chaque mot du dictionnaire. Le code est presque identique :

struct KeyStruct
{
   char* key;
   
   KeyStruct() {} // Nécessaire
   KeyStruct(char* key) : key(key) {}
   
   bool operator == (const KeyStruct &other) const
   {
      return !strcmp(key, other.key);
   }
   
   // Calculer la valeur de hachage
   size_t operator () (const KeyStruct& k) const
   {
      size_t value = 0;
      for (int i = 0; k.key[i] && i < sizeof(size_t); i++)
         value = (value << 8) | k.key[i];
      return value;
   }
};


int main()
{
   // Premier argument : le type de clé à stocker
   // Second argument : le type des valeurs associées aux clés
   // Troisième argument (si type personnalisé seulement) :
   // la structure contenant la fonction de hachage,
   // sous la forme d'un opérateur ()
   hash_map<KeyStruct, int, KeyStruct> dict;
   
   // Si nécessaire, hash_map utilise 0 comme valeur par défaut,
   // on peut donc utiliser '++' sans initialiser explicitement la valeur.
   dict[KeyStruct("universe")]++;
   dict[KeyStruct("universe")]++;
   dict[KeyStruct("forty-two")] = 3;
   printf("universe frequency? %d\n", dict[KeyStruct("universe")]);
   printf("world frequency? %d\n", dict[KeyStruct("world")]);
   
   return 0;
}

Exercice

Écrivez un programme gérant les chambres et les clients d'un hôtel. On peut donner trois types de requêtes, à raison d'une requête par ligne :

• enregistrement d'un client : add client_name room_number : écrire le nombre de clients dans l'hôtel.
• récupération du numéro de chambre d'un client donné : get client_name, écrire le numéro, ou -1 si le client n'est pas dans l'hôtel.
• libération d'une chambre : remove client_name, écrire le nombre de clients dans l'hôtel.

Exemple de session :

add Dupond 3         réponse : 1
add Smith 5          réponse : 2
add Dupond 7         réponse : 2
get Dupond           réponse : 7
remove Dupond        réponse : 1
get Dupond           réponse : -1

Contraintes : 1 000 000 clients simultanément, 10 000 000 requêtes, 1 seconde, pas de limite de mémoire.

Tri

La bibliothèque standard du C contient déjà la fonction qsort() pour trier un tableau. Cependant cette fonction est lente, car elle utilise des pointeurs de fonctions. De plus, elle oblige à créer une fonction utilitaire même pour les cas simples, comme trier un tableau d'entiers.

La STL contient une fonction de tri à base de templates nettement plus performante, ce qui peut faire la différence pour les très gros tableaux. Cette fonction s'appelle tout simplement sort(), se trouve dans le header #include <algorithm>, et trie les éléments par ordre croissant, selon l'opérateur <. Elle prend en argument un pointeur sur le premier élément du tabeau à trier, ainsi qu'un pointeur sur l'élément qui suit le dernier élément à trier. Attention, le deuxième pointeur n'est pas un pointeur sur le dernier élément du tableau.

Déclaration

#include <algorithm>
using namespace std;

Utilisation

// Ordre par défaut : opérateur <
sort(pointeur_début, pointeur_fin);

// Ordre personnalisé : opérateur () de ClasseDeTri
sort(pointeur_début, pointeur_fin, ClasseDeTri());

Dans les deux cas d'utilisation, pointeur_début est un pointeur sur le début du tableau, et pointeur_fin un pointeur sur l'élément qui suit le dernier élément du tableau ; ce n'est pas un pointeur sur le dernier élément du tableau. Si le tableau est vide, pointeur_fin est égal à pointeur_début.

Dans le cas d'un tableau, on utilise sort(tab, tab + N); où N est le nombre d'éléments du tableau. Dans le cas d'un tableau dynamique vector, on utilise sort(vec.begin(), vec.end());.

Exemple 1 : types prédéfinis

#include <cstdio>
#include <algorithm>
using namespace std;

struct OrdreDecroissant
{
   // Renvoie true si 'a' doit être placé avant 'b'
   // dans le tableau trié
   // Le "const" est obligatoire
   bool operator () (int a, int b) const
   {
      return a > b;
   }
};

int tab[3];
tab[0] = 15;
tab[1] = 3;
tab[2] = 7;

// Par défaut, opérateur < : ordre croissant
sort(tab, tab + 3);
// tab contient : 3, 7, 15

sort(tab, tab + 3, OrdreDecroissant());
// tab contient : 15, 7, 3

Exemple 2 : classe personnalisée

struct MyData
{
   bool operator < (const MyData& data) const
   {
      return ...;
   }
};

MyData data[3];
// ...

// Trier selon l'opérateur < défini plus haut
sort(data, data + 3);

Exemple 3 : vector

#include <cstdio>
#include <algorithm>
using namespace std;

vector<int> tab;
tab.push_back(15);
tab.push_back(3);
tab.push_back(7);

// Trier dans l'ordre croissant
sort(tab.begin(), tab.end());

// Trier dans l'ordre décroissant :
// pas besoin de classe de tri,
// il suffit d'utiliser les pointeurs inversés
// Notez le 'r' pour "reverse" devant rbegin() et rend()
sort(tab.rbegin(), tab.rend());

Autres fonctions

La STL définit d'autres fonctions fréquemment utilisées, comme min() et max().

Déclaration

#include <algorithm>
using namespace std;

Utilisation

min(a, b);
max(a, b);
min(pointeur_début, pointeur_fin);
max(pointeur_début, pointeur_fin);

Exemple

int tab[3];
tab[0] = 3;
tab[1] = 15;
tab[2] = 7;

// Affiche 3
printf("%d\n", min(3, 15));

// Affiche le max de l'ensemble du tableau : 15
printf("%d\n", max(tab, tab + 3));