VIII - La librairie standard

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

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()

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

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.

Haut de la page

Haut de la page

Haut de la page

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

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)

Haut de la page

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

Haut de la page

Haut de la page