Conteneurs associatifs

Un conteneur associatif est un conteneur dans lequel les éléments peuvent être indexés par des objets, et non plus seulement par des entiers.
Vous allez donc ici voir les différents types de conteneurs associatifs proposés par la STL.

Pour cet exercice, vous modifierez les fichiers :
- chap-05/3-associatives/main.cpp
- chap-05/3-associatives/keys.h

La cible à compiler est c5-3-associatives.

Les sets (ensembles)

Un set est un conteneur dans lequel les éléments sont “indexés par eux-mêmes”. Il y a deux cas d’utilisation classiques d’un set:

  • disposer d’un conteneur qui ne peut contenir qu’une seule fois un même élément,
  • savoir si un conteneur contient ou non un élément très rapidement.

Dans la librairie standard, vous pouvez trouver std::set et std::unordered_set qui permettent de manipuler des sets. En analysant leur documentation, pouvez-vous identifier les différences principales entre ces deux classes ?

Solution

Dans les fichiers de l’exercice, on vous fournit deux classes ComparableDog et HashableDog. Ces deux classes sont pour le moment identique : elles contiennent deux attributs _name et _species.
Votre objectif sera d’ajouter les fonctions nécessaires pour utiliser ces classes dans des sets.

std::set

Pour pouvoir placer des éléments dans un set, nous avons dit qu’ils devaient être comparables. Le plus simple pour cela, c’est de créer un operator< pour la classe. Les opérateurs de comparaison peuvent être définis soit en tant que fonction-membre, soit en tant que fonction libre.

Fonction-membre :

class SomeClass
{
public:
    bool operator<(const SomeClass& other) const
    {
        return /* whether this and other are equal */;
    }
};

Fonction libre :

// SomeClass.h

class SomeClass
{
    ...
};

bool operator<(const SomeClass& a, const SomeClass& b);

// SomeClass.cpp

bool operator<(const SomeClass& a, const SomeClass& b)
{
    return /* whether a and b are equal */;
}

Notez bien que si vous voulez utiliser une fonction libre, vous devrez peut-être exposer vos attributs dans des getters ou déclarer operator< comme une fonction amie de la classe.

Commencez par définir un set contenant des ComparableDog dans la fonction main. Essayez de compiler. Jusque là, tout devrait bien se passer.
Instanciez maintenant une variable de type ComparableDog, et ajoutez-là à votre set.

Solution

Essayez à nouveau de compiler. Vos yeux devraient désormais commencer à saigner, ce qui est normal. Je vous rassure, avec un peu d’entraînement, cela n’arrivera plus.
Du coup, essuyez vos larmes et enfilez vos lunettes si vous en avez, et tentez d’identifier ce que le compilateur essaye de vous communiquer.

Solution

Implémentez ce qu’il manque pour que votre programme compile.

Solution

Créez maintenant une nouvelle instance de ComparableDog, différente de la première, et ajoutez-là au set.
Affichez le nombre d’éléments du set pour vérifier qu’il en contient maintenant 2.

Solution

Instanciez maintenant une copie de votre premier chien, et ajoutez-là à votre set.
Combien y a-t-il d’éléments dans le set après cette opération ? Pourquoi ?

Solution

std::unordered_set

Vous allez maintenant faire le même exercice, mais avec un std::unordered_set plutôt qu’un set.

Commencez par définir un unordered_set contenant des HashableDog dans la fonction main et essayez de compiler. Vous devriez vous retrouver avec un paquet d’erreurs.
Comme tout à l’heure, essayez d’identifier la cause de leur déclenchement.

Solution

Afin de rendre une classe hashable, il faut spécialiser une fonction de la librairie standard que l’on appelle hash. Pour ce faire, vous devez d’abord inclure le header <functional>, puis écrire le code suivant :

namespace std {

template <>
struct hash<ClassToMakeHashable>
{
    size_t operator()(const ClassToMakeHashable& c) const
    {
        return /* some value that can be computed from c */;
    } 
};

}

Ne vous posez pas trop de questions pour le moment sur la syntaxe du code ci-dessus. Vous pouvez directement le copier-coller à la fin du fichier keys.h, en remplaçant ClassToMakeHashable par le nom de votre classe. En ce qui concerne le contenu de la fonction, vous allez devoir générer un hash en combinant les hashs des attributs de la classe HashableDog.

Pour récupérer le hash d’une string, vous devez déclarer une variable de type std::hash<std::string>, puis appeler son operator() sur la string en question. Ca donne quelque chose comme ça :

std::hash<std::string> hash_fcn;
size_t                 hash_of_blablabla = hash_fcn("blablabla");

Vous pouvez ensuite combiner plusieurs valeurs de hash ensemble en utilisant des opérateurs binaires (^, +, *, ou n’importe quoi d’autres, ce n’est pas vraiment important du moment que vous renvoyer bien quelque chose à la fin) :

std::hash<std::string> hash_fcn;
size_t                 hash_final = hash_fcn("first") ^ hash_fcn("second") ^ hash_fcn("third");

Lorsqu’on défini un operator() dans une classe, il est ensuite possible d’utiliser les instances de cette classe comme des fonctions. C’est pour cela que ce genre d’objets est appelé foncteur.

Implémentez le contenu de hash<HashableDog>::operator().
Afin de pouvoir accéder aux attributs de HashableDog depuis cette fonction, vous pouvez les déplacer dans la partie publique.

Solution

Une fois que cela compile, refactorisez votre code pour remettre les attributs dans la partie privée.
Pour cela, définissez une fonction-membre publique get_hash dans la classe HashableDog, que vous appelerez depuis hash<HashableDog>::operator().

Solution

Instanciez maintenant une variable de type HashableDog, ajoutez-là à votre set et essayez de compiler.
Comme vous pouvez le voir, aujourd’hui, le compilateur de vous apprécie pas. Déterminez à partir des erreurs de compilation ce qu’il manque dans la classe HashableDog pour que le programme compile.

Solution

Ajoutez la fonction manquante (même signature que operator<) et vérifiez ensuite que tout fonctionne.

Solution

Vous pouvez ensuite essayer d’ajouter de nouveaux éléments dans votre unordered_set. Vous devriez avoir le même comportement qu’avec la classe set : les éléments sont ajoutés seulement s’ils n’apparaissent pas déjà dans le conteneur.

Les maps (dictionnaires)

Une map est un conteneur dans lequel chaque valeur est indexé par une clef. Dans la STL, vous pouvez trouver les classes std::map et std::unordered_map.

Les différences entre map et unordered_map sont exactement les mêmes que les différences entre set et unordered_set. D’ailleurs, std::[unordered_]map, c’est la même chose que std::[unordered_]set, si ce n’est que pour chaque élément du conteneur, on stocke une valeur en plus de la clef.
En particulier, vous retrouvez les mêmes contraintes sur le type des clefs :

  • opérateur de comparaison pour la clef d’une map,
  • fonction de hash et opérateur d’égalité pour la clef d’une unordered_map.

Vous allez maintenant définir une variable de type std::map<key, value> qui stocke pour chaque chien (= clef) le nom et prénom de son propriétaire (= valeur).
Quel type pouvez-vous utiliser pour la clef ? Pour la valeur, vous pouvez utiliser une std::pair<std::string, std::string> (n’hésitez pas à créer un alias).

Solution

Pour insérer des éléments dans une map, vous pouvez utiliser plein de fonctions différentes. Consultez la documentation pour trouver le nom de ces fonctions et identifiez leurs différences (comportement / syntaxe).

Solution

Essayez d’ajouter plusieurs éléments à votre map, en utilisant chacune de ces fonctions.

Solution

Que faut-il maintenant faire si vous souhaitez utiliser une unordered_map plutôt qu’une map ?

Solution