/* Fichier List_Entiers.cpp Explications : en classe Généralement c'est : list où T est un type ou une classe Ici T est le type entier : list ======================================================= C'est un exemple TECHNIQUE sur certaines manipulations de base d'une liste. ======================================================= DESSINEZ des schémas, observez l'exécution pour BIEN COMPRENDRE! ------ ------ ------ ------ ------ ------ | 25 | | 27 | | 36 | | etc | | 19 | |||||| ------ ------ ------ ------ ------ ------ ^ ^ | | liste.begin() liste.end() Un itérateur de liste (l'abrégé : il) permet souvent - de parcourir d'une liste du début vers la fin for (list::iterator il = liste.begin(); il != liste.end(); il++) - quand il positionne sur un élément *il est le "contenu" ( un entier, un pays, une station de métro, etc ...) - d'indiquer si OUI ou non on trouve un élément dans une liste - de supprimer un élément si on positionne un itérateur sur lui - d'insérer un nouvel élément ... - etc ... Malgré qu'on puisse travailler dans 2 sens, dans l'exemple on parcourt du début à la fin et dans ce sens on parle de liste "FIFO" si on ajoute à la fin de la liste Soit T le nom d'un type ou d'une classe, voici quelques manipulations avec le conteneur list : void list::push_back(const T& x) : insérer x après le dernier élément Ainsi, si on parcourt du début à la fin de la liste, dans cette direction, on considère "pratiquement" une liste FIFO void list::push_front(const T& x) : insérer x avant le premier élément Ainsi, si on parcourt du début à la fin de la liste, dans cette direction, on considère "pratiquement" une liste LIFO T& list::front() Le premier élément du conteneur T& list::back() Le dernier élément list::iterator list::insert( list::iterator p, const T& x) Insérer x avant p et retourne un itérateur positionnant vers la valeur insérée list::iterator list::erase( list::iterator p,) Supprimer l'élément positionné par p void sort() : trie la liste en ordre croissant etc ... Soit I un itérateur, on a quelques "algorithmes" suivants : I find(I début, I fin, T x) renvoie un itérateur positionnant vers la première occurence rencontrée entre [début, fin[ si trouvée, sinon positionnant vers fin Très souvent : list::iterator il = find(liste.begin(), liste.end(), aChercher); I min_element(I début, I fin) renvoie un itérateur positionnant sur l'élément le plus petit I max_element(I début, I fin) renvoie un itérateur positionnant sur l'élément le plus grand etc ... Préparé par LVN pour IFT 1166 */ #include // input-output stream : flot d'entrée-sortie #include #include #include #include #include using namespace std; // librairie standard void continuer() { cout << endl << endl << "Appuyez sur une lettre suivie de Entree " ; char lettre; cin >> lettre ; cout << endl << endl; } void afficher(list liste, string mess) { cout << "Contenu de la liste " << mess << " :\n"; cout << "Elle contient " << liste.size() << " entier(s) :\n"; for (list::iterator il = liste.begin(); il != liste.end(); il++) cout << setw(5) << *il ; cout << endl; } void chercher(int aChercher, list liste ) { list::iterator il = find(liste.begin(), liste.end(), aChercher); if (il != liste.end()) // on trouve la valeur recherchee cout << "L'iterateur il positionne vers l'element ayant la valeur " << *il << endl; else cout << aChercher << " n'existe pas\n"; } void supprimer(int aSupprimer, list & liste ) { list::iterator il = find(liste.begin(), liste.end(), aSupprimer); if (il != liste.end()) // on trouve la valeur a supprimer { cout << "L'iterateur il positionne vers l'element ayant la valeur " << *il << " et on le supprime" << endl; liste.erase(il); } else cout << aSupprimer << " n'existe pas (=> pas de suppression)\n"; } int main() { // A) déclarer : list liste; // la liste est vide au début // B) ajouter à la fin de la liste liste.push_back(25); // ajouter à la fin de la liste => ordre FIFO liste.push_back(27); liste.push_back(36); liste.push_back(25); liste.push_back(50); liste.push_back(25); liste.push_back(19); afficher(liste, "apres avoir ajoute 7 elements a la fin de la liste "); cout << "liste.front() vaut " << liste.front() << endl; cout << "liste.back() vaut " << liste.back() << endl; continuer(); // C) modifications : // doubler la valeur du premier élément liste.front() *= 2; // soustraire la valeur du dernier élément de 6 liste.back() -= 6; // diviser la valeur de 3 ième élément par 9 list::iterator il = liste.begin(); // positionner il au début de la liste // chercher à positionner il, si possible, vers le 3ième élément for (int n = 1 ; n < 3 && il != liste.end(); n++) il++; // modifier le contenu : if (il != liste.end()) *il /= 9; afficher(liste, "apres ces modifications"); continuer(); // D) recherche d'un élément (notez que l'opérateur == existe déjà pour le type int) : chercher(27, liste); chercher(777, liste); continuer(); // E) chercher puis supprimer si trouvé liste.remove(4); liste.remove(4567); liste.remove(3399); afficher(liste, "apres ces suppressions"); continuer(); // F) insérer quelques valeurs : liste.insert(liste.begin(), 999); // ajouter au tout début liste.insert(liste.end(), 333); // ajouter à la toute fin // ajouter 765 avant le 4ième élément il = liste.begin(); // positionner il au début de la liste for(int k = 1; k < 4 && il != liste.end(); k++) il++; if (il != liste.end()) liste.insert(il, 765); // ajouter avant le 4ième élément afficher(liste, "apres ces insertions"); continuer(); // G) rechercher puis supprimer /* la recherche fonctionne car l'opérateur == existe pour les entiers (liste d'entiers) */ supprimer(999, liste); supprimer(777, liste); supprimer( 50, liste); afficher(liste, "apres ces suppressions"); continuer(); // H) quelques algorithmes de base : il = min_element(liste.begin(), liste.end()); cout << "plus petite valeur de la liste : " << *il << endl ; il = max_element(liste.begin(), liste.end()); cout << "plus grande valeur de la liste : " << *il << endl ; int nbFois = count(liste.begin(), liste.end(), 25); cout << "On rencontre 25 " << nbFois << " fois\n"; // I) trier : notez que l'opérateurs < est bien défini pour les entiers (int) liste.sort(); afficher(liste, "apres le tri"); int valeur ; do { cout << "Insertion en gardant la liste triée : quelle valeur ? " ; cin >> valeur; for(il = liste.begin(); il != liste.end(); il++) if ( *il > valeur ) break; liste.insert(il, valeur); afficher(liste, "apres cette insertion"); } while(valeur >= 0); bool trouve = binary_search(liste.begin(), liste.end(), 25); if (trouve) cout << "On trouve 25\n"; trouve = binary_search(liste.begin(), liste.end(), 12345); if (trouve) cout << "On trouve 12345\n"; else cout << "On ne trouve pas 12345\n"; continuer(); return 0; } /* Exécution: Contenu de la liste apres avoir ajoute 7 elements a la fin de la liste : Elle contient 7 entier(s) : 25 27 36 25 50 25 19 liste.front() vaut 25 liste.back() vaut 19 Appuyez sur une lettre suivie de Entree k Contenu de la liste apres ces modifications : Elle contient 7 entier(s) : 50 27 4 25 50 25 13 Appuyez sur une lettre suivie de Entree k L'iterateur il positionne vers l'element ayant la valeur 27 777 n'existe pas Appuyez sur une lettre suivie de Entree k Contenu de la liste apres ces suppressions : Elle contient 6 entier(s) : 50 27 25 50 25 13 Appuyez sur une lettre suivie de Entree k Contenu de la liste apres ces insertions : Elle contient 9 entier(s) : 999 50 27 765 25 50 25 13 333 Appuyez sur une lettre suivie de Entree k L'iterateur il positionne vers l'element ayant la valeur 999 et on le supprime 777 n'existe pas (=> pas de suppression) L'iterateur il positionne vers l'element ayant la valeur 50 et on le supprime Contenu de la liste apres ces suppressions : Elle contient 7 entier(s) : 27 765 25 50 25 13 333 Appuyez sur une lettre suivie de Entree k plus petite valeur de la liste : 13 plus grande valeur de la liste : 765 On rencontre 25 2 fois Contenu de la liste apres le tri : Elle contient 7 entier(s) : 13 25 25 27 50 333 765 Insertion en gardant la liste triÚe : quelle valeur ? 40 Contenu de la liste apres cette insertion : Elle contient 8 entier(s) : 13 25 25 27 40 50 333 765 Insertion en gardant la liste triÚe : quelle valeur ? 15 Contenu de la liste apres cette insertion : Elle contient 9 entier(s) : 13 15 25 25 27 40 50 333 765 Insertion en gardant la liste triÚe : quelle valeur ? -6 Contenu de la liste apres cette insertion : Elle contient 10 entier(s) : -6 13 15 25 25 27 40 50 333 765 On trouve 25 On ne trouve pas 12345 Appuyez sur une lettre suivie de Entree k */