Concepts avancés de programmation en C++

Version Imprimable

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
    • traitement séquentiel, avec insertion ou retrait n'importe où dans la liste
  3. deque
    • file
  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) > 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

Collaboratrices: Emilie Lavigne et Sophie-Catherine Jeaurond