La bibliothèque standard

La bibliothèque standard est livrée avec le compilateur, à condition que celui-ci soit assez récent pour respecter la norme ANSI de 1997 du C++: il est donc important d'utiliser toujours la version la plus récente possible de son compilateur. La bibliothèque comprend une multitude d'objets et de fonctions fort utiles, dont nous présentons brièvement ici les plus importants.

Compléments sur le langage

Certaines particularités du langage n'ont pas encore été abordées: elles peuvent en effet être ignorées, dans une première approche du C++. Cependant, il est nécessaire de les connaître, ne serait-ce que pour comprendre la documentation ou le code de la bibliothèque standard.

Les espaces de noms

Un problème se pose dès lors que l'on travaille avec des bibliothèques venant de plusieurs sources différentes: les noms de classes, de fonctions, de types, etc. employés par les uns et par les autres peuvent parfaitement entrer en conflit; Une manière classique de résoudre le problème est d'inciter les développeurs à utiliser des noms ayant peu de chances d'entrer en conflit, par exemple en mettant devant chaque nom un préfixe particulier. Ainsi, si la bibliothèque GenialeBibliotheque utilise le type string, elle l'appellera GenialeBibliotheque_string . Si la bibliothèque SublimeBibliotheque définit elle aussi un type string, elle l'appellera SublimeBiblitoheque_string. Cependant, le C++ offre un mécanisme bien plus astucieux;

La déclaration namespace

Chacune des deux bibliothèques encapsule toutes ses déclarations dans un bloc appelé namespace, comme on le voit ci-dessous:

namespace GenialeBibliotheque {
   class string {
      ...
   }
}

pour la première bibliothèque et:

namespace SublimeBibliotheque {
   class string {
      ...
   }
}

pour la seconde.

Les aliases d'espaces de noms

On conseille de donner des noms longs pour les espaces de noms: plus le long sera long plus le risque de conflit sera faible. Par contre, plus le long sera long plus la souffrance sera aigûe pour l'utilisateur. Mais, heureusement, nous avons la possibilité de définir des aliases d'espaces de noms comme suit:

namespace GB = GenialeBibliotheque;
namespace SB = SublimeBibliotheque;

L'utilisation des espaces de noms

A partir de là, comment le code utilisateur va-t-il prévenir le compilateur qu'il veut utiliser l'un ou l'autre des espaces de noms ? Trois solutions:

• L'opérateur de portée
• Les déclarations using
• La directive using

L'opérateur de portée permet de spécifier la totalité du nom, comme indiqué ci-dessous:

GB::string S;

La notation est lourde, conduisant à un code peu lisible.

Les déclarations using sont intéressantes, elles permettent de déclarer, objet par objet, le nom de l'espace de nom correspondant. L'opérateur de portée figure dans la déclaration, mais ensuite il est sous-entendu. Par exemple:

using GB::string;
string S;

On a autant de contrôle qu'avec la méthode précédente, mais sans la lourdeur de la notation.

La directive using est plus radicale: elle dit au compilateur que tous les objets de l'espace de noms considéré doivent être accessibles:

using namespace GB;
string S;

Sympathique, car la notation est allégée mais attention: si un nouveau symbole apparaît lors de la prochaine version de la bibliothèque SublimeBibliotheque, par exemple la classe class1, un nouveau conflit peut être généré dans le code utilisateur... il est toujours très désagréable d'avoir de nouvelles erreurs de compilation parce qu'on a changé de version de bibliothèque. La solution la meilleure semble donc bien être celle des déclarations using.

L'espace de noms de la bibliothèque standard

Tous les symboles définis par la bibliothèque standard se trouvent dans l'espace de noms std. D'autre part, les en-tétes de la bibliothèque standard ne comprennent pas le traditionnel .h. D'où les quelques lignes suivantes que l'on trouve en tête des programmes:

#include <iostream>
using namespace std;

Les instructions typedef, using et auto

Les instructions typedef et using permettent de donner un autre nom (synonyme) à un type existant. Il est recommandé de s'en servir, car l'utilisation systématique des modèles dans la bibliothèque standard rend le code difficilement compréhensible si on ne l'utilise pas. using est la manière "C++ moderne" de définir des aliases de types, plus lisible et plus riche que typedef (voir ici pour les détails).

Une autre manière de rendre le code lisible est l'utilisation du spécificateur de type auto.

// à l'ancienne
typedef vector<int> vint_t;

// en C++ moderne
using vint_t = vector<int>

vint_t v1;
auto v2 = v1;

Les types locaux

Nous avons vu qu'il est possible de définir des types à l'intérieur d'une classe: on parle alors de types locaux. La bibliothèque standard fait largement appel à la notion de types locaux, par exemple pour définir des énumérations:

class semaine {
public:
   enum jour {lundi,mardi,mercredi,jeudi,
              vendredi,samedi,dimanche};
   jour j;
...
}

...
if (j == semaine::lundi) {
   ...
}

Remarquez la notation semaine::lundi, utilisant l'opérateur de portée ::
Les itérateurs décrits ci-dessous, apparaissent eux aussi comme des types locaux dans les prototypes de la bibliothèque standard. D'où la syntaxe que nous verrons ci-dessous:

typedef vector <int>::iterator i_int;

L'instruction typename

Dans certains cas, lors de la définition de modèles, il n'est pas simple pour le compilateur de déterminer si une déclaration est une déclaration de type ou de variable: en fait, cette détermination n'est possible que lors de l'instantiation du modèle. Or, suivant qu'il s'agit d'un type ou d'une variable, l'utilisation ultérieure de la chose sera bien différente. On doit donc pouvoir dire au compilateur que tel objet est soit une variable, soit un type. La règle est la suivante:

• Soit rien n'est spécifié, dans ce cas il s'agit d'une variable
• Si on veut forcer une définition de type, on emploie typename

top

Les conteneurs

Les conteneurs sont des objets qui en contiennent d'autres: ce terme général inclue un grand nombre de structures de données: les tableaux, les listes, les queues, ... mais aussi les tableaux associatifs. Comme on pouvait s'y attendre, les conteneurs sont implémentés grâce aux modèles : on devra donc spécifier "ce que" le conteneur contient lors de la déclaration de la variable. Par rapport à un tableau classique "à la C", un conteneur offre un certain nombre d'avantages:

• Allocation dynamique et automatique de mémoire
• Possibilité d'insérer ou supprimer les éléments, pour certains types de conteneurs
• Utilisation d'algorithmes prédéfinis sur ces conteneurs

La surcharge des opérateurs permettra d'écrire du code lisible (opérateur [] pour l'accès aux données dans un vecteur ou opérateur ++ pour les itérateurs, par exemple). Suivant les opérations que l'on doit réaliser, on devra utiliser tel ou tel type de conteneur, afin d'obtenir la meilleure performance. D'ailleurs, certaines opérations ne seront pas implémentées sur tous les conteneurs, non pas parce que ce ne serait pas possible, mais parce que ce serait inefficace.

Conteneurs d'objets ou conteneurs de pointeurs ?

Un conteneur doit-il contenir des objets ou des pointeurs vers des objets ? Le problème avec les conteneurs est qu'on est amené, lorsqu'on remplit le conteneur, à copier les objets. Ceux-ci doivent donc avoir un constructeur de copie et un opérateur=. Si le conteneur contient beaucoup d'objets, si les objets eux-mêmes sont gros, cela peut conduire à une utilisation excessive de la mémoire. Dans ce cas, il peut être intéressant d'utiliser un conteneur de pointeurs. Cependant, une solution plus élégante, disponible en C++11, consiste à définir pour vos objets un constructeur de déplacement et un opérateur= de déplacement: ceux-ci seront utilisés et permettront alors de générer des "copies" bien plus efficaces. Attention tout de même, l'existence de ces fonction entraine quelques conséquences sur l'écriture des objets eux-mếmes (non abordées dans ce cours).

Une possibilité offerte par les conteneurs de pointeurs: mettre un même objet "dans" plusieurs conteneurs. Attention toutefois à ce qui précède: lors de la destruction de l'objet, il faudra supprimer plusieurs pointeurs dans plusieurs conteneurs différents. Une solution peut être alors d'utiliser des objets qui comptent leurs références

Conteneurs hétérogènes ou homogènes ?

Reprenons l'exemple des shape : un conteneur hétérogène pourrait contenir des shape*; cela permettrait de mettre dans le conteneur n'importe quelle forme; le problème est au moment de récupérer l'objet: qu'est-ce que j'ai bien pu mettre là dedans ? Les conteneurs de classes de bases sont les seuls conteneurs hétérogènes vraiment utiles: grâce à l'utilisation des relations d'héritage et des fonctions virtuelles, vous n'aurez pas à vous poser cette question.

Conteneurs séquentiels et conteneurs associatifs (ordonnés).

Les conteneurs de la bibliothèque standard se regroupent en deux familles principales:

• Conteneurs séquentiels
• Conteneurs ordonnés, ou encore conteneurs associatifs

Les conteneurs séquentiels permettent au programmeur de contrôler l'ordre dans lequel les éléments sont insérés.

Les conteneurs ordonnés déterminent eux-mêmes l'ordre dans lequel les éléments sont rangés: ils seront mis dans un ordre permettant de les rechercher très rapidement. Un accès par clé permet d'ailleurs cette recherche: il s'agit donc de conteneurs associatifs, qui fonctionnement de la même manière qu'un tableau associatif en perl, ou un dictionnaire en python.

typedef pair<int,int> p_i_i;
p_i_i p;
p.first=67;
p.second=54;

Les conteneurs de la bibliothèque standard

Les conteneurs disponibles dans la bibliothèque standard sont présentés rapidement ci-dessous:

Conteneurs séquentiels généralistes:

array (c++11)

Tableau à une dimension, taille fixe

vector

Tableau à une dimension, peut se redimensionner

list

Liste doublement chaînée

forward_list (c++11)

Liste simplement chaînée

deque

Ressemble à un vecteur, sauf que l'insertion et la suppression en tête de liste sont plus performantes.

queue

File d'attente (premier entré, premier sorti). Une queue est un adaptateur de conteneur, qui repose (par dé faut) sur un conteneur de type deque.

stack

Pile (dernier entré, premier sorti). C'est un adaptateur de conteneur.

Conteneurs ordonnés généralistes:

map, multimap

Tableau associatif, dans le cas de multimap plusieurs éléments peuvent avoir la même clé Les clés sont mises dans l'ordre, donc on doit pouvoir les comparer

unordered_map, unordered_multimap (c++11)

Tableau associatif, dans le cas de multimap plusieurs éléments peuvent avoir la même clé Les clés sont hachées, donc il doit exister une fonction de hachage.

set, multiset

Ensemble (set), dans le cas de multiset on peut avoir plusieurs fois le même élément.

priority_queue

File d'attente. On accède uniquement à l'objet situé en haut de la queue. De plus, le conteneur garantit que l'objet situï¿œ en haut est le "plus grand". Il s'agit d'un adaptateur de conteneur, qui repose sur un vecteur.

Conteneurs spécialisés:

string, wstring

Chaînes de caractères

bitset

Tableau de booléens.

Types définis sur les conteneurs

Les conteneurs définissent des types en tant que membres publics dont les plus importants sont écrits ci-dessous. On supposera dans ce qui suit qu'on travaille avec l'un de ces deux objets:

• seq<objet> (un conteneur séquentiel)
• ord<cle,valeur> ou ord<cle> (un conteneur ordonné paramétré par un type de clé et éventuellement de valeur).

value_type

Type d'élément: seq<objet>::value_type n'est autre que objet

reference

value_type& (ici objet &)

const_reference

const value_type & (ici const objet & )

size_type

Numéros d'indices, nombre d'éléments, etc.

iterator

value_type*, (ici objet *) permet de balayer le conteneur

const_iterator

Méme chose, mais garantit que les objets récupérés ne seront pas modifiés.

reverse_iterator

Pour balayer le conteneur à l'envers

const_reverse_iterator

no comment

difference_type

Différence entre deux itérateurs

Cas des conteneurs associatifs

Les conteneurs associatifs définissent également les types suivants:

Key ou key_type

Clé d'accès aux éléments. (Ici, cle)

T ou data_type

Type d'éléments stockés. (Ici, valeur)

pair<key,T>

Les objets stockés dans un map (donc value_type). On accède à la clé par le champ first, à la valeur par le champ second. A noter que les paires sont rangées par ordre croissant du champ key. Il est possible de définir ce qu'est cet ordre (cf. la documentation de l'objet map).

top

Quelques fonctions membres ou opérateurs définis sur les conteneurs

Ce paragraphe expose quelques fonctions-membres (les plus utiles) définies sur les conteneurs les plus souvent utilisés: autant dire qu'il ne prétend en aucune façon à l'exhaustivité. Ne sont en effet considérés ici que les conteneurs suivants: vector, list, deque, queue, stack, map, set.

• Itérateurs

  iterator begin(), const_iterator begin() (tous)

  Retourne un itérateur qui pointe sur le premier élément. Permet donc de démarrer une boucle pour faire défiler tous les éléments du conteneur.

  iterator end(),const_iterator begin() (tous)

  Retourne un itérateur qui pointe après le dernier élément. Permet donc de donner une condition de fin à la boucle. Cet objet est aussi utilisé par de nombreuses fonctions (algorithmes ), par exemple find pour signifier que l'objet recherché n'a pas été trouvé.

  typedef conteneur<int>::const_iterator citr;
  for (citr i=V1.begin(); i!=V1.end(); ++i) {
     cout << *i << endl;
  }
  

  ou, plus lisible, en c++11:

  for ( auto i=V1.begin(); i!=V1.end(); ++i) {
     cout << *i << endl;
  }

  encore plus lisible, toujours en c++11:

  for ( auto x : V1 ) {
     cout << x << endl;
  }

• Accès aux éléments

  reference top() const, const_reference top() const (stack)

  Renvoie l'élément situé en haut de la pile. Temps d'exécution constant. La pile ne doit pas être vide.

  reference front() const, const_reference front() const (vector,list,deque)

  Renvoie le premier élément

  reference back() const,const_reference back() const (vector,list,deque)

  Renvoie le dernier élément

  vector<int> V1;
  ...
  int f = V1.front();
  int b = V1.back();
  
  cout << "Premier entier " << f  << endl;
  cout << "Dernier entier " << b  << endl;
  

  reference operator[](size_type n), const_reference operator[](size_type n) (vector,string,deque )

  Permet d'accéder à un élément indicé. Attention, il n'y a pas de contrôle de débordement. Le premier élément a l'indice 0.

  string s = "hello";
  cout << s[0]; // renvoie h
  

  data_type & operator[](const key_type& k) (map)

  Permet d'accéder à un élément à partir de sa clé. Si l'élément n'existe pas, un nouvel enregistrement est créé et inséré dans le conteneur. En conséquence, il n'existe pas de version const de cet opérateur.

  map<string,string> couleurs;
  ...
  couleurs["foreground_color"]="rouge";
  couleurs["background_color"]="blanc";
  

  iterator find(const key_type & k), const_iterator find(const key_type & k) (map,set)

  Renvoie un itérateur pointant sur l'élément de clé k. S'il n'y a pas d'élément de clé k, renvoie end()

  map<string,string> couleurs;
  ...
  map<string,string>::iterator i = couleurs.find("foreground_color");
  if (i==couleurs.end()) {
     cout << "Pas trouvé" << endl;
  } else {
     cout  << "clé=" << i->first << "valeur=" << i->second << endl;
  

  ou, plus lisible, en c++11:

  map<string,string> couleurs;
  ...
  auto i = couleurs.find("foreground_color");
  if (i==couleurs.end()) {
     cout << "Pas trouvé" << endl;
  } else {
     cout  << "clé=" << i->first << "valeur=" << i->second << endl;
  

• Opérations d'insertion et de suppression d'éléments.

  void push(const value_type & x)(stack,queue)

  Insère x en haut de la pile ou à la fin de la queue. Temps d'exécution constant.

  void pop()(stack,queue)

  Supprime l'élément situé en haut de la pile ou en tête de la queue. Temps d'exécution constant. La pile ou la queue ne doit pas être vide.

  void push_front(const value_type & x) (deque,list)

  Insère x au début.

  void pop_front() (deque,list)

  Supprime x du début. Ces fonctions ont un comportement indéfini si le conteneur est vide: utiliser la fonction empty() auparavant.

  void push_back(const value_type & x) (string, deque,list,vector)

  Insère x à la fin.

  void pop_back() (string, deque,list,vector)

  Supprime x à la fin. Ces fonctions ont un comportement indéfini si le conteneur est vide: utiliser la fonction empty() auparavant.

  iterator insert(iterator p,const value_type & x) (vector,list,deque)

  Insère x avant p et retourne un itérateur pointant sur x.

  void insert(iterator p, In first, In last) (vector,list,deque)

  Insère les éléments de l'intervalle semi-fermé [first,last[ immédiatement avant p. Le code suivant insère tout le vecteur V1, moins les trois premiers éléments, au début de la liste L1. Cette insertion est performante, puisque le conteneur de destination est une liste. Par ailleurs, on remarquera que la nature des conteneurs source et destination n'a aucune importance.

  vector<int> V1;
  list<int> L1;
  ...
  vector<int>::iterator i=V1.begin()+3;
  L1.insert(L1.begin(),i, V1.end());
  

  ou, plus lisible, en c++11:

  vector<int> V1;
  list<int> L1;
  ...
  auto i=V1.begin()+3;
  L1.insert(L1.begin(),i, V1.end());
  

  iterator erase(iterator p) (vector,deque,list)
  void erase(iterator p) (map,set)

  Supprime l'élément sur lequel pointe p. La performance dépend du type de conteneur. Pour un conteneur séquentiel, renvoie un itï¿œrateur pointant sur le successeur immédiat de l'élément détruit, éventuellement end().

  iterator erase(iterator first, iterator last) (vector,deque,list)
  void erase(iterator first, iterator last) (map,set)

  Supprime tous les éléments de l'intervalle semi-ouvert [first,last[. La performance dépend du type de conteneur. Pour un conteneur séquentiel, renvoie un itérateur pointant sur le successeur immédiat du dernier élément détruit, éventuellement end().

  void remove(const value_type & valeur) (list)

  Supprime de la liste tous les éléments égaux à valeur

  void unique() (list)

  Supprime de la liste tous les éléments conécutifs égaux de la liste, sauf un.

  void clear() (tous sauf stack)

  Efface tous les éléments.

• Opérations affectant l'ordre des éléments (uniquement list)

  void reverse()

  Retourne l'ordre des éléments dans la liste.

  void sort()

  Trie les éléments de la liste en utilisant operator<

• Opérations diverses

  size_type size() const (tous)

  renvoie le nombre d'éléments dans le conteneur.

  bool empty() const (tous)

  renvoie true si le conteneur est vide.

top

string: les chaînes de caractères

Ce conteneur permet de définir un type chaîne de caractères et de le manipuler simplement et efficacement. Voici quelques-unes des fonctions-membres associées:

Construction de chaînes

On peut utiliser un constructeur par défaut, un constructeur permettant d'initialiser le string à partir d'un char *, ainsi que beaucoup d'autres constructeurs.

Concaténation de chaînes

Surcharge de l'opérateur +

string A="hello";
string B="world";
string C = A + "   " + B;   // C contient hello world
...

Tester l'égalité entre deux chaînes.

Comme d'habitude, les opéteurs ==, !=, <, > etc. sont là pour cela.

Connaître la longueur d'une chaîne.

Par la fonction-membre length().

Trouver un caractère ou une sous-chaîne dans une chaîne

La fonction-membre find renvoie un nombre de type string::size_type. Si le caractère n'existe pas, elle renvoie le membre constant string::npos. Comme pour les autres conteneurs, le premier élément a pour indice 0.

...
string::size_type p1 = C.find('o');	  // renvoie 4
string::size_type p2 = C.find('o',p1+1);  // renvoie 9
string::size_type p3 = C.find('z');       // renvoie npos
if (p3 == string::npos) {
   cout << "Pas de lettre z " << endl;
...

ou, plus lisible, en c++11:

...
auto p1 = C.find('o');	  // renvoie 4
auto p2 = C.find('o',p1+1);  // renvoie 9
auto p3 = C.find('z');       // renvoie npos
if (p3 == string::npos) {
   cout << "Pas de lettre z " << endl;
...

Touver un caractère différent d'un caractère donné:

La fonction-membre find_first_not_of est faite pour cela:

...
string::size_type c1 = C.find(' ');	             // renvoie 5
string::size_type m2 = C.find_first_not_of(' ',c1);  // renvoie 8
...

ou, plus lisible, en c++11:

...
auto c1 = C.find(' ');	             // renvoie 5
auto c2 = C.find_first_not_of(' ',c1);  // renvoie 8
...

Définir une sous-chaîne

Fonction-membre substr. Ses deux paramètres sont: la position à partir de laquelle démarrer la sous-chaîne, et la longueur de celle-ci.

...
string milieu = C.substr(p1,p2-p1+1); // renvoie o   wo 
...

Effacer une sous-chaîne

Fonction-membre erase. Ses deux paramètres sont: la position à partir de laquelle démarrer la sous-chaîne, et la longueur de celle-ci. Renvoie la chaîne après la suppression réalisée:

...
C.erase(p1,p2-p1+1);   // C vaut maintenant hellrld
string milieu = C.substr(p1,p2-p1+1); // renvoie o   wo 
...

Insérer une sous-chaîne

Fonction-membre insert. Ses deux paramètres sont: la position à partir de laquelle démarrer l'insertion, et la chaîne à insérer.

...
C.insert(1,milieu);    // C vaut maintenant ho   woellrld 
...

Ajouter des caractères en fin de chaîne

La fonction-membre push_back est utilisable dans ce but.

Travailler avec des char *

De nombreuses fonctions C utilisent non pas l'objet string, mais le type char *. La fonction c_str() permet de passer d'une string vers un char *, alors que le constructeur de chaîne permet de passer d'un char * vers une string, ainsi qu'on l'a vu au dï¿œbut de ce chapitre.

...
char * c = C.c_str();
...

top

Les itérateurs

Un itérateur est un objet associé à un conteneur, qui va permettre de balayer l'ensemble des objets se trouvant dans le conteneur, et ceci sans avoir aucune idée de la structure de données sous-jacente; des boucles for ou while permettront de balayer le conteneur, exactement comme on balaierait un tableau classique en C:

typedef vector<int> v_int;
typedef vector<int>::iterator v_int_it;

v_int V;
V.push_back(1);
V.push_back(2);
V.push_back(3);
...
V.push_back(10);

for (v_int_it i=V.begin();i!=V.end();++i) {
  cout << *i << endl;
};
  ...

vector<int> V;
V.push_back(1);
V.push_back(2);
V.push_back(3);
...
V.push_back(10);

for (auto i=V.begin();i!=V.end();++i) {
  cout << *i << endl;
};
  ...

vector<int> V{1,2,3,4,5,6,7,8,9,10};
for (auto x : V) {
  cout << x << endl;
};
  ...

Itérateurs valides et invalides

Un itérateur qui pointe sur un élément est dit valide. Dans ce cas, *i renvoie un élément du conteneur. Un itérateur peut être valide à un certain moment de l'exécution du programme, puis être invalide un peu plus tard. Un itérateur peut être invalide pour les raisons suivantes:

• Il n'a pas été initialisé
• Le conteneur a été redimensionné (par des insertions ou des suppressions, par exemple).
• Le conteneur a été détruit
• L'itérateur pointe sur la fin de la séquence (V1.end() dans l'exemple ci-dessus).

Les conteneurs se différencient par la manière dont les itérateurs deviennent invalides: par exemple, le code suivant a toutes les chances d'invalider i:

vector <int> V1;
i=V1.begin() + 4;      // pointe sur le 5 è élément.
V1.insert(i,100000,0); // insère plein de cases juste avant i
cout << *i <<endl;     // plantage car i est devenu invalide

En effet, lors de l'insertion de 100000 entiers, il y a fort à parier que le vecteur s'est trouvé une autre zône de mémoire, de sorte que l'itérateur s'est mis à pendouiller bêtement. Par contre, le code suivant ne présentera pas de problème:

typedef list <int> l_int;
typedef list <int>::iterator l_int_it;

l_int L1;
L1.push_back(1);
L1.push_back(2);
L1.push_back(3);
...
L1.push_back(10);

l_int_v1 i = L1.begin();
i++;i++;i++;i++;       // pointe sur le 5 è élément.
L1.insert(i,100000,0); // insère plein de cases juste avant i
cout << *i <<endl;     // Pas de plantage

En effet, l'objet de type list s'arrange pour que i reste toujours valide dans ce cas.

Les différentes catégories d'itérateurs

Les itérateurs peuvent être classés en plusieurs catégories; suivant les catégories auxquelles ils appartiennent, nous avons plus ou moins d'opérations à notre disposition;

Intérateurs In (Input)

On ne peut effectuer que 4 opérations:

1. égalité j = i
2. Incrémentation ++i ou i++
3. Déréférencement, en lecture seule A = *i
4. Test d'égalité i == j

On doit penser à cet itérateur comme à un objet permettant de lire un fichier.

Intérateurs Out (Output)

On ne peut effectuer que 3 opérations:

1. égalité j = i
2. Incrémentation ++i ou i++
3. Déréférencement, en écriture seule *i = A

On doit penser à cet itérateur comme à un objet permettant d'écrire un fichier.

Intérateurs For (Forward)

Permet de balayer une séquence du début à la fin, mais sans retour en arrière possible. Les opérations supportées par les itérateurs In et Out sont également disponibles avec cet itérateur. On peut également déréférencer l'itérateur autant de fois qu'on veut.

Intérateurs Bi (Bidirectionnels)

Tout ce qui est permis par l'itérateur For, avec en plus:

1. Décrémentation --i ou i--

Intérateurs Ran (Random)

Tout ce qui est permis par l'itérateur Bi, avec en plus:

1. Opérateur d'indexation i[3]
2. Ajout ou suppression d'entiers j=i+3; j=i-4; i +=2;
3. Opérateur -: la différence entre deux itérateurs random est un entier if (j-i==4)...

Les itérateurs const

La fonction suivante ne pourra pas être compilée:

typedef list<int> li;
typedef list<int>::iterator ili;

void  print_list(const li & L) {
  for(ili i=L.begin();i!=L.end();i++) {
    cout << *i <<  endl;
  };
};

En effet, le type ili ne peut s'appliquer sur un objet constant, puisqu'il est susceptible de modifier cet objet. Il faut dans ce cas déclarer un const_iterator, d'où le code ci-dessous:

typedef list<int> li;
typedef list<int>::const_iterator cili;

void  print_list(const li & L) {
  for(cili i=L.begin();i!=L.end();i++) {
    cout << *i <<  endl;
  };
};

typedef list<int> li;
void  print_list(const li & L) {
  for(auto i=L.begin();i!=L.end();i++) {
    cout << *i <<  endl;
  };
};

Les itérateurs reverse

Ils permettent de balayer la séquence en sens inverse.

typedef list<int> li;
void  print_list(const li & L) {
  for(auto i=L.rbegin();i!=L.rend();i++) {
    cout << *i <<  endl;
  };
};

Leur description complète sort toutefois du cadre de ce cours.

Spécifier un intervalle à l'aide de deux itérateurs.

Un grand nombre de fonctions membres, ou d'algorithmes, demandent deux itérateurs en entrée, afin de spécifier un intervalle: Dans tous les cas, cet intervalle est semi-ouvert:

• Fermé sur la borne inférieure
• Ouvert sur la borne supérieure

En effet, utiliser des intervalles de ce type présente plusieurs intérêts:

• La borne supérieure de l'intervalle étant en-dehors de celui-ci, on peut utiliser la fonction end(), présente dans tous les conteneurs, pour signifier qu'on va jusqu'au bout de celui-ci. Même si le dernier élément change au cours du temps, (lorsqu'on ajoute un élément en bout de conteneur, par exemple) end() ne changera pas
• Dans le cas d'itérateurs "Random", la différence entre borne supérieure et borne inférieure renverra toujours le nombre d'éléments se trouvant entre les deux bornes: pas besoin de se creuser la tête pour résoudre des problèmes tordus d'intervalles...

top

Qui fait quoi ?

Les tableaux ci-dessous ne sont qu'un résumé des paragraphes ci-dessus. En particulier, on a insité ici sur les différences de performances entre les différents conteneurs, suivant les fonctions membres.

• o Fonction-membre présente
• const Fonction-membre présente, performance constante (quelque soit le nombre d'éléments dans le conteneur)
• O(n) Fonction-membre présente, durée proportionnelle au nombre d'éléments
• O(log(n)) Fonction-membre présente, durée proportionnelle au logarithme du nombre d'éléments
• + surcoût à prévoir de temps en temps (lors de demandes automatiques d'allocation mémoire, par exemple)

top

Algorithmes

La bibliothèque standard fournit également des algorithmes (fonctions) qui permettent de réaliser toutes sortes d'opérations sur les éléments d'un conteneur. Il sera souvent nécessaire de passer un objet fonction en paramètre; par exemple l'algorithme find_if qui recherche dans un conteneur les éléments qui répondent à une condition donnée: la condition sera passée sous forme d'un objet fonction à un paramètre, qui renverra soit true, soit false (un tel objet est appelé un prédicat).
Les principales fonctionnalités sont les suivantes:

• Appeler une fonction pour chaque objet d'un conteneur (for_each, équivalente à la fonction prédéfinie map du perl).
• Trouver un élément, une paire d'éléments
• Trouver la première occurrence, ou la dernière occurrence d'une valeur dans une séquence.
• Compter les occurrences d'une valeur dans une séquence
• copie, remplace, copie si telle condition est réalisée,...
• retire un élément, retire tous les éléments correspondant à une condition particulière,...
• Trie, effectue une recherche binaire (sur une séquence triée)
• recherche le minimum ou le maximum
• etc.

Un exemple d'utilisation d'algorithmes

L'extrait de code ci-dessous montre une manière amusante d'imprimer tous les éléments d'un conteneur (quelque soit le conteneur, d'ailleurs):

class sortie {
    public: 
    sortie (const string & s): msg(s){;};
    void operator()(int i) {
	cout << msg << i << "\n";
    };
    private:
    string msg;
};

...

vector<int> V1;
...

sortie s("coucou ");
for_each(V1.begin(), V1.end(),s);

La classe sortie permet de définir un objet-fonction, c'est-à-dire un objet comportant operator(). Le constructeur de cet objet initialise un membre privé. Par la suite, on crée un objet de type sortie, et on appelle la fonction for_each en lui passant deux itérateurs (pour définir un intervalle) ainsi que l'objet-fonction précédemment créé. Pour plus de détails, aller voir la documentation de for_each.

top

Trier un conteneur

Seuls les conteneurs suivants peuvent être triés:

• vector
• deque
• list

Trier un vector ou un deque

Les vecteurs et les deque étant munis d'un itérateur à accès direct, ils peuvent être triés en ordre croissant en utilisant l'algorithme sort, ainsi qu'on le voit ci-dessous:

vector<int> v1;
sort(v1.begin(),v1.end());          // trie le vecteur entier
sort(v1.begin(),v1.begin()+10);     // trie les 10 premiers éléments

Les objets du conteneur seront physiquement changés de place, ce qui n'est pas gênant pour des entiers, mais peut devenir pénalisant dans le cas d'objets.

Trier une list

L'algorithme sort n'est pas utilisable avec les listes, car il n'existe pas d'itérateur à accès direct pour ce type de conteneurs. Par contre, la structure chainée d'une liste permet d'envisager des tris bien plus performants que dans le cas des vecteurs. On utilise donc la fonction-membre sort:

list<int> l1;
l1.sort();  // trie la liste en entier

Par contre, il n'est pas possible de trier partiellement une liste

Contrôler l'ordre du tri

Les exemples ci-dessus trient les conteneurs dans l'ordre croissant de leurs éléments. Encore faut-il que cet ordre soit défini, ce qui n'est a priori pas évident lorsqu'il s'agit d'objets. On peut définir l'ordre de deux manières:

• Par la surcharge de l'opérateur < (utilisation par défaut de sort)
• Par la définiton d'une fonction de comparaison, et le passage de cette fonction à la fonction de tri:

bool Comparaison(const objet& o1, const objet& o2) {
   if (o1 est inférieur à o2)
      return true;
   else
      return false;
}
list<int> l1;
l1.sort(Comparaison);

vector<int> v1;
sort(v1.begin(),v1.end(),Comparaison);

Manipuler des listes

Il est aisé de manipuler des éléments de liste: on trouve ainsi de fonctions-membres permettant de:

• Supprimer un ou plusieurs objets (remove, remove_if)
• Faire une liste à partir de deux listes, tout en respectant l'ordre des élémets (merge)
• Vider une liste de tous ses éléments (ou seulement de quelques-uns) pour les mettre dans une autre: splice

Ci-dessous un exemple d'utilisation de splice:

list<int>l1, l2,l3;
...
l1.splice(l1.end(),l2); // (1)
l3.splice(l3.end(),l2.begin()); // (2)

Dans l'exemple (1), on a "vidé" l2 en mettant tous ses éléments à la fin de l1. Dans l'exemple (2), on a simplement mis le premier élément de l2 à la fin de l3.

Les entrées-sorties

Les entrées-sorties se font à travers plusieurs objets "flots" dont la hiérarchie se trouve partiellement résumée ci-dessous:

ios
   istream
       ifstream
       istringstream
       iostream -------
   ostream             |
       ofstream        iostream
       ostringstream   |    fstream
       iostream -------     stringstream

Les objets de type ostream ou istream

Pour ouvrir un fichier, il suffit d'instancier un objet de type ostream (ouverture en écriture), de type istream (ouverture en lecture), ou encore de type iostream (ouverture en lecture-écriture)

Pour fermer le fichier ouvert, le plus simple est de détruire l'objet, par exemple d'attendre la fin du bloc afin qu'il soit automatiquement détruit (il n'est alors pas nécessaire de se préoccuper de la fermeture du fichier), ou dans le cas d'un objet créé avec l'opérateur new d'appeler l'opérateur delete.:

{                            // debut de bloc
   ofstream F1("toto");      // ouvre un fichier en sortie et l'appelle toto
   ...
}                           // fin de bloc = fermeture du fichier

Lecture-écriture en binaire

Pour écrire ou lire des données en binaire, c'est-è-dire simplement écrire (lire) une image d'un bloc de mémoire, il suffit d'utiliser les fonctions-membres write ou read.

char bfr[50000];
int size;
...
{
   ofstream OUT("toto-bin",ios::binary);  // ouvre un fichier en écriture
   OUT.write(bfr,size);                   // recopie le buffer
}                                         // ferme le fichier
...
{
   ifstream IN("toto-bin",ios::binary);  // ouvre un fichier en écriture
   IN.read(bfr,size);                    // recopie le buffer
}                                        // ferme le fichier

Fonctions get, put, getline

La fonction out.put(c) où c est un char, permet d'envoyer ce caractère sur la sortie. Elle est strictement équivalente à out << c.

La fonction in.get(c) où c est un char est plus intéressante, dans la mesure où, contrairement à l'opérateur >>, elle ne fait aucune interprétation du caractère lu. Elle permet par exemple de lire les espaces ou les '\n', qui sont interprétés par >>.

La fonction-membre getline est bien pratique pour lire un fichier ligne par ligne. Son prototype est le suivant:

getline(char* buffer, int taille, char delimiteur='\n')

Le délimiteur par défaut est le caractère de fin de ligne, tandis que la possibilité de fixer une taille permet de s'assurer que le buffer ne déborde pas. Juste après un appel getline, la fonction-membre gcount() permet de savoir quelle est la longueur de la chaine de caractères effectivement lue.

Entrées-sorties formattées: << et >>

Les opérateurs << et >> sont surchargés de sorte qu'ils permettent respectivement l'entrée ou la sortie:

string A = "voici une chaine";
int B = 56;
objet O;                     // Objet dont le type a été défini plus haut
...

ofstream F1("toto");         // ouvre un fichier en sortie et l'appelle toto
F1 << A << " " << B << "\n"; // Ecrit A, puis B
F1 << O << "\n";             // Ecrit O

En particulier, tous les types de base du langage peuvent être utilisés avec ces opérateurs. Mais par ailleurs, lorsque vous écrivez la définition de la classe objet, vous pouvez surcharger cet opérateur, afin de vous permettre par la suite d'écrire: F1 << O << "\n"; Nous verrons plus tard comment écrire un tel opérateur.

Le contrôle du format

Nous avons plusieurs outils à notre disposition pour contrôler le format d'écriture ou de lecture:

• Les manipulateurs
• Les fonctions membres
• Les bits de contrôle

Les manipulateurs

Les manipulateurs s'interposent entre les données imprimées pour agir sur le fonctionnement du flots. Particulièrement bien intégrés au systéme d'entrées-sorties, ils sont d'un usage très pratique.

Les fonctions membres

Un flots étant tout simplement un objet, plusieurs fonctions membres sont définies afin de fixer la valeur de tel ou tel paramètre. Il existe aussi des fonctions membres pour lire la valeur fixée actuellement. Cela permet, par exemple, de sauvegarder un paramètre avant de le modifier, pour ensuite lui redonner sa valeur initiale.

Les bits de contrôle

Plus classique: certains paramètres sont accessibles via le positionnement de bits de contrôle. Les fonctions setf et unsetf permettent respectivement d'activer et désactiver les bits de contrôle, tout en renvoyant leur ancienne valeur pour sauvegarde éventuelle.

Précision, largeur de champ, caractère de remplissage

float x = 4.56782765;
int savprec=cout.precision();
cout.precision(3);
cout << "x = ";
cout.width(7);
cout << x << "cm\n";

cout << "x = ";
cout.width(7);
cout.fill('#');
cout << x << "cm\n";
   

x =4.57cm




x = ###4.57cm

float x = 4.56782765;
cout << setprecision(3) << "x = " 
     << setw(7) << x << "cm\n";
cout << setprecision(3) << setfill('#') 
     << "x = " << setw(7) << x << "cm\n";

x =    4.57cm

x = ###4.57cm

Alignement à gauche ou à droite

float x = -4.56782765;
cout.precision(3);
cout.fill('-');
cout.setf(ios::left,ios::adjustfield);
cout << "x = ";
cout.width(7);
cout << x << "cm\n";

cout.setf(ios::right,ios::adjustfield);
cout << "x = ";
cout.width(7);
cout << x << "cm\n";

x = -4.57  cm




x =   -4.57cm

Notation scientifique, fixe

float x = 4567.82765;
cout.precision(3);
cout.setf(ios::fixed,ios::floatfield);
cout << "x = ";
cout.width(10);
cout << x << "cm\n";

cout.setf(ios::scientific,ios::floatfield);
cout.precision(3);
cout << "x = ";
cout.width(10);
cout << x << "cm\n";

x =   4567.828cm





x =  4.568e+03cm

Afficher en hexadécimal ou en octal

int i =987654;
cout.setf(ios::showbase);
cout << "x = ";
cout.width(10);
cout << i << "..\n";

cout.setf(ios::oct,ios::basefield);
cout << "x = ";
cout.width(10);
cout << i << "..\n";

cout.setf(ios::hex,ios::basefield);
cout.setf(ios::showbase);
cout << "x = ";
cout.width(10);
cout << i << "..\n";

cout.setf(ios::uppercase);
cout << "x = ";
cout.width(10);
cout << i << "..\n";

x =     987654..




x =   03611006..





x =    0xf1206..




x =    0XF1206..

cout.unsetf(ios::showbase);
cout << "x = "<< dec << i << "..\n";

cout << "x = "<< oct << i << "..\n";

cout << "x = "<< hex << i << "..\n";

x = 987654..

x = 3611006..

x = f1206..

Jouer avec les tampons

int i =987654;
cout.setf(ios::unitbuf);
cout << "x = " << i;
    

cout << "x = "<< i << flush;
    

unitbuf assure que toute opération de sortie sera envoyée immédiatement (le tampon n'est pas utilisé); cela peut être important par exemple lorsqu'on écrit dans un pipe, pour assurer une bonne syncrhonisation. Le manipulateur flush vide le tampon immédatement.

Ecrire... ou lire l'état du flot

L'opérateur () est surchargé de sorte que l'on puisse écrire:

OUT << ...;
if (OUT) {
    ...    // Pas de pb
    ..
};

De même, l'opérateur ! est surchargé de sorte que l'on puisse écrire:

OUT << ...;
if (!OUT) {
    ...    // BIG PB
    ..
};

Par ailleurs, plusieurs fonctions-membres permettent de tester plus précisément l'état du fichier. Parmi elles, la plus utile est eof() permettant de détecter la fin de fichier.

Surcharger l'opérateur <<

L'opérateur << peut être surchargé lorsqu'on écrit une classe, ainsi qu'on le voit ci-dessous avec notre classe complexe; Le mieux est de définir une fonction amie, en utilisant un prototype analogue au prototype ci-dessous:

class complexe {
...
  friend ostream & operator<<(ostream& os, const complexe& c) {
    os << "Partie reelle = " << c.r << " Partie imaginaire = " << c.i;
    os << endl;
  }
}

...

complexe A;
cout << A << "\n";

La dernière opération de sortie écrit:

Partie reelle = 0 Partie imaginaire = 0

Surcharger l'opérateur >>

L'opérateur >> peut lui aussi être surchargé. Attention, il est bon de s'assurer que les données fournies par l'utilisateur correspondent bien à ce que l'on attend, et dans le cas contraire il faut agir sur l'état du flot, afin que le programme principal sache que quelque chose d'anormal est arrivé.
Le programme ci-dessous montre l'opérateur >> ainsi que le programme principal qui va avec; on voit qu'on utilise l'opérateur ! sur le flot cin afin de détecter les erreurs, et de boucler le cas échéant. Tout cela ne peut fonctionner que parceque >> positionne correctement les bits d'état lorsqu'il rencontre un problème.

class complexe {
...
  friend istream& operator>>(istream& is, complexe& c) {
    char sep;
    float r,i;
    is.clear();                           // remise a 0 du status
    is >> r >> sep;
    if (sep == ',') {
      is >> i;
      c.r = r;
      c.i = i;
    } else {
      string dump;
      getline(is,dump);                   // pour jeter la fin de ligne
      is.clear(ios::badbit|is.rdstate()); // pb en lecture
    };
    return is;
  }
};

main() {
  complexe C1;
  do {
    cout <<"Entrer reel,imag:";
  } while(!(cin >> C1));
  cout<< "Voici le complexe = " << C1 << endl;
};

Les itérateurs de flots

Une autre manière d'utiliser les flots est de faire "comme si" il s'agissait d'un conteneur, et d'utiliser un itérateur, ainsi qu'on peut le voir ci-dessous pour l'entrée:

istream_iterator<int> input (cin);
istream_iterator<int> end_of_input;
while(input != end_of_input) {
    int i = *input;
    ...
    ++input;
}

Et pour la sortie:

ostream_iterator<int> output(cout);
while(...) {
    *output = ...;
    ++output;
}

Remplir un conteneur à partir d'un fichier

Le code ci-dessous utilise la fonction back_insert_iterator afin de générer à partir d'un conteneur, un type particulier d'itérateurs: un itérateur d'insertion. Celui-ci sert à insérer les objets dans le conteneur par la fin. Associé aux itérateurs de flots, on remplit le conteneur avec une ligne de code... mais surtout, le fait qu'on lit depuis un fichier est totalement masqué: changez les itérateurs i et i_end par des itérateurs définissant un intervalle, par exemple, le code sera exactement le même. Elégant, n'est-il pas ?

vector<int> V1;

ifstream data("file.data");
istream_iterator<int> i(data);
istream_iterator<int> i_end;
back_insert_iterator<vector<int> > bii1 = back_inserter(V1);

copy(i,i_end, bii1);

Emmanuel Courcelle <emmanuel.courcelle@inp-toulouse.fr>