14.3. Les types numériques

En plus des types d'intérêt général vus dans les sections précédentes, la librairie standard fournit des types de données plus spécialisés dans les calculs numériques ou mathématiques. Ces types de données permettent d'effectuer des calculs sur les nombres complexes, ainsi que des calculs parallèles sur des tableaux de valeurs.

14.3.1. Les complexes

Les types de base du langage C++ fournissent une approximation relativement fiable des différents domaines de nombres mathématiques. Par exemple, le type int permet de représenter une plage de valeurs limitée des entiers relatifs, mais suffisamment large toutefois pour permettre d'effectuer la plupart des calculs intervenant dans la vie réelle. De même, les types des nombres à virgule flottante fournissent une approximation relativement satisfaisante des nombres réels des mathématiques. L'approximation cette fois porte non seulement sur la plage de valeur accessible, mais également sur la précision des nombres.

Il existe en mathématiques un autre type de nombres, qui n'ont pas de représentation physique immédiate pour le commun des mortels, mais qui permettent souvent de simplifier beaucoup certains calculs : les nombres complexes. Ces nombres étendent en effet le domaine des nombres accessibles et permettent de poursuivre les calculs qui n'étaient pas réalisables avec les nombres réels seulement, en s'affranchissant des contraintes imposées sur les solutions des équations algébriques. Les nombres complexes sont donc d'une très grande utilité dans toute l'algèbre, et en particulier dans les calculs matriciels où ils prennent une place prédominante. Les nombres complexes permettent également de simplifier sérieusement les calculs trigonométriques, les calculs de signaux en électricité et les calculs en mécanique quantique. Le plus intéressant avec ces nombres est sans doute le fait que même si les résultats intermédiaires que l'on trouve avec eux n'ont pas de signification réelle, les résultats finaux, eux, peuvent en avoir une et n'auraient pas été trouvés aussi facilement en conservant toutes les contraintes imposées par les nombres réels.

Afin de simplifier la vie des programmeurs qui ont besoin de manipuler des nombres complexes, la librairie standard C++ définit la classe template complex, qui permet de les représenter et d'effectuer les principales opérations mathématiques dessus. Si l'utilisation de la classe complex en soi ne pose aucun problème particulier, il peut être utile de donner une description sommaire de ce qu'est un nombre complexe pour les néophytes en mathématiques. Toutefois, cette description n'est pas destinée aux personnes n'ayant aucune connaissance en mathématiques (si tant est qu'un programmeur puisse être dans ce cas...). Si vous ne la comprenez pas, c'est sans doute que vous n'avez aucunement besoin des nombres complexes et vous pouvez donc passer cette section sans crainte.

14.3.1.1. Définition et principales propriétés des nombres complexes

Il n'est pas compliqué de se représenter ce que signifie un nombre réel puisqu'on les utilise couramment dans la vie courante. La méthode la plus simple est d'imaginer une règle graduée où chaque position est donnée par un nombre réel par rapport à l'origine. Ce nombre indique le nombre de fois que l'unité de distance doit être répétée depuis l'origine pour arriver à cette position.

Pour se représenter la valeur d'un nombre complexe, il faut utiliser une dimension supplémentaire. En fait, tout nombre complexe peut être exprimé avec deux valeurs réelles : la partie réelle du complexe, et sa partie imaginaire. Plusieurs notations existent pour représenter les nombres complexes à partir de ces deux parties. La plus courante est de donner la partie réelle et la partie imaginaire entre parenthèses, séparées par une virgule :

(réelle, imaginaire)
réelle est la valeur de la partie réelle, et imaginaire la valeur de la partie imaginaire. Il est également très courant en France de noter les deux parties directement en les séparant d'un signe d'addition et en accolant le caractère 'i' (pour « imaginaire ») à la partie imaginaire :
réelle + imaginaire i
L'exemple suivant vous présente quelques nombres complexes :
7.56
3i
5+7i
Vous constaterez que les nombres réels peuvent parfaitement être représentés par les nombres complexes, puisqu'il suffit simplement d'utiliser une partie imaginaire nulle.

Les opérations algébriques classiques ont été définies sur les nombres complexes. Les additions et soustractions se font membre à membre, partie réelle avec partie réelle et partie imaginaire avec partie imaginaire. En revanche, la multiplication est un peu plus complexe, car elle se base sur la propriété fondamentale que le carré de l'unité de la partie imaginaire vaut -1. Autrement dit, le symbole i de la notation précédente dispose de la propriété fondamentale suivante : i²=-1. Il s'agit en quelque sorte d'une racine carrée de -1 (la racine carrée des nombres négatifs n'ayant pas de sens, puisqu'un carré est normalement toujours positif, on comprend la qualification d'« imaginaire » des nombres complexes). À partir de cette règle de base, et en conservant les règles d'associativité des opérateurs, on peut définir le produit de deux nombres complexes comme suit :

(a,b) * (c,d) = (ac - bd, ad + bc)
Enfin, la division se définit toujours comme l'opération inverse de la multiplication, c'est-à-dire l'opération qui trouve le nombre qui, multiplié par le diviseur, redonne le dividende. Chaque nombre complexe non nul dispose d'un inverse, qui est le résultat de la division de 1 par ce nombre. On peut montrer facilement que l'inverse d'un nombre complexe est défini comme suit :
1/(a,b) = (a / (a² + b²), -b / (a² + b²))
À partir de l'inverse, il est simple de calculer une division quelconque.

Comme il l'a été dit plus haut, les nombres complexes peuvent être représentés en utilisant une dimension supplémentaire. Ainsi, si on définit un repère dans le plan, dont l'axe des abscisses est associé à la partie réelle des nombres complexes et l'axe des ordonnées à la partie imaginaire, à tout nombre complexe est associé un point du plan. On appelle alors ce plan le plan complexe. La définition des complexes donnée ici correspond donc à un système de coordonnées cartésiennes du plan complexe, et chaque nombre complexe dispose de ses propres coordonnées.

En mathématiques, il est également courant d'utiliser un autre système de coordonnées : le système de coordonnées polaires. Dans ce système, chaque point du plan est identifié non plus par les coordonnées de ses projections orthogonales sur les axes du repère, mais par sa distance à l'origine et par l'angle que la droite qui rejoint l'origine au point fait avec l'axe des abscisses. Ces deux nombres sont couramment notés respectivement avec les lettres grecques rho et theta. La dénomination de coordonnées polaires provient du fait que l'origine du repère joue le rôle d'un pôle par rapport auquel on situe le point dans le plan.

Il est donc évident que les nombres complexes peuvent également être représentés par leurs coordonnées polaires. On appelle généralement la distance à l'origine la norme du nombre complexe, et l'angle qu'il fait avec l'axe des abscisses son argument. Faites bien attention à ce terme, il ne représente pas un argument d'une fonction ou quoi que ce soit qui se rapporte à la programmation.

La plupart des fonctions mathématiques classiques ont été définies sur les nombres complexes, parfois en restreignant leur domaine de validité. Ainsi, il est possible de calculer un sinus, un cosinus, une exponentielle, etc. pour les nombres complexes. Il est bien entendu hors de question de définir rigoureusement, ni même de présenter succinctement ces fonctions dans ce document. Cependant, il est bon de savoir qu'on ne peut pas définir une relation d'ordre sur les nombres complexes. Autrement dit, on ne peut pas faire d'autre comparaison que l'égalité entre deux nombres complexes (essayez de comparer les nombres complexes situés sur un cercle centré à l'origine dans le plan complexe pour vous en rendre compte).

14.3.1.2. La classe complex

La classe template complex est définie dans l'en-tête complex de la librairie standard. Cette classe peut être instanciée pour l'un quelconque des trois types de nombre à virgule flottante du langage : float, double ou long double. Elle permet d'effectuer les principales opérations définies sur les nombres complexes, comme les additions, soustractions, multiplications, division, mais également des opérations spécifiques aux nombres complexes, comme la détermination de leur argument ou de leur norme. Enfin, l'en-tête complex contient des surcharges des fonctions mathématiques standards, telles que les fonctions trigonométriques, la racine carrée, les puissances et exponentielles, ainsi que les logarithmes (définis sur le plan complexe auquel l'axe des abscisses négatives a été ôté).

La construction d'un complexe ne pose aucun problème en soi. La classe complex dispose d'un constructeur par défaut, d'un constructeur de copie et d'un constructeur prenant en paramètre la partie réelle et la partie imaginaire du nombre :

L'exemple précédent présente également l'opérateur de sortie sur les flux standards, qui formate un nombre complexe en utilisant la notation (réel,imaginaire). Il existe également une surcharge de l'opérateur d'entrée pour le flux d'entrée :

Note : Malheureusement, cette notation pose des problèmes avec la locale française, puisque nous utilisons des virgules pour séparer la partie entière de la partie décimale des nombres à virgules. Lorsque l'un des deux nombres flottants est un entier, il est impossible de déterminer où se trouve la virgule séparant la partie entière de la partie imaginaire du nombre complexe. Une première solution est de modifier le formatage des nombres réels pour que les chiffres après la virgule soient toujours affichés, même s'ils sont nuls. Cependant, il faut également imposer que les saisies des nombres soient également toujours effectués avec des nombres à virgules, ce qui est sujet à erreur et invérifiable. Il est donc recommandé de n'utiliser que la locale de la librairie C lorsqu'on fait un programme utilisant les nombres complexes.

Il n'existe pas de constructeur permettant de créer un nombre complexe à partir de ses coordonnées polaires. En revanche, la fonction polar permet d'en construire un. Cette fonction prend en paramètre la norme du complexe à construire ainsi que son argument. Elle renvoie le nombre complexe nouvellement construit.

La partie imaginaire et la partie réelle d'un nombre complexe peuvent être récupérées à tout instant à l'aide des méthodes real et imag de la classe template complex. Il est également possible d'utiliser les fonctions template real et imag, qui prennent toutes deux le nombre complexe dont il faut calculer la partie réelle et la partie imaginaire. De même, la norme d'un nombre complexe est retournée par la fonction abs, et son argument peut être obtenu avec la fonction arg.

Bien entendu, les opérations classiques sur les complexes se font directement, comme s'il s'agissait d'un type prédéfini du langage :

Les fonctions spécifiques permettant de manipuler les complexes et de leur appliquer les opérations qui leurs sont propres sont récapitulées dans le tableau suivant :

14.3.2. Les tableaux de valeurs

Comme il l'a été expliqué dans le Chapitre 1, les programmes classiques fonctionnent toujours sur le même principe : ils travaillent sur des données qu'ils reçoivent en entrée et produisent des résultats en sortie. Ce mode de fonctionnement convient dans la grande majorité des cas, et en fait les programmes que l'on appelle couramment les « filtres » en sont une des applications principales. Un filtre n'est rien d'autre qu'un programme permettant, comme son nom l'indique, de filtrer les données reçues en entrée selon un critère particulier et de ne fournir en sortie que les données qui satisfont ce critère. Certains filtres plus évolués peuvent même modifier les données à la volée ou les traduire dans un autre format. Les filtres sont très souvent utilisés avec les mécanismes de redirection des systèmes qui les supportent afin d'exécuter des traitements complexes sur les flux de données à partir de filtres simples, en injectant les résultats des uns dans le flux d'entrée des autres.

Cependant, ce modèle a une limite pratique en terme de performances, car il nécessite un traitement séquentiel des données. La vitesse d'exécution d'un programme conçu selon ce modèle est donc directement lié à la vitesse d'exécution des instructions, donc à la vitesse du processeur de la machine utilisée. Lorsqu'un haut niveau de performance doit être atteint, plusieurs solutions sont disponibles. Dans la pratique, on distingue trois solutions classiques.

La première solution consiste simplement, pour augmenter la puissance d'une machine, à augmenter celle du processeur. Cela se traduit souvent par une augmentation de la fréquence de ce processeur, technique que tout le monde connaît. Les avantages de cette solution sont évidents : tous les programmes bénéficient directement de l'augmentation de la puissance du processeur et n'ont pas à être modifiés. En revanche, cette technique atteindra un jour ou un autre ses limites en termes de coûts de fabrication et de moyens techniques à mettre en oeuvre pour produire les processeurs.

La deuxième solution est d'augmenter le nombre de processeurs de la machine. Cette solution est très simple, mais suppose que les programmes soient capables d'effectuer plusieurs calculs indépendants simultanément. En particulier, les traitements à effectuer doivent être suffisamment indépendants et ne pas à avoir à attendre les données produites par les autres afin de pouvoir réellement être exécutés en parallèle. On quitte donc le modèle séquentiel, pour entrer dans un modèle de traitement où chaque processeur travaille en parallèle (modèle « MIMD », abréviation de l'anglais « Multiple Instruction Multiple Data »). Cette technique est également souvent appelée le parallélisme de traitement. Malheureusement, pour un unique processus purement séquentiel, cette technique ne convient pas, puisque de toutes façons, les opérations à exécuter ne le seront que par un seul processeur.

Enfin, il existe une technique mixte, qui consiste à paralléliser les données. Les mêmes opérations d'un programme séquentiel sont alors exécutées sur un grand nombre de données similaires. Les données sont donc traitées par blocs, par un unique algorithme : il s'agit du parallélisme de données (« SIMD » en anglais, abréviation de « Single Instruction Multiple Data »). Cette solution est celle mise en oeuvre dans les processeurs modernes qui disposent de jeux d'instructions spécialisées permettant d'effectuer des calculs sur plusieurs données simultanément (MMX, 3DNow et SSE pour les processeurs de type x86 par exemple). Bien entendu, cette technique suppose que le programme ait effectivement à traiter des données semblables de manière similaire. Cette contrainte peut paraître très forte, mais, en pratique, les situations les plus consommatrices de ressources sont justement celles qui nécessite la répétition d'un même calcul sur plusieurs données. On citera par exemple tous les algorithmes de traitement de données multimédia, dont les algorithmes de compression, de transformation et de combinaison.

Si l'augmentation des performances des processeurs apporte un gain directement observable sur tous les programmes, ce n'est pas le cas pour les techniques de parallélisation. Le parallélisme de traitement est généralement accessible au niveau système, par l'intermédiaire du multitâche et de la programmation multithreadée. Il faut donc écrire les programmes de telle sorte à bénéficier de ce parallélisme de traitement, à l'aide des fonctions spécifique au système d'exploitation. De même, le parallélisme de données nécessite la définition de types de données complexes, capables de représenter les blocs de données sur lesquels le programme doit travailler. Ces blocs de données sont couramment gérés comme des vecteurs ou des matrices, c'est-à-dire, en général, comme des tableaux de nombres. Le programme doit donc utiliser ces types spécifiques pour accéder à toutes les ressources de la machine. Cela nécessite un support de la part du langage de programmation.

Chaque environnement de développement est susceptible de fournir les types de données permettant d'effectuer des traitements SIMD. Cependant, ces types dépendent de l'environnement utilisé et encore plus de la plate-forme utilisée. La librairie standard C++ permet d'éviter ces écueils, car elle définit un type de donnée permettant de traiter des tableaux unidimensionnels d'objets, en assurant que les mécanismes d'optimisation propre aux plates-formes matérielles et aux compilateurs seront effectivement utilisés : les valarray.

14.3.2.1. Fonctionnalités de base des valarray

La classe valarray est une classe template capable de stocker un tableau de valeurs de son type template. Il est possible de l'instancier pour tous les types de données pour lesquels les opérations définies sur la classe valarray sont elles-mêmes définies. La librairie standard C++ garantit que la classe valarray est écrite de telle sorte que tous les mécanismes d'optimisation des compilateurs pourront être appliqués sur elle, afin d'obtenir des performances optimales. De plus, chaque implémentation est libre d'utiliser les possibilités de calcul parallèle disponible sur chaque plate-forme, du moins pour les types pour lesquels ces fonctionnalités sont présentes. Par exemple, la classe valarray instanciée pour le type float peut utiliser les instructions spécifiques de calcul sur les nombres flottants du processeur si elles sont disponibles. Toutefois, la norme n'impose aucune contrainte à ce niveau, et la manière dont la classe valarray est implémentée reste à la discrétion de chaque fournisseur.

La classe valarray fournit toutes les fonctionnalités nécessaires à la construction des tableaux de valeurs, à leur initialisation, ainsi qu'à leur manipulation. Elle est déclarée comme suit dans l'en-tête valarray :

// Déclaration des classes de sélection de sous-tableau :
class slice;
class gslice;

// Déclaration de la classe valarray :
template <class T>
class valarray
{
public:
    // Types des données :
    typedef T value_type;

    // Constructeurs et destructeurs :
    valarray();
    explicit valarray(size_t taille);
    valarray(const T &valeur, size_t taille);
    valarray(const T *tableau, size_t taille);
    valarray(const valarray &source);
    valarray(const mask_array<T> &source);
    valarray(const indirect_array<T> &source);
    valarray(const slice_array<T> &source);
    valarray(const gslice_array<T> &source);
    ~valarray();

    // Opérateurs d'affectation :
    valarray<T> &operator=(const T &valeur);
    valarray<T> &operator=(const valarray<T> &source);
    valarray<T> &operator=(const mask_array<T> &source);
    valarray<T> &operator=(const indirect_array<T> &source);
    valarray<T> &operator=(const slice_array<T> &source);
    valarray<T> &operator=(const gslice_array<T> &source);

    // Opérateurs d'accès aux éléments :
    T operator[](size_t indice) const;
    T &operator[](size_t indice);

    // Opérateurs de sélection de sous-ensemble du tableau :
    valarray<T>       operator[](const valarray<bool> &masque) const;
    mask_array<T>     operator[](const valarray<bool> &masque);
    valarray<T>       operator[](const valarray<size_t> &indices) const;
    indirect_array<T> operator[](const valarray<size_t> &indices);
    valarray<T>       operator[](slice selecteur) const;
    slice_array<T>    operator[](slice selecteur);
    valarray<T>       operator[](const gslice &selecteur) const;
    gslice_array<T>   operator[](const gslice &selecteur);

    // Opérateurs unaires :
    valarray<T> operator+() const;
    valarray<T> operator-() const;
    valarray<T> operator~() const;
    valarray<T> operator!() const;

    // Opérateurs d'affectation composée :
    valarray<T> operator*=(const T &valeur);
    valarray<T> operator*=(const valaray<T> &tableau);
    valarray<T> operator/=(const T &valeur);
    valarray<T> operator/=(const valaray<T> &tableau);
    valarray<T> operator%=(const T &valeur);
    valarray<T> operator%=(const valaray<T> &tableau);
    valarray<T> operator+=(const T &valeur);
    valarray<T> operator+=(const valaray<T> &tableau);
    valarray<T> operator-=(const T &valeur);
    valarray<T> operator-=(const valaray<T> &tableau);
    valarray<T> operator^=(const T &valeur);
    valarray<T> operator^=(const valaray<T> &tableau);
    valarray<T> operator&=(const T &valeur);
    valarray<T> operator&=(const valaray<T> &tableau);
    valarray<T> operator|=(const T &valeur);
    valarray<T> operator|=(const valaray<T> &tableau);
    valarray<T> operator<<=(const T &valeur);
    valarray<T> operator<<=(const valaray<T> &tableau);
    valarray<T> operator>>=(const T &valeur);
    valarray<T> operator>>=(const valaray<T> &tableau);

    // Opérations spécifiques :
    size_t size() const;
    T sum() const;
    T min() const;
    T max() const;
    valarray<T> shift(int) const;
    valarray<T> cshift(int) const;
    valarray<T> apply(T fonction(T)) const;
    valarray<T> apply(T fonction(const T &)) const;
    void resize(size_t taille, T initial=T());
};
Nous verrons dans la section suivante la signification des types slice, gslice, slice_array, gslice_array, mask_array et indirect_array.

Il existe plusieurs constructeurs permettant de créer et d'initialiser un tableau de valeurs. Le constructeur par défaut initialise un tableau de valeur vide. Les autres constructeurs permettent d'initialiser le tableau de valeur à partir d'une valeur d'initialisation pour tous les éléments du valarray, ou d'un autre tableau contenant les données à affecter aux éléments du valarray :

Vous pouvez constater que le deuxième argument des constructeurs qui permettent d'initialiser les valarray prennent un argument de type size_t, qui indique la taille du valarray. Une fois un valarray construit, il est possible de le redimensionner à l'aide de la méthode resize. Cette méthode prend en premier paramètre la nouvelle taille du valarray et la valeur à affecter aux nouveaux éléments dans le cas d'un agrandissement. La valeur par défaut est celle fournie par le constructeur par défaut du type des données contenues dans le valarray. La taille courante d'un valarray peut être récupérée à tout moment grâce à la méthode size.

Toutes les opérations classiques des mathématiques peuvent être appliquées sur un valarray pourvu qu'elles puissent l'être également sur le type des données contenues par ce tableau. La définition de ces opérations est très simple : l'opération du type de base est appliquée simplement à chaque élément contenu dans le tableau de valeurs.

La librairie standard définit également les opérateurs binaires nécessaires pour effectuer les opérations binaires sur chaque élément des valarray. En fait, ces opérateurs sont classés en deux catégories, selon la nature de leurs arguments. Les opérateurs de la première catégorie permettent d'effectuer une opération entre deux valarray de même dimension, en appliquant cette opération membre à membre. Il s'agit donc réellement d'une opération vectorielle dans ce cas. En revanche, les opérateurs de la deuxième catégorie appliquent l'opération avec une même et unique valeur pour chaque donnée stockée dans le valarray.

Parmi les opérateurs binaires que l'on peut appliquer à un valarray, on trouve bien entendu les opérateurs de comparaison. Ces opérateurs, contrairement aux opérateurs de comparaison habituels, ne renvoient pas un booléen, mais plutôt un autre tableau de booléens. En effet, la comparaison de deux valarray a pour résultat le valarray des résultats des comparaisons membres à membres des deux valarray.

La classe valarray dispose de méthodes permettant d'effectuer diverses opérations spécifiques aux tableaux de valeurs. La méthode sum permet d'obtenir la somme de toutes les valeurs stockées dans le tableau de valeur. Les méthodes shift et cshift permettent, quant à elles, de construire un nouveau valarray dont les éléments sont les éléments du valarray auquel la méthode est appliquée, décalés ou permutés circulairement d'un certain nombre de positions. Le nombre de déplacements effectués est passé en paramètre à ces deux fonctions, les valeurs positives entraînant des déplacements vers la gauche et les valeurs négatives des déplacements vers la droite. Dans le cas des décalages les nouveaux éléments introduits pour remplacer ceux qui n'ont pas eux-mêmes de remplaçant prennent la valeur spécifiée par le constructeur par défaut du type utilisé.

Enfin, il existe deux méthodes apply permettant d'appliquer une fonction à chaque élément d'un valarray et de construire un nouveau valarray de même taille et contenant les résultats. Ces deux surcharges peuvent travailler respectivement avec des fonctions prenant en paramètre soit par valeur, soit par référence, l'objet sur lequel elles doivent être appliquées.

14.3.2.2. Sélection multiple des éléments d'un valarray

Les éléments d'un valarray peuvent être accédés à l'aide de l'opérateur d'accès aux éléments de tableau '[]'. La fonction affiche des exemples du paragraphe précédent utilise cette fonctionnalité pour en récupérer la valeur. Cependant, les valarray dispose de mécanismes plus sophistiqués pour manipuler les éléments des tableaux de valeur en groupe, afin de bénéficier de tous les mécanismes d'optimisation qui peuvent exister sur une plate-forme donnée. Grâce à ces mécanismes, il est possible d'effectuer des opérations sur des parties seulement d'un valarray ou d'écrire de nouvelles valeurs dans certains de ses éléments seulement.

Pour effectuer ces sélections multiples, plusieurs techniques sont disponibles. Cependant, toutes ces techniques se basent sur le même principe, puisqu'elles permettent de filtrer les éléments du valarray pour n'en sélectionner qu'une partie seulement. Le résultat de ce filtrage peut être un nouveau valarray ou une autre classe pouvant être manipulée exactement de la même manière qu'un valarray.

En pratique, il existe quatre manières de sélectionner des éléments dans un tableau. Nous allons les détailler dans les sections suivantes.

14.3.2.2.1. Sélection par un masque

La manière la plus simple est d'utiliser un masque de booléens indiquant quels éléments doivent être sélectionnés ou non. Le masque de booléens doit obligatoirement être un valarray de même dimension que le valarray contenant les éléments à sélectionner. Chaque élément est donc sélectionné en fonction de la valeur du booléen correspondant dans le masque.

Une fois le masque construit, la sélection des éléments peut être réalisée simplement en fournissant ce masque à l'opérateur [] du valarray contenant les éléments à sélectionner. La valeur retournée par cet opérateur est alors une instance de la classe template mask_array, par l'intermédiaire de laquelle les éléments sélectionnés peuvent être manipulés. Pour les valarray constants cependant, la valeur retournée est un autre valarray, contenant une copie des éléments sélectionnés.

La classe mask_array fournit un nombre limité d'opérations. En fait, ses instances ne doivent être utilisées que pour effectuer des opérations simples sur les éléments du tableau sélectionné par le masque fourni à l'opérateur []. Les opérations réalisables seront décrites dans la Section 14.3.2.2.4.

La sélection des éléments d'un tableau par l'intermédiaire d'un masque est utilisée couramment avec les opérateurs de comparaison des valarray, puisque ceux-ci renvoient justement un tel masque. Il est donc très facile d'effectuer des opérations sur les éléments d'un valarray qui vérifient une certaine condition.

14.3.2.2.2. Sélection par indexation explicite

La sélection des éléments d'un valarray par un masque de booléens est explicite et facile à utiliser, mais elle souffre de plusieurs défauts. Premièrement, il faut fournir un tableau de booléen de même dimension que le valarray source. Autrement dit, il faut fournir une valeur booléenne pour tous les éléments du tableau, même pour ceux qui ne nous intéressent pas. Ensuite, les éléments sélectionnés apparaissent systématiquement dans le même ordre que celui qu'ils ont dans le valarray source.

La librairie standard C++ fournit donc un autre mécanisme de sélection, toujours explicite, mais qui permet de faire une réindexation des éléments ainsi sélectionnés. Cette fois, il ne faut plus fournir un masque à l'opérateur [], mais un valarray contenant directement les indices des éléments sélectionnés. Ces indices peuvent ne pas être dans l'ordre croissant, ce qui permet donc de réarranger l'ordre des éléments ainsi sélectionnés.

La valeur retournée par l'opérateur de sélection sur les valarray non constants est cette fois du type indirect_array. Comme pour la classe mask_array, les opérations réalisables par l'intermédiaire de cette classe sont limitées et doivent servir uniquement à modifier les éléments sélectionnés dans le valarray source.

14.3.2.2.3. Sélection par indexation implicite

Dans beaucoup de situations, les indices des éléments sélectionnés suivent un motif régulier et il n'est pas toujours pratique de spécifier ce motif explicitement. La méthode de sélection précédente n'est dans ce cas pas très pratique et il est alors préférable de sélectionner les éléments par un jeu d'indices décrits de manière implicite. La librairie fournit à cet effet deux classes utilitaires permettant de décrire des jeux d'indices plus ou moins complexes : la classe slice et la classe gslice.

Ces deux classes définissent les indices des éléments à sélectionner à l'aide de plusieurs variables pouvant prendre un certain nombre de valeurs espacées par un pas d'incrémentation fixe. La définition des indices consiste donc simplement à donner la valeur de départ de l'indice de sélection, le nombre de valeurs à générer pour chaque variable et le pas qui sépare ces valeurs. Les variables de contrôle commencent toutes leur itération à partir de la valeur nulle et prennent comme valeurs successives les multiples du pas qu'elles utilisent.

La classe slice est relativement facile à utiliser, puisqu'il suffit de spécifier la valeur de départ de l'indice, le nombre de valeurs à générer et le pas qui doit les séparer. Elle est déclarée comme suit dans l'en-tête valarray :

class slice
{
public:
    slice();
    slice(size_t debut, size_t nombre, size_t pas);

    // Accesseurs :
    size_t start() const;
    size_t size() const;
    size_t stride() const;
};

La classe gslice est en revanche un peu plus difficile d'emploi puisqu'il faut donner le nombre de valeurs et le pas pour chaque variable de contrôle. Le constructeur utilisé prend donc en deuxième et troisième paramètres non plus deux valeurs de type size_t, mais deux valarray de size_t. La déclaration de la classe gslice est donc la suivante :

class gslice
{
public:
    gslice();
    gslice(size_t debut,
        const valarray<size_t> nombres,
        const valarray<size_t> pas);

    // Accesseurs :
    size_t start() const;
    valarray<size_t> size() const;
    valarray<size_t> stride() const;
};

Les deux valarray déterminant le nombre de valeurs des variables de contrôle et leurs pas doivent bien entendu avoir la même taille. L'ordre dans lequel les indices des éléments sélectionnés sont générés par la classe gslice est celui obtenu en faisant varier en premier les dernières variables caractérisées par les valarray fournis lors de sa construction. Par exemple, une classe gslice utilisant trois variables prenant respectivement 2, 3 et 5 valeurs et variant respectivement par pas de 3, 1 et 2 unités, en partant de l'indice 2, générera les indices suivants :

2, 4, 6, 8, 10,
3, 5, 7, 9, 11,
4, 6, 8, 10, 12,

5, 7, 9, 11, 13,
6, 8, 10, 12, 14,
7, 9, 11, 13, 15
La variable prenant cinq valeurs et variant de deux en deux est donc celle qui évolue le plus vite.

Comme vous pouvez le constater avec l'exemple précédent, un même indice peut apparaître plusieurs fois dans la série définie par une classe gslice. La librairie standard C++ n'effectue aucun contrôle à ce niveau : il est donc du ressort du programmeur de bien faire attention à ce qu'il fait lorsqu'il manipule des jeux d'indices dégénérés.

Comme pour les autres techniques de sélection, la sélection d'éléments d'un valarray non constant par l'intermédiaire des classes slice et gslice retourne une instance d'une classe particulière permettant de prendre en charge les opérations de modification des éléments ainsi sélectionnés. Pour les sélections simples réalisées avec la classe slice, l'objet retourné est de type slice_array. Pour les sélections réalisées avec la classe gslice, le type utilisé est le type gslice_array.

14.3.2.2.4. Opérations réalisables sur les sélections multiples

Comme on l'a vu dans les sections précédentes, les sélections multiples réalisées sur des objets non constants retournent des instances des classes utilitaires mask_array, indexed_array, slice_array et gslice_array. Ces classes référencent les éléments ainsi sélectionnés dans le valarray source, permettant ainsi de les manipuler en groupe. Cependant, ce ne sont pas des valarray complets et, en fait, ils ne doivent être utilisés, de manière générale, que pour effectuer une opération d'affectation sur les éléments sélectionnés. Ces classes utilisent donc une interface restreinte de celle de la classe valarray, qui n'accepte que les opérateurs d'affectation sur les éléments qu'elles représentent.

Par exemple, la classe mask_array est déclarée comme suit dans l'en-tête valarray :

template <class T>
class mask_array
{
public:
    typedef T value_type;
    ~mask_array();

    // Opérateurs d'affectation et d'affectation composées :
    void operator=(const valarray<T> &) const;
    void operator*=(const valarray<T> &) const;
    void operator/=(const valarray<T> &) const;
    void operator%=(const valarray<T> &) const;
    void operator+=(const valarray<T> &) const;
    void operator-=(const valarray<T> &) const;
    void operator^=(const valarray<T> &) const;
    void operator&=(const valarray<T> &) const;
    void operator|=(const valarray<T> &) const;
    void operator<<=(const valarray<T> &) const;
    void operator>>=(const valarray<T> &) const;
    void operator=(const T &valeur);
};

Tous ces opérateurs permettent d'affecter aux éléments de la sélection représentés par cette classe les valeurs spécifiées par leur paramètre. En général, ces valeurs doivent être fournies sous la forme d'un valarray, mais il existe également une surcharge de l'opérateur d'affectation permettant de leur affecter à tous une même valeur.

Note : Les sélections réalisées sur les valarray constants ne permettent bien entendu pas de modifier leurs éléments. Les objets retournés par l'opérateur [] lors des sélections multiples sur ces objets sont donc des valarray classiques contenant une copie des valeurs des éléments sélectionnés.

14.3.3. Les champs de bits

De tous les types de données qu'un programme peut avoir besoin de stocker, les booléens sont certainement l'un des plus importants. En effet, les programmes doivent souvent représenter des propriétés qui sont soit vraies, soit fausses. Après tout, la base du traitement de l'information telle qu'il est réalisé par les ordinateurs est le bit, ou chiffre binaire...

Il existe plusieurs manières de stocker des booléens dans un programme. La technique la plus simple est bien entendu d'utiliser le type C++ natif bool, qui ne peut prendre que les valeurs true et false. Les programmes plus vieux utilisaient généralement des entiers et des constantes prédéfinies ou encore une énumération. Malheureusement, toutes ces techniques souffrent du gros inconvénient que chaque information est stockée dans le type sous-jacent au type utilisé pour représenter les booléens et, dans la plupart des cas, ce type est un entier. Cela signifie que pour stocker un bit, il faut réserver un mot mémoire complet. Même en tenant compte du fait que la plupart des compilateurs C++ stockent les variables de type bool dans de simples octets, la déperdition reste dans un facteur 8. Bien entendu, cela n'est pas grave si l'on n'a que quelques bits à stocker, mais si le programme doit manipuler un grand nombre d'informations booléennes, cette technique est à proscrire.

Nous avons vu dans la Section 3.1.4 qu'il est possible de définir des champs de bits en attribuant un nombre de bits fixe à plusieurs identificateurs de type entier. Cette solution peut permettre d'économiser de la mémoire, mais reste malgré tout relativement limitée si un grand nombre de bits doit être manipulé. Afin de résoudre ce problème, la librairie standard C++ fournit la classe template bitset qui, comme son nom l'indique, encapsule des champs de bits de tailles arbitraires. Le paramètre template est de type size_t et indique le nombre de bits que le champ de bits encapsulé contient.

Note : Vous noterez que cela impose de connaître à la compilation la taille du champ de bits. Cela est regrettable et limite sérieusement l'intérêt de cette classe. Si vous devez manipuler des champs de bits de taille dynamique, vous devrez écrire vous-même une classe d'encapsulation dynamique des champs de bits.

La classe bitset est déclarée comme suit dans l'en-tête bitset :

template <size_t N>
class bitset
{
public:
    class reference;    // Classe permettant de manipuler les bits.

    // Les constructeurs :
    bitset();
    bitset(unsigned long val);
    template<class charT, class traits, class Allocator>
    explicit bitset(
        const basic_string<charT, traits, Allocator> &chaine,
        typename basic_string<charT, traits, Allocator>::size_type debut = 0,
        typename basic_string<charT, traits, Allocator>::size_type taille =
            basic_string<charT, traits, Allocator>::npos);

    // Les fonctions de conversion :
    unsigned long to_ulong() const;
    template <class charT, class traits, class Allocator>
        basic_string<charT, traits, Allocator> to_string() const;

    // Les opérateurs de manipulation :
    bitset<N> &operator&=(const bitset<N> &);
    bitset<N> &operator|=(const bitset<N> &);
    bitset<N> &operator^=(const bitset<N> &);
    bitset<N> &operator<<=(size_t pos);
    bitset<N> &operator>>=(size_t pos);
    bitset<N> operator<<(size_t pos) const;
    bitset<N> operator>>(size_t pos) const;
    bitset<N>  operator~() const;
    bitset<N> &set();
    bitset<N> &set(size_t pos, bool val = true);
    bitset<N> &reset();
    bitset<N> &reset(size_t pos);
    bitset<N> &flip();
    bitset<N> &flip(size_t pos);
    bool test(size_t pos) const;
    reference operator[](size_t pos);   // for b[i];

    // Les opérateurs de comparaison :
    bool operator==(const bitset<N> &rhs) const;
    bool operator!=(const bitset<N> &rhs) const;

    // Les fonctions de test :
    size_t count() const;
    size_t size() const;
    bool any() const;
    bool none() const;
};

La construction d'un champ de bits nécessite de connaître le nombre de bits que ce champ doit contenir afin d'instancier la classe template bitset. Les différents constructeurs permettent d'initialiser le champ de bits en affectant la valeur nulle à tous ses bits ou en les initialisant en fonction des paramètres du constructeur. Le deuxième constructeur affectera aux premiers bits du champ de bits les bits correspondant de l'entier de type unsigned long fourni en paramètre, et initialisera les autres bits du champ de bits à la valeur 0 si celui-ci contient plus de bits qu'un unsigned long. Le troisième constructeur initialise le champ de bits à partir de sa représentation sous forme de chaîne de caractères ne contenant que des '0' ou des '1'. Cette représentation doit être stockée dans la basic_string fournie en premier paramètre, à partir de la position debut et sur une longueur de taille caractères. Cette taille peut être inférieure à la taille du champ de bits. Dans ce cas, le constructeur considérera que les bits de poids fort sont tous nuls et initialisera les premiers bits du champ avec les valeurs lues dans la chaîne. Notez bien que les premiers caractères de la chaîne de caractères représentent les bits de poids fort, cette chaîne est donc parcourue en sens inverse lors de l'initialisation. Ce constructeur est susceptible de lancer une exception out_of_range si le paramètre debut est supérieur à la taille de la chaîne ou une exception invalid_argument si l'un des caractères utilisés est différent des caractères '0' ou '1'.

Comme vous pouvez le constater d'après la déclaration, la classe bitset fournit également des méthodes permettant d'effectuer les conversions inverses de celles effectuées par les constructeurs. La méthode to_ulong renvoie donc un entier de type unsigned long correspondant à la valeur des premiers bits du champ de bits, et la méthode template to_string renvoie une chaîne de caractères contenant la représentation du champ de bits sous la forme d'une suite de caractères '0' et '1'. La classe bitset fournit également des surcharges des opérateurs operator<< et operator>> pour les flux d'entrée / sortie de la librairie standard.

Les opérateurs de manipulation des champs de bits ne posent pas de problème particulier puisqu'ils ont la même sémantique que les opérateurs standards du langage, à ceci près qu'ils travaillent sur l'ensemble des bits du champ en même temps. Le seul opérateur qui demande quelques explications est l'opérateur d'accès unitaire aux bits du champ, à savoir l'opérateur operator[]. En effet, cet opérateur ne peut pas retourner une référence sur le bit désigné par son argument puisqu'il n'y a pas de type pour représenter les bits en C++. Par conséquent, la valeur retournée est en réalité une instance de la sous-classe reference de la classe bitset. Cette sous-classe encapsule l'accès individuel aux bits d'un champ de bits et permet de les utiliser exactement comme un booléen. En particulier, il est possible de faire des tests directement sur cette valeur ainsi que de lui affectuer une valeur booléenne. Enfin, la sous-classe reference dispose d'une méthode flip dont le rôle est d'inverser la valeur du bit auquel l'objet reference donne accès.

La classe template bitset dispose également de méthodes spécifiques permettant de manipuler les bits sans avoir recours à l'opérateur operator[]. Il s'agit des méthodes test, set, reset et flip. La première méthode permet de récupérer la valeur courante d'un des bits du champ de bits. Elle prend en paramètre le numéro de ce bit et renvoie un booléen valant true si le bit est à 1 et false sinon. La méthode set permet de réinitialiser le champ de bits complet en positionnant tous ses bits à 1 ou de fixer manuellement la valeur d'un bit particulier. La troisième méthode permet de réinitialiser le champ de bits en annulant tous ses bits ou d'annuler un bit spécifique. Enfin, la méthode flip permet d'inverser la valeur de tous les bits du champ ou d'inverser la valeur d'un bit spécifique. Les surcharges des méthodes qui travaillent sur un seul bit prennent toutes en premier paramètre la position du bit dans le champ de bits.

Enfin, la classe bitset fournit quelques méthodes permettant d'effectuer des tests sur les champs de bits. Outre les opérateurs de comparaison classiques, elle fournit les méthodes count, size, any et none. La méthode count renvoie le nombre de bits positionnés à 1 dans le champ de bits. La méthode size renvoie quant à elle la taille du champ de bits, c'est-à-dire la valeur du paramètre template utilisée pour instancier la classe bitset. Enfin, les méthodes any et none renvoient true si un bit au moins du champ de bits est positionné ou s'ils sont tous nuls.