3. TP: surcharge d’opérateurs

3.1. Implémentation de grands entiers

3.1.1. Problème

Dans certains calculs, on se heurte à un problème de précision: dans le cas des entiers, ça se traduit par un débordement de capacité (overflow). Exécutez par exemple le programme factorial qui vous est fourni:

• Téléchargez l’archive ELP-TP-CPP.tar.gz
• Compilez avec make
• Exécutez ./factorial

3.1.2. Solution

Pour éviter ce type problème, on souhaite implémenter et utiliser une classe modélisant un nombre entier non borné (pouvant avoir un nombre arbitraire de chiffres). Le squelette de la classe, appelée BigInt, vous est fourni. Certaines méthodes sont déjà données, d’autres sont à complétées. Des tests que doivent valider les méthodes que vous développerez vous sont aussi fournis.

3.1.3. Choix d’implémentation

Un nombre entier sera représenté par un tableau dynamique d’entiers dont chaque case correspond à un chiffre. On raisonne en base 10 pour commencer.

Les chiffres de 0 à 9 seront stockés dans des variables de type int (redéfini en Digit), tandis que le tableau dynamique sera de type std::vector<Digit> (redéfini en Container).

Par commodité, les chiffres d’un nombre seront stockés dans le conteneur de la gauche vers la droite avec le chiffre des unités dans la première case du conteneur.

Par convention, zéro est représenté par un conteneur vide. Le chiffre le plus à droite ne doit pas être un zéro.

3.1.4. Illustration

3.1.5. Compétences

Au cours de ce travail, vous allez vous familiariser avec plusieurs caractéristiques du C++:

1. la surcharge d’opérateurs
2. la référence et le passage par référence.
3. le mot-clef const, qualifiant une variable ou une méthode.

3.2. La surcharge d’opérateurs

3.2.1. Opérateurs

En C++, on peut surcharger (presque) tous les opérateurs

• arithmétique (+, -, *, etc.)
• logiques (&&, ||, etc.)
• comparaison (==, <=, etc.)
• flux (<<, >>, etc.)
• même les opérateurs moins courants comme cast, virgule, etc.

Consultez la liste d’opérateurs.

3.2.2. Comment surcharger un opérateur ?

On peut ajouter dans la classe A l’opérateur + ainsi:

A operator+(A a)
{
  A res;
  ...
  return res;
}

3.2.3. Comment appeler un opérateur ?

Dans le code client, on peut alors appeler directement la méthode operator+ ou bien utilisez l’opérateur +:

A x, y, z;
z = x.operator+(y); //method-call style
z = x + y;          //operator style

NB. L’ordre compte: avec x+y, on appelle la méthode operator+ de x avec y en paramètre, tandis qu’avec y+x, on appelle la méthode operator+ de y avec x en paramètre. Les deux sens devraient aboutir au même résultat si l’opérateur est commutatif.

3.3. Références

3.3.1. Le passage par référence

Tandis qu’en C, les passages de paramètres se font toujours par copie, en C++, on peut choisir un passage par copie ou par référence.

Prenez l’exemple de la fonction std::swap:

template <class T> void swap ( T& a, T& b )
{
  T c(a); a=b; b=c;
}

Les paramètres formels a et b de type T sont passés par référence (à cause de la présence du &). Tout se passe donc comme si on manipulait directement les paramètres effectifs passés à l’appel de la fonction; la permutation a donc bien lieu.

3.3.2. Retour par référence

Par convention, les opérateurs de la famille des affectations retournent une référence vers l’objet courant.

A& operator=(A a)
{
  ...
  return *this;
}

A& operator+=(A a)
{
  ...
  return *this;
}

3.4. Le mot-clef const

3.4.1. Appliqué à une variable

Il rend celle-ci constante: dès lors, impossible de lui assigner une nouvelle valeur. Souvent, les paramètres formels d’entrée d’une méthode ou d’une fonction sont définis comme des références constantes. Référence pour éviter la recopie (c’est plus efficace), constante pour éviter de modifier leur valeur par erreur (c’est plus sûr).

Par exemple, l’un des constructeurs de la classe BigInt a la signature suivante, car l’entier donné en entrée ne devrait pas être modifié:

BigInt(const int& aInt)

3.4.2. Appliqué à une méthode

Il garantit que l’état de l’objet, dont la méthode est appelée, ne sera pas modifié (c’est plus sûr).

Par exemple, l’opérateur d’égalité de la classe BigInt pourra avoir la signature suivante, car le test d’égalité ne devrait pas changer l’état de l’objet:

bool operator==(const BigInt& other) const;

NB. Bien sûr, dans cet exemple, on parle du second const, appliqué à la méthode operator==.

3.4.3. Conséquence sur les conteneurs

Quand un conteneur est déclaré const, ou bien quand il est un champs d’une classe et qu’il est manipulé dans une méthode déclarée const, vous devez utiliser les types d’itérateurs constants:

• const_iterator,
• const_reverse_iterator.

3.5. Ce que vous devez faire

3.5.1. Services de base

1. Implémentez un nouveau constructeur permettant de créer un grand entier à partir d’une chaine de caractères. (Attention à l’ordre des chiffres.) Vous pourrez alors créer un grand entier ainsi:

BigInt i("164321545654");

2. Implémentez l’opérateur d’égalité et de différence. Pour des entiers de même taille, c’est-à-dire ayant le même nombre de chiffres, pensez à utiliser la fonction std::equal.

3.5.2. Addition

3. Implémentez l’opérateur d’addition. L’algorithme est celui que vous utilisez depuis le CE2. Pour chaque position, en partant du chiffre des unités, on ajoute les chiffres de chacun des deux nombres, plus la valeur de la retenue (initialisée à zéro). Si la somme est supérieure à la base (10 ici), on n’écrit que le chiffre des unités mais on reporte une retenue.

   Pensez à traiter proprement le cas de deux nombres de taille différente.

3.5.3. Multiplication

4. Implémentez l’opérateur de multiplication. L’algorithme est le suivant. Multiplions a par b. Dans un premier temps, on stocke dans un buffer les multiplications de 1 par b, de 2 par b, ... de 9 par b, calculées par additions successives. Dans un second temps, pour chaque chiffre de a, on multiplie ce chiffre par b (en lisant le buffer), puis on multiplie le résultat par une puissance de 10 dépendant de la position du chiffre courant (simple décalage). Enfin, on ajoute le résultat à la somme des termes (initialisée à zéro).

   NB: il est conseillé d’implémenter la multiplication par une puissance de 10 dans une méthode privée séparée.

3.5.4. Comparison

5. Implémentez l’opérateur de comparaison <=. Pensez à comparer les entiers de taille différente correctement.
6. Une fois ces opérateurs (addition, multiplication, comparaison) implémentés, dans le fichier factorial.cpp, vous pouvez appelez la fonction factorial sur un entier de la classe BigInt plutôt que sur un entier primitif de type int (une seule ligne à changer).

3.5.5. Encore des comparaisons

7. Ecrivez une fonction de test pour tous les opérateurs de comparaisons (<, <=, >, >=).
8. Imaginez un moyen d’implémenter de manière uniforme les quatre opérateurs de comparaison. Dans ce but, les foncteurs std::less, std::less_equal, std::greater, std::greater_equal, peuvent vous être fort utiles. Consultez la liste des foncteurs.

3.5.6. Pour aller plus loin

9. Commencez par surcharger les quatre opérateurs d’incrémentation/décrémentation.
10. Que faire pour modéliser des grands entiers signés ? Implémentez les opérateurs de soustraction (unaire et binaire).
11. Que faire pour modéliser des grands entiers représentés dans une base quelconque ? Testez votre classe en base 2, 10 et 16.