CSI2772 - Concepts avancés de programmation en C++

VIII - La librairie standard

1. STL: Standard Template Library

1. vectors :
   • tableau dynamique
   • élément avec accès aléatoire, retrait et insertion.
   • peu ou pas de retrait au milieu
2. list :
   • liste doublement chainée
   • aussi forward_list pour une liste simplement chainée
   • traitement séquentiel, avec insertion ou retrait n'importe où dans la liste
3. deque
   • file à deux extrémités
   • se comporte comme un vecteur mais avec insertion et retrait en tête ou en queue de liste
   • les éléments se sont pas nécessairement contigus
4. array
   • tableau fixe

• Le conteneur contient des copies des éléments ajoutés.
• Les éléments à mettre dans le contenueur doivent avoir un constructeur par défaut, un constructeur copieur, et un opérateur =

Haut de la page

2. Les vecteurs

Il existe quatre types d'itérateurs pouvant parcourir un conteneur.

• ::iterator
• ::reverse_iterator
• ::const_iterator
• ::const_reverse_iterator

Les itérateurs const ne permettent pas de modifier le conteneur. Les itérateurs inversés utilisent rbegin() et rend() alors que les autres utilisent begin() et end()

Exemple : Initialisation et itération

Exemple : Manipulation de vecteurs

Exemple : Vecteurs multidimensionnels

En tout temps, utiliser vector plutôt qu'un tableau fixe, ou de l'allocation dynamique. Il faut toutefois l'utiliser efficacement :

• Il est possible de réserver l'espace approprié
  

  vector v(10);
  v.reserve(10);

• La conversion vector -> int* (un tableau régulier) est possible.

  void fct(int a[], int dim); vector<int> v;
  [...]
  fct(&v[0], v.size());
  fct(&*v.begin(), v.size());

• Il est recommandé d'utiliser swap afin de réduire la taille du vecteur.

  vector<int>(v.begin(), v.end()).swap(v);
  
  // un nouveau vecteur d'entier est initialisé avec les valeurs de v.
  // La durée de vie correspond à la durée de l'énoncé.

• Les vector<bool> sont spéciaux: ils utilisent une représentation compacte où un bool équivaut à un bit

Haut de la page

3. Les itérateurs

Les itérateurs servent à désigner des partitions à l'intérieur d'un conteneur.

Les itérateurs peuvent être invalidés lors d'une insertion ou retrait.

Les itérateurs permettent de définir des intervalles à la construction.

Remarque : Là où des itérateurs sont requis, on peut toujours utiliser des pointeurs.

Exemple 1

Exemple 2

Haut de la page

4. Les tri des éléments

Haut de la page

5. Les ostream_iterator et istream_iterator

Exemple 1

Exemple 2

Haut de la page

6. Les maps

map<CLEF, VALEUR> m;

• Une map associe une clé à une valeur.
• Ses éléments sont ordonnés par clé.
• Une map a une seule valeur par clé.
• Une map utilise le < pour comparer / trier les éléments.
• Les itérateurs ne sont jamais invalidés par des insertions ou des retraits.

Attention, le find utilise le < pour trouver l'élément

Équivalence : !(a < b) && !(b < a);

Conclusion :

• insertion : insert est plus efficace
• mise-à-jour : [] est plus efficace

**Attention aux tests avec [] pour des clés qui n'existent pas.

if (m["banane"] > 10)
Si la clé n'existe pas, un int est créé par défaut et la clé banane est insérée. Ce int contient n'importe quoi.

Il vaut mieux utiliser
if (m.find("banane") != m.end() && m["banane"] > 10)

Exemple

Haut de la page

7. Les multimaps

Le multimap permet d'avoir plus d'une valeur par clé, donc insert est toujours valide.

**Attention: Il ne faut jamais mettre à jour la clé d'un conteneur associatif.

Haut de la page

8. Les sets

Haut de la page

9. Les algorithmes

Exemple 1

Exemple 2

Exemple 3

Exemple 4

Exemple 5

Haut de la page