Discussion :

[alexandrempg]

Bonjour,

Je réalise un TP actuellement sur la substitution par chiffrement, évolution du chiffrement par décalage de César. La substitution fonctionne ainsi: on possède un fichier .txt où se trouve "la clé" qui est composé dans une colonne de l'alphabet dans l'ordre, puis dans l'autre colonne, la lettre qui substitue celle de l'alphabet.
En général, on a ça: AEBKCUDP.... où "A" sera substituté par "E", "B" par "K" et ainsi de suite.

Ensuite, on a un chaîne de caractères stockée dans un string, et le but est d'appliquer la substitution à la chaîne de caractères. Mon intérêt est de passer par un foncteur et des itérateurs, puis plus tard par des algorithmes. Mon code actuel est le suivant, et je bloque clairement sur la substitution, alors que je n'ai pas eu ce problème pour le chiffrement par décalage (même si le dernier est plus simple).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <string>
#include <iterator>
#include <fstream>
using namespace std;
 
int main()
{
 
    // Le message a crypter
    string texte("TEXTE A TESTER");
 
    // Demande de la cle a l'utilisateur
    cout << "Quel fichier contenant la cle voulez-vous utiliser ? ";
    string nomFichier;
    cin >> nomFichier;
 
    ifstream fichier(nomFichier);
    istream_iterator<char> it(fichier);
    istream_iterator<char> end;
 
    string a;
    while (it != end)
    {
        a.push_back(*it);
        ++it;
    }
 
    for (int i =0; i < a.size(); i++)
    {
         if (i%2 == 0)
         {
               a[i] = a[i+1];
          }
 
        cout << a[i];
     }
 
    return 0;
}

Déjà, j'ai un petit problème aussi avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

ifstream fichier(nomFichier);

qui n'accepte pas mon string nomFichier. Je comprends pas pourquoi, quand je remplace par le nom du fichier "cle.txt", il n'y a pas de problème, et ifstream est censé recevoir du type string.

Ensuite, ce que j'effectue dans ma boucle for, j'aimerai l'effectuer dans ma boucle while, c'est à dire que je ne souhaite pas passer par du string pour parcourir la chaîne via les index, mais par la boucle while avec l'itérateur.

Dans l'attente de toutes vos réponses, je reste à l'écoute!

[Bousk]

Hello,

Déjà, j'ai un petit problème aussi avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

ifstream fichier(nomFichier);

qui n'accepte pas mon string nomFichier.

parce que comme l'indique la doc, le constructeur de ifstream prend un const char*, ce qu'est "cle.txt" et non un std::string.

Pour un tel exercice, j'opterais pour un std::map<char, char> et std::for_each, std::transform ou std::replace.
Il y a aussi une autre méthode dont j'oublie toujours le nom qui permet de faire du push_back à la volée

[alexandrempg]

Hello,

parce que comme l'indique la doc, le constructeur de ifstream prend un const char*, ce qu'est "cle.txt" et non un std::string.

J'avais vu ça dans mes erreurs mais je comprenais pas qu'au final le "cle.txt" était de type const char*. Du coup, ce problème ce pallie par cette solution:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

ifstream fichier(nomFichier.c_str());

Pour un tel exercice, j'opterais pour un std::map<char, char> et std::for_each, std::transform ou std::replace.
Il y a aussi une autre méthode dont j'oublie toujours le nom qui permet de faire du push_back à la volée

Je vais m'intéresser à la map puis je reviendrai si j'ai d'autres éventuelles questions, j'avais hésité à passer par là. Pour ce qui est des algorithmes, c'est bien ceux que j'avais en tête, notamment std::transform().

[jo_link_noir]

Depuis la norme C++11 (5ans maintenant), ifstream peut prendre un std::string.

@Bousk: emplace_back, également depuis C++11.

@alexandrempg: Utiliser une boucle for pour le parcours d'itérateur est plus idiomatique qu'une boucle while et le risque d'oublier l'incrémentation y est moins fort. l'utilisation d'algorithme simplifie aussi pas mal (cf: std::copy + std::back_inserter), mais dans l'absolu, std::string peut s'initialiser avec 2 itérateurs, un simple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
std::string a{
  std::istreambuf_iterator<char>{fichier},
  std::istreambuf_iterator<char>{}
};

est beaucoup plus simple.

[Bousk]

@Bousk: emplace_back, également depuis C++11.

Non, je parlais de back_inserter.

[zobal]

Salut

Je ne vois pas trop l'intérêt de lire le fichier avec un itérateur puisqu'il faut faire un traitement non homogène sur les données. Personnellement, j'aurais écrit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
ifstream fichier("cle.txt");
map<char,char> lut;
char cle, valeur;
while (fichier >> cle) { if (fichier >> valeur) lut[cle] = valeur; }

Le map est effectivement une bonne idée (ne pas oublier de tester si le caractère est bien dans la map lors de la substitution...). Pour l'algorithme de substitution, je pense que for_each sera le plus simple et le plus efficace.

Bon courage

[JolyLoic]

La map ne me semble pas une si bonne idée, puisqu'elle va effectuer des recherches en O(ln N) alors qu'en utilisant directement un indice dans un tableau, on est en O(1), en plus d'être compact en mémoire...

[zobal]

@JolyLoic: tu as raison cependant si on considère les lettres de l'alphabet (N=26) on a une map de profondeur 5 (au mieux; 26 au pire); le gain n'est donc pas très important. Par contre, le tableau rend le code moins lisible (genre lut[int(c-'a')]) et surtout moins polyvalent (par exemple, si on veut mettre des chiffres ou des signes de ponctuation dans la clé).

[alexandrempg]

Bonsoir à tous!

Je vous remercie tous pour vos différentes réponses que j'ai bien pris le temps de lire, diverses solutions toutes autant intéressantes que les autres, j'ai actuellement réussi à effectuer la substitution, cependant cette dernière n'est pas optimisée encore à 100% avec un itérateur manquant, ainsi que les foncteurs et algorithmes que je n'ai pas encore appliqué à mon foncteur. Je prendrai le temps de revenir ici afin de vous poster ce que j'ai effectué.

Pour utiliser la substitution, je suis déjà parti sur l'idée de zobal qui donne une certaine version pour "affecter" la clé et la valeur.

Salut

Je ne vois pas trop l'intérêt de lire le fichier avec un itérateur puisqu'il faut faire un traitement non homogène sur les données. Personnellement, j'aurais écrit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
ifstream fichier("cle.txt");
map<char,char> lut;
char cle, valeur;
while (fichier >> cle) { if (fichier >> valeur) lut[cle] = valeur; }

J'aurai cependant une petite question pour toi zobal, si tu me lis encore, ou bien les autres éventuellement qui auraient la réponse. Comment cette ligne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

while (fichier >> cle) { if (fichier >> valeur) lut[cle] = valeur; }

arrive-t'elle à déterminer qui est la clé et qui est la valeur dans mon fichier .txt? Car c'est la première utilisation que je vois de map pour affecter des valeurs d'un fichier. Pour moi la map, si je ne lis pas un fichier, je passe directement par les déclarations du genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
lut['A'] = 'E';
lut['B'] = 'K';
lut['C'] = 'O';

qui me permettent de définir qui est la clé et qui est la valeur. Mais dans le fichier .txt, on ne le sait pas à priori, donc, comment la boucle while et if arrive à le déterminer? Car ça m'éclairerait sur un point noir du côté du conteneur map qui m'aiderait grandement, et via la doc sur C++reference je n'ai pas trouvé d'éventuels exemples qui permettraient de comprendre tout ça.

Pour ce qui est de l'algorithme, je ne l'ai pas précisé au début, mais j'utiliserai à coup sûr std::transform() sur ma chaîne de caractère en lui appliquant le foncteur, et en stockant le résultat sur une autre chaîne de caractère qui sera

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

string texte_crypte;

afin de ne pas modifier la première chaîne de caractère contenant le texte original.

[JolyLoic]

Je ne pensais pas à un tableau où l'on ne mettrait que les lettres, mais à un tableau où l'on mettrait tous les chars.
Un truc genre (code écrit à la volée, non testé):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
 
using Conversion = std::array<char, std::numeric_limit<unsigned char>::max()>;
 
Conversion createConversion()
{
  Conversion conversion;
  static_assert(sizeof(char)<sizeof(int));
  for (int c = 0; c<std::numeric_limit<unsigned char>::max() ; ++c)
  {
    conversion[c] = static_cast<char>(c);
  }
  // On modifie alors les valeurs qui n'ont pas une conversion standard...
  return conversion;
}
// Pour définir le cryptage d'un caractère :
void setConv(Conversion &conv, char normalChar, char cryptedChar)
{
    conv[static_cast<unsigned_char>(normalChar)] = cryptedChar;
}
 
// Pour crypter :
char encrypt(Conversion const &conv, char normalChar)
{
    return conv[static_cast<unsigned_char>(normalChar)];
}

Le seul truc pas hyper évident là dedans, c'est la conversion en unsigned_char pour le cas où char serait signé. Mais de toute façon, point de vue lisibilité, tout le but du jeu est d'encapsuler ça.

Et du point de vue performance, une profondeur de 5, c'est toujours 5 branchements à faire, et 5 possibilités de cache miss. Je n'ai pas le temps de faire les mesures, mais il y a des chances que pour des données en mémoire, ça se traduise par un taux de caractères cryptés par seconde 5 fois plus faible au moins. Je ne trouve pas ça forcément négligeable. Pour des données sur disque ou sur réseau, je n'ai aucune idée de ce que ça donnerait
Certes, il ne s'agit là que d'un exercice, mais le but d'un exercice n'est-il pas aussi de prendre les bons réflexes ?

[zobal]

@JolyLoic: oui bien vu, avec le mapping complet on gère tous les caractères. Par contre, je continue à croire que le map est plus lisible et que le gain n'est pas très important : il s'agit de la complexité par rapport à la taille de la clé (qui est bornée) mais ce qui risque d'être couteux, c'est la complexité par rapport à la taille du texte à chiffrer et dans ce cas, on est en linéaire dans les deux solutions. Le choix dépend plutôt de l'application visée, sachant aussi que "early optimisation is the root of all evil"...

@alexandrempg: j'ai compris que le fichier cle.txt contient un caractère non chiffré (cle dans la map) puis son caractère chiffré (valeur dans la map) et ainsi de suite pour les autres caractères. Du coup, la ligne while (fichier >> cle) { if (fichier >> valeur) lut[cle] = valeur; } lit tout simplement deux caractères, les place dans la map puis recommence pour les suivants. Les valeurs de retour de >> sont testées pour vérifier la fin du flux mais en gros, ça revient à faire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
while (fichier) {
    fichier >> cle;  // on lit le caractère à chiffrer
    fichier >> valeur;  // on lit le caractère "chiffré" correspondant
    lut[cle] = valeur;  // on remplit la map
}  // on boucle pour les caractères cle/valeur suivants

[Bousk]

La map c'est le premier jet, l'application naïve. Par la suite l'utilisation d'un vector est effectivement préférable par souci de performance
Et le passage de map à vector devrait être totalement gratuit grâce à l'opérateur [] de part et d'autre

[Astraya]

Tu ne travaille que sur l'alphabet?
Dans ce cas c'est très simple.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/** Table de remplacement */
//                                   { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M','N', 'O', 'P', 'Q','R','S','T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
static const char ReplacementMaj[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M','N', 'O', 'P', 'Q','R','S','T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
//                                   { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm','n', 'o', 'p', 'q','r','s','t', 'u', 'v', 'w', 'x', 'y', 'z' };
static const char ReplacementMin[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm','n', 'o', 'p', 'q','r','s','t', 'u', 'v', 'w', 'x', 'y', 'z' };
 
char Decrypt(const char C)
{
    // Recuperer la value numerique du character
    const int CleNum = (int)C;
 
    // La lettre est-elle Majuscule?
    if (CleNum >= (int)'A' && CleNum <= (int)'Z') // C-cast. et alors? :)
    {
        return ReplacementMaj[CleNum - (int)'A'];
    }
    // Est-elle possible Minuscule?
    if ( CleNum >= ('a') && CleNum <= 'z' )
    {
        return ReplacementMin[CleNum - (int)'a'];
    }
    //La lettre n'est pas decryptable    
    return '?';
}
 
char Decrypt(const wchar_t C)
{
    if(C > 0x7F) // Le caractère n'est pas ASCII pure
        return '?'; //La lettre n'est pas decryptable
    return Decrypt((char)C);
}

Celui qui me parle de C-Cast je le clou sur place.

[zobal]

@Astraya; oui mais je pense que le but de la discussion est d'aider alexandrempg à écrire de lui-même une solution en C++ propre, pas de lui fournir un code tout fait en C tout moche....

[Astraya]

On va prendre le problème a l'envers. Qu'est ce qui ne compile pas en C++ dans ce programme?
La map n'a aucun intérêt. Tu veux pas du tableau static? Mets un vector et prouve moi que c'est mieux. Tu veux du static_cast, met le et prouve moi que c'est plus lisible et plus rapide et plus mieux.

Le code fourni lui permets de comprendre comment faire pour changer une lettre par un autre, ce n'est en aucun cas la réponse à son TP

[zobal]

On va prendre le problème a l'envers. Qu'est ce qui ne compile pas en C++ dans ce programme?
La map n'a aucun intérêt. Tu veux pas du tableau static? Mets un vector et prouve moi que c'est mieux. Tu veux du static_cast, met le et prouve moi que c'est plus lisible et plus rapide et plus mieux.

Ok, excuse-moi d'avoir oser critiquer ta solution, elle est merveilleuse et tu es beau, fort et intelligent.

[Ehonn]

Petit message juste en passant (je n'ai pas lu le reste et ne veux pas prendre au débat "le C c'est mal" ici).

Mets un vector et prouve moi que c'est mieux. Tu veux du static_cast, met le et prouve moi que c'est plus lisible et plus rapide et plus mieux.

L'équivalent serait plus :
- std::array (pour éviter l'allocation dynamique)
- les "constructeurs" pour les casts (exemple : int(a_char)) (coding style)
- l'utilisation de std::isupper et std::islower (coding style)
- on pourrait utiliser un else if dans la fonction Decrypt (coding style)

[Bousk]

- std::array (pour éviter l'allocation dynamique)

allocation dynamique d'un tableau static const ?

- les "constructeurs" pour les casts (exemple : int(a_char)) (coding style)

inutile

- l'utilisation de std::isupper et std::islower (coding style)

totalement gadget. Perso je ferais un gros switch case.

- on pourrait utiliser un else if dans la fonction Decrypt (coding style)

inutile puisqu'on ne sort jamais d'un if vu qu'ils ont tous un return

[Ehonn]

Pas sûr que mon message a été bien interprété :s

Astraya "proposait" (avec "ironie") des changements pour introduire plus de "C++" dans le code qu'il propose.
Il parlait de std::vector et static_cast, je disais juste que std::array et T() était plus "adapté".
Le reste est évidement "inutile" et cela est précisé par « coding style ».

Du coup j'ai une question.
Dans static const std::vector<int> v = { 1, 2, 3 };, il n'y a pas d'allocation dynamique ?

[jo_link_noir]

Du coup j'ai une question.
Dans static const std::vector<int> v = { 1, 2, 3 };, il n'y a pas d'allocation dynamique ?

static const ne fait rien de magique sur le constructeur, alors si, il y a allocation dynamique. Mais qu'une fois.
Perso, les constantes dans les fonctions, je les préfère en static constexpr pour les optimisations potentielles.