Cet article est d'abord et avant tout un divertissement, un exercice de style.
Si vous trouvez l'article intéressant, vous voudrez peut-être examiner la classe standard std::bitset qui est une proche cousine (pas la même chose, mais des techniques semblables et une similitude d'effet) de la classe entier explorée ici, de même que le mal nommé mais très utile std::vector<bool>. Ce sont des outils de calibre industriel qui permettent d'atteindre des résultats connexes.
Parfois, je suis fatigué de corriger ou d'écrire des documents pour mes cours. Il arrive que je m'arrête pour dessiner ou pour lire quelque chose de différent. À d'autres moments, j'attaque de petits (!) dossiers pas simples dont je n'ai jamais vraiment le temps de m'occuper et qui me travaillent juste là, derrière les oreilles.
Ce qui suit est le fruit d'une telle étude de dossier. Je me suis mis en tête d'écrire une classe entier, construite sur un int, mais rédigée sous forme plutôt générique ce qui en faciliterait l'adaptation à d'autres types et, si on se donnait la peine d'y ajouter quelques traits, à des nombres entiers arbitrairement grands. Je suis même tenté de faire quelque chose de semblable avec les nombres à virgule flottante (question de temps).
Mon objectif était :
Sans pouvoir garantir que le dossier est clos, je pense qu'il est suffisamment avancé pour qu'il soit intéressant de jeter un coup d'oeil au résultat et pour étudier àla fois les aléas de cette entreprise et les techniques requises pour arriver à un résultat raisonnable.
En plus d'être joli comme problème, c'est pas simple du tout à réaliser. Nous verrons pourquoi sous peu. Procédons.
Une sage approche au développement est de réfléchir au préalable à l'usage qui sera fait de nos objets, en particulier aux tests qui devront être réalisés pour les valider.
Un programme comme celui visible à droite devra absolument fonctionner. Il est raisonnable d'avoir certaines attentes face à ce programme :
|
|
Notez la différence entre entier<int> e0; (où le substrat int est explicité) et entier e2 = 25; (où le substrat int est sous-entendu). Je profite ici de CTAD pour déduire implixitement la part générique du type entier lorsque cela s'avère possible, dans le but d'alléger l'écriture. Ce mécanisme n'existe que depuis C++ 17, alors si vous utilisez un compilateur plus ancien, il vous faudra expliciter <int> dans les trois cas.
Je permets au code client de spécifier le substrat du type entier<T> pour permettre d'opérer sur les bits de n'importe quel type entier.
|
Un programme comme celui visible à droite devra aussi fonctionner. Pour nos fins, e.valeur() retournera la valeur entière de e, dont le type correspondra à celui de la représentation interne utilisée dans e. Puisque nous voulons pouvoir accéder, au besoin, directement à un bit d'un entier, nous concevrons que l'opération e[1] = 1; allumera (au sens de déposera la valeur 1 dans) le bit à la position 1 de e (ce qui fera passer sa valeur de 25 à 27 puisque sur le plan binaire, sa représentation passera de ...0011001 à ...0011011). Pour nos fins toujours, l'affichage de e devra projeter à la sortie standard (à l'écran console) la représentation binaire de e, allant du bit le plus significatif au bit le moins significatif lorsque lu de gauche à droite, alors que l'affichage de e.valeur() devra afficher la valeur 27. Notez que l'affichage bit a bit d'un entier comme e lorsqu'on le projette sur un flux de sortie est un choix arbitraire et discutable mais qui me permettra de montrer comment il est possible d'utiliser des itérateurs sur les bits d'un entier, mon objectif premier dans cet exercice. |
|
En fait, les deux programmes ci-dessous devraient offrir essentiellement le même affichage. J'indique essentiellement ici car, pour des raisons de lisibilité, la partie de gauche groupera les bits quatre par quatre :
|
|
Ceci signifie que projeter e sur un flux de sortie devrait équivaloir à projeter chacun de ses bits, du dernier au premier (par souci de lisibilité), sur ce flux en séparant chacun par un espace. La présomption faite ici est que le premier bit est le moins significatif et que le dernier bit est le plus significatif, ce qui est l'inverse de l'ordre normal de lecture. On pourrait critiquer ce choix et réécrire la classe entier de manière à ce que la situation soit inversée.
Si vous trouvez ce code trop compact et opaque, alors la version ci-dessous (plus longue, plus lente et plus lourde) vous semblera peut-être plus lisible. Elle devrait fonctionner tout autant que les précédentes :
#include "entier.h"
#include <iostream>
int main() {
using std::cout;
entier e = 25;
for (auto it = rbegin(e); it != rend(e); ++it)
cout << *it << ' ';
}J'écris « équivalent moral » car il est impossible d'adresser un bit directement en C++. Cela signifie que nous devrons tricher un peu... et qu'il y aura des conséquences!
Ici, rbegin(e) et rend(e) retournent un entier::reverse_iterator. Ce type sera un « itérateur sur les bits » d'un entier.
L'térateur retourné par la méthode rbegin(e) est l'équivalent moral d'un pointeur sur le dernier bit valide de e alors que l'itérateur retourné par la méthode rend(e) est l'équivalent moral d'un pointeur situé (conceptuellement) juste avant le premier bit valide de e.
On devrait évidemment aussi pouvoir utiliser begin(e) et end(e) mais cela ne sied pas à l'ordre usuel de lecture chez les occidentaux.
On voudra qu'un programme comme celui ci-dessous fonctionne aussi, ce qui constitue un test plus sérieux :
#include "entier.h"
#include <iostream>
#include <algorithm>
int main() {
using namespace std;
entier e = 25; // 0000 0000 0001 1001
e[1] = 1; // 0000 0000 0001 1011
cout << e << endl << e.valeur() << endl;
reverse(begin(e), end(e)); // 1101 1000 0000 0000
cout << e << endl << e.valeur() << endl;
reverse(begin(e), end(e)); // 0000 0000 0001 1011
cout << e << endl << e.valeur() << endl;
}La complexité de ce test tient au fait qu'on exposera e en tant que conteneur standard à un algorithme susceptible d'en exploiter pleinement les facilités. En effet, std::reverse(a,b) inverse l'ordre d'apparition des éléments situés dans l'intervalle d'éléments dans la déterminée par les itérateurs du conteneur en question; ici, nous souhaitons inverser des bits, pas des bytes.
L'affichage de e entre les deux inversions devrait montrer les bits en ordre inverse de leur ordre original (du moins significatif au plus significatif lorsque lu de gauche à droite).
Présumant que la représentation interne soit un int, donc un entier signé, la valeur affichée suite à l'application de l'algorithme d'inversion des éléments devrait être négative puisque le nombre original (27, soit 25 auquel le bit 1, de valeur 2 en base 10, a été allumé) devrait être négative puisque le nombre original était impair, donc le bit le moins significatif était allumé, ce qui implique que le bit le plus à gauche suite à l'inversion sera allumé et que le nombre résultant sera négatif.
Enfin, on voudra qu'un programme comme celui-ci fonctionne :
#include "entier.h"
#include <iostream
#include <fstream>
int main()
{
using namespace std;
entier e = 25;
e[1] = 1;
cout << e << endl << e.valeur() << endl;
{
ofstream{"test.txt"} << e;
}
{
entier x;
if (ifstream{"test.txt"} >> x)
cout << x << endl;
}
}Sérialiser e, donc projeter une représentation de e sur un flux de sortie sur un fichier (nommé "test.txt") puis extraire un entier de la représentation tirée de ce même fichier devrait donner, de manière visible et reconnaissable, le même entier (lire : un entier de même valeur) avant la sérialisation et après la désérialisation.
Avant de lire le reste de ce document, qui paraîtra somme toute assez dense aux non initiés, je vous recommande de consulter les articles suivants et de vous familiariser avec le contenu de chacun, au moins pour saisir l'idée qui se cache derrière et pour avoir une intuition de la motivation derrière les concepts et techniques qui y sont exposés.
Chacune de ces thématiques sera mise en application plus loin dans ce document :
Le code tout entier suit et peut être lu de haut en bas. Les commentaires ont été supprimés des sources par souci d'économie d'espace mais ils ont été remplacés par des annotations à la gauche du code. Vous pouvez télécharger ici un projet Visual Studio .NET 2008 contenant les sources originales et commentées.
Dans le but de réduire la redondance, surtout dans l'implémentation des opérateurs relationnels et logiques, plusieurs des types définis plus loin exploiteront l'idiome CRTP et injecteront sur eux-mêmes des versions standardisées de ces opérateurs (par exemple, il est banal d'exprimer != à partir de == et de la négation logique pour un type au comportement conforme à celui des types artihmétiques usuels, ce que nous souhaitons ici comme comportement de toute manière).
|
La technique est relativement simple et rejoint celle détaillée dans l'article qui en discute plus en détail. Ici, une classe T se déclarant dérivée (privée, pourquoi pas?) de relation::equivalence<T> fait en sorte d'injecter l'opérateur != sur elle-même, dans la mesure où il existe un opérateur == conforme aux usages de l'arithmétique usuelle et applicable à lui-même. Remarquez qu'une telle classe s'injecte aussi un nombre arbitrairement grand d'opérateurs != définis sur elle et d'autres types (de manière symétrique; ceci présume un == commutatif) dans la mesure où les opérateurs == équivalents existent. La relation d'ordonnancement génère les opérateurs >, <= et >= à partir de l'opérateur <. Les groupes de relations logique et bit_a_bit sont plus subtils. Tout d'abord, il y a des risques très sérieux à implémenter une surcharge des opérateurs && et || du fait que ces surcharges sont des méthodes « normales », qui ne respecteront pas les raccourcis des opérateurs logiques usuels, comme l'a entre autres fait remarquer Scott Meyers. Par exemple, en temps normal, l'expression a && b n'évaluera b que si a est vrai, ce qui est fortement utilisé pour valider des pointeurs avant d'accéder à ce vers quoi ils pointent; si && est surchargé dans ce cas, a et b seront tous deux évalués, quoiqu'il arrive. Dans le cas de nos classes quasi arithmétiques, j'ai choisi de les implémenter, mais il demeure que ce choix est contestable. Dans un ordre d'idées semblables, j'ai implémenté les déclinaisons inverses des opérateurs bit à bit binaires (à deux opérandes) pour alléger l'écriture des classes elles-mêmes. J'ai choisi ici de spécifier un type de retour qui, par défaut, serait int mais pourrait être autre chose; ce choix est, si je ne m'abuse, une divergence du standard qui retourne des int, mais je n'ai pas près de moi les références nécessaires pour valider cette présomption. Si le type int est imposé par le standard pour les opérateurs bit à bit, alors le correctif requis aura le mérite d'être localisé. Une stratégie de métaprogrammation déduisant le bon type à retourner à partir du type des opérandes serait probablement la chose à faire ici, de toute manière (avis aux gens qui veulent s'amuser). |
relations.h |
|
|
Les bibliothèques qui seront incluses dans entier.h seront :
S'ajoutera à celles-ci la bibliothèque relations.h, décrite plus haut, qui permet d'appliquer CRTP pour la définition de quelques relations logiques utiles et l'allégement du code qui suit en général (le code en question étant volumineux, nous apprécierons toutes et tous ces quelques simplifications). |
|
class entier
: relation::equivalence<entier>,
relation::ordonnancement<entier>
{
public:
using elem_type = int;
using size_type = short;
static constexpr size_type nbits = sizeof(elem_type)*CHAR_BIT;
class DivisionParZero {};
class Debordement {};
class HorsBornes {};La directive servant à réactiver cet avertissement (la moindre des choses dans un programme est de laisser le système dans un état normal) apparaît plus loin.
Notre classe entier commence par l'annonce de certaines données de compilation importantes et publiques :
Notez l'emploi d'une constante en minuscule, ce qui diffère de l'usage enseigné en classe mais se rapproche de ceux utilisés dans les bibliothèques standards. Ne faites pas ça à la maison!
private:
elem_type valeur_;Dans une section privée, on trouvera la valeur de la représentation interne de l'entier (valeur_). Si j'avais choisi d'avoir recours à un mutateur de premier ordre (par exemple, une méthode Setvaleur()), je l'aurais aussi déclaré ici, pour qu'il soit privé et qu'il ne fasse pas partie de la barrière d'abstraction offerte par entier pour que le code client puisse transiger avec lui.
En vieillissant, cela dit, j'utilise de moins en moins de mutateurs, préférant utiliser l'opérateur d'affectation si possible. Dans le cas de la classe entier, la gamme d'opérateurs susceptibles de muter valeur_ est importante (+=, -=, ++ et compagnie), mais il n'était pas clair à l'usage que le recours à un mutateur pour centraliser le déverminage allégeait vraiment le travail. J'ai fini par m'en débarrasser.
Le langage C++ ne nous permet pas d'accéder directement à un bit à travers une variable ou une constante. Pour consulter ou modifier un bit, il est nécessaire d'accéder au moins à l'octet auquel il appartient puis d'y appliquer des opérations bit à bit.
Ceci complique fortement l'atteinte de l'objectif que nous nous sommes fixés qui est d'utiliser un entier comme une séquence de bits et de permettre de s'en servir à l'aide d'algorithmes standards. Nous devons donc construire l'idée d'un bit (aussi proche que possible, du moins) à l'aide d'une classe qui nous servira d'intermédiaire entre l'idée de bit et le bit effectif, tout en faisant en sorte que l'accès à un bit à travers cette classe soit à la fois rapide et peu coûteux en terme d'espace.
Dans notre cas, l'abstraction décrivant un bit se nommera BaseBit et sera un type générique appliqué au type de la valeur servant de représentation interne pour un entier. BaseBit est ce qu'on nomme un Proxy Object, et sera à la fois nécessaire et problématique pour nous (voir la remarque plus bas sur vector<bool>, une erreur historique qui repose sur cette technique).
public:
template <class T>
class BaseBit
: relation::equivalence<BaseBit<T>>,
relation::logique<BaseBit<T>>,
relation::bit_a_bit<BaseBit<T>>
{
mutable T *pvaleur; // donnée partagée...
size_type bitpos;
using basemodifop = void (BaseBit::*)();
void allumer()
{ *pvaleur |= (1 << bitpos); }
void eteindre()
{ *pvaleur &= (~(1 << bitpos)); }
bool est_allume() const
{ return (*pvaleur & (1 << bitpos)) != 0; }
bool est_eteint() const
{ return !est_allume(); }Suit ensuite la classe interne et publique BaseBit, un modèle (template) applicable à une représentation interne donnée. Nous la déclinerons plus loin en deux saveurs, soit une constante et l'autre modifiable. Notez qu'elle implémentera quelques relations à partir de l'idiome CRTP décliné dans relations.h, plus haut.
Le recours à un BaseBit générique peut sembler discutable mais, en pratique, cela simplifiera la programmation. Au lieu de rédiger deux représentations du concept de bit, soit une immutable et l'autre dont les instances sont modifiables, nous laisserons le compilateur gérer les tentatives de modification sur une représentation interne pour laquelle ces opérations sont illégales.
Un premier groupe de membres privés contiendra en premier lieu la représentation interne d'un bit, soit un pointeur sur la représentation d'un entier (donc soit un un elem_type*, soit un const elem_type*, selon le type T appliqué à l'instanciation du template BaseBit).Ceci est philosophique : les bits se veulent transitoires et doivent permettre de modifier le bit réel correspondant dans l'entier original.
Deux mutateurs primitifs (allumer() et eteindre()) sont offerts pour usage interne, et il en va de même pour deux accesseurs primitifs (est_allume() et est_eteint()). Pour le code client, de nombreuses opérations plus sophistiquées sont disponibles. Si le type est utilisé massivement, ce sont ces opérations qu'on voudra tester et optimiser au maximum.
Notez le type privé basemodifop. Sa signature est étrange, mais signifie pointeur sur une méthode d'instance de type void dans BaseBit et ne prenant pas de paramètres. Ce type est pour usage interne seulement et permettra une petite optimisation lors de certaines tentatives de modification de l'état d'un bit, plus loin – il sera important pour nous que l'accès à un bit soit très rapide.
Notez aussi le caractère mutable du pointeur pvaleur_. L'idée est que nous souhaitons permettre la définition d'opérations copiant un BaseBit (par exemple, le constructeur de copie) dans toutefois nous limiter à des BaseBit constants. Évidemment, la prudence sera de mise, puisque du code malsain pourrait mener à des effets secondaires compliquant l'analyse du code (pas plus que du code malsain partageant manuellement un entier, cependant).
// ...
public:
BaseBit(T *pvaleur, size_type bitpos)
: pvaleur{pvaleur}, bitpos{bitpos}
{
}Un seul constructeur sera offert, soit un constructeur paramétrique, informé de la donnée à laquelle il réfère et à la position du bit qu'il représente (il aurait pu être utile de lever une exception dans le cas où pValeur==0; à vous de juger).
Le destructeur et le constructeur de copie générés automatiquement par le compilateur nous suffiront amplement. Un BaseBit ne sera pas responsable de la gestion des données qui lui sont confiées et n'aura pas à gérer leur portée. Nous implémenterons par contre un certain nombre d'opérateurs d'affectation, pour permettre entre autres d'affecter un bool ou un int à un BaseBit.
Notez le choix d'utiliser un pointeur plutôt qu'une référence pour mener vers la valeur originale n'est pas accidentel : ce choix permet, au besoin, d'implémenter l'affectation d'un BaseBit à un autre BaseBit de manière à permettre de référer à un nouveau bit (une référence, une fois construite et liée au référé, ne peut plus pointer ailleurs).
// ...
private:
void set_bit_val(bool b)
{
static const basemodifop Op[] =
{
&BaseBit::eteindre, &BaseBit::allumer
};
(this->*Op[b])();
}
public:
BaseBit& operator=(bool b)
{
set_bit_val(b);
return *this;
}
BaseBit& operator=(int val)
{
set_bit_val(val!=0);
return *this;
}
BaseBit& operator=(const BaseBit &bb)
{
set_bit_val(bb);
return *this;
}L'affectation sur un BaseBit représente la capacité d'affecter une valeur à un bit d'un entier. L'implémentation proposée ici repose sur une délégation à travers un tableau constant de pointeurs de méthodes d'instances non polymorphiques, généré à la compilation. Un compilateur de qualité devrait pouvoir optimiser les appels (sinon, des alternatives – if – sont une option).
Trois déclinaisons sont offertes, par souci d'efficacité (car, rappelons-le, quiconque voudra utiliser un objet représentant une séquence de bits dans un entier sera préoccupé à la fois par le caractère compact de la représentation et par la vitese des opérations que cet objet met à la disposition du code client) :
Remarquez l'utilisation d'un tableau constant de pointeurs de méthodes (à l'aide du type interne et privé nommé basemodifop), ce qui permet d'invoquer une méthode sans utiliser d'alternative ce qui peut économiser un évidage du pipeline dans le processeur et accélérer l'exécution du programme.
Pour mieux comprendre cette stratégie, je vous invite à consulter cet article portant sur les tableaux de pointeurs de méthodes d'instances qui cherche à décrire cette stratégie d'optimisation par et pour elle-même.
La stratégie appliquée ici et consistant à offrir des méthodes pour manipuler et comparer un BaseBit avec un bool et avec un int sera respectée pour l'ensemble des méthodes et des opérateurs conventionnels de cette classe. Notez que != est obtenu par CRTP et n'est donc pas explicitement défini ici. L'opérateur de conversion en bool, plus bas, aurait aussi pu être utilisé implicitement.
// ...
bool operator==(const BaseBit &b) const
{ return est_allume() == b.est_allume(); }
bool operator==(bool b) const
{ return est_allume() == b; }
bool operator==(int val) const
{ return est_allume() == (val != 0); }Les opérateurs relationnels devraient aller de soi.
Remarquez le soin pris à comparer les int avec 0 plutôt qu'avec 1. Cela peut sembler étranger aux gens moins habitués de travailler avec des entiers pris au sens de booléens et mérite donc qu'on s'y attarde quelques instants.
Le langage C dans ses acceptions classiques n'offrait pas de type booléen à proprement dit, même si plusieurs le définissaient à l'aide de macros (#define bool int par exemple) ou à l'aide d'alias (typedef int bool; étant une forme fréquemment rencontrée). La tradition veut que 0 soit faux et que toute valeur non nulle soit vraie au sens des évaluaitons booléennes. Cette approche fut maintes fois décriée, mais le fait reste que dans la pratique cela fonctionne assez bien et permet l'écriture de code plutôt élégant.
Cela implique toutefois que sur le plan logique, il y a une seule valeur fausse et une multitude de valeurs vraies. La question de savoir comment définir le concept de vrai s'est vue offrir plusieurs réponses, souvent intéressantes, et typiquement sous forme de macros :
Notez dans chaque cas que le sens de faux est fixé alors que le sens de vrai varie, et n'est de toute manière que convention puisque plusieurs valeurs distinctes de véracité dans chacune des acceptions proposées ici restent vraies au sens du langage, et puisque deux sous-programmes liés ensembles peuvent avoir une vision distincte de l'implémentaiton de ce concept.
// ...
bool operator && (const BaseBit &b) const
{ return est_allume() && b.est_allume(); }
friend bool operator && (const BaseBit &b0, bool b1)
{ return b0.est_allume() && b1; }
friend bool operator && (const BaseBit &b, int val)
{ return b0.est_allume() && val != 0; }
bool operator || (const BaseBit &b) const
{ return est_allume() || b.est_allume (); }
friend bool operator || (const BaseBit &b0, bool b1)
{ return b0.est_allume() || b1; }
friend bool operator || (const BaseBit &b, int val)
{ return b0.est_allume() || val != 0; }
bool operator!() const
{ return est_eteint(); }Clairement, tester si un entier est vrai est périlleux alors que tester s'il est faux est sécuritaire. Sachant cela, on comprendra que comparer les booléens avec le littéral pour faux respecte l'usage sécuritaire des héritiers du langage C où il y a un seul faux (0) mais des tas de vrai. Cela reste une saine stratégie même si la constante littérale true en C++ vaut bien 1 sur le plan entier.
Revenant à notre classe BaseBit, notons que tous ces opérateurs relationnels qui y sont exposés sont constants au sens où ils ne modifient pas l'opérande de gauche. Ils sont définis comme fonctions globales, pour que BaseBit puisse aussi servir d'opérande de droite, et profitent de la commutativité résultant de l'injection par CRTP des relations logiques.
Il devrait en être de même pour les opérateurs logiques, que ce soit la conjonction, la disjonction ou la négation. Il est hautement probable que la définition de ces divers opérateurs vous semble évidente.
Les remarques applicables aux opérateurs relationnels, plus haut, sont valides ici aussi. Notez aussi les avertissements quant aux risques inhérents à la surcharge des opérateurs logiques, mentionnés précédemment.
|
Les opérations bit à bit sont aussi simples, ressemblant beaucoup aux opérations logiques proposées plus haut (quand on manipule un bit, la logique et le bit à bit se confondent). L'idiome CRTP est ici encore mis à profit de manière à déduire les versions des opérateurs bit à bit que sont &, | et ^ auxquelles la commutativité se serait appliquée dans le code client. La subtilité ici est, tel qu'annoncé plus haut, le type de retour des divers opérandes. J'ai utilisé T, le type d'une représentation interne, mais il est possible que int soit un meilleur choix. Les seules valeurs admissibles pour un bit étant 0 et 1, de toute manière, il probable qu'un simple bool aurait fait l'affaire dans la majorité des cas. |
|
|
Il y a cependant un hic important: ces opérations provoquent un bris de symétrie. La valeur retournée par chaque opérateur correspond à la valeur représentée par le bit suite à l'opération, mais pas au bit lui-même. C'est là l'une des premières difficultés conceptuelles auxquelles nous ferons face, et qui rendra notre tâche difficile : C++ ne permet pas de représenter un bit en tant que bit. La plus petite entité adressable de manière naturelle en C++ est le byte. À ce sujet, je vous invite à lire sure le type std::vector<bool> de C++, qui se veut une représentation économique en espace d'une séquence de bits (donc un cousin conceptuel de la classe entier sur laquelle le présent article pose son regard). Le plus gros défaut de std::vector<bool> est que l'itérateur permettant d'en parcourir les éléments ne permet pas un véritabel accès symétrique aux éléments, utilisant (comme nous le faisons ici) une représentation intermédiaire (schéma de conception Proxy) plutôt que les bits représentant (individuellement) les booléens de la séquence. Plusieurs textes ont été rédigés pour relever les failles conceptuelles de l'approche appliquée dans le cas de std::vector<bool>. Je vous invite à lire cet article-ci, ou encore cet autre article , les deux remontant à 1999, pour en savoir plus sur le sujet. En plus de discuter des failles de cette spécialisation du concept de vecteur, ces textes mettent en relief plusieurs points pertinents à notre démarche. |
|
Notre entreprise, qui vise à permettre de manipuler un bit en tant que concept, nous force à passer par un objet intermédiaire et à faire certains compromis, parmi lesquels on trouve entre autres l'acceptation d'un bris de symétrie.
Ce problème, encore mineur à ce stade-ci, nous causera quelques maux de tête lorsque nous chercherons à déterminer un itérateur conforme sur une séquence de bits.
/ ...
operator bool() const
{ return est_allume(); }Les opérations bit à bit modifiant l'instance active entraînent moins de bris de symétrie du fait que l'acteur se retourne lui-même tel qu'il est devenu suite à l'opération.
Il peut être utile de pouvoir traiter implicitement un BaseBit en tant que bool sur une base occasionnelle. Conceptuellement, il s'agit de l'un des usages les plus probables de cette abstraction. Ceci explique la présence dans l'interface publique de cette classe d'un opérateur implicite de conversion en booléen.
// ...
void swap(BaseBit &b)
{
bool etatAutre = b;
const basemodifop Op[] =
{
&BaseBit::eteindre, &BaseBit::allumer
};
(b.*Op[est_allume()])();
(this->*Op[etatAutre])();
}
};Enfin, notons que nous devrons implémenter l'opération d'échange de valeurs (swap()) entre deux BaseBit pour permettre la mise en application de la plupart des algorithmes standards.
Interchanger des valeurs est une opération mathématique extrêmement fondamentale. Le caractère asymétrique d'un BaseBit et de la valeur booléenne qu'il représente empêcherait de véritablement échanger leurs valeurs (le cas de std::reverse(), sur lequel nous reviendrons, est éloquent en ce sens).
Tel qu'indiqué précédemment, la classe BaseBit est exprimée sous forme de template pour faciliter son instanciation à partir d'un entier::elem_type constant ou modifiable. Procéder ainsi réduit la quantité de code à écrire et responsabilise le compilateur pour ce qui est de valider les opérations sur un bit modifiable ou non.
Pour simplifier le propos et alléger la syntaxe, le type entier::Bit sera chargé de représenter un bit d'un entier::elem_type modifiable alors que le type entier::ConstBit sera chargé de représenter un bit d'un entier::elem_type constant. Ces abstractions simples serviront en particulier à déclarer les types d'itérateurs sur un entier.
Pour éviter de déclarer une classe distincte pour chaque catégorie d'itérateur dans notre conteneur, nous allons définir de manière distincte l'idée d'itérateur et l'idée de mouvement vers l'avant ou vers l'arrière (que nous nommerons des bougeurs).
En effet, les itérateurs permettant de faire une séquence avançant ou reculant sont essentiellement identiques, à ceci près que la séquence définie par l'un des types est l'inverse conceptuel de celle éfinie par l'autre type. Après tout, un itérateur détermine une séquence sur un conteneur, mais (les mathématiciens le savent depuis longtemps) plusieurs séquences sont possibles sur les mêmes éléments. Qu'on liste les entiers de 1 à 100 ou de 100 à 1, ce sont les mêmes entiers, et seul l'ordre dans la séquence diffère (les ordinaux sont différents mais les cardinaux ne le sont pas); on pourrait définir une séquence sur les pairs sans pour autant détruire l'idée des nombres impairs.
Mon choix d'implémentation fut donc de séparer les idées de aller vers l'avant (Avanceur) et aller vers l'arrière (Reculeur) en deux classes, que je nommerai bougeurs faute d'un meilleur nom, puis de déterminer un itérateur sur des bits d'un entier à partir d'une combinaison du modèle (template) d'itérateur sur des bits et du concept d'aller dans une direction ou l'autre. Procéder ainsi allège de beaucoup le code.
Vous remarquerez deux hiérarchies en parallèle et en collaboration : celle des traits, qui sont une forme d'autodocumentation à même le code de caractéristiques des classes, et celle des classes elles-mêmes. Il s'agit de caractéristiques fréquemment rencontrées lorsque le code générique et les traits sont utilisés en collaboration.
Cette séparation est strictement d'usage interne. Les classes Avanceur et Reculeur proposées ici sont privées à la classe entier et constituent un outil interne pour simplifier la description des règles permettant aux itérateurs de déterminer le sens de prochain élément comme celui d'élément précédent.
// ...
template <class ElemT, class PosT>
struct BougeurTraits
{
using elem_type = ElemT;
using size_type = PosT;
};
template <class ElemT, class PosT>
struct AvanceurTraits
: BougeurTraits<class ElemT, class PosT>
{
static constexpr size_type PositionDebut = 0;
static constexpr size_type PositionFin = sizeof(elem_type)*CHAR_BIT;
};
template <class ElemT, class PosT>
struct ReculeurTraits
: BougeurTraits<class ElemT, class PosT>
{
static constexpr size_type PositionDebut = sizeof(elem_type)*CHAR_BIT - 1;
static constexpr size_type PositionFin = -1;
};Dans un bougeur, qu'il représente le concept d'avancer ou le concept de reculer, ce qui importe sur le plan des données sont les bornes sur lesquelles il opère. Celles-ci dépendent quant à elles du type de la représentation interne d'un entier et du type utilisé pour représenter la position d'un bit dans la séquence.
Ces caractéristiques sont des traits, et ont été découplés du concept de mouvement en tant que tel. Notez que le recours à l'opérateur sizeof(elem_type) pour certaines positions limite les types susceptibles de servir à titre de elem_type à des types primitifs.
Un parent, BougeurTraits, détermine les types pour les valeurs et les positions, peu importe qu'il s'agisse de traits destinés à des bougeurs vers l'avant ou vers l'arrière. Des enfants, AvanceurTraits et ReculeurTraits, dérivent publiquement de ce parent commun et déterminent les positions aux extrémités d'une séquence vers l'avant ou vers l'arrière. Comme c'est souvent le cas avec les traits, nous obtiendrons ainsi des types et des constantes connues à la compilation, donc du code essentiellement optimal en temps d'exécution et en espace dans le code compilé.
Si le besoin se faisait sentir de construire un entier sur un autre type de représentation interne que int, en particulier sur des classes représentant des nombres et susceptibles de profiter d'un parcours bit à bit, alors il faudrait élargir le concept de position limite en utilisant un template spécialisé sur sizeof() pour les types primitifs (probablement en ayant recours aux traits des types impliqués à l'aide de std::numeric_limits) et sur des mécanismes plus près des représentations internes des données pour les classes.
// ...
template <class PosT, class TraitsT>
struct Deplaceur
{
using offset_type = PosT;
static constexpr offset_type
DEBUT = TraitsT::PositionDebut,
FIN = TraitsT::PositionFin;
};
template <class T, class PosT, class TraitsT = AvanceurTraits<T, PosT>>
struct Avanceur
: Deplaceur<PosT, TraitsT>
{
static void avancer(offset_type &pos)
{
if (++pos > FIN) throw HorsBornes{};
}
static void avancer(offset_type &pos, const size_type n)
{ if (pos += n > FIN) throw HorsBornes{}; }
static void reculer (offset_type &pos)
{ if (--pos < DEBUT) throw HorsBornes{}; }
static void reculer (offset_type &pos, const size_type n)
{ if (pos -= n < DEBUT) throw HorsBornes{}; }
static bool precede(offset_type posA, offset_type posB)
{ return posA < posB; }
static bool est_legal(offset_type pos)
{ return DEBUT <= pos && pos <= FIN; } // tolérance à end()
};
template <class T, class PosT, class TraitsT = ReculeurTraits<T, PosT>>
struct Reculeur
: Deplaceur<PosT, TraitsT>
{
static void avancer(offset_type &pos)
{ if (--pos < FIN) throw HorsBornes{}; }
static void avancer(offset_type &pos, size_type n)
{ if (pos -= n < FIN) throw HorsBornes{}; }
static void reculer(offset_type &pos)
{ if (++pos > DEBUT) throw HorsBornes{}; }
static void reculer(offset_type &pos, size_type n)
{ if (pos += n > DEBUT) throw HorsBornes{}; }
static bool precede(const offset_type posA, const offset_type posB)
{ return posB < posA; }
static bool est_legal(offset_type pos)
{ return DEBUT <= pos && pos <= FIN; } // tolérance à end()
};Tout comme dans le cas des traits de bougeurs, nous aurons une hiérarchie pour les classes de bougeurs, avec un parent (nommé Deplaceur, pour éviter la confusion avec le mot Bougeur plus bas) définissant des types utiles pour tous ses enfants (standardisation on ne peut plus pratique) et des constantes déduites des traits et qui allégeront l'écriture du code des bougeurs en tant que tels.
Un Avanceur représentera les opérations permettant d'avancer dans une séquence de positions bornée par un début et une fin, en allant du début vers la fin. Un Reculeur jouera le même rôle mais définira une progression de la fin vers le début.
Les opérations supportées seront avancer() pour avancer d'une ou de plusieurs positions (deux déclinaisons de cette méthode, variant selon le nombre de paramètres), et leur équivalent (reculer()) pour reculer. J'ai choisi de lever une exception si des débordements des bornes admissibles se produisent; du fait que de telles occurrences ne devraient jamais se produire, la levée (potentielle) d'exceptions devrait se faire à coût nul (ou à peu près nul, selon la qualité des compilateurs).
La relation d'ordre entre deux positions dépendra de la direction du parcours de l'itérateur visé, ce qui explique le prédicat de classe precede().
Une méthode supplémentaire permet de vérifier la légalité d'une position. Notez que FIN est incluse dans les positions valides pour que l'itérateur de fin, bien que pointant vers une position illlégale dans une séquence, soit estimé légal en tant que position. Cette méthode aurait raisonnablement pu faire partie des traits si ce n'eût été du caractère fluide de la relation entre position, début et fin, qui n'est pas nécessairement la même quand on parcourt une séquence du dernier au premier ou du premier au dernier.
Remarquez que toutes les méthodes sont qualifiées static, du fait que les seuls attributs des classes Avanceur et Reculeur sont des constantes de classes.
Remarquez aussi que, pour Avanceur comme pour Reculeur, les méthodes permettant d'avancer ou de reculer une position procèdent à partir de références sur des positions. Cela n'est pas un bris d'encapsulation; personne ne force les clients de ces classes à leur confier leurs positions. Les classes Avanceur et Reculeur sont des outils internes pour simplifier le code, pas des tiers hostiles.
L'idée d'itérateur sur une séquence de bits dépend de la sorte de bit (constant ou non) et du type de mouvement permettant de déterminer la séquence (par en avant ou par en arrière).
Une stratégie par composition aurait été possible mais aurait ici alourdi inutilement le code; la composition est ramenée à un niveau conceptuel à l'aide de traits et de classes modèles.
public:
template <class T, class Bougeur>
class bititt
: relation::equivalence<bititt<T, Bougeur>>,
relation::ordonnancement<bititt<T, Bougeur>>,
public std::iterator<random_access_iterator_tag, T, size_type>
{
public:
using bornes_type = Bougeur;
using elem_wrap_t = T;L'itérateur sur des bits dévoilera ses types publics internes sous les noms suivants :
Remarquez tout de suite que notre choix de suppléer une abstraction représentant une stratégie de progression dans une séquence de bits nous permettra d'écrire un seul type générique d'itérateur, et de le spécialiser par de simples alias (avec typedef) par la suite.
Remarquez aussi que nous appliquons encore une fois l'idiome CRTP pour obtenir != à partir de == et pour obtenir la gamme des relations d'ordonnancement à partir de <, économie d'écriture de code appréciable s'il en est une.
// ...
private:
elem_type *pvaleur;
size_type bitpos;
size_type bit_pos() const noexcept
{ return bitpos; }De manière privée, car cela ne concerne que nous (et la classe bititt elle-même), la valeur ne sera pas un bit mais bien un pointeur vers la valeur de l'entier.
Un bititt connaîtra à la fois l'entier effectif et la position du bit couramment référé; le bit constant ou non (le elem_wrap_t) ne servira que lors d'opérations d'indirection, pour faciliter le travail du code client.
// ...
public:
bititt(elem_type *pvaleur, size_type bitpos)
: pvaleur{pvaleur}, bitpos{bitpos}
{
if (!bornes_type::est_legal(bit_pos()))
throw HorsBornes{};
}Un seul constructeur, paramétrique, sera exposé. La sainte-trinité (constructeur de copie, affectation, destructeur) générée par le compilateur est tout à fait convenable pour un bititt puisqu'il s'agit d'un type valeur, qui n'est pas responsable de gérer la portée de ses attributs. Une copie d'un bititt est un itérateur de bits représentant le même bit du même entier que l'itérateur dont il est une copie.
Construire un bititt avec une position illégale est une opération dangereuse qui ne devrait pas être possible à travers les mécanismes normaux exposés par la classe entier. Remarquez que le bougeur est responsable de valider une position puisque ce qui constitue une position légale dépend de l'intervalle possible des positions, et que le concept de fin de séquence dépend de l'ordre de traversée de cette séquence (la position de fin peut être placée juste après ou juste avant la séquence, selon le cas, et doit être considérée valide).
// ...
bititt& operator++()
{
bornes_type::avancer(bitpos_);
return *this;
}
bititt operator++(int)
{
bititt b{*this};
operator++();
return b;
}
bititt& operator--()
{
bornes_type::reculer(bitpos_);
return *this;
}
bititt operator--(int)
{
bititt b{*this};
operator--();
return b;
}Les itérateurs doivent offrir des mécanismes arithmétiques semblables à ceux applicables à des pointeurs lorsque ceux-ci sont utilisés à titre d'itérateurs sur un tableau. Cette décision de design du modèle standard de C++ (et mis de l'avant pas les gens oeuvrant sur STL) permet de rédiger des algorithmes applicables à la fois sur des objets, des conteneurs évolués (comme le nôtre) et sur des conteneurs primitifs tels que des tableaux typiques du langage C.
Un bititt sera ce qu'on appelle un itérateur à accès direct (Random Access Iterator) et permettra de se déplacer n'importe où dans la séquence qu'il sert à représenter à l'aide d'une arithmétique de pointeurs normale.
Vous remarquerez que l'action effective de bouger sera prise en charge par le bougeur (type interne bornes_type) qui exposera une méthode de classe exprimant ce que signifient les opérations avancer d'une ou de plusieurs position et reculer d'une ou de plusieurs positions.
Ceci permettra par exemple d'utiliser l'opérateur ++ sur un itérateur dans une séquence vers l'avant, par exemple dans une séquence passant de begin() à end(), ou dans une séquence vers l'arrière, dont un digne représentant serait celle passant de rbegin() à rend(), de manière à ce que l'effet réel sur l'itérateur dépende de sa direction, et ce sans la moindre perte de performance.
Notez que, comme il se doit, l'opérateur ++ postfixé est exprimé en termes du constructeur de copie et de l'opérateur ++ préfixé, et que la même approcha a été appliquée à l'opérateur -- dans ses deux déclinaisons. Il s'agit d'une saine stratégie, à privilégier sauf si des cas pathologiques vous en empêchent.
// ...
bool operator==(const bititt &b) const
{
if (pvaleur != b.pvaleur) throw HorsBornes{};
return bit_pos() == b.bit_pos();
}
bool operator<(const bititt &b) const
{
if (pvaleur != b.pvaleur) throw HorsBornes{};
return bornes_type::precede(bit_pos(), b.bit_pos());
}Les opérateurs relationnels dénotent une relation d'ordre dans une séquence. Ils sont donc valides seulement si les deux itérateurs comparés oeuvrent sur le même entier. Ce constat explique le test réalisé au début des méthodes operator==() et operator<() (car, tel que mentionné plus haut, nous obtenons le reste de la gamme des opérateurs relationnels grâce à notre implémentation de l'idiome CRTP).
Les itérateurs doivent être conceptualisés comme des pointeurs sur les éléments d'une séquence plutôt que comme des indices dans un tableau ou comme des éléments d'un tableau.
Les relations d'ordre n'ont de sens que s'il est raisonnable de leur en donner un – si nous prenons par exemple un itérateur sur une liste, il n'y aura pas lieu d'exposer de méthodes pour ordonnancer ses itérateurs puisque la seule manière de vérifier si un itérateur en précède un autre serait de parcourir les éléments de cette séquence jusqu'à ce que l'on rencontre l'un ou l'autre des itérateurs impliqués. Cette opération ne peut être implémentée de manière efficace, et il n'estdocn pas raisonnable de l'offrir.
Cela dit, dans notre cas, il est tout à fait acceptable de déterminer une relation d'ordre entre deux itérateurs d'une même séquence dans la mesure où cette relation reposera sur la position relative des bits représentés par chacun des itérateurs dans la séquence.
L'égalité positionnelle dépend strictement de la position pour deux itérateurs d'une même séquence. Les relations d'ordre dépendent quant à eux de l'ordre de parcours et sont donc implémentés en partie par délégation à la méthode precede() du type bougeur bornes_type.
// ...
friend bititt operator+(const bititt &b, int n)
{ return bititt{b.pvaleur_, b.bit_pos() + n}; }
friend bititt operator+ (int n, const bititt &b)
{ return b + n; }
bititt operator-(size_type n) const
{ return bititt{pvaleur_, bit_pos() - n}; }
elem_wrap_t operator[](size_type n)
{ return *(*this+n); }
elem_wrap_t operator[](size_type n) const
{ return *(*this+n); }L'arithmétique sur les bititt sera particulière à plusieurs égards. Notons tout d'abord que l'arithmétique de pointeurs permettant de déplacer un itérateur de n positions (n étant un entier) génère une copie de l'itérateur, et se décline en deux versions, l'addition étant commutative. Notons aussi que la soustraction sur nos itérateurs n'est pas définie de manière commutative (cela serait, à mes yeux, suspects pour la grande majorité des usages envisageables, mais je suis ouvert aux critiques constructives et appuyées).
Notez aussi que l'arithmétique sur les itérateurs peut servir de raccourci efficace dans certaines circonstances (voir l'opérateur [] de la classe entier, plus bas).
Remarquez au passage qu'un opérateur d'indirection par indice est offert par souci de conformité entre l'arithmétique des pointeurs et celle s'appliquant aux itérateurs. Sans que ce soit vraiment essentiel, cette délicatesse est souvent appréciée des gens appelés à rédiger des programmes reposant sur nos objets: un itérateur sur une séquence de bits se comporte un peu plus comme le ferait un pointeur sur un tableau primitif. Je l'ai décliné en versions constante et non constante, par souci d'homogénéité, mais il reste que chaque elem_wrap_t retourné sera une temporaire, puisqu'il n'existe pas de type bit.
// ...
bititt& operator+=(size_type n)
{
bornes_type::avancer(bitpos_, n);
return *this;
}
bititt& operator-=(size_type n)
{
bornes_type::reculer(bitpos_, n);
return *this;
}
elem_wrap_t operator*()
{
if (!pvaleur) throw HorsBornes{};
return elem_wrap_t{pvaleur, bit_pos()};
}
void swap(bititt &b)
{ (*b).swap(*(*this)); }
};L'arithmétique de pointeurs sur des opérateurs d'autoincrémentation et d'autodécrémentation tend, comme c'est souvent le cas, à être plus rapide que celle générant des copies d'itérateurs, du fait qu'elle escamote les variables temporaires au passage.
L'indirection sur un bititt génère un elem_wrap_t, donc un bit constant ou non selon le cas, de manière à ce que ce bit représente le lieu vers lequel pointe l'itérateur à ce moment précis.
L'asymétrie fondamentale à laquelle nous faisons face s'exprime ici: on voudrait que l'indirection sur un itérateur de bits donne un bit à proprement dit, mais c'est chose impossible en C++ (il n'existe pas de type donnant accès à un bit). On obtient plutôt un objet capable de se comporter comme ce bit à toutes fins pratiques.
Remarquez l'opération swap(). Elle est essentielle si nous souhaitons rendre la majorité des algorithmes standard applicables à notre type entier, mais il est encore un peu trop tôt pour l'expliquer à ce stade de notre discussion (nous y reviendrons en temps et lieu). Oui, l'écriture appliquée ici est la bonne, si... particulière soit-elle. Nous sommes clairement dans du code de grandes personnes avec cette manoeuvre-ci.
// ...
using iterator = bititt<Bit, Avanceur <elem_type, size_type>>;
using const_iterator = bititt<ConstBit, Avanceur <elem_type, size_type>>;
using reverse_iterator = bititt<Bit, Reculeur <elem_type, size_type>>;
using const_reverse_iterator = bititt<ConstBit, Reculeur <elem_type, size_type>>;Les itérateurs conformes au standard mis en place par STL se nomment habituellement iterator (itérateur vers l'avant vers un référé modifiable), const_iterator (itérateur vers l'avant vers un référé non modifiable), reverse_iterator (itérateur vers l'arrière vers un référé modifiable) et const_reverse_iterator (itérateur vers l'arrière vers un référé non modifiable).
Puisque l'intérêt de toute cette démarche est d'abord et avant tout de permettre de manipuler un entier comme une séquence standard de bits, nous prendrons soin de donner à nos itérateurs des noms conformes au standard.
La stratégie mise de l'avant jusqu'ici porte fruit: concevoir un itérateur signifie déclarer un type bititt applicable à un bit constant ou non et à un bougeur convenant aux besoins. Les alias utilisés pour les quatre principales saveurs d'itérateurs en font foi, ne différant que sur la base de ces deux paramètres.
private:
template <class Itt, class T>
friend Itt make_begin_iterator(T &val)
{
using bornes_type = typename Itt::bornes_type;
return Itt(&val, bornes_type::DEBUT);
}
template <class Itt, class T>
friend Itt make_begin_iterator(const T &val)
{
using bornes_type = typename Itt::bornes_type;
return Itt(&const_cast<T&>(val), bornes_type::DEBUT);
}
template <class Itt, class T>
friend Itt make_end_iterator(T &val)
{
using bornes_type = typename Itt::bornes_type;
return Itt(&val, bornes_type::FIN);
}
template <class Itt, class T>
friend Itt make_end_iterator(const T &val)
{
using bornes_type = typename Itt::bornes_type;
return Itt(&const_cast<T&>(val), bornes_type::FIN);
}
public:
iterator begin()
{ return make_begin_iterator<iterator>(valeur_); }
const_iterator begin() const
{ return make_begin_iterator<const_iterator>(valeur_); }
reverse_iterator rbegin()
{ return make_begin_iterator<reverse_iterator>(valeur_); }
const_reverse_iterator rbegin() const
{ return make_begin_iterator<const_reverse_iterator>(valeur_); }
iterator end()
{ return make_end_iterator<iterator>(valeur_); }
const_iterator end() const
{ return make_end_iterator<const_iterator>(valeur_); }
reverse_iterator rend()
{ return make_end_iterator<reverse_iterator>(valeur_); }
const_reverse_iterator rend() const
{ return make_end_iterator<const_reverse_iterator>(valeur_); }Remarquez le choix clair d'exprimer les méthodes comme begin() et end() en utilisant des types comme iterator ou const_iterator plutôt que des termes plus locaux. Agir ainsi clarifie le propos et détache la proposition d'interface des détails d'implémentation.
Puisque la construction de chaque saveur d'itérateur est identique à celle des autres saveurs, à quelques détails près, j'ai choisi de définir quelques sous-programmes utilitaires. Chacun d'entre eux ne fait rien, ou presque, outre alléger l'écriture des méthodes comme begin() et end(). Contrairement aux croyances, les méthodes qui ne font presque rien sont souvent les meilleures, ayant un focus très clair et étant extrêmement faciles à optimiser pour un compilateur de qualité. C'est le cas de celles-ci, qui ne sont en fait que de petites fabriques créant des objets anonymes – le compilateur pourra presque systématiquement éliminer tout le code généré, alors que notre classe offrira malgré tout la gamme complète des fonctionnalités auxquelles le code client est en droit de s'attendre.
Les méthodes begin(), end(), rbegin() et rend(), qui seront utilisées par le code client désireux de parcourir les bits d'un entier, se déclineront chacune en versions constante et non constante et créeront chacune un itérateur sur la valeur de l'entier dont la position conceptuelle est, selon le cas, le début ou la fin de la séquence.
Les versions constantes utiliseront un const_cast pour lever la restriction locale de constance sur valeur_ puisque le type utilisé pour la représentation interne dans le bit sera garant de la constance de l'objet. L'alternative à ce schème est de concevoir véritablement deux types d'itérateurs, ce qui demande de rédiger beaucoup plus de code.
// ...
elem_type valeur() const
{ return valeur_; }
entier() noexcept
: valeur{}
{
}
entier(elem_type valeur)
: valeur_{valeur}
{
}
entier(bool valeur)
: valeur_{valeur? 1 : 0}
{
}La classe entier, enfin, est relativement simple. Si nous avions la certitude qu'elem_type se copiait sans risque, comme c'est le cas s'il s'agit d'un type primitif, alors des clauses noexcept auraient pu être utilisées. Ceci pourrait être testé par des assertions statiques. Cette remarque s'applique d'ailleurs à la plupart des petites méthodes de cette classe.
La définition des constructeurs est évidente, et la Sainte-Trinité (constructeur de copie, destructeur, affectation) s'applique puisqu'il s'agit d'un pur type valeur.
L'accesseur valeur() est, convenons-en, tout ce qu'il y a de plus banal.
Petite mise en garde au passage : un programme prudent et qui ne souhaite pas planter lamentablement évitera de créer un entier dont la durée de vie excèderait celle du int qui lui sert de substrat.
Opérateurs relationnels pour entierChacun des opérateurs relationnels sera une simple délégation de responsabilité vers la valeur utilisée pour représentation interne. L'idiome CRTP réduit la quantité de code à écrire à ces deux méthodes somme toute très simples. |
|
Opérateurs artihmétiques binaires pour entierLes opérations artihmétiques binaires (à deux opérandes) sont implémentées selon la même stratégie. Le code utilisé ici valide les divisions par zéro dans les deux cas où c'est pertinent (opérateurs / et %), mais il aurait été possible aussi de trapper d'autres cas suspectes comme les cas de débordements. Pour ce faire, la stratégie sage aurait été d'utiliser std::numeric_limits du fichier d'en-tête standard <limits>. On aurait pu envisager de remplacer ces façades opératoires par une simple conversion implicite d'un entier en entier::elem_type mais cela aurait pu générer des effets de bord imprévisibles et silencieux de la part du moteur d'inférence de types du langage (une conversion automatique d'un entier en un entier::elem_type pourrait générer une temporaire convertie plus tard en entier ce qui générerait une asymétrie dommageable à ce que nous essayons de faire ici). |
|
Opérateurs artihmétiques unaires pour entierLes opérations arithmétiques unaires sont des plus banales. Les opérations d'autoincrémentation et d'autodécrémentation respectent l'usage normal et sont, elles aussi, très simples. Ne confondez pas ++ sur un entier, opération représentant un changement de valeur, avec ++ sur un itérateur comme entier::iterator, représentant un changement de position du bit référé. |
|
Opérateurs bit à bit pour entierLes opérations bit à bit pourraient être réalisées à partir de bits créés spécifiquement à cet effet. Cela dit, dans le cas qui nous intéresse, agir à travers un objet intermédiaire serait plus lourd que de réaliser les opérations directement à partir des valeurs des instances de entier qui sont mises en scène par ces diverses opérations. Notez que les débordements potentiels de capacité sont validés dans les opérations de glissement de bits. |
|
|
Les opérateurs bit à bit modifiant directement l'opérande de gauche peuvent être implémentés de différentes manières mais il est peu recommandable de pêcher par paresse dans leur implémentation. Les gens ayant recours à ces formes syntaxiques sont préoccupés par la performance de leurs programmes et ne souhaitent pas payer le prix encouru suite à une rédaction négligente de méthode. Ainsi, il est nettement préférable d'écrire la première instruction de l'opérateur &= sous la forme proposée ici : que sous la forme suivante, en apparence plus simple mais beaucoup plus lourde du point de vue de la mécanique : |
|
Opérateurs logiques pour entierLes opérateurs logiques, toujours dans la même veine, sont proposés sous forme d'indirections sur les valeurs internes à chacune des instances de entier étant impliquées. Les avertissements d'usage s'appliquent encore une fois. |
|
L'implémentation des opérateurs d'accès à travers un indice s'exprimer correctement à l'aide d'arithmétique sur des itérateurs.
|
Remarquez la présence de deux versions (une constante et l'autre pas) de cet opérateur. Le type des méthodes correspond à celui retourné par chacun des types d'itérateurs lors d'une opération d'indirection. |
|
Ceci conclut la classe entier en tant que telle, mais pas notre travail. En effet, quelques outils satellites devront accompagner notre classe pour que celle-ci soit véritablement utilisable.
ostream& operator<<(ostream&, const entier&);
istream& operator>>(istream&, entier&);L'accès aux flux standard est une chose essentielle pour la bonne intégration d'une classe à un modèle de programmation, et la classe entier n'échappe pas à cette contrainte.
La déclaration des opérateurs d'extraction d'un flux et d'insertion dans un flux sont tout ce qu'il y a de plus standard dans le genre. Ils seront définis dans le fichier source de la classe entier, un peu plus loin.
Un dernier détail important de notre démarche sera la spécialisation de l'un des algorithmes les plus fondamentaux de STL : l'échange de valeurs.
Les algorithmes comme std::reverse() ont souvent recours à l'opération fondamentale d'échange de valeurs référées par une paire d'itérateurs. Cet algorithme se nomme std::iter_swap() et n'a de sens que sur les itérateurs non constants.
Dans notre cas, la définition normale de cet algorithme ne sied pas du fait que *itt sur un itérateur retourne un bit et que *b sur un bit retourne un bool, duquel on ne peut plus retrouver de manière modifiable le bit d'origine.
namespace std
{
template <>
void iter_swap(entier::iterator, entier::iterator);
template <>
void iter_swap(entier::reverse_iterator, entier::reverse_iterator);
}
#endifIl nous faudra donc avoir une opération d'échange de valeurs spécialisée sur des itérateurs de bits, qui permettra d'utiliser sans bris d'encapsulation un mécanisme d'échange de valeurs correct pour une paire de bits. Nous verrons plus loin comment y arriver.
Le fichier source de la classe entier couvrira deux types d'opérations :
Notez le soin pris dans chaque cas de capturer au préalable la stratégie d'affichage sur le flux (appel de la méthode flags() – sans paramètres – du flux) puis de remettre en place ces paramètres avant de quitter (appel de la méthode flags() – avec paramètres – du flux). C'est du simple civisme. Une approche RAII aurait d'ailleurs été encore mieux ici.
Enfin, le mécanisme spécialisé d'échange de valeurs à travers des itérateurs non constants est banal : une simple délégation au swap() subjectif de l'itérateur suffit.
namespace std
{
template <>
void iter_swap(entier::iterator a, entier::iterator b)
{ a.swap(b); }
template <>
void iter_swap(entier::reverse_iterator a, entier::reverse_iterator b)
{ a.swap(b); }
}Procéder ainsi permet d'éviter l'indirection fatale par * causant l'asymétrie tout en conservant intacte la barrière d'abstraction d'un bit et d'un itérateur de bit.
Échanger des valeurs devient une opération subjective aussi efficace que possible.
L'effort est important. Le jeu en valait-il la chandelle?
On se doutera que ma réponse sera affirmative. En premier lieu parce que ce fut amusant à écrire et à réfléchir, ce qui est la meilleure raison pour s'adonner à la résolution de problèmes complexes en l'absence d'un motif concret, pécunier ou autre.
Ensuite parce que ce genre de code est sujet à être écrit (et testé) une fois puis utilisé longtemps. L'effort supplémentaire pour intégrer l'idée à un modèle plus grand est un effort local et ponctuel; le retour sur l'investissement, en temps comme en effort, est un retour sur une longue période.
Enfin, ça a un petit côté pédagogique...
Quelques liens pour enrichir le propos.
