Discussion :

[goran kajfes]

Bonjour à tous. À l'exercice 7-1 du livre Accelerated C++, on demande de faire évoluer un code servant à compter le nombre d'occurrences de mots, pour que le trie se fasse non plus par ordre alphabétique des mots trouvés (acrobate: 2 fois, jongleur: 3 fois, ...) mais par ordre des occurrences (Mots apparaissant n fois: mes_mots1, Mots apparaissant (n-1) fois: mes_mots2...).

Quelques lignes au-dessus de la question, l'expression suivante apparait:

Code :

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

map<K, V> m(cmp);

Cela ne peut être un hasard. cmp est le prédicat servant à déterminer l'ordre des éléments. Jusque là, c'est tout ce qui est dit à propos des prédicats des map.

Voici le code initial:

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
#include <iostream>
#include <map>
#include <string>
 
using std::cin;
using std::cout;
using std::endl;
using std::map;
using std::string;
 
int main()
{
	string s;
	map<string, int> counters; // store each word and an associated counter
 
	// read the input, keeping track of each word and how often we see it
	while (cin >> s)
		++counters[s];
 
	// write the words and associated counts
#ifdef _MSC_VER
	for (std::map<string, int>::const_iterator it = counters.begin();
#else
	for (map<string, int>::const_iterator it = counters.begin();
#endif
	     it != counters.end(); ++it) {
		cout << it->first << "\t" << it->second << endl;
	}
	return 0;
}

Voici mon code:

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
#include <iostream>
#include <map>
#include <string>
 
using namespace std;
 
typedef map<string, int> Map;
typedef Map::const_iterator Map_iter;
 
bool cmp(const Map_iter& a, const Map_iter& b) {
	return a->second < b->second;
}
 
int main()
{
	string s;
	Map counters(cmp);
 
	while (cin >> s)
		++counters[s];
 
	for (Map_iter it = counters.begin(); it != counters.end(); ++it)
		/* code à ajouter pour afficher les occurrences,
                suivis des mots correspondants */
	return 0;
}

La compilation échoue (ligne Map counters(cmp)). Au début j'avais écrit cmp() de la façon suivante:

Code :

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

1
2
3
bool cmp(const pair<string, int>& a, const pair<string, int>& b) {
	return a->second < b->second;
}

... sans davantage de succès.

[Goten]

Hum non, ton prédicat doit prendre en argument le type des clefs de ta map. Voici comment j'écrirais ça :

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
 
#include <iostream>
#include <map>
#include <string>
 
struct myPred
{
    bool operator()(const std::string& a, const std::string& b) const
    {
        return a<b;
    }
};
 
int main()
{
	std::string s;
	std::map<std::string, int, myPred> counters;
 
	while (std::cin >> s)
		++counters[s];
 
	return 0;
}

je passe toujours mon prédicat comme template il y'a surement une différence avec le fait de le passer à la construction mais je connais pas.

[ptyxs]

J'avais eu les mêmes idées que goran_kajfes et suis tout aussi perplexe...
Il me semble que la technique utilisée par Goten, pour pertinente qu'elle puisse être par ailleurs, ne fait pas partie des 'acquis' au point où l'exercice est donné dans le livre de Koenig et Moo.
D'autre part, ce qu'il faudrait comparer dans cet exercice, ce sont les valeurs et non les clés...
Or si je comprends bien, dans

Code :

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

map<K, V> m(cmp);

(donné peu avant par KM)
le prédicat cmp sert uniquement à comparer les clés, non ?
Je me demande s'il ne faudrait pas créer une map qui fasse de chaque valeur de la map actuelle une clé qui aurait pour valeur un vecteur contenant tous les mots ayant cette valeur dans la clé actuelle...

[JolyLoic]

Bonjour à tous. À l'exercice 7-1 du livre Accelerated C++, on demande de faire évoluer un code servant à compter le nombre d'occurrences de mots, pour que le trie se fasse non plus par ordre alphabétique des mots trouvés (acrobate: 2 fois, jongleur: 3 fois, ...) mais par ordre des occurrences (Mots apparaissant n fois: mes_mots1, Mots apparaissant (n-1) fois: mes_mots2...).

Je pense que là est le problème, tu as mal compris l'énoncé (le gras est de moi) :

Expand the program from §1.2/124 to produce its output sorted by occurence count.

Il ne faut pas changer la façon dont le tri est fait dans la map, car la façon dont il est fait est nécessaire au bon fonctionnement du programme. Il faut juste changer l'affichage pour que ce dernier se fasse dans un autre ordre.

C'est justement un bon exercice pour voir si on a bien compris les map, et le fait que l'ordre défini sur les clefs sert avant tout à différencier une clef d'une autre. C'est l'un des premiers exercices que je donne à mes élèves.

J'ai bien vérifié, tu as tout en main à la fin du chapitre 7 pour résoudre ce problème. Je te laisse un peu chercher ?

[ptyxs]

Le code suivant fonctionne sur mon système. Il crée une seconde map où la clé est un nombre de lignes n et la valeur est un vecteur contenant les mots attestés dans n lignes.

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
#include <iostream>
#include <map>
#include <string>
#include <vector>
 
using namespace std;
 
int main()	
{
 string s;
 map<string, int> counters; // store each word and an associated counter
 
 // read the input, keeping track of each word and how often we see it
 while (cin >> s)
      ++counters[s];
 
// on crée une nouvelle map
// formée de paires dont la clé représente un nombre de lignes
// et dont la valeur est un vecteur de strings 
// contenant tous les mots apparaissant dans le nombre de lignes
// représenté par la clé
 map<int, vector<string> > newcounters;
 
 for (map<string, int>::const_iterator it = counters.begin();it != counters.end(); ++it)
	newcounters[it->second].push_back(it->first);
 
// on imprime le contenu de cette nouvelle map
 for(map<int, vector<string> >::const_iterator it = newcounters.begin();
	  it != newcounters.end(); ++it) {
 	      cout << "\nMots présents dans " << it->first << " lignes : " << endl << endl;
	      for(vector<string>::const_iterator it2 = it->second.begin(); it2 != it->second.end();++it2)
		cout <<  *it2 << ' '; 
 }on 
  return 0;
}

Le code est assez compact mais présente l'inconvénient de créer DEUX map simultanément. Une solution qui se contenterait de la première map et qui l'imprimerait correctement occuperait sans doute moins de mémoire.

[ptyxs]

Et ce code fonctionne aussi, sans créer une deuxième map :

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
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main()	
{
  string s;
  map<string, int> counters; // store each word and an associated counter
 
  // read the input, keeping track of each word and how often we see it
  while (cin >> s)
    ++counters[s];
 
  int max_freq = 0;
// trouver la plus grande valeur de counter (correspondant au  mot le plus fréquent) 
  for(map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it)  
    max_freq = max(max_freq, it->second);    
 
  for (int i = 1;  i<= max_freq;++i) { // on recherche les mots présents dans i lignes
    cout << endl << endl;
    cout << "Mots figurant dans : " << i << " lignes :" << endl;
 
    for (map<string, int>::iterator it = counters.begin(); it != counters.end(); ++it) {
      if (it->second == i) {
	cout << it->first << ' ';
      } 
    }
  }
  return 0;
}

[JolyLoic]

La deuxième solution me semble assez horrible en terme de complexité algorithmique.

Personnellement, ce qui me vient le plus directement en tête est une solution où l'on copie le contenu de la map dans un vector<pair<string, int> > (puisque l'ordre dans un vector est contrôlé par l'utilisateur), puis où l'on trie ce vector selon le critère requis.

[ptyxs]

La deuxième solution me semble assez horrible en terme de complexité algorithmique.

C'était bien mon impression aussi...

Personnellement, ce qui me vient le plus directement en tête est une solution où l'on copie le contenu de la map dans un vector<pair<string, int> > (puisque l'ordre dans un vector est contrôlé par l'utilisateur), puis où l'on trie ce vector selon le critère requis.

Est-ce que ce serait 'mieux' que la première solution finalement (qui recopie une map dans une autre map) ?
L'idéal serait sans doute d'éviter une recopie de conteneur, vecteur ou map, et de trouver un algo un peu plus élégant que la 'seconde solution' pour afficher directement le contenu de la map 'counters' ?

[goran kajfes]

Merci pour vos réponses.

Goten: on n'est pas encore censé savoir qu'une structure peut « abriter » des fonctions, ni que des maps peuvent avoir 3 arguments.

Je pense que là est le problème, tu as mal compris l'énoncé (le gras est de moi)

Un énoncé est comme le code pénal: tout ce qui n'est pas interdit est autorisé. On ne me dit pas de ne pas changer la déclaration du map, mais de modifier la sortie. En modifiant le map (sa déclaration), je modifie ainsi sa sortie. Mais je ne suis pas dans la tête de Koenig et Moo.

Voilà comme les auteurs définissent le map<K, V> m(cmp); :

map<K, V> m(cmp);
Creates a new empty map with keys of type const K and values of type V, that uses the predicate cmp to determine the order of the elements.

Ça ressemble quand même beaucoup à ce qui m'est demandé. Par contre, j'ai eu beau chercher un moment sur internet, je n'ai rien trouvé qui corresponde à ce genre de déclaration. Est-ce que quelqu'un saurait l'utiliser?

Je ne sais pas ce que tu en penses mais je trouve beaucoup d'exercices du livre ambigüs (et ce n'est pas parce que c'est de l'anglais). J'espère que leur sujets d'examens le sont moins. Par contre, j'apprécie tout le reste (le générateur de phrases aléatoires m'a bluffé).

ptyxs: J'ai aussi créé une deuxième map. Je n'avais pas regardé ton code avant, mais le reste de tes messages (qui parlait notamment de 2 maps simultanées). Je ne le donne pas. C'est quasiment un copier-coller du tien: 3 boucles for, map<int, vector<string> > ...
Avec ta deuxième méthode, tu répertories des fréquences sans qu'elles ne soient associées au moindre mot.

Je vais attendre un peu avant de mettre en résolu.

[JolyLoic]

Un énoncé est comme le code pénal: tout ce qui n'est pas interdit est autorisé. On ne me dit pas de ne pas changer la déclaration du map, mais de modifier la sortie. En modifiant le map (sa déclaration), je modifie ainsi sa sortie. Mais je ne suis pas dans la tête de Koenig et Moo.

Tout à fait, c'est autorisé. Le problème, c'est que ça ne te mènera pas vers la solution. Le comparateur associé à une map sert à comparer entre elles les valeurs des clefs, et rien d'autre. Tu ne pourras pas t'en servir pour comparer les nombres d'occurrence. En outre, ce comparateur doit être stable, c'est à dire que si un jour, il dit A<B, le lendemain, il doit toujours dire A<B. Tu voudrais un comparateur qui tiendrait compte du nombre d'occurrence alors que celui-ci varie au cours du temps.

Voilà comme les auteurs définissent le map<K, V> m(cmp); :

Ça ressemble quand même beaucoup à ce qui m'est demandé.

Peut-être, mais dans ce cas, la ressemblance est trompeuse.

Par contre, j'ai eu beau chercher un moment sur internet, je n'ai rien trouvé qui corresponde à ce genre de déclaration. Est-ce que quelqu'un saurait l'utiliser?

Il s'agit d'un raccourci/un bug des auteurs. Le comparateur se défini comme indiqué par Goten par un argument template supplémentaire. Ce constructeur sert alors pour passer une instance particulière de ce template. Exemple :

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
41
#include <map>
#include <iostream>
#include <string>
 
using namespace std;
 
class Cmp
{
public:
	Cmp(bool reverse) : myReverse(reverse) {}
	bool operator()(string const &s1, string const &s2) const
	{
		if (myReverse)
			return s2<s1;
		else
			return s1<s2;
	}
private:
	bool myReverse;
};
 
void f(bool b)
{
	Cmp myCmp(b);
	map<string, string, Cmp> dico(myCmp);
	dico["chat"] = "cat";
	dico["souris"] = "mice";
 
	for(std::map<string, string, Cmp>::const_iterator it = dico.begin();
		it != dico.end();
		++it)
	{
		cout << it->first << "=>" << it->second << endl;
	}
}
 
int main()
{
	f(true);
	f(false);
}

Je ne sais pas ce que tu en penses mais je trouve beaucoup d'exercices du livre ambigüs (et ce n'est pas parce que c'est de l'anglais).

Je n'ai pas regardé en détail, vu que quand j'ai eu ce livre entre les mains, je n'étais plus vraiment leur public cible, mais ça ne me choquerait pas trop. Un vrai programme dans la vraie vie sera toujours mal défini, et aura plusieurs façon d'être obtenu. Je trouve donc des sujets un peu ouverts plus stimulants qu'autre chose.

[ptyxs]

ptyxs: J'ai aussi créé une deuxième map. Je n'avais pas regardé ton code avant, mais le reste de tes messages (qui parlait notamment de 2 maps simultanées). Je ne le donne pas. C'est quasiment un copier-coller du tien: 3 boucles for, map<int, vector<string> > ...
Avec ta deuxième méthode, tu répertories des fréquences sans qu'elles ne soient associées au moindre mot.

En ce qui concerne la deuxième méthode, tu as raison, le fait d'imprimer les fréquences qui ne correspondent à aucun mot n'est sans doute pas très souhaitable. On peut tout de même remédier à cela assez facilement, la version suivante évite cette maladresse et donne une sortie un peu différente mais qui me semble envisageable (il reste que, comme le signalait JolyLoic, l'algorithmique de cette deuxième méthode n'est par ailleurs pas très satisfaisante (dans la mesure où elle parcourt toute la map pour chaque nombre de lignes)) :

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
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main()	
{
  string s;
  map<string, int> counters; // store each word and an associated counter
 
  // read the input, keeping track of each word and how often we see it
  while (cin >> s)
    ++counters[s];
 
  int max_freq = 0;
  // trouver la plus grande valeur de counter (correspondant au  mot le plus fréquent) 
  for(map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it)  
    max_freq = max(max_freq, it->second);    
 
  for (int i = 1;  i<= max_freq;++i) { // on recherche les mots présents dans i lignes
    for (map<string, int>::iterator it = counters.begin(); it != counters.end(); ++it) {
      if (it->second == i) {
	cout << "Mot figurant dans : " << i << " lignes : ";
	cout << it->first << endl;
      } 
    }
  }
  return 0;
}