/* 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?) 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? 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". 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). */ #include #include #include #include using namespace __gnu_cxx; using namespace std; 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) ; } }; typedef hash_map Fr_Map; typedef vector triesFr_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)); } }; static Fr_Map chaines; int main(int argc, char *argv[]) { string mc; Fr_Map::iterator index; while (cin >> mc) { index = chaines.find(mc); if (index == chaines.end()) chaines.insert(make_pair(mc,1)); else ++(index->second); } triesFr_Map tries; for (Fr_Map::const_iterator itr = chaines.begin(); itr != chaines.end(); ++itr) tries.push_back(itr); sort(tries.begin(), tries.end(), TriMap()); for (triesFr_Map::const_iterator itr = tries.begin(); itr != tries.end(); ++itr) cout << (*itr)->second << '\t' << (*itr)->first << endl; return 0; }