IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Cours de C/C++


précédentsommairesuivant

13. Services et notions de base de la bibliothèque standard

La bibliothèque standard C++ fournit un certain nombre de fonctionnalités de base sur lesquelles toutes les autres fonctionnalités de la bibliothèque s'appuient. Ces fonctionnalités apparaissent comme des classes d'encapsulation de la bibliothèque C et des classes d'abstraction des principales constructions du langage. Ces dernières utilisent des notions très évoluées pour permettre une encapsulation réellement générique des types de base. D'autre part, la bibliothèque standard utilise la notion de complexité algorithmique pour définir les contraintes de performance des opérations réalisables sur ses structures de données ainsi que sur ses algorithmes. Bien que complexes, toutes ces notions sont omniprésentes dans toute la bibliothèque, aussi est-il extrêmement important de les comprendre en détail. Ce chapitre a pour but de vous les présenter et de les éclaircir.

13.1. Encapsulation de la bibliothèque C standard

La bibliothèque C définit un grand nombre de fonctions C standards, que la bibliothèque standard C++ reprend à son compte et complète par toutes ses fonctionnalités avancées. Pour bénéficier de ces fonctions, il suffit simplement d'inclure les fichiers d'en-tête de la bibliothèque C, tout comme on le faisait avec les programmes C classiques.

Toutefois, les fonctions ainsi déclarées par ces en-têtes apparaissent dans l'espace de nommage global, ce qui risque de provoquer des conflits de noms avec des fonctions homonymes (rappelons que les fonctions C ne sont pas surchargeables). Par conséquent, et dans un souci d'homogénéité avec le reste des fonctionnalités de la bibliothèque C++, un jeu d'en-têtes complémentaires a été défini pour les fonctions de la bibliothèque C. Ces en-têtes définissent tous leurs symboles dans l'espace de nommage std::, qui est réservé pour la bibliothèque standard C++.

Ces en-têtes se distinguent des fichiers d'en-tête de la bibliothèque C par le fait qu'ils ne portent pas d'extension .h et par le fait que leur nom est préfixé par la lettre 'c'. Les en-têtes utilisables ainsi sont donc les suivants :

 
Sélectionnez
cassert
cctype
cerrno
cfloat
ciso646
climits
clocale
cmath
csetjmp
csignal
cstdarg
cstddef
cstdio
cstdlib
cstring
ctime
cwchar
cwctype

Par exemple, on peut réécrire notre tout premier programme que l'on a fait à la Section 1.9 de la manière suivante :

 
Sélectionnez
#include <cstdio>
 
long double x, y;
 
int main(void)
{
    std::printf("Calcul de moyenne\n");
    std::printf("Entrez le premier nombre : ");
    std::scanf("%Lf", &x);
    std::printf("\nEntrez le deuxième nombre : ");
    std::scanf("%Lf", &y);
    std::printf("\nLa valeur moyenne de %Lf et de %Lf est %Lf.\n",
        x, y, (x+y)/2);
    return 0;
}

Note : L'utilisation systématique du préfixe std:: peut être énervante sur les grands programmes. On aura donc intérêt soit à utiliser les fichiers d'en-tête classiques de la bibliothèque C, soit à inclure une directive using namespace std; pour intégrer les fonctionnalités de la bibliothèque standard dans l'espace de nommage global.

Remarquez que la norme ne suppose pas que ces en-têtes soient des fichiers physiques. Les déclarations qu'ils sont supposés faire peuvent donc être réalisées à la volée par les outils de développement, et vous ne les trouverez pas forcément sur votre disque dur.

Certaines fonctionnalités fournies par la bibliothèque C ont été encapsulées dans des fonctionnalités équivalentes de la bibliothèque standard C++. C'est notamment le cas pour la gestion des locales et la gestion de certains types de données complexes. C'est également le cas pour la détermination des limites de représentation que les types de base peuvent avoir. Classiquement, ces limites sont définies par des macros dans les en-têtes de la bibliothèque C, mais elles sont également accessibles au travers de la classe template numeric_limits, définie dans l'en-tête limits :

 
Sélectionnez
// Types d'arrondis pour les flottants :
enum float_round_style
{
    round_indeterminate       = -1,
    round_toward_zero         =  0,
    round_to_nearest          =  1,
    round_toward_infinity     = 2,
    round_toward_neg_infinity = 3
};
 
template <class T>
class numeric_limits
{
public:
    static const bool is_specialized = false;
    static T min() throw();
    static T max() throw();
    static const int digits   = 0;
    static const int digits10 = 0;
    static const bool is_signed  = false;
    static const bool is_integer = false;
    static const bool is_exact   = false;
    static const int radix = 0;
    static T epsilon() throw();
    static T round_error() throw();
    static const int min_exponent   = 0;
    static const int min_exponent10 = 0;
    static const int max_exponent   = 0;
    static const int max_exponent10 = 0;
    static const bool has_infinity  = false;
    static const bool has_quiet_NaN = false;
    static const bool has_signaling_NaN = false;
    static const bool has_denorm        = false;
    static const bool has_denorm_loss   = false;
    static T infinity() throw();
    static T quiet_NaN() throw();
    static T signaling_NaN() throw();
    static T denorm_min() throw();
    static const bool is_iec559  = false;
    static const bool is_bounded = false;
    static const bool is_modulo  = false;
    static const bool traps      = false;
    static const bool tinyness_before = false;
    static const float_round_style
        round_style = round_toward_zero;
};

Cette classe template ne sert à rien en soi. En fait, elle est spécialisée pour tous les types de base du langage, et ce sont ces spécialisations qui sont réellement utilisées. Elles permettent d'obtenir toutes les informations pour chaque type grâce à leurs données membres et à leurs méthodes statiques.

Exemple 13-1. Détermination des limites d'un type
Sélectionnez
#include <iostream>
#include <limits>
 
using namespace std;
 
int main(void)
{
    cout << numeric_limits<int>::min() << endl;
    cout << numeric_limits<int>::max() << endl;
    cout << numeric_limits<int>::digits << endl;
    cout << numeric_limits<int>::digits10 << endl;
    return 0;
}

Ce programme d'exemple détermine le plus petit et le plus grand nombre représentable avec le type entier int, ainsi que le nombre de bits utilisés pour coder les chiffres et le nombre maximal de chiffres que les nombres en base 10 peuvent avoir en étant sûr de pouvoir être stockés tels quels.

13.2. Définition des exceptions standards

La bibliothèque standard utilise le mécanisme des exceptions du langage pour signaler les erreurs qui peuvent se produire à l'exécution au sein de ses fonctions. Elle définit pour cela un certain nombre de classes d'exceptions standards, que toutes les fonctionnalités de la bibliothèque sont susceptibles d'utiliser. Ces classes peuvent être utilisées telles quelles ou servir de classes de base à des classes d'exceptions personnalisées pour vos propres développements.

Ces classes d'exception sont presque toutes déclarées dans l'en-tête stdexcept, et dérivent de la classe de base exception. Cette dernière n'est pas déclarée dans le même en-tête et n'est pas utilisée directement, mais fournit les mécanismes de base de toutes les exceptions de la bibliothèque standard. Elle est déclarée comme suit dans l'en-tête exception :

 
Sélectionnez
class exception
{
public:
    exception() throw();
    exception(const exception &) throw();
    exception &operator=(const exception &) throw();
    virtual ~exception() throw();
    virtual const char *what() const throw();
};

Outre les constructeurs, opérateurs d'affectation et destructeurs classiques, cette classe définit une méthode what qui retourne une chaîne de caractères statique. Le contenu de cette chaîne de caractères n'est pas normalisé. Cependant, il sert généralement à décrire la nature de l'erreur qui s'est produite. C'est une méthode virtuelle, car elle est bien entendu destinée à être redéfinie par les classes d'exception spécialisées pour les différents types d'erreurs. Notez que toutes les méthodes de la classe exception sont déclarées comme ne pouvant pas lancer d'exceptions elle-mêmes, ce qui est naturel puisque l'on est déjà en train de traiter une exception lorsqu'on manipule des objets de cette classe.

L'en-tête exception contient également la déclaration de la classe d'exception bad_exception. Cette classe n'est, elle aussi, pas utilisée en temps normal. Le seul cas où elle peut être lancée est dans le traitement de la fonction de traitement d'erreur qui est appelée par la fonction std::unexpected lorsqu'une exception a provoqué la sortie d'une fonction qui n'avait pas le droit de la lancer. La classe bad_exception est déclarée comme suit dans l'en-tête exception :

 
Sélectionnez
class bad_exception : public exception
{
public:
    bad_exception() throw();
    bad_exception(const bad_exception &) throw();
    bad_exception &operator=(const bad_exception &) throw();
    virtual ~bad_exception() throw();
    virtual const char *what() const throw();
};

Notez que l'exception bad_alloc lancée par les gestionnaires de mémoire lorsque l'opérateur new ou l'opérateur new[] n'a pas réussi à faire une allocation n'est pas déclarée dans l'en-tête stdexcept non plus. Sa déclaration a été placée avec celle des opérateurs d'allocation mémoire, dans l'en-tête new. Cette classe dérive toutefois de la classe exception, comme le montre sa déclaration :

 
Sélectionnez
class bad_alloc : public exception
{
public:
    bad_alloc() throw();
    bad_alloc(const bad_alloc &) throw();
    bad_alloc &operator=(const bad_alloc &) throw();
    virtual ~bad_alloc() throw();
    virtual const char *what() const throw();
};

Les autres exceptions sont classées en deux grandes catégories. La première catégorie regroupe toutes les exceptions dont l'apparition traduit sans doute une erreur de programmation dans le programme, car elles ne devraient jamais se produire à l'exécution. Il s'agit des exceptions dites « d'erreurs dans la logique du programme » et, en tant que telles, dérivent de la classe d'exception logic_error. Cette classe est déclarée comme suit dans l'en-tête stdexcept :

 
Sélectionnez
class logic_error : public exception
{
public:
    logic_error(const string &what_arg);
};

Elle ne contient qu'un constructeur, permettant de définir la chaîne de caractères qui sera renvoyée par la méthode virtuelle what. Ce constructeur prend en paramètre cette chaîne de caractères sous la forme d'un objet de la classe string. Cette classe est définie par la bibliothèque standard afin de faciliter la manipulation des chaînes de caractères et sera décrite plus en détail dans la Section 14.1.

Les classes d'exception qui dérivent de la classe logic_error disposent également d'un constructeur similaire. Ces classes sont les suivantes :
  • la classe domain_error, qui spécifie qu'une fonction a été appelée avec des paramètres sur lesquels elle n'est pas définie. Il faut contrôler les valeurs des paramètres utilisées lors de l'appel de la fonction qui a lancé cette exception ;
  • la classe invalid_argument, qui spécifie qu'un des arguments d'une méthode ou d'une fonction n'est pas valide. Cette erreur arrive lorsqu'on utilise des valeurs de paramètres qui n'entrent pas dans le cadre de fonctionnement normal de la méthode appelée ; cela traduit souvent une mauvaise utilisation de la fonctionnalité correspondante ;
  • la classe length_error, qui indique qu'un dépassement de capacité maximale d'un objet a été réalisé. Ces dépassements se produisent dans les programmes bogués, qui essaient d'utiliser une fonctionnalité au delà des limites qui avaient été fixées pour elle ;
  • la classe out_of_range, qui spécifie qu'une valeur située en dehors de la plage de valeurs autorisées a été utilisée. Ce type d'erreur signifie souvent que les paramètres utilisés pour un appel de fonction ne sont pas corrects ou pas initialisés, et qu'il faut vérifier leur validité.

La deuxième catégorie d'exceptions correspond aux erreurs qui ne peuvent pas toujours être corrigées lors de l'écriture du programme, et qui font donc partie des événements naturels qui se produisent lors de son exécution. Elles caractérisent les erreurs d'exécution, et dérivent de la classe d'exception runtime_error. Cette classe est déclarée de la manière suivante dans l'en-tête stdexcept :

 
Sélectionnez
class runtime_error : public exception
{
public:
    runtime_error(const string &what_arg);
};

Elle s'utilise exactement comme la classe logic_error.

Les exceptions de la catégorie des erreurs d'exécution sont les suivantes :
  • la classe range_error, qui signifie qu'une valeur est sortie de la plage de valeurs dans laquelle elle devait se trouver suite à un débordement interne à la bibliothèque ;
  • la classe overflow_error, qui signifie qu'un débordement par valeurs supérieures s'est produit dans un calcul interne à la bibliothèque ;
  • la classe underflow_error, qui signifie qu'un débordement par valeurs inférieures s'est produit dans un calcul interne à la bibliothèque.

13.3. Abstraction des types de données : les traits

Un certain nombre de classes ou d'algorithmes peuvent manipuler des types ayant une signification particulière. Par exemple, la classe string, que nous verrons plus loin, manipule des objets de type caractère. En réalité, ces classes et ces algorithmes peuvent travailler avec n'importe quels types pourvu que tous ces types se comportent de la même manière. La bibliothèque standard C++ utilise donc la notion de « traits », qui permet de définir les caractéristiques de ces types. Les traits sont définis dans des classes prévues à cet usage. Les classes et les algorithmes standards n'utilisent que les classes de traits pour manipuler les objets, garantissant ainsi une abstraction totale vis-à-vis de leurs types. Ainsi, il suffit de coder une spécialisation de la classe des traits pour un type particulier afin de permettre son utilisation dans les algorithmes génériques. La bibliothèque standard définit bien entendu des spécialisations pour les types de base du langage.

Par exemple, la classe de définition des traits des types de caractères est la classe template char_traits.

Elle contient les définitions des types suivants :
  • le type char_type, qui est le type représentant les caractères eux-mêmes ;
  • le type int_type, qui est un type capable de contenir toutes les valeurs possibles pour les caractères, y compris la valeur spéciale du marqueur de fin de fichier ;
  • le type off_type, qui est le type permettant de représenter les déplacements dans une séquence de caractères, ainsi que les positions absolues dans cette séquence. Ce type est signé car les déplacements peuvent être réalisés aussi bien vers le début de la séquence que vers la fin ;
  • le type pos_type, qui est un sous-type du type off_type, et qui n'est utilisé que pour les déplacements dans les fonctions de positionnement des flux de la bibliothèque standard ;
  • le type state_type, qui permet de représenter l'état courant d'une séquence de caractères dans les fonctions de conversion. Ce type est utilisé dans les fonctions de transcodage des séquences de caractères d'un encodage vers un autre.

Note : Pour comprendre l'utilité de ce dernier type, il faut savoir qu'il existe plusieurs manières de coder les caractères. La plupart des méthodes utilisent un encodage à taille fixe, où chaque caractère est représenté par une valeur entière et une seule. Cette technique est très pratique pour les jeux de caractères contenant moins de 256 caractères, pour lesquels un seul octet est utilisé par caractère. Elle est également utilisée pour les jeux de caractères de moins de 65536 caractères, car l'utilisation de 16 bits par caractères est encore raisonable. En revanche, les caractères des jeux de caractères orientaux sont codés avec des valeurs numériques supérieures à 65536 par les encodages standards (Unicode et ISO 10646), et ne peuvent donc pas être stockés dans les types char ou wchar_t. Pour ces jeux de caractères, on utilise donc souvent des encodages à taille variable, où chaque caractère peut être représenté par un ou plusieurs octets selon sa nature et éventuellement selon sa position dans la chaîne de caractères.

Pour ces encodages à taille variable, il est évident que le positionnement dans les séquences de caractères se fait en fonction du contexte de la chaîne, à savoir en fonction de la position du caractère précédent et parfois en fonction des caractères déjà analysés. Les algorithmes de la bibliothèque standard qui manipulent les séquences de caractères doivent donc stocker le contexte courant lors de l'analyse de ces séquences. Elles le font grâce au type state_type de la classe des traits de ces caractères.

L'exemple suivant vous permettra de vérifier que le type char_type de la classe de définition des traits pour le type char est bien entendu le type char lui-même :

 
Sélectionnez
#include <iostream>
#include <typeinfo>
#include <string>
 
using namespace std;
 
int main(void)
{
    // Récupère les informations de typage des traits :
    const type_info &ti_trait =
        typeid(char_traits<char>::char_type);
    // Récupère les informations de typage directement :
    const type_info &ti_char = typeid(char);
    // Compare les types :
    cout << "Le nom du type caractère des traits est : " <<
        ti_trait.name() << endl;
    cout << "Le nom du type char est : " <<
        ti_char.name() << endl;
    if (ti_trait == ti_char)
        cout << "Les deux types sont identiques." << endl;
    else
        cout << "Ce n'est pas le même type." << endl;
    return 0;
}

La classe char_traits définit également un certain nombre de méthodes travaillant sur les types de caractères et permettant de réaliser les opérations de base sur ces caractères. Ces méthodes permettent essentiellement de comparer, de copier, de déplacer et de rechercher des caractères dans des séquences de caractères, en tenant compte de toutes les caractéristiques de ces caractères. Elle contient également la définition de la valeur spéciale utilisée dans les séquences de caractères pour marquer les fin de flux (« EOF », abréviation de l'anglais « End Of File »).

Par exemple, le programme suivant permet d'afficher la valeur utilisée pour spécifier une fin de fichier dans une séquence de caractères de type wchar_t :

 
Sélectionnez
#include <iostream>
#include <string>
 
using namespace std;
 
int main(void)
{
    char_traits<wchar_t>::int_type wchar_eof =
        char_traits<wchar_t>::eof();
    cout << "La valeur de fin de fichier pour wchar_t est : "
        << wchar_eof << endl;
    return 0;
}

Les autres méthodes de la classe de définition des traits des caractères, ainsi que les classes de définition des traits des autre types, ne seront pas décrites plus en détail ici. Elles sont essentiellement utilisées au sein des algorithmes de la bibliothèque standard et n'ont donc qu'un intérêt limité pour les programmeurs, mais il est important de savoir qu'elles existent.

13.4. Abstraction des pointeurs : les itérateurs

La bibliothèque standard définit un certain nombre de structures de données évoluées, qui permettent de stocker et de manipuler les objets utilisateur de manière optimale, évitant ainsi au programmeur d'avoir à réinventer la roue. On appelle ces structures de données des conteneurs. Ces conteneurs peuvent être manipulés au travers de fonctions spéciales, selon un grand nombre d'algorithmes possibles dont la bibliothèque dispose en standard. L'ensemble des fonctionnalités fournies par la bibliothèque permet de subvenir au besoin des programmeurs dans la majorité des cas. Nous détaillerons la notion de conteneur et les algorithmes disponibles plus loin dans ce document.

La manière d'accéder aux données des conteneurs dépend bien entendu de leur nature et de leur structure. Cela signifie qu'en théorie, il est nécessaire de spécialiser les fonctions permettant d'appliquer les algorithmes pour chaque type de conteneur existant. Cette technique n'est ni pratique, ni extensible, puisque les algorithmes fournis par la bibliothèque ne pourraient dans ce cas pas travailler sur des conteneurs écrits par le programmeur. C'est pour cette raison que la bibliothèque standard utilise une autre technique pour accéder aux données des conteneurs. Cette technique est basée sur la notion d'itérateur.

13.4.1. Notions de base et définition

Un itérateur n'est rien d'autre qu'un objet permettant d'accéder à tous les objets d'un conteneur donné, souvent séquentiellement, selon une interface standardisée. La dénomination d'itérateur provient donc du fait que les itérateurs permettent d'itérer sur les objets d'un conteneur, c'est-à-dire d'en parcourir le contenu en passant par tous ses objets.

Comme les itérateurs sont des objets permettant d'accéder à d'autres objets, ils ne représentent pas eux-mêmes ces objets, mais plutôt le moyen de les atteindre. Ils sont donc comparables aux pointeurs, dont ils ont exactement la même sémantique. En fait, les concepteurs de la bibliothèque standard se sont basés sur cette propriété pour définir l'interface des itérateurs, qui sont donc une extension de la notion de pointeur. Par exemple, il est possible d'écrire des expressions telles que « *i » ou « ++i » avec un itérateur i. Tous les algorithmes de la bibliothèque, qui travaillent normalement sur des itérateurs, sont donc susceptibles de fonctionner avec des pointeurs classiques.

Bien entendu, pour la plupart des conteneurs, les itérateurs ne sont pas de simples pointeurs, mais des objets qui se comportent comme des pointeurs et qui sont spécifiques à chaque conteneur. Ainsi, les algorithmes sont écrits de manière uniforme, et ce sont les conteneurs qui fournissent les itérateurs qui leur sont appropriés afin de permettre l'accès à leurs données.

Il n'y a que trois manières d'obtenir un itérateur. Les itérateurs qui sont effectivement des pointeurs peuvent être obtenus naturellement en prenant l'adresse de l'élément auquel ils donnent accès. Les pointeurs ne doivent être utilisés en tant qu'itérateurs que pour accéder aux données d'un tableau, car la sémantique de l'arithmétique des pointeurs suppose que les éléments référencés successivement par un pointeur sont stockés en des emplacements contigus de la mémoire. Pour les itérateurs de conteneurs en revanche, il faut impérativement utiliser des méthodes spécifiques du conteneur pour obtenir des itérateurs. La plupart des conteneurs fournissent une méthode pour obtenir un itérateur initial, qui référence le premier élément du conteneur, et une méthode pour obtenir la valeur de l'itérateur lorsque le parcours du conteneur est achevé. Enfin, certains algorithmes et certaines méthodes des conteneurs peuvent retourner un itérateur à l'issu de leur traitement.

Quelle que soit la manière d'obtenir les itérateurs, leur validité est soumise à des limites. Premièrement, ils deviennent obligatoirement invalides dès lors que le conteneur auquel ils permettent d'accéder est détruit. De plus, les conteneurs gèrent leur structure de données de manière dynamique, et sont susceptibles de la réorganiser dès qu'on les manipule. On veillera donc à ne plus utiliser les itérateurs d'un conteneur dès qu'une méthode permettant de le modifier aura été appelée. Ne pas respecter cette règle conduirait, dans le meilleur des cas, à ne pas parcourir complètement l'ensemble des objets du conteneur, et dans le pire des cas, à planter immédiatement le programme.

13.4.2. Classification des itérateurs

La bibliothèque définit plusieurs catégories d'itérateurs qui contiennent des itérateurs plus ou moins puissants. Le comportement des itérateurs les plus puissants se rapproche beaucoup des pointeurs classiques, et quasiment toutes les opérations applicables aux pointeurs peuvent l'être à ces itérateurs. En revanche, les itérateurs des classes plus restrictives ne définissent qu'un sous-ensemble des opérations que les pointeurs supportent, et ne peuvent donc être utilisés que dans le cadre de ce jeu d'opérations réduit.

Les algorithmes de la bibliothèque n'utilisent que les itérateurs des classes les plus faibles permettant de réaliser leur travail. Ils s'imposent ces restrictions afin de garantir leur utilisation correcte même avec les itérateurs les plus simples. Bien entendu, comme les pointeurs disposent de toutes les fonctionnalités définies par les itérateurs, même les plus puissants, les algorithmes standards fonctionnent également avec des pointeurs. Autrement dit, la bibliothèque standard est écrite de façon à n'utiliser qu'une partie des opérations applicables aux pointeurs, afin de garantir que ce qui fonctionne avec des itérateurs fonctionne avec des pointeurs.

Les itérateurs de chaque catégorie possèdent toutes les propriétés des itérateurs des catégories inférieures. Il existe donc une hiérarchie dans la classification des itérateurs.

Les catégories définies par la bibliothèque standard sont les suivantes :
  • les itérateurs de la catégorie « Output » sont utilisés pour effectuer des affectations de valeurs aux données qu'ils référencent. Ces itérateurs ne peuvent donc être déréférencés par l'opérateur '*' que dans le cadre d'une affectation. Il est impossible de lire la valeur d'un itérateur de type Output, et on ne doit écrire dans la valeur qu'ils référencent qu'une fois au plus. Les algorithmes qui utilisent ces itérateurs doivent donc impérativement ne faire qu'une seule passe sur les données itérées ;
  • les itérateurs de la catégorie « Input » sont similaires aux itérateurs de type Output, à ceci près qu'ils ne peuvent être déréférencés que pour lire une valeur. Contrairement aux itérateurs de type Output, il est possible de comparer deux itérateurs. Cependant, le fait que deux itérateurs soient égaux ne signifie aucunement que leurs successeurs le seront encore. Les algorithmes qui utilisent les itérateurs de type Input ne peuvent donc faire aucune hypothèse sur l'ordre de parcours utilisé par l'itérateur. Ce sont donc nécessairement des algorithmes en une passe ;
  • les itérateurs de la catégorie « Forward » possèdent toutes les fonctionnalités des itérateurs de type Input et de type Output. Comme ceux-ci, ils ne peuvent passer que d'une valeur à la suivante, et jamais reculer ou revenir à une valeur déjà itérée. Les algorithmes qui utilisent des itérateurs de cette catégorie s'imposent donc de ne parcourir les données des conteneurs que dans un seul sens. Cependant, la restriction imposée sur l'égalité des opérateurs de type Input est levée, ce qui signifie que plusieurs parcours successifs se feront dans le même ordre. Les algorithmes peuvent effectuer plusieurs parcours, par exemple en copiant la valeur initiale de l'itérateur et en parcourant le conteneur plusieurs fois avec chaque copie ;
  • les itérateurs de la catégorie « Bidirectionnal » disposent de toutes les fonctionnalités des itérateurs de type Forward, mais lèvent la restriction sur le sens de parcours. Ces itérateurs peuvent donc revenir sur les données déjà itérées, et les algorithmes qui les utilisent peuvent donc travailler en plusieurs passes, dans les deux directions ;
  • enfin, les itérateurs de la catégorie « RandomAccess » sont les plus puissants. Ils fournissent toutes les fonctionnalités des itérateurs de type Bidirectionnal, plus la possibilité d'accéder aux éléments des conteneurs par l'intermédiaire d'un index en un temps constant. Il n'y a donc plus de notion de sens de parcours, et les données peuvent être accédées comme les données d'un tableau. Il est également possible d'effectuer les opérations classiques de l'arithmétique des pointeurs sur ces itérateurs.

Tous les itérateurs de la bibliothèque standard dérivent de la classe de base suivante :

 
Sélectionnez
template <class Category,
    class T, class Distance = ptrdiff_t,
    class Pointer = T*, class Reference = T &>
struct iterator
{
    typedef T         value_type;
    typedef Distance  difference_type;
    typedef Pointer   pointer;
    typedef Reference reference;
    typedef Category  iterator_category;
};

Cette classe est déclarée dans l'en-tête iterator.

Cette classe définit les types de base des itérateurs, à savoir : le type des valeurs référencées, le type de la différence entre deux itérateurs dans les calculs d'arithmétique des pointeurs, le type des pointeurs des valeurs référencées par l'itérateur, le type des références pour ces valeurs et la catégorie de l'itérateur.

Ce dernier type doit être l'une des classes suivantes, également définies par la bibliothèque standard :
  • input_iterator_tag, pour les itérateurs de la catégorie des itérateurs de type Input ;
  • output_iterator_tag, pour les itérateurs de la catégorie des itérateurs de type Output ;
  • forward_iterator_tag, pour les itérateurs de la catégorie des itérateurs de type Forward ;
  • bidirectionnal_iterator_tag, pour les itérateurs de la catégorie des itérateurs bidirectionnels ;
  • random_access_iterator_tag, pour les itérateurs de la catégorie des itérateurs à accès complet.

Notez que le type par défaut pour la différence entre deux pointeurs est le type ptrdiff_t, qui est utilisé classiquement pour les pointeurs normaux. De même, le type pointeur et le type référence correspondent respectivement, par défaut, aux types T * et T &. Pour les itérateurs pour lesquels ces types n'ont pas de sens, le type utilisé est void, ce qui permet de provoquer une erreur de compilation si on cherche à les utiliser

Ces types sont utilisés par les itérateurs nativement, cependant, ils ne le sont généralement pas par les algorithmes. En effet, ceux-ci sont susceptibles d'être appelées avec des pointeurs normaux, et les pointeurs ne définissent pas tous ces types. C'est pour cette raison qu'une classe de traits a été définie pour les itérateurs par la bibliothèque standard. Cette classe est déclarée comme suit dans l'en-tête iterator :

 
Sélectionnez
template <class Iterator>
struct iterator_traits
{
    typedef Iterator::value_type        value_type;
    typedef Iterator::difference_type   difference_type;
    typedef Iterator::pointer           pointer;
    typedef Iterator::reference         reference;
    typedef Iterator::iterator_category iterator_category;
};

La classe des traits permet donc d'obtenir de manière indépendante de la nature de l'itérateur la valeur des types fondamentaux de l'itérateur. Comme ces types n'existent pas pour les pointeurs classiques, cette classe est spécialisée de la manière suivante :

 
Sélectionnez
template <class T>
struct iterator_traits<T *>
{
    typedef T         value_type;
    typedef ptrdiff_t difference_type;
    typedef T         *pointer;
    typedef T         &reference;
    typedef random_access_iterator_tag iterator_category;
};

Ainsi, le type iterator_traits<itérateur>::difference_type renverra toujours le type permettant de stocker la différence entre deux itérateurs, que ceux-ci soient des itérateurs ou des pointeurs normaux.

Pour comprendre l'importance des traits des itérateurs, prenons l'exemple de deux fonctions fournies par la bibliothèque standard permettant d'avancer un itérateur d'un certain nombre d'étapes, et de calculer la différence entre deux itérateurs. Il s'agit respectivement des fonctions advance et distance. Ces fonctions devant pouvoir travailler avec n'importe quel itérateur, et n'importe quel type de donnée pour exprimer la différence entre deux itérateurs, elles utilisent la classe des traits. Elles sont déclarées de la manière suivante dans l'en-tête iterator :

 
Sélectionnez
template <class InputIterator, class Distance>
void advance(InputIterator &i, Distance n);
 
template <class InputIterator>
iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last);

Notez que le type de retour de la fonction distance est Iterator::difference_type pour les itérateurs normaux, et ptrdiff_t pour les pointeurs.

Note : Ces deux méthodes ne sont pas très efficaces avec les itérateurs de type Forward, car elles doivent parcourir les valeurs de ces itérateurs une à une. Cependant, elles sont spécialisées pour les itérateurs de type plus évolués (en particulier les itérateurs à accès complet), et sont donc plus efficaces pour eux. Elles permettent donc de manipuler les itérateurs de manière uniforme, sans pour autant compromettre les performances.

13.4.3. Itérateurs adaptateurs

Les itérateurs sont une notion extrêmement utilisée dans toute la bibliothèque standard, car ils regroupent toutes les fonctionnalités permettant d'effectuer un traitement séquentiel des données. Cependant, il n'existe pas toujours d'itérateur pour les sources de données que l'on manipule. La bibliothèque standard fournit donc ce que l'on appelle des itérateurs adaptateurs, qui permettent de manipuler ces structures de données en utilisant la notion d'itérateur même si ces structures ne gèrent pas elles-mêmes la notion d'itérateur.

13.4.3.1. Adaptateurs pour les flux d'entrée / sortie standards

Les flux d'entrée / sortie standards de la bibliothèque sont normalement utilisés avec les opérations '>>' et '<<', respectivement pour recevoir et pour envoyer des données. Il n'existe pas d'itérateur de type Input et de type Output permettant de lire et d'écrire sur ces flux. La bibliothèque définit donc des adaptateurs permettant de construire ces itérateurs.

L'itérateur adaptateur pour les flux d'entrée est implémenté par la classe template istream_iterator. Cet adaptateur est déclaré comme suit dans l'en-tête iterator :

 
Sélectionnez
template <class T, class charT, class traits = char_traits<charT>,
    class Distance=ptrdiff_t>
class istream_iterator :
    public iterator<input_iterator_tag, T, Distance,
        const T *, const T &>
{
public:
    typedef charT  char_type;
    typedef traits trait_type;
    typedef basic_istream<char, traits> istream_type;
    istream_iterator();
    istream_iterator(istream_iterator &flux);
    istream_iterator(const istream_iterator<T, charT, traits,
        Distance> &flux);
    ~istream_iterator();
    const T &operator*() const;
    const T *operator->() const;
    istream_iterator<T, charT, traits, Distance> &operator++();
    istream_iterator<T, charT, traits, Distance> operator++(int);
};

Les opérateurs d'égalité et d'inégalité sont également définis pour cet itérateur.

Comme vous pouvez le constater d'après cette déclaration, il est possible de construire un itérateur sur un flux d'entrée permettant de lire les données de ce flux une à une. S'il n'y a plus de données à lire sur ce flux, l'itérateur prend la valeur de l'itérateur de fin de fichier pour le flux. Cette valeur est celle qui est attribuée à tout nouvel itérateur construit sans flux d'entrée. L'exemple suivant présente comment faire la somme de plusieurs nombres lus sur le flux d'entrée, et de l'afficher lorsqu'il n'y a plus de données à lire.

Exemple 13-2. Itérateurs de flux d'entrée
Sélectionnez
#include <iostream>
#include <iterator>
 
using namespace std;
 
int main(void)
{
    double somme = 0;
    istream_iterator<double, char> is(cin);
    while (is != istream_iterator<double, char>())
    {
        somme = somme + *is;
        ++is;
    }
    cout << "La somme des valeurs lue est : " <<
        somme << endl;
    return 0;
}

Vous pourrez essayer ce programme en tapant plusieurs nombres successivement puis en envoyant un caractère de fin de fichier avec la combinaison de touches CTRL + Z. Ce caractère provoquera la sortie de la boucle while et affichera le résultat.

L'itérateur adaptateur pour les flux de sortie fonctionne de manière encore plus simple, car il n'y a pas à faire de test sur la fin de fichier. Il est déclaré comme suit dans l'en-tête iterator :

 
Sélectionnez
template <class T, class charT = char, class traits = char_traits<charT> >
class ostream_iterator :
    public iterator<output_iterator_tag, void, void, void, void>
{
public:
    typedef charT  char_type;
    typedef traits trait_type;
    typedef basic_ostream<charT, traits> ostream_type;
    ostream_iterator(ostream_type &flux);
    ostream_iterator(ostream_type &flux, const charT *separateur);
    ostream_iterator(const ostream_iterator<T, charT, traits> &flux);
    ~ostream_iterator();
    ostream_iterator<T, charT, traits> &operator=(const T &valeur);
    ostream_iterator<T, charT, traits> &operator*();
    ostream_iterator<T, charT, traits> &operator++();
    ostream_iterator<T, charT, traits> &operator++(int);
};

Cet itérateur est de type Output, et ne peut donc être déréférencé que dans le but de faire une écriture dans l'objet ainsi obtenu. Ce déréférencement retourne en fait l'itérateur lui-même, si bien que l'écriture provoque l'appel de l'opérateur d'affectation de l'itérateur. Cet opérateur envoie simplement les données sur le flux de sortie que l'itérateur prend en charge et renvoie sa propre valeur afin de réaliser une nouvelle écriture. Notez que les opérateurs d'incrémentation existent également, mais ne font strictement rien. Ils ne sont là que pour permettre d'utiliser ces itérateurs comme de simples pointeurs.

L'itérateur ostream_iterator peut envoyer sur le flux de sortie un texte intercalaire entre chaque donnée qu'on y écrit. Ce texte peut servir à insérer des séparateurs entre les données. Cette fonctionnalité peut s'avérer très pratique pour l'écriture de données formatées. Le texte à insérer automatiquement doit être passé en tant que deuxième argument du constructeur de l'itérateur.

Exemple 13-3. Itérateur de flux de sortie
Sélectionnez
#include <iostream>
#include <iterator>
 
using namespace std;
 
const char *texte[6] = {
    "Bonjour", "tout", "le", "monde", "!", NULL
};
 
int main(void)
{
    ostream_iterator<const char *, char> os(cout, " ");
    int i = 0;
    while (texte[i] != NULL)
    {
        *os = texte[i];  // Le déréférencement est facultatif.
        ++os;            // Cette ligne est facultative.
        ++i;
    }
    cout << endl;
    return 0;
}

Il existe également des adaptateurs pour les tampons de flux d'entrée / sortie basic_streambuf. Le premier adaptateur est implémenté par la classe template istreambuf_iterator. Il permet de lire les données provenant d'un tampon de flux basic_streambuf aussi simplement qu'en manipulant un pointeur et en lisant la valeur de l'objet pointé. Le deuxième adaptateur, ostreambuf_iterator, permet quant à lui d'écrire dans un tampon en affectant une nouvelle valeur à l'objet référencé par l'itérateur. Ces adaptateurs fonctionnent donc exactement de la même manière que les itérateurs pour les flux d'entrée / sortie formatés. En particulier, la valeur de fin de fichier que prend l'itérateur d'entrée peut être récupérée à l'aide du constructeur par défaut de la classe istreambuf_iterator, instanciée pour le type de tampon utilisé.

Note : L'opérateur de d'incrémentation suffixé des itérateurs istreambuf_iterator a un type de retour particulier qui permet de représenter la valeur précédente de l'itérateur avant incrémentation. Les objets de ce type sont toujours déréférençables à l'aide de l'opérateur '*'. La raison de cette particularité est que le contenu du tampon peut être modifié après l'appel de l'opérateur 'operator ++(int)', mais l'ancienne valeur de cet itérateur doit toujours permettre d'accéder à l'objet qu'il référençait. La valeur retournée par l'itérateur contient donc une sauvegarde de cet objet et peut se voir appliquer l'opérateur de déréférencement '*' par l'appelant afin d'en récupérer la valeur.

La notion de tampon de flux sera présentée en détail dans la Section 15.2.
13.4.3.2. Adaptateurs pour l'insertion d'éléments dans les conteneurs

Les itérateurs fournis par les conteneurs permettent d'en parcourir le contenu et d'obtenir une référence sur chacun de leurs éléments. Ce comportement est tout à fait classique et constitue même une des bases de la notion d'itérateur. Toutefois, l'insertion de nouveaux éléments dans un conteneur ne peut se faire que par l'intermédiaire des méthodes spécifiques aux conteneurs. La bibliothèque standard C++ définit donc des adaptateurs pour des itérateurs dits d'insertion, qui permettent d'insérer des éléments dans des conteneurs par un simple déréférencement et une écriture. Grâce à ces adaptateurs, l'insertion des éléments dans les conteneurs peut être réalisée de manière uniforme, de la même manière qu'on écrirait dans un tableau qui se redimensionnerait automatiquement, à chaque écriture.

Il est possible d'insérer les nouveaux éléments en plusieurs endroits dans les conteneurs. Ainsi, les éléments peuvent être placés au début du conteneur, à sa fin, ou après un élément donné. Bien entendu, ces notions n'ont de sens que pour les conteneurs qui ne sont pas ordonnés, puisque dans le cas contraire, la position de l'élément inséré est déterminée par le conteneur lui-même.

La classe template back_insert_iterator est la classe de l'adaptateur d'insertion en fin de conteneur. Elle est déclarée comme suit dans l'en-tête iterator :

 
Sélectionnez
template <class Container>
class back_insert_iterator :
    public iterator<output_iterator_tag, void, void, void, void>
{
public:
    typedef Container container_type;
    explicit back_insert_iterator(Container &conteneur);
    back_insert_iterator<Container> &
        operator=(const typename Container::value_type &valeur);
    back_insert_iterator<Container> &operator*();
    back_insert_iterator<Container> &operator++();
    back_insert_iterator<Container> operator++(int);
};

Comme vous pouvez le constater, les objets des instances cette classe peuvent être utilisés comme des itérateurs de type Output. L'opérateur de déréférencement '*' renvoie l'itérateur lui-même, si bien que les affectations sur les itérateurs déréférencés sont traitées par l'opérateur 'operator=' de l'itérateur lui-même. C'est donc cet opérateur qui ajoute l'élément à affecter à la fin du conteneur auquel l'itérateur permet d'accéder, en utilisant la méthode push_back de ce dernier.

De même, la classe template front_insert_iterator de l'adaptateur d'insertion en tête de conteneur est déclarée comme suit dans l'en-tête iterator :

 
Sélectionnez
template <class Container>
class front_insert_iterator :
    public iterator<output_iterator_tag, void, void, void, void>
{
public:
    typedef Container container_type;
    explicit front_insert_iterator(Container &conteneur);
    front_insert_iterator<Container> &
        operator=(const typename Container::value_type &valeur);
    front_insert_iterator<Container> &operator*();
    front_insert_iterator<Container> &operator++();
    front_insert_iterator<Container> operator++(int);
};

Son fonctionnement est identique à celui de back_insert_iterator, à ceci près qu'il effectue les insertions des éléments au début du conteneur, par l'intermédiaire de sa méthode push_front.

Enfin, la classe template de l'adaptateur d'itérateur d'insertion à une position donnée est déclarée comme suit :

 
Sélectionnez
template <class Container>
class insert_iterator :
    public iterator<output_iterator_tag, void, void, void, void>
{
public:
    typedef Container container_type;
    insert_iterator(Container &conteneur,
        typename Container::iterator position);
    insert_iterator<Container> &
        operator=(const typename Container::value_type &valeur);
    insert_iterator<Container> &operator*();
    insert_iterator<Container> &operator++();
    insert_iterator<Container> operator++(int);
};

Le constructeur de cette classe prend en paramètre, en plus du conteneur sur lequel l'itérateur d'insertion doit travailler, un itérateur spécifiant la position à laquelle les éléments doivent être insérés. Les éléments sont insérés juste avant l'élément référencé par l'itérateur fourni en paramètre. De plus, ils sont insérés séquentiellement, les uns après les autres, dans leur ordre d'affectation via l'itérateur.

La bibliothèque standard C++ fournit trois fonctions template qui permettent d'obtenir les trois types d'itérateur d'insertion pour chaque conteneur. Ces fonctions sont déclarées comme suit dans l'en-tête iterator :

 
Sélectionnez
template <class Container>
back_insert_iterator<Container>
    back_inserter(Container &conteneur);
 
template <class Container>
front_insert_iterator<Container>
    front_inserter(Container &conteneur);
 
template <class Container, class Iterator>
insert_iterator<Container>
    inserter(Container &conteneur, Iterator position);

Le programme suivant utilise un itérateur d'insertion pour remplir une liste d'élément, avant d'en afficher le contenu.

Exemple 13-4. Itérateur d'insertion
Sélectionnez
#include <iostream>
#include <list>
#include <iterator>
 
using namespace std;
 
// Définit le type liste d'entier :
typedef list<int> li_t;
 
int main()
{
    // Crée une liste :
    li_t lst;
    // Insère deux éléments dans la liste de la manière classique :
    lst.push_back(1);
    lst.push_back(10);
    // Récupère un itérateur référençant le premier élément :
    li_t::iterator it = lst.begin();
    // Passe au deuxième élément :
    ++it;
    // Construit un itérateur d'insertion pour insérer de nouveaux
    // éléments avant le deuxième élément de la liste :
    insert_iterator<li_t> ins_it = inserter(lst, it);
    // Insère les éléments avec cet itérateur :
    for (int i = 2; i < 10; ++i)
    {
        *ins_it = i;
        ++ins_it;
    }
    // Affiche le contenu de la liste :
    it = lst.begin();
    while (it != lst.end())
    {
        cout << *it << endl;
        ++it;
    }
    return 0;
}

La manière d'utiliser le conteneur de type list sera décrite en détail dans le Chapitre 17.

13.4.3.3. Itérateur inverse pour les itérateurs bidirectionnels

Les itérateurs bidirectionnels et les itérateurs à accès aléatoire peuvent être parcourus dans les deux sens. Pour ces itérateurs, il est donc possible de définir un itérateur associé dont le sens de parcours est inversé. Le premier élément de cet itérateur est donc le dernier élément de l'itérateur associé, et inversement.

La bibliothèque standard C++ définit un adaptateur permettant d'obtenir un itérateur inverse facilement dans l'en-tête iterator. Il s'agit de la classe template reverse_iterator :

 
Sélectionnez
template <class Iterator>
class reverse_iterator :
    public iterator<
        iterator_traits<Iterator>::iterator_category,
        iterator_traits<Iterator>::value_type,
        iterator_traits<Iterator>::difference_type,
        iterator_traits<Iterator>::pointer,
        iterator_traits<Iterator>::reference>
{
public:
    typedef Iterator iterator_type;
    reverse_iterator();
    explicit reverse_iterator(Iterator iterateur);
    Iterator base() const;
    Reference operator*() const;
    Pointer operator->() const;
    reverse_iterator &operator++();
    reverse_iterator operator++(int);
    reverse_iterator &operator--();
    reverse_iterator operator--(int);
    reverse_iterator operator+(Distance delta) const;
    reverse_iterator &operator+=(Distance delta);
    reverse_iterator operator-(Distance delta) const;
    reverse_iterator &operator-=(Distance delta);
    Reference operator[](Distance delta) const;
};

Les opérateurs de comparaison classiques et d'arithmétique des pointeurs externes operator+ et operator- sont également définis dans cet en-tête.

Le constructeur de cet adaptateur prend en paramètre l'itérateur associé dans le sens inverse duquel le parcours doit se faire. L'itérateur inverse pointera alors automatiquement sur l'élément précédent l'élément pointé par l'itérateur passé en paramètre. Ainsi, si on initialise l'itérateur inverse avec la valeur de fin de l'itérateur direct, il référencera le dernier élément que l'itérateur direct aurait référencé avant d'obtenir sa valeur finale dans un parcours des éléments du conteneur. La valeur de fin de l'itérateur inverse peut être obtenue en construisant un itérateur inverse à partir de la valeur de début de l'itérateur direct.

Note : Notez que le principe spécifiant que l'adresse suivant celle du dernier élément d'un tableau doit toujours être une adresse valide est également en vigueur pour les itérateurs. La valeur de fin d'un itérateur est assimilable à cette adresse, pointant sur l'emplacement suivant le dernier élément d'un tableau, et n'est pas plus déréférençable, car elle se trouve en dehors du tableau. Cependant, elle peut être utilisée dans les calculs d'arithmétique des pointeurs, et c'est exactement ce que fait l'adaptateur reverse_iterator.

La méthode base permet de récupérer la valeur de l'itérateur direct associé à l'itérateur inverse. On prendra garde que l'itérateur renvoyé par cette méthode ne référence pas le même élément que celui référencé par l'itérateur inverse. En effet, l'élément référencé est toujours l'élément suivant l'élément référencé par l'itérateur inverse, en raison de la manière dont cet itérateur est initialisé. Par exemple, l'itérateur inverse référence le dernier élément du conteneur lorsqu'il vient d'être intialisé avec la valeur de fin de l'itérateur directe, valeur qui représente le dernier élément passé. De même, lorsque l'itérateur inverse a pour valeur sa valeur de fin d'itération (ce qui représente l'élément précédent le premier élément du conteneur en quelque sorte), l'itérateur direct référence le premier élément du conteneur.

En fait, les itérateurs inverses sont utilisés en interne par les conteneurs pour fournir des itérateurs permettant de parcourir leurs données dans le sens inverse. Le programmeur n'aura donc généralement pas besoin de construire des itérateurs inverses lui-même, il utilisera plutôt les itérateurs fournis par les conteneurs.

Exemple 13-5. Utilisation d'un itérateur inverse
Sélectionnez
#include <iostream>
#include <list>
#include <iterator>
 
using namespace std;
 
// Définit le type liste d'entier :
typedef list<int> li_t;
 
int main(void)
{
    // Crée une nouvelle liste :
    li_t li;
    // Remplit la liste :
    for (int i = 0; i < 10; ++i)
        li.push_back(i);
    // Affiche le contenu de la liste à l'envers :
    li_t::reverse_iterator rev_it = li.rbegin();
    while (rev_it != li.rend())
    {
        cout << *rev_it << endl;
        ++rev_it;
    }
    return 0;
}

13.5. Abstraction des fonctions : les foncteurs

La plupart des algorithmes de la bibliothèque standard, ainsi que quelques méthodes des classes qu'elle fournit, donnent la possibilité à l'utilisateur d'appliquer une fonction aux données manipulées. Ces fonctions peuvent être utilisées pour différentes tâches, comme pour comparer deux objets par exemple, ou tout simplement pour en modifier la valeur.

Cependant, la bibliothèque standard n'utilise pas ces fonctions directement, mais a plutôt recours à une abstraction des fonctions : les foncteurs. Un foncteur n'est rien d'autre qu'un objet dont la classe définit l'opérateur fonctionnel '()'. Les foncteurs ont la particularité de pouvoir être utilisés exactement comme des fonctions puisqu'il est possible de leur appliquer leur opérateur fonctionnel selon une écriture similaire à un appel de fonction. Cependant, ils sont un peu plus puissants que de simples fonctions, car ils permettent de transporter, en plus du code de l'opérateur fonctionnel, des paramètres additionnels dans leurs données membres. Les foncteurs constituent donc une fonctionnalité extrêmement puissante qui peut être très pratique en de nombreux endroits. En fait, comme on le verra plus loin, toute fonction peut être transformée en foncteur. Les algorithmes de la bibliothèque standard peuvent donc également être utilisés avec des fonctions classiques moyennant cette petite transformation.

Les algorithmes de la bibliothèque standard qui utilisent des foncteurs sont déclarés avec un paramètre template dont la valeur sera celle du foncteur permettant de réaliser l'opération à appliquer sur les données en cours de traitement. Au sein de ces algorithmes, les foncteurs sont utilisés comme de simples fonctions, et la bibliothèque standard ne fait donc pas d'autre hypothèse sur leur nature. Cependant, il est nécessaire de ne donner que des foncteurs en paramètres aux algorithmes de la bibliothèque standard, pas des fonctions. C'est pour cette raison que la bibliothèque standard définit un certain nombre de foncteurs standards afin de faciliter la tâche du programmeur.

13.5.1. Foncteurs prédéfinis

La bibliothèque n'utilise, dans ses algorithmes, que des foncteurs qui ne prennent qu'un ou deux paramètres. Les foncteurs qui prennent un paramètre et un seul sont dits « unaires », alors que les foncteurs qui prennent deux paramètres sont qualifiés de « binaires ». Afin de faciliter la création de foncteurs utilisables avec ses algorithmes, la bibliothèque standard définit deux classes de base qui pour les foncteurs unaires et binaires. Ces classes de base sont les suivantes :

 
Sélectionnez
template <class Arg, class Result>
struct unary_function
{
    typedef Arg    argument_type;
    typedef Result result_type;
};
 
template <class Arg1, class Arg2, class Result>
struct binary_function
{
    typedef Arg1   first_argument_type;
    typedef Arg2   second_argument_type;
    typedef Result result_type;
};

Ces classes sont définies dans l'en-tête functional.

La bibliothèque définit également un certain nombre de foncteurs standards qui encapsulent les opérateurs du langage dans cet en-tête. Ces foncteurs sont les suivants :

 
Sélectionnez
template <class T>
struct plus : binary_function<T, T, T>
{
    T operator()(const T &operande1, const T &operande2) const;
};
 
template <class T>
struct minus : binary_function<T, T, T>
{
    T operator()(const T &operande1, const T &operande2) const;
};
 
template <class T>
struct multiplies : binary_function<T, T, T>
{
    T operator()(const T &operande1, const T &operande2) const;
};
 
template <class T>
struct divides : binary_function<T, T, T>
{
    T operator()(const T &operande1, const T &operande2) const;
};
 
template <class T>
struct modulus : binary_function<T, T, T>
{
    T operator()(const T &operande1, const T &operande2) const;
};
 
template <class T>
struct negate : unary_function<T, T>
{
    T operator()(const T &operande) const;
};
 
template <class T>
struct equal_to : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};
 
template <class T>
struct not_equal_to : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};
 
template <class T>
struct greater : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};
 
template <class T>
struct less : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};
 
template <class T>
struct greater_equal : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};
 
template <class T>
struct less_equal : binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};

Ces foncteurs permettent d'utiliser les principaux opérateurs du langage comme des fonctions classiques dans les algorithmes de la bibliothèque standard.

Exemple 13-6. Utilisation des foncteurs prédéfinis
Sélectionnez
#include <iostream>
#include <functional>
 
using namespace std;
 
// Fonction template prenant en paramètre deux valeurs
// et un foncteur :
template <class T, class F>
T applique(T i, T j, F foncteur)
{
    // Applique l'opérateur fonctionnel au foncteur
    // avec comme arguments les deux premiers paramètres :
    return foncteur(i, j);
}
 
int main(void)
{
    // Construit le foncteur de somme :
    plus<int> foncteur_plus;
    // Utilise ce foncteur pour faire faire une addition
    // à la fonction "applique" :
    cout << applique(2, 3, foncteur_plus) << endl;
    return 0;
}

Dans l'exemple précédent, la fonction template applique prend en troisième paramètre un foncteur et l'utilise pour réaliser l'opération à faire avec les deux premiers paramètres. Cette fonction ne peut théoriquement être utilisée qu'avec des objets disposant d'un opérateur fonctionnel '()', et pas avec des fonctions normales. La bibliothèque standard fournit donc les adaptateurs suivants, qui permettent de convertir respectivement n'importe quelle fonction unaire ou binaire en foncteur :

 
Sélectionnez
template <class Arg, class Result>
class pointer_to_unary_function :
    public unary_function<Arg, Result>
{
public:
    explicit pointer_to_unary_function(Result (*fonction)(Arg));
    Result operator()(Arg argument1) const;
};
 
template <class Arg1, Arg2, Result>
class pointer_to_binary_function :
    public binary_function<Arg1, Arg2, Result>
{
public:
    explicit pointer_to_binary_function(Result (*fonction)(Arg1, Arg2));
    Result operator()(Arg1 argument1, Arg2 argument2) const;
};
 
template <class Arg, class Result>
pointer_to_unary_function<Arg, Result>
    ptr_fun(Result (*fonction)(Arg));
 
template <class Arg, class Result>
pointer_to_binary_function<Arg1, Arg2, Result>
    ptr_fun(Result (*fonction)(Arg1, Arg2));

Les deux surcharges de la fonction template ptr_fun permettent de faciliter la construction d'un foncteur unaire ou binaire à partir du pointeur d'une fonction du même type.

Exemple 13-7. Adaptateurs de fonctions
Sélectionnez
#include <iostream>
#include <functional>
 
using namespace std;
 
template <class T, class F>
T applique(T i, T j, F foncteur)
{
    return foncteur(i, j);
}
 
// Fonction classique effectuant une multiplication :
int mul(int i, int j)
{
    return i * j;
}
 
int main(void)
{
    // Utilise un adaptateur pour transformer le pointeur
    // sur la fonction mul en foncteur :
    cout << applique(2, 3, ptr_fun(&mul)) << endl;
    return 0;
}

Note : En réalité le langage C++ est capable d'appeler une fonction directement à partir de son adresse, sans déréférencement. De plus le nom d'une fonction représente toujours sont adresse, et est donc converti implicitement par le compilateur en pointeur de fonction. Par conséquent, il est tout à fait possible d'utiliser la fonction template applique avec une autre fonction à deux paramètres, comme dans l'appel suivant :

 
Sélectionnez
    applique(2, 3, mul);

Cependant, cette écriture provoque la conversion implicite de l'identificateur mul en pointeur de fonction prenant deux entiers en paramètres et renvoyant un entier, d'une part, et l'appel de la fonction mul par l'intermédiaire de son pointeur sans déréférencement dans la fonction template applique d'autre part. Cette écriture est donc acceptée par le compilateur par tolérance, mais n'est pas rigoureusement exacte.

La bibliothèque standard C++ définit également des adaptateurs pour les pointeurs de méthodes non statiques de classes. Ces adaptateurs se construisent comme les adaptateurs de fonctions statiques classiques, à ceci près que leur constructeur prend un pointeur de méthode de classe et non un pointeur de fonction normale. Ils sont déclarés de la manière suivante dans l'en-tête functional :

 
Sélectionnez
template <class Result, class Class>
class mem_fun_t :
    public unary_function<Class *, Result>
{
public:
    explicit mem_fun_t(Result (Class::*methode)());
    Result operator()(Class *pObjet);
};
 
template <class Result, class Class, class Arg>
class mem_fun1_t :
    public binary_function<Class *, Arg, Result>
{
public:
    explicit mem_fun1_t(Result (Class::*methode)(Arg));
    Result operator()(Class *pObjet, Arg argument);
};
 
template <class Result, class Class>
class mem_fun_ref_t :
    public unary_function<Class, Result>
{
public:
    explicit mem_fun_ref_t(Result (Class::*methode)());
    Result operator()(Class &objet);
};
 
template <class Result, class Class, class Arg>
class mem_fun1_ref_t :
    public binary_function<Class, Arg, Result>
{
public:
    explicit mem_fun1_ref_t(Result (Class::*methode)(Arg));
    Result operator()(Class &objet, Arg argument);
};
 
template <class Result, class Class>
mem_fun_t<Result, Class> mem_fun(Result (Class::*methode)());
 
template <class Result, class Class, class Arg>
mem_fun1_t<Result, Class> mem_fun(Result (Class::*methode)(Arg));
 
template <class Result, class Class>
mem_fun_ref_t<Result, Class> mem_fun_ref(Result (Class::*methode)());
 
template <class Result, class Class, class Arg>
mem_fun1_ref_t<Result, Class>
    mem_fun_ref(Result (Class::*methode)(Arg));

Comme vous pouvez le constater d'après leurs déclarations les opérateurs fonctionnels de ces adaptateurs prennent en premier paramètre soit un pointeur sur l'objet sur lequel le foncteur doit travailler (adaptateurs mem_fun_t et mem_fun1_t), soit une référence sur cet objet (adaptateurs mem_fun_ref_t et mem_fun1_ref_t). Le premier paramètre de ces foncteurs est donc réservé pour l'objet sur lequel la méthode encapsulée doit être appelée.

En fait, la liste des adaptateurs présentée ci-dessus n'est pas exhaustive. En effet, chaque adaptateur présenté est doublé d'un autre adaptateur, capable de convertir les fonctions membres const. Il existe donc huit adaptateurs au total permettant de construire des foncteurs à partir des fonctions membres de classes. Pour diminuer cette complexité, la bibliothèque standard définit plusieurs surcharges pour les fonctions mem_fun et mem_fun_ref, qui permettent de construire tous ces foncteurs plus facilement, sans avoir à se soucier de la nature des pointeurs de fonction membre utilisés. Il est fortement recommandé de les utiliser plutôt que de chercher à construire ces objets manuellement.

13.5.2. Prédicats et foncteurs d'opérateurs logiques

Les foncteurs qui peuvent être utilisés dans une expression logique constituent une classe particulière : les prédicats. Un prédicat est un foncteur dont l'opérateur fonctionnel renvoie un booléen. Les prédicats ont donc un sens logique, et caractérisent une propriété qui ne peut être que vraie ou fausse.

La bibliothèque standard fournit des prédicats prédéfinis qui effectuent les opérations logiques des opérateurs logiques de base du langage. Ces prédicats sont également déclarés dans l'en-tête functional :

 
Sélectionnez
template <class T>
struct logical_and :
    binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};
 
template <class T>
struct logical_or :
    binary_function<T, T, bool>
{
    bool operator()(const T &operande1, const T &operande2) const;
};

Ces foncteurs fonctionnent exactement comme les foncteurs vus dans la section précédente.

La bibliothèque standard définit aussi deux foncteurs particuliers, qui permettent d'effectuer la négation d'un autre prédicat. Ces deux foncteurs travaillent respectivement sur les prédicats unaires et sur les prédicats binaires :

 
Sélectionnez
template <class Predicate>
class unary_negate :
    public unary_function<typename Predicate::argument_type, bool>
{
public:
    explicit unary_negate(const Predicate &predicat);
    bool operator()(const argument_type &argument) const;
};
 
template <class Predicate>
class binary_negate :
    public binary_function<typename Predicate::first_argument_type,
        typename Predicate::second_argument_type, bool>
{
public:
    explicit binary_negate(const Predicate &predicat);
    bool operator()(const first_argument_type &argument1,
        const second_argument_type &argument2) const;
};
 
template <class Predicate>
unary_negate<Predicate> not1(const Predicate &predicat);
 
template <class Predicate>
binary_negate<Predicate> not2(const Predicate &predicat);

Les fonctions not1 et not2 servent à faciliter la construction d'un prédicat inverse pour les prédicats unaires et binaires.

13.5.3. Foncteurs réducteurs

Nous avons vu que la bibliothèque standard ne travaillait qu'avec des foncteurs prenant au plus deux arguments. Certains algorithmes n'utilisant que des foncteurs unaires, ils ne sont normalement pas capables de travailler avec les foncteurs binaires. Toutefois, si un des paramètres d'un foncteur binaire est fixé à une valeur donnée, celui-ci devient unaire, puisque seul le deuxième paramètre peut varier. Il est donc possible d'utiliser des foncteurs binaires même avec des algorithmes qui n'utilisent que des foncteurs unaires, à la condition de fixer l'un des paramètres.

La bibliothèque standard définit des foncteurs spéciaux qui permettent de transformer tout foncteur binaire en foncteur unaire à partir de la valeur de l'un des paramètres. Ces foncteurs effectuent une opération dite de réduction car ils réduisent le nombre de paramètres du foncteur binaire à un. Pour cela, ils définissent un opérateur fonctionnel à un argument, qui applique l'opérateur fonctionnel du foncteur binaire à cet argument et à une valeur fixe qu'ils mémorisent en donnée membre.

Ces foncteurs réducteurs sont déclarés, comme les autres foncteurs, dans l'en-tête fonctional :

 
Sélectionnez
template <class Operation>
class binder1st :
    public unary_function<typename Operation::second_argument_type,
        typename Operation::result_type>
{
protected:
    Operation op;
    typename Operation::first_argument_type value;
public:
    binder1st(const Operation &foncteur,
        const typename Operation::first_argument_type &valeur);
    result_type operator()(const argument_type &variable) const;
};
 
template <class Operation>
class binder2nd :
    public unary_function<typename Operation::first_argument_type,
        typename Operation::result_type>
{
protected:
    Operation op;
    typename Operation::second_argument_type value;
public:
    binder2nd(const Operation &foncteur,
        const typename Operation::second_argument_type &valeur);
    result_type operator()(const argument_type &variable) const;
};
 
template <class Operation, class T>
binder1st<Operation> bind1st(const Operation &foncteur, const T &valeur);
 
template <class Operation, class T>
binder2nd<Operation> bind2nd(const Operation &foncteur, const T &valeur);

Il existe deux jeux de réducteurs, qui permettent de réduire les foncteurs binaires en fixant respectivement leur premier ou leur deuxième paramètre. Les réducteurs qui figent le premier paramètre peuvent être construits à l'aide de la fonction template bind1st, et ceux qui figent la valeur du deuxième paramètre peuvent l'être à l'aide de la fonction bind2nd.

Exemple 13-8. Réduction de foncteurs binaires
Sélectionnez
#include <iostream>
#include <functional>
 
using namespace std;
 
// Fonction template permettant d'appliquer une valeur
// à un foncteur unaire. Cette fonction ne peut pas
// être utilisée avec un foncteur binaire.
template <class Foncteur>
typename Foncteur::result_type applique(
    Foncteur f,
    typename Foncteur::argument_type valeur)
{
    return f(valeur);
}
 
int main(void)
{
    // Construit un foncteur binaire d'addition d'entiers :
    plus<int> plus_binaire;
    int i;
    for (i = 0; i < 10; ++i)
    {
        // Réduit le foncteur plus_binaire en fixant son
        // premier paramètre à 35. Le foncteur unaire obtenu
        // est ensuite utilisé avec la fonction applique :
        cout << applique(bind1st(plus_binaire, 35), i) << endl;
    }
    return 0;
}

13.6. Gestion personnalisée de la mémoire : les allocateurs

L'une des plus grandes forces de la bibliothèque standard est de donner aux programmeurs le contrôle total de la gestion de la mémoire pour leurs objets. En effet, les conteneurs peuvent être amenés à créer un grand nombre d'objets, dont le comportement peut être très différent selon leur type. Si, dans la majorité des cas, la gestion de la mémoire effectuée par la bibliothèque standard convient, il peut parfois être nécessaire de prendre en charge soi-même les allocations et les libérations de la mémoire pour certains objets.

La bibliothèque standard utilise pour cela la notion d'allocateur. Un allocateur est une classe C++ disposant de méthodes standards que les algorithmes de la bibliothèque peuvent appeler lorsqu'elles désirent allouer ou libérer de la mémoire. Pour cela, les conteneurs de la bibliothèque standard C++ prennent tous un paramètre template représentant le type des allocateurs mémoire qu'ils devront utiliser. Bien entendu, la bibliothèque standard fournit un allocateur par défaut, et ce paramètre template prend par défaut la valeur de cet allocateur. Ainsi, les programmes qui ne désirent pas spécifier un allocateur spécifique pourront simplement ignorer ce paramètre template.

Les autres programmes pourront définir leur propre allocateur. Cet allocateur devra évidemment fournir toutes les fonctionnalités de l'allocateur standard, et satisfaire à quelques contraintes particulières. L'interface des allocateurs est fournie par la déclaration de l'allocateur standard, dans l'en-tête memory :

 
Sélectionnez
template <class T>
class allocator
{
public:
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef T         *pointer;
    typedef const T   *const_pointer;
    typedef T         &reference;
    typedef const T   &const_reference;
    typedef T         value_type;
    template <class U>
    struct rebind
    {
        typedef allocator<U> other;
    };
 
    allocator() throw();
    allocator(const allocator &) throw();
    template <class U>
    allocator(const allocator<U> &) throw();
    ~allocator() throw();
    pointer address(reference objet);
    const_pointer address(const_reference objet) const;
    pointer allocate(size_type nombre,
        typename allocator<void>::const_pointer indice);
    void deallocate(pointer adresse, size_type nombre);
    size_type max_size() const throw();
    void construct(pointer adresse, const T &valeur);
    void destroy(pointer adresse);
};
 
// Spécialisation pour le type void pour éliminer les références :
template <>
class allocator<void>
{
public:
    typedef void       *pointer;
    typedef const void *const_pointer;
    typedef void       value_type;
    template <class U>
    struct rebind
    {
        typedef allocator<U> other;
    };
};

Vous noterez que cet allocateur est spécialisé pour le type void, car certaines méthodes et certains typedef n'ont pas de sens pour ce type de donnée.

Le rôle de chacune des méthodes des allocateurs est très clair et n'appelle pas beaucoup de commentaires. Les deux surcharges de la méthode address permettent d'obtenir l'adresse d'un objet alloué par cet allocateur à partir d'une référence. Les méthodes allocate et deallocate permettent respectivement de réaliser une allocation de mémoire et la libération du bloc correspondant. La méthode allocate prend en paramètre le nombre d'objets qui devront être stockés dans le bloc à allouer et un pointeur fournissant des informations permettant de déterminer l'emplacement où l'allocation doit se faire de préférence. Ce dernier paramètre peut ne pas être pris en compte par l'implémentation de la bibliothèque standard que vous utilisez et, s'il l'est, son rôle n'est pas spécifié. Dans tous les cas, s'il n'est pas nul, ce pointeur doit être un pointeur sur un bloc déjà alloué par cet allocateur et non encore libéré. La plupart des implémentations chercheront à allouer un bloc adjacent à celui fourni en paramètre, mais ce n'est pas toujours le cas. De même, notez que le nombre d'objets spécifié à la méthode deallocate doit exactement être le même que celui utilisé pour l'allocation dans l'appel correspondant à allocate. Autrement dit, l'allocateur ne mémorise pas lui-même la taille des blocs mémoire qu'il a fourni.

Note : Le pointeur passé en paramètre à la méthode allocate n'est ni libéré, ni réalloué, ni réutilisé par l'allocateur. Il ne s'agit donc pas d'une modification de la taille mémoire du bloc fourni en paramètre, et ce bloc devra toujours être libéré indépendamment de celui qui sera alloué. Ce pointeur n'est utilisé par les implémentations que comme un indice fourni à l'allocateur afin d'optimiser les allocations de blocs dans les algorithmes et les conteneurs internes.

La méthode allocate peut lancer l'exception bad_alloc en cas de manque de mémoire ou si le nombre d'objets spécifié en paramètre est trop gros. Vous pourrez obtenir le nombre maximal que la méthode allocate est capable d'accepter grâce à la méthode max_size de l'allocateur.

Les deux méthodes construct et destroy permettent respectivement de construire un nouvel objet et d'en détruire un à l'adresse indiquée en paramètre. Elles doivent être utilisées lorsqu'on désire appeler le constructeur ou le destructeur d'un objet stocké dans une zone mémoire allouée par cet allocateur et non par les opérateurs new et delete du langage (rappelons que ces opérateurs effectuent ce travail automatiquement). Pour effectuer la construction d'un nouvel objet, construct utilise l'opérateur new avec placement, et pour le détruire, destroy appelle directement le destructeur de l'objet.

Note : Les méthodes construct et destroy n'effectuent pas l'allocation et la libération de la mémoire elles-mêmes. Ces opérations doivent être effectuées avec les méthodes allocate et deallocate de l'allocateur.

Exemple 13-9. Utilisation de l'allocateur standard
Sélectionnez
#include <iostream>
#include <memory>
 
using namespace std;
 
class A
{
public:
    A();
    A(const A &);
    ~A();
};
 
A::A()
{
    cout << "Constructeur de A" << endl;
}
 
A::A(const A &)
{
    cout << "Constructeur de copie de A" << endl;
}
 
A::~A()
{
    cout << "Destructeur de A" << endl;
}
 
int main(void)
{
    // Construit une instance de l'allocateur standard pour la classe A :
    allocator<A> A_alloc;
 
    // Alloue l'espace nécessaire pour stocker cinq instances de A :
    allocator<A>::pointer p = A_alloc.allocate(5);
 
    // Construit ces instances et les initialise :
    A init;
    int i;
    for (i=0; i<5; ++i)
        A_alloc.construct(p+i, init);
    // Détruit ces instances :
    for (i=0; i<5; ++i)
        A_alloc.destroy(p+i);
 
    // Reconstruit ces 5 instances :
    for (i=0; i<5; ++i)
        A_alloc.construct(p+i, init);
    // Destruction finale :
    for (i=0; i<5; ++i)
        A_alloc.destroy(p+i);
 
    // Libère la mémoire :
    A_alloc.deallocate(p, 5);
    return 0;
}

Vous voyez ici l'intérêt que peut avoir les allocateurs de la bibliothèque standard. Les algorithmes peuvent contrôler explicitement la construction et la destruction des objets, et surtout les dissocier des opérations d'allocation et de libération de la mémoire. Ainsi, un algorithme devant effectuer beaucoup d'allocations mémoire pourra, s'il le désire, effectuer ces allocations une bonne fois pour toutes grâce à l'allocateur standard, et n'effectuer les opérations de construction et de destruction des objets que lorsque cela est nécessaire. En procédant ainsi, le temps passé dans les routines de gestion de la mémoire est éliminé et l'algorithme est d'autant plus performant. Inversement, un utilisateur expérimenté pourra définir son propre allocateur mémoire adapté aux objets qu'il voudra stocker dans un conteneur. En imposant au conteneur de la bibliothèque standard d'utiliser cet allocateur personnalisé, il obtiendra des performances optimales.

La définition d'un allocateur maison consiste simplement à implémenter une classe template disposant des mêmes méthodes et types que ceux définis par l'allocateur allocator.

Toutefois, il faut savoir que la bibliothèque impose des contraintes sur la sémantique de ces méthodes :
  • toutes les instances de la classe template de l'allocateur permettent d'accéder à la même mémoire. Ces instances sont donc interchangeables et il est possible de passer de l'une à l'autre à l'aide de la structure template rebind et de son typedef other. Notez que le fait d'encapsuler ce typedef dans une structure template permet de simuler la définition d'un type template ;
  • toutes les instances d'un allocateur d'un type donné permettent également d'accéder à la même mémoire. Cela signifie qu'il n'est pas nécessaire de disposer d'une instance globale pour chaque allocateur, il suffit simplement de créer un objet local d'une des instances de la classe template de l'allocateur pour allouer et libérer de la mémoire. Notez ici la différence avec la contrainte précédente : cette contrainte porte ici sur les objets instances des classes template instanciées, alors que la contrainte précédente portait sur les instances elles-mêmes de la classe template de l'allocateur ;
  • toutes les méthodes de l'allocateur doivent s'exécuter dans un temps amorti constant (cela signifie que le temps d'exécution de ces méthodes est majoré par une borne supérieure fixe, qui ne dépend pas du nombre d'allocation déjà effectuées ni de la taille du bloc de mémoire demandé) ;
  • les méthodes allocate et deallocate sont susceptibles d'utiliser les opérateurs new et delete du langage. Ce n'est pas une obligation, mais cette contrainte signifie que les programmes qui redéfinissent ces deux opérateurs doivent être capable de satisfaire les demandes de l'allocateur standard ;
  • les types pointer, const_pointer, size_type et difference_type doivent être égaux respectivement aux types T *, const T*, size_t et ptrdiff_t. En fait, cette contrainte n'est imposée que pour les allocateurs destinés à être utilisés par les conteneurs de la bibliothèque standard, mais il est plus simple de la généraliser à tous les cas d'utilisation.

Pour terminer ce tour d'horizon des allocateurs, sachez que la bibliothèque standard définit également un type itérateur spécial permettant de stocker des objets dans une zone de mémoire non initialisée. Cet itérateur, nommé raw_storage_iterator, est de type Output et n'est utilisé qu'en interne par la bibliothèque standard. De même, la bibliothèque définit des algorithmes permettant d'effectuer des copies brutes de blocs mémoire et d'autres manipulations sur les blocs alloués par les allocateurs. Ces algorithmes sont également utilisés en interne, et ne seront donc pas décrits plus en détail ici.

13.7. Notion de complexité algorithmique

En aucun endroit la norme C++ ne spécifie la manière de réaliser une fonctionnalité. En effet, elle n'impose ni les structures de données, ni les algorithmes à utiliser. Les seules choses qui sont spécifiées par la norme sont les interfaces bien entendu (c'est-à-dire les noms des classes, des objets et les signatures des fonctions et des méthodes) et la sémantique des diverses opérations réalisables. Cependant, la norme C++ ne permet pas de réaliser toutes ces fonctionnalités n'importe comment, car elle impose également des contraintes de performances sur la plupart de ses algorithmes ainsi que sur les méthodes des conteneurs. Ces contraintes sont exprimées généralement en terme de complexité algorithmique, aussi est-il nécessaire de préciser un peu cette notion.

Note : En pratique, les contraintes de complexité imposées par la bibliothèque standard sont tout simplement les plus fortes réalisables. En d'autres termes, on ne peut pas faire mieux que les algorithmes de la bibliothèque standard.

XVI-G-1. 13.7.1. Généralités

La nature des choses veut que plus un programme a de données à traiter, plus il prend du temps pour le faire. Cependant, certains algorithmes se comportent mieux que d'autres lorsque le nombre des données à traiter augmente. Par exemple, un algorithme mal écrit peut voir son temps d'exécution croître exponentiellement avec la quantité de données à traiter, alors qu'un algorithme bien étudié aurait n'aurait été plus lent que proportionnellement à ce même nombre. En pratique, cela signifie que cet algorithme est tout simplement inutilisable lorsque le nombre de données augmente. Par exemple, le fait de doubler la taille de l'ensemble des données à traiter peut engendrer un temps de calcul quatre fois plus long, alors que le temps d'exécution de l'algorithme bien écrit n'aurait été que du double seulement. Et si le nombre de données est triplé et non doublé, cet algorithme demandera huit fois plus de temps, là où le triple seulement est nécessaire. Si l'on prend quatre fois plus de données, le temps sera multiplié par soixante-quatre. On voit clairement que les choses ne vont pas en s'améliorant quand le nombre de données à traiter augmente...

En réalité, il est relativement rare de considérer le temps d'exécution pour qualifier les performances d'un algorithme. En effet, le calcul du temps d'exécution n'est pas toujours possible d'une part, parce qu'il se base sur des paramètres a priori inconnus, et n'est pas toujours ce qui est intéressant au niveau du coût d'autre part. Pour illustrer ce dernier point, supposons que chaque opération effectuée par l'algorithme coûte une certaine quantité d'énergie. Dans certains contextes, il est plus important de s'intéresser à l'énergie dépensée qu'au temps passé pour effectuer l'ensemble des traitements. Or certaines opérations peuvent prendre relativement peu de temps, mais coûter très cher énergétiquement parlant, et l'optimisation du temps d'exécution ne donne pas forcément la meilleure solution. Un autre exemple est tout simplement celui de la lecture de secteurs sur un disque dur. La lecture de ces secteurs en soi ne prend pas tellement de temps, en revanche le déplacement de la tête de lecture se fait en un temps d'accès considérablement plus grand. Les algorithmes de gestion des entrées / sorties sur disque des systèmes d'exploitation cherchent donc naturellement à diminuer au maximum ces déplacements en réorganisant en conséquence les requêtes de lecture et d'écriture.

Il est donc généralement beaucoup plus simple de compter le nombre d'opérations que les algorithmes effectuent lors de leur déroulement, car cette donnée est bien moins spécifique au contexte d'utilisation de l'algorithme. Bien entendu, toutes les opérations effectuées par un algorithme n'ont pas le même coût dans un contexte donné, et de plus ce coût varie d'un contexte d'utilisation à un autre. La complexité d'un algorithme doit donc toujours s'exprimer en nombre d'opérations élémentaires d'un certain type, étant entendu que les opérations de ce type sont celles qui coûtent le plus cher selon les critères choisis...

Remarquez que les opérations qui sont réalisées par un algorithme peuvent être elles-mêmes relativement complexes. Par exemple, un algorithme qui applique une fonction sur chaque donnée à traiter peut utiliser une fonction inimaginablement complexe. Cependant, cela ne nous intéresse pas dans la détermination de la complexité de cet algorithme. Bien entendu, ce qu'il faut compter, c'est le nombre de fois que cette fonction est appelée, et la complexité de l'algorithme doit se calculer indépendamment de celle de cette fonction. L'opération élémentaire de l'algorithme est donc ici tout simplement l'appel de cette fonction, aussi complexe soit-elle.

13.7.2. Notions mathématiques de base et définition

Le nombre des opérations élémentaires effectuées par un algorithme est une fonction directe du nombre de données à traiter. La complexité d'un algorithme est donc directement reliée à cette fonction : plus elle croît rapidement avec le nombre de données à traiter, plus la complexité de l'algorithme est grande.

En réalité, la fonction exacte donnant le nombre d'opérations élémentaires effectuées par un algorithme n'est pas toujours facile à calculer. Cependant, il existe toujours une fonction plus simple qui dispose du même comportement que la fonction du nombre d'opérations de l'algorithme quand le nombre de données à traiter augmente. Cette « forme simplifiée » n'est en fait rien d'autre que la partie croissant le plus vite avec le nombre de données, car lorsque celui-ci tend vers l'infini, c'est elle qui devient prédominante. Cela signifie que si l'on trace le graphe de la fonction, sa forme finit par ressembler à celle de sa forme simplifiée lorsque le nombre de données à traiter devient grand.

La formulation complète de la fonction du nombre d'opérations réalisées par un algorithme n'importe donc pas tant que cela, ce qui est intéressant, c'est sa forme simplifiée. En effet, non seulement elle est plus simple (à exprimer, à manipuler et bien évidemment à retenir), mais en plus elle caractérise correctement le comportement de l'algorithme sur les grands nombres. La complexité d'un algorithme est donc, par définition, le terme prépondérant dans la fonction donnant le nombre d'opérations élémentaires effectuées par l'algorithme en fonction du nombre des données à traiter.

Mathématiquement parlant, le fait que la forme simplifiée d'une fonction se comporte comme la fonction elle-même à l'infini se traduit simplement en disant que les termes d'ordre inférieurs sont écrasés par le terme de premier ordre. Par conséquent, si l'on divise une fonction par l'autre, les termes d'ordre inférieur deviennent négligeables et la valeur du rapport tend à se stabiliser vers les grand nombres. Autrement dit, il est possible de trouver deux constantes A et B positives et non nulles telles que, à partir d'une certaine valeur de n, la triple inéquation 0 ? A×c(n) ? f(n) ? B×c(n), dans laquelle c(n) est la forme simplifiée de la fonction f(n), est toujours vérifiée. La fonction f(n) est donc, en quelque sortes, encadrée par deux « gendarmes » qui suivent le même « trajet » : celui de la fonction c(n).

Note : Notez que cette formulation n'utilise pas le rapport des fonctions f(n) et c(n) directement. Elle est donc toujours valide, même lorsque ces deux fonctions sont nulles, ce qui aurait posé des problèmes si l'on avait utilisé un rapport.

En fait, la limite inférieure A×c(n) ne nous intéresse pas spécialement. En effet, seul le coût maximal d'un algorithme est intéressant, car s'il coûte moins cher que prévu, personne ne s'en plaindra... Il est donc courant d'utiliser une formulation plus simple et plus connue des mathématiciens, dans laquelle seule la dernière inéquation est utilisée. On dit alors que la fonction f(n) est en grand O de c(n) (ce qui se note « O(c(n)) »). Cela signifie qu'il existe une constante A telle que, pour toutes les valeurs de n supérieures à une valeur suffisamment grande, la double inéquation 0 ? f(n) ? A×c(n) est toujours vérifiée.

Note : La notion de grand O permet donc de donner une borne supérieure de la complexité de la fonction. En fait, si f(n) est en O(c(n)), elle l'est pour toutes les fonctions plus grandes que c(n). Toutefois, en général, on cherche à déterminer la plus petite fonction c(n) qui est un grand O de f(n).

Il est évident que si une fonction f(n) dispose d'une forme simplifiée c(n), elle est en O(c(n)). En effet, l'inéquation supérieure est toujours vérifiée, on ne fait ici qu'ignorer la deuxième inéquation de la définition de la forme simplifiée.

13.7.3. Interprétation pratique de la complexité

Toutes ces notions peuvent vous paraître assez abstraites, mais il est important de bien comprendre ce qu'elles signifient. Il est donc peut-être nécessaire de donner quelques exemples de complexité parmi celles que l'on rencontre le plus couramment.

Tout d'abord, une complexité de 1 pour un algorithme signifie tout simplement que son coût d'exécution est constant, quel que soit le nombre de données à traiter. Notez bien ici que l'on parle de coût d'exécution et non de durée. Le coût est ici le nombre d'opérations élémentaires effectuées par cet algorithme. Les algorithmes de complexité 1 sont évidemment les plus intéressants, mais ils sont hélas assez rares ou tout simplement triviaux.

Généralement, les algorithmes ont une complexité de n, leur coût d'exécution est donc proportionnel au nombre de données à traiter. C'est encore une limite acceptable, et généralement acceptée comme une conséquence « logique » de l'augmentation du nombre de données à traiter. Certains algorithmes sont en revanche nettement moins performants et ont une complexité en n², soit le carré du nombre des éléments à traiter. Cette fois, cela signifie que leur coût d'exécution a tendance à croître très rapidement lorsqu'il y a de plus en plus de données. Par exemple, si l'on double le nombre de données, le coût d'exécution de l'algorithme ne double pas, mais quadruple. Et si l'on triple le nombre de données, ce coût devient neuf fois plus grand. Ne croyez pas pour autant que les algorithmes de ce type soient rares ou mauvais. On ne peut pas toujours, hélas, faire autrement...

Il existe même des algorithmes encore plus coûteux, qui utilisent des exposants bien supérieurs à 2. Inversement, certains algorithmes extrêmement astucieux permettent de réduire les complexités n ou n2 en ln(n) ou n×ln(n), ils sont donc nettement plus efficaces.

Note : La fonction ln(n) est la fonction logarithmique, qui est la fonction inverse de l'exponentielle, bien connue pour sa croissance démesurée. La fonction logarithme évolue beaucoup moins vite que son argument, en l'occurrence n dans notre cas, et a donc tendance à « écraser » le coût des algorithmes qui l'ont pour complexité.

Enfin, pour terminer ces quelques notions de complexité algorithmique, sachez que l'on peut évaluer la difficulté d'un problème à partir de la complexité du meilleur algorithme qui permet de le résoudre. Par exemple, il a été démontré que le tri d'un ensemble de n éléments ne peut pas se faire en mieux que n×ln(n) opérations (et on sait le faire, ce qui est sans doute le plus intéressant de l'affaire). Malheureusement, il n'est pas toujours facile de déterminer la complexité d'un problème. Il existe même toute une classe de problèmes extrêmement difficiles à résoudre pour lesquels on ne sait même pas si leur solution optimale est polynomiale ou non. En fait, on ne sait les résoudre qu'avec des algorithmes de complexité exponentielle (si vous ne savez pas ce que cela signifie, en un mot, cela veut dire que c'est une véritable catastrophe). Cependant, cela ne veut pas forcément dire qu'on ne peut pas faire mieux, mais tout simplement qu'on n'a pas pu trouver une meilleure solution, ni même prouver qu'il y en avait une ! Toutefois, tous ces problèmes sont liés et, si on trouve une solution polynomiale pour l'un d'entre eux, on saura résoudre aussi facilement tous ses petits camarades. Ces problèmes appartiennent tous à la classe des problèmes dits « NP-complets ».


précédentsommairesuivant

Copyright © 2003 Christian Casteyde. Permission vous est donnée de copier, distribuer et modifier ce document selon les termes de la licence GNU pour les documentations libres, version 1.1 ou toute autre version ultérieure publiée par la Free Software Foundation. Une copie de cette licence est incluse dans l'annexe intitulée "GNU Free Documentation License". Vous trouverez également une traduction non officielle de cette licence dans l'annexe intitulée "Licence de documentation libre GNU".