/* IFT1169 - tp#4 - exercice 03 - 08-avril -2006 v1.00 M.Lokbani - idée de Phil ajustée pour gcc 3.4.2 Description: Un exemple d'utilisation des hash_map. Après avoir compilé le programme, pour tester son fonctionnement faire la commande suivante: (Linux) cat test.txt | tp4exo3.exe (Windows) type test.txt | tp4exo3.exe La description de la classe hash_map, ses différentes méthodes, ainsi que d'autres exemples associés à cette classe sont disponibles à cette adresse url: http://www.sgi.com/tech/stl/hash_map.html Répondre aux questions suivantes: -------------------------------- 1) Expliquer ligne par ligne les instructions du programme. 2) Expliquer ce que ce programme essaye de réaliser (à quoi sert-il exactement?) But: illustrer les STLs de C++ pour sensibiliser au fait que le traitement de grandes quantites necessite parfois des languages un peu plus adaptes que des shell scripts Objet: lit un flux de mots depuis l'entree standard et compte la frequence de chacun des types. Affiche les types par ordre decroissant de frequence. Comment: on suppose qu'il y a un mot par ligne, pas d'espace dans le mot. le code n'est pas optimise, car on pourrait preciser la taille attendue de la hash_table, ce qui limite ses aggrandissements dynamiques (couteux) 3) Pourquoi est-il nécessaire (obligatoire) de définir le functeur de la ligne 67 de la structure "StrHash". 4) Les lignes 99-103: Pourquoi fallait-il utiliser une structure intermédiaire pour pouvoir effectuer un tri par ordre décroissant? // on tri par ordre decroissant de frequence // comme un hash_map ne le permet pas, on passe par une structure intermediaire de pointeurs // sur les donnees a trier 5) Bonus (1 point si vous répondez à toute la question): Ajouter à la ligne 98: a) Afficher en sortie le nombre de buckets utilisées par "chaines". cout << "Nbre de buq: " << chaines.bucket_count() << endl; b) Afficher en sortie pour chaque élément du conteneur "chaines": "la clé", la valeur de hachage de cette clé, et le numéro de bucket où elle se trouve (elle est située dans quelle bucket). StrHash X; for (Fr_Map::const_iterator itt = chaines.begin(); itt != chaines.end(); itt++){ cout << "La cle: " << itt->first << " a une valeur de hachage: " << X(itt->first) << \ " et sera situé dans lquelle bucket " << (X(itt->first) % chaines.bucket_count()) << endl; } */ #include #include #include #include using namespace __gnu_cxx; using namespace std; // definit la fonction de hachage, et de comparaison de deux cles struct StrHash { hash SH; size_t operator() (const string& s) const { return SH(s.c_str()); } bool operator() (const string& s1, const string& s2) const { return (strcmp(s1.c_str(), s2.c_str()) == 0) ; } }; // raccourcis notationels typedef hash_map Fr_Map; typedef vector triesFr_Map; // le critere de tri du map struct TriMap { bool operator()(const Fr_Map::const_iterator& it1,const Fr_Map::const_iterator& it2) const { return (it1->second > it2->second) || ((it1->second == it2->second) && (it1->first < it2->first)); } }; // la veritable structure qui contient les frequences static Fr_Map chaines; int main(int argc, char *argv[]) { string mc; // contient le mot courant Fr_Map::iterator index; // un iterateur de travail sur la structure // lecture sur l'entree standard des mots, ligne par ligne while (cin >> mc) { index = chaines.find(mc); // existe-t-il ? if (index == chaines.end()) chaines.insert(make_pair(mc,1)); // non -> ajout else ++(index->second); // oui -> mise a jour de la frequence } // Question Bonus cout << "Nbre de buq: " << chaines.bucket_count() << endl; StrHash X; for (Fr_Map::const_iterator itt = chaines.begin(); itt != chaines.end(); itt++){ cout << "La cle: " << itt->first << " a une valeur de hachage: " << X(itt->first) << \ " et sera situé dans lquelle bucket " << (X(itt->first) % chaines.bucket_count()) << endl; } // on tri par ordre decroissant de frequence // comme un hash_map ne le permet pas, on passe par une structure intermediaire de pointeurs // sur les donnees a trier triesFr_Map tries; for (Fr_Map::const_iterator itr = chaines.begin(); itr != chaines.end(); ++itr) tries.push_back(itr); // recopie sort(tries.begin(), tries.end(), TriMap()); // trie // affichage des frequences et des mots for (triesFr_Map::const_iterator itr = tries.begin(); itr != tries.end(); ++itr) cout << (*itr)->second << '\t' << (*itr)->first << endl; return 0; }