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 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;

ATTENTIONCertains compilateurs nécessitent l'utilisation d'une option de compilation pour utiliser la bibliothèque standard. A vérifier dans votre documentation.

Les instructions typedef et auto

L'instruction typedef (issue du C) ne définit pas, contrairement à ce que son nom pourrait laisser croire, un nouveau type. Elle ne fait que 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.

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

Les types locaux

Nous avons vu avant 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 apres 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:

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 avant: 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:

ATTENTION Ne pas utiliser de tableaux "à la C" en C++: il est bien plus commode et aussi performant (à condition de prendre quelques précautions) d'utiliser à la place un conteneur de type vector

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

ATTENTION On a déjà évoqué avant les problèmes posés par les pointeurs: les conteneurs de pointeurs n'y échappent pas, bien entendu. En particulier, attention, si l'objet est détruit le pointeur correspondant doit être retiré du conteneur, faute de quoi il pendouillera.

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

ATTENTION L'objet auto_ptr avant n'est pas une bonne solution dans ce cas: lors de la copie d'un auto_ptr, l'objet source est en effet détruit.

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

Reprenons l'exemple des shape avant: 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.

REGLE D'OR La règle d'or:

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

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

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.

ATTENTION Certains conteneurs, en particulier map et multimap, utilisent la struct modèle pair, qui comprend deux champs: first et second, ainsi qu'on peut le voir ci-dessous:

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.

ATTENTION Les type bitset, multimap, multiset, priority_queue ne seront pas abordés plus avant dans ce cours.

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:

ATTENTION Même si cela peut paraitre lourd à première vue, il est important d'utiliser ces types, pour générer du code portable: peut-être que sur votre système le type size_type est équivalent à unsigned int. Mais sur un autre système, size_type risque d'être en fait équivalent à unsigned long. D'où de gros soucis de portabilité.

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 apres
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.

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;
};
  ...
ou, plus lisible, en c++11:
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;
};
  ...
ou, encore plus lisible, toujours en c++11 (utilisation de la liste d'initialisation et de la boucle for par intervalles):
vector<int> V{1,2,3,4,5,6,7,8,9,10};
for (auto x : V) {
  cout << x << endl;
};
  ...

ATTENTIONLa ligne cout << *i << endl ne signifie pas que i est un véritable pointeur: i est un objet qui implémente une abstraction de la notion de pointeur: l'opérateur * est ici surchargé.

ATTENTION V1.begin() et V1.end() sont tous deux des itérateurs, mais alors que V1.begin() pointe sur le premier élément du conteneur, V1.end() pointe après le dernier élément. De la sorte, pour balayer l'ensemble du conteneur, il faut:

ATTENTION La troisième version de la boucle for est particulièrement intéressante, car l'itérateur est masqué, de sorte qu'on peut utiliser une sémantique de valeurs, toujours plus sûre et plus claire qu'une sémantique pointeurs.

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:

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

ATTENTIONIl est impossible de faire *i = A avec cet itérateur.

ATTENTIONIl est impossible de déréférencer plus d'une fois le même élément. Ainsi, le code A = *i; B = *i ne marche pas.

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

ATTENTIONIl est impossible de faire A = *i avec cet itérateur.

ATTENTIONIl est impossible de déréférencer plus d'une fois le même élément. Ainsi, le code *i = A; *i = B ne marche pas.

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.

ATTENTION Partout où un itérateur In ou Out est requis, vous pourrez fournir un itérateur For.

Intérateurs Bi (Bidirectionnels)

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

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

ATTENTION Partout où un itérateur In ou In, Out ou For est requis, vous pourrez fournir un itérateur Bi.

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

ATTENTION Partout où un itérateur In ou In, Out, For ou Bi est requis, vous pourrez fournir un itérateur Bi.

ATTENTION Un itérateur random offre les mêmes possibilités qu'un pointeur conventionnel.

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;
  };
};
Là encore, le C++11 permet au programmeur de ne plus se creuser la tête:
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.

Un exemple simple en c++11
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:

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

ATTENTION Lorsque vous spécifiez un intervalle par [first,last[ first et last doivent être deux itérateurs valides du même conteneur. Le type de conteneur n'a par contre aucune importance.

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.

Fonctions membres "non mutantes"
Conteneurs Itérateurs Fonctions membres
    (r)begin(),
(r)end()
front(),
back()
[] find() size()
vector Ran o o const   o
list Bi o o     o
deque Ran o o const   o
queue           o
priority_queue           o
stack           o
map Bi o   O(log(n)) O(log(n)) o
set Bi o     O(log(n)) o

 

Fonctions membres "mutantes"
Conteneurs Fonctions membres
  push_back,
pop_back
push_front,
pop_front
pop push top insert()
erase()
clear()
vector const+         O(n)+ o
list const const       const o
deque const const       O(n) o
queue     const const+      
priority_queue     O(log(n)) O(log(n)) o    
stack     const const+ o    
map           O(log(n))+ o
set           O(log(n))+ o

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:

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:

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:

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:

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

ATTENTION Attention aux débordements de buffers en utilisant ces fonctions !!! Rien ne garantit que size n'est pas supérieur à 50000 dans l'exemple ci-dessus.

Fonctions get, put, getline

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

La fonction in.get(c)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.

ATTENTION Il existe aussi une fonction getline (qui n'est pas une fontion membre) permettant de lire une ligne dans un objet de type string. On pourrait penser que cette fonction est bien sympathique, puisqu'il n'y a plus à se préoccuper des débordements de tampons... mais attention, elle va environ quatre fois plus lentement que la fonction-membre getline... A utiliser avec parcimonie, donc.

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

Fonctions membres Résultats
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
Manipulateurs Résultats
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

ATTENTION La fonction width ainsi que le manipulateur setw ne précisent la largeur d'impression que pour la prochaine opération de sortie. Il n'en est pas de même pour la plupart des autres fonctions ou manipulateurs,dont l'effet est permanent.

Alignement à gauche ou à droite

champs de bits Résultats
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

champs de bits Résultats
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

champs de bits Résultats
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..
Manipulateurs Résultats
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

champs de bits
int i =987654;
cout.setf(ios::unitbuf);
cout << "x = " << i;
    
Manipulateurs
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;avant 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;
}

ATTENTION La première ligne associe un itérateur de flot à un flot existant (ici cin). La seconde ligne construit un itérateur de flot sans l'associer à quoique ce soit: il s'agit par convention d'un signal de fin de fichier.

Et pour la sortie:

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

ATTENTION La ligne *output = ... utilisera en fait l'opérateur << de l'objet situé à droite du signe =.

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

xhtml Licence Creative Commons Emmanuel Courcelle <emmanuel.courcelle@inp-toulouse.fr>