2. Introduction à la STL§

2.1. Rappel§

2.1.1. La librairie standard C++§

La librairie standard C++ est composée:

  • de la librairie standard C (en-têtes commençant par la lettre ‘c’)
  • de la librarie de flux d’entrée-sortie
  • de la STL (= Standard Template Library) composé de:
    • conteneurs (ensembles structurés de données)
    • iterateurs (généralisation des pointeurs)
    • foncteurs (généralisation des fonctions)
    • algorithmes

Comme en Java, une bonne maîtrise du langage C++, c’est aussi une bonne maîtrise de la librairie standard.

2.1.2. La STL§

Sa force est

  • d’être générique (les conteneurs et algorithmes sont paramétrés par le type des données via le mécanisme template),
  • de rendre conteneurs et algorithmes orthogonaux (les algorithmes manipulent des itérateurs plutôt qu’un conteneur, de sorte qu’un même algorithme peut être appliquer à différents conteneurs),
  • d’être compatible avec le C (notamment en généralisant les pointeurs et les fonctions).

2.2. Conteneurs§

2.2.1. Quelques exemples§

Un conteneur est un ensemble structuré de données:

  • std::vector (tableau dynamique)
  • std::list (liste doublement chaînée)
  • std::map (tableau associatif)
  • std::set (ensemble non ordonné, sans doublon)
  • ...

Consultez aussi http://www.cplusplus.com/.

2.2.2. Construction§

Tous les conteneurs sont paramétrables par le type d’éléments à contenir (via le mécanisme template) et ont un constructeur par défaut:

#include<vector>
#include<list>
#include<set>
#include<map>
...
std::vector<double> v1;
std::vector<std::string> v2;
std::list<int> l;
std::set<std::string> s;
std::map<std::string, int> m;

Les conteneurs ainsi créés sont vides.

2.2.3. Alimentation§

Les conteneurs qui satisfont le concept de Sequence ont une méthode insert() qui prend en paramètre la valeur à insérer.

s.insert("toto");

Les conteneurs qui satisfont en plus le concept BackInsertionSequence, comme std::vector ou std::list, ont une méthode push_back() pour ajouter à la fin du conteneur.

v1.push_back(2.0);

2.2.4. Paire§

Les std::map sont des ensembles de paires (clé-valeur). Les paires sont modélisés par la classe std::pair.

std::pair<std::string, int> p("janvier", 31);

Attention, dans std::map, ce sont des paires qui sont stockées; on insère donc des paires:

m.insert( p );

2.2.5. Ex.1. Map/Vector (10 min)§

  • Dans un programme TestMap.cpp, écrivez le code permettant d’alimenter un tableau associant les 12 mois de l’année avec leur durée en nombre de jours.
  • Dans un programme TestVector.cpp, écrivez le code permettant d’alimenter un tableau des 50 premiers nombres paires positifs.

2.3. Iterateurs§

2.3.1. Qu’est-ce que c’est ?§

Un iterateur est un objet léger donnant un moyen de parcourir, lire et/ou écrire les données d’un conteneur.

Ce sont une généralisation des pointeurs. En tant que tels, si it est un iterateur, on peut faire, entre autres opérations, it++ pour atteindre la donnée suivante et *it pour obtenir la donnée pointée.

2.3.2. Comment créer un iterateur ?§

Tous les conteneurs de la STL ont les types internes suivants

  • iterator (données en lecture/écriture)
  • const_iterator (données en lecture seule)

et fournissent des iterateurs par les méthodes suivantes

  • begin(): itérateur positionné sur la première donnée,
  • end(): itérateur positionné après la dernière.

En général, on ne construit pas un iterateur de zéro, on en demande aux conteneurs.

2.3.3. Comment les utiliser ?§

Avec un itérateur, le parcours de tous les éléments d’un conteneur ressemble à ceci:

for (Conteneur::const_iterator it = leConteneur.begin();
     it != leConteneur.end(); it++)
{
  *it = 0; //initialisation a zero
}

On imite ainsi le code C, basé sur un pointeur:

int tab[N];
for (int* ptr = tab; ptr != (tab + N); ptr++)
{
  *ptr = 0;
}

2.3.4. En sens contraire§

De nombreux conteneurs supportent un parcours de leurs éléments dans les deux sens. Il suffit d’opter pour les bons itérateurs:

for (Conteneur::const_reverse_iterator it = leConteneur.rbegin();
     it != leConteneur.rend(); it++)
{
  ...
}

2.3.5. Concept de range§

Un range est un intervalle de données d’un conteneur implicitement décrit par une paire (ordonnée) d’itérateurs.

Par exemple, leConteneur.begin() et leConteneur.end() décrivent un range correspondant à l’ensemble des données du conteneur.

Pour une paire d’itérateurs (itb, ite), on suppose que:

  • ite est atteignable par itb, en incrémentant itb un nombre fini de fois.
  • ite pointe après la dernière donnée (past-the-end).

2.3.6. Ex.2. Parcours (20 min)§

  • Dans testMap.cpp, affichez sur la sortie standard le contenu du tableau associatif. (Une paire possède les champs first et second contenant les deux données de la paire).
  • Dans testVector.cpp, affichez sur la sortie standard le contenu du tableau (à l’aide d’itérateurs) en sens direct, puis en sens contraire.
  • Dans le même fichier, copiez toutes les valeurs du vecteur dans un tableau statique à la C (à l’aide d’itérateurs et d’un pointeur, sans utiliser l’opérateur d’accès []).

2.4. Algorithmes§

2.4.1. Quelle forme ont-ils ?§

Les algorithmes sont des fonctions dont les paramètres d’entrées sont des itérateurs sur un ou deux conteneurs (plus, pour certains un foncteur agissant sur les données) .

Cette interface sous forme de fonctions

  • les rend compatibles avec le C.
  • facilite leur utilisation dans le code client (pas besoin de préciser les paramètres template, car ils sont automatiquement déduits par le compilateur).

2.4.2. Principaux algorithmes§

Sont disponibles après #include<algorithm>:

  • std::equal (vérifie que deux ranges sont égaux)
  • std::fill (inialise un range avec une valeur)
  • std::copy (copie un range dans un autre)
  • std::sort (trie les données d’un range)
  • std::min_element, std::max_element (min, max d’un range)
  • std::reverse (inverse l’ordre d’un range)
  • ...

Consultez la liste des algorithmes

2.4.3. Ex.3. Algorithmes (15 min)§

Dans testVecteur.cpp:

  • utilisez std::equal pour tester si, après la copie, le vecteur et le tableau statique contiennent bien les mêmes données.
  • utilisez std::copy pour réaliser la copie en une seule ligne.

2.5. Foncteurs§

2.5.1. Qu’est-ce que c’est ?§

Un foncteur est la généralisation d’une fonction. C’est un objet possédant l’opérateur (), qui admet le plus souvent aucun, un ou deux paramètres et retourne une valeur.

NB. Un predicat est un foncteur qui retourne une valeur de type bool.

Le foncteur se distingue d’une fonction en ce qu’il peut, comme tout objet, avoir un état.

2.5.2. Comment écrire un foncteur ?§

Pour créer un foncteur, l’étape cruciale consiste à surcharger l’opérateur () (la méthode s’appelle operator(), d’où les doubles parenthèses):

#include<cstdlib> //pour std::rand
class GenerateurAleatoire {
  public:
    int operator()() {
      return std::rand()%100;
    }
};

Après avoir instancier votre foncteur, vous pouvez l’utiliser comme une fonction:

MonGenerateurAleatoire g;
std::cout << g() << std::endl; //entre 0 et 99

2.5.3. Ajouter un état§

Dans cet example, on peut aussi bien utiliser une fonction:

int g() {
  return std::rand()%100;
}
...
std::cout << g() << std::endl; //entre 0 et 99

Mais, un foncteur est adaptable, sans modifier la liste des paramètres de l’opérateur ():

#include<cstdlib> //pour std::rand
class GenerateurAleatoire {
  public:
    int monMax;
    GenerateurAleatoire(int max): monMax(max) {}
    int operator()() {
      return std::rand()%monMax; //entre 0 et monMax-1
    }
};

2.5.4. Ex.4. Foncteurs/Algorithmes (20 min)§

  • Créez un foncteur retournant un nombre aléatoire entre 0 et 99. Utilisez-le pour alimenter un conteneur de type std::vector par des nombres aléatoires à l’aide de std::generate.
  • Créez un foncteur affichant sur la sortie standard un entier donné. Utilisez-le pour afficher les données du conteneur à l’aide de std::for_each.
  • A l’aide d’un foncteur et de std::transform, divisez par deux les nombres paires.

2.5.5. Ce qu’il faut retenir§

La STL est composé de:

  • conteneurs,
  • iterateurs,
  • foncteurs,
  • algorithmes.

Elle est générique, conteneurs et algorithmes sont orthogonaux.

Elle est compatible avec le C, notamment grâce à la surcharge d’opérateurs, qui permet d’écrire des généralisations des pointeurs (itérateurs) et des fonctions (foncteurs).