INF3105 — Structures de données et algorithmes
Été 2024
UQAM
Département d'informatique

Laboratoire 10 : Conteneurs de la bibliothèque standard de C++ et Héritage en C++

Lectures préalables

Objectifs

* Autrefois appelé Standard Template Library» ou sous l'acronyme «STL».

Équivalences

Le tableau suivant présent des équivalences entre les structures de données étudiées dans le cours INF3105 et les conteneurs de la bibliothèque standard de C++.

Structure de données Lib3105++ Bibliothèque standard de C++
Tableau Tableau std::vector
Pile Pile std::stack
File FIFO File std::queue
Liste chaînée Liste std::forward_list  (simplement chaînée)
std::list  (doublement chaînée)
Arbre binaire de recherche ArbreAVL std::set  (arbre rouge-noir)
Dictionnaire ArbreMap std::map

Tâches

Expérimentations

Transcrivez, compilez et expérimentez les programmes suivants.

lab10a.cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    vector<string> tab;
    tab.push_back("un"); // tab.ajouter("un");
    tab.push_back("deux");
    tab.push_back("trois");
    tab.push_back("quatre");
    tab.push_back("cinq");

    vector<string> tab2 = tab;
    for(vector<string>::iterator iter = tab2.begin(); iter != tab2.end(); ++iter)
       std::cout << *iter << std::endl;
    return 0;
}
Pour compiler et tester :
g++ lab10a.cpp
./a.out
ou
g++ -o lab10a lab10a.cpp
./lab10a

lab10b.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<string> tab;
    tab.push_back("un"); // tab.ajouter("un");
    tab.push_back("deux");
    tab.push_back("trois");
    tab.push_back("quatre");
    tab.push_back("cinq");

    sort(tab.begin(), tab.end());
    for(vector<string>::iterator iter = tab.begin(); iter != tab.end(); ++iter)
       std::cout << *iter << std::endl;

    return 0;
}

lab10c.cpp

#include <iostream>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    set<string> ensemble;
    ensemble.insert("un");
    ensemble.insert("deux");
    ensemble.insert("trois");
    ensemble.insert("quatre");
    ensemble.insert("cinq");

    for(set<string>::iterator iter = ensemble.begin(); iter != ensemble.end(); ++iter)
       std::cout << *iter << std::endl;

    return 0;
}

lab10d.cpp

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    map<int, string> dictionnaire;
    dictionnaire[1] = "un";
    dictionnaire[2] = "deux";
    dictionnaire[3] = "trois";
    dictionnaire[4] = "quatre";
    dictionnaire[5] = "cinq";

    cout << "dictionnaire[5]=" << dictionnaire[5] << std::endl;
    cout << "dictionnaire[1]=" << dictionnaire[1] << std::endl;
    cout << "dictionnaire[3]=" << dictionnaire[3] << std::endl;
    cout << "dictionnaire[2]=" << dictionnaire[2] << std::endl;
    cout << "dictionnaire[4]=" << dictionnaire[4] << std::endl;

    cout << "---" << std::endl;
    for(map<int, string>::iterator iter = dictionnaire.begin(); iter != dictionnaire.end(); ++iter) {
        cout << "dictionnaire[" << iter->first << "]=" << iter->second << std::endl;
    }

    return 0;
}

Résolution d'un problème

Afin d'éviter un trop grand nombre de gagnants au loto 6/49, Loto-Québec se réserve le droit de refuser la mise d'une combinaison si cette dernière a déjà été choisie MAX fois. Vous devez écrire un programme efficace permettant d'accepter ou de refuser des mises au loto 6/49. Pour simplifier, la limite est fixée à MAX=1 fois. Le programme principal est fourni ci-dessous. Les numéros d'une combinaison peuvent être entrés dans le désordre. Par exemple, si on entre les combinaisons « 31 05 15 11 20 12 » et « 5 11 12 15 20 31 », alors la deuxième doit être refusée. Vous n'avez pas à gérer les combinaisons invalides (ex.: « 1 1 2 3 4 5 »). 

#include <iostream>

class Combinaison {
  public:
    // À compléter

  private:
    // Attribut(s)



    // Opérateurs

    friend istream& operator >> (istream& is, Combinaison& c) {
        int nombre;
        for(int i = 0; i < 6; i++) {
            is >> nombre;

            // À compléter
        }
        return is;
    }

    friend bool operator<(const Combinaison& c1, const Combinaison& c2) {
        // À compléter
    }
};

int main() {
    ChoixStructureDeDonnees<Combinaison> mises;
    while(std::cin) {
        Combinaison combinaison_choisie;
        std::cin >> combinaison_choisie;
        if(mises.contient(combinaison_choisie))
            std::cout << "La combinaison est refusee!" << std::endl;
        else
            mises.ajouter(combinaison_choisie);
    }
    return 0;
}

Un objet Combinaison peut être représenté par un tableau natif à taille fixe, un std::vector, une std::list ou un std::set. Selon vous, quel est le meilleur choix?
Des tests sont disponibles dans tache2_tests.zip pour vous aidez à comparer les temps d'exécution des différentes structures de données.

Héritage et conteneurs en C++