Licence CC BY-NC

De nouvelles structures de données

Dernière mise à jour :

Lors de ce cours, nous avons eu l’occasion d’utiliser des données sous de nombreuses formes : types de base, chaînes de caractères, collections de données, etc. Cependant, toutes ces formes de données sont finalement assez rudimentaires, et on souhaite parfois avoir plus de souplesse dans la manière dont sont structurées nos données.

Dans ce chapitre, nous allons justement découvrir de nouvelles structures de données qui vont nous offrir plus de flexibilité dans nos programmes. Pour chaque structure, nous verrons comment elle s’utilise et en quoi elle est utile.

struct — Un agrégat de données

En C++, il existe une structure de données permettant de regrouper plusieurs données en un seul bloc. Dans leur grande originalité, elle s’appelle… structure. :)

Point de vocabulaire

À partir de maintenant, j’emploierai le terme « structure » pour désigner l’agrégat que nous allons introduire et l’expression « structure de données » pour désigner les formes complexes de données de manière générale.

Les structures sont très utiles pour regrouper des données qui ont un lien entre elles et travailler dessus de manière uniforme, et non sur chaque donnée séparément. Voyons un exemple concret avec un petit exercice.

Stockage d’informations personnelles1

Essayez de créer un programme qui demande des informations sur une personne et les stocke dans un fichier Prenom.Nom.csv sous le format suivant.

nom,prenom,sexe,age

En sortie, la console devrait ressembler à quelque chose comme ci-dessous.

Nom ? Lagrume
Prénom ? Clem
Sexe ? Fruit
Age ? 4

Ces données seront enregistrées dans le fichier Clem.Lagrume.csv.

Le programme va ensuite enregistrer ces informations dans un fichier Clem.Lagrume.csv, organisé comme suit.

Lagrume,Clem,Fruit,4

Bonne chance. :)

Correction
#include <fstream>
#include <iostream>
#include <limits>
#include <string>

template<typename T>
void entree_securisee(T & variable)
{
    while (!(std::cin >> variable))
    {
        std::cout << "Entrée invalide. Recommence." << std::endl;
        std::cin.clear();
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }
}

template <typename T, typename Predicat>
void entree_securisee(T & variable, Predicat predicat)
{
    while (!(std::cin >> variable) || !predicat(variable))
    {
        std::cout << "Entrée invalide. Recommence." << std::endl;
        std::cin.clear();
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }
}

void demander_infos(std::string & nom, std::string & prenom, std::string & sexe, int & age)
{
    std::cout << "Nom ? ";
    entree_securisee(nom);
    std::cout << "Prénom ? ";
    entree_securisee(prenom);
    std::cout << "Sexe ? ";
    entree_securisee(sexe);
    std::cout << "Age ? ";
    entree_securisee(age, [](int & age) { return age >= 0; });
}

std::string enregistrer_infos(std::string const & nom, std::string const & prenom, std::string const & sexe, int age)
{
    std::string nom_fichier { prenom + "." + nom + ".csv" };
    std::ofstream fichier { nom_fichier };
    fichier << nom << ',' << prenom << ',' << sexe << ',' << age;

    return nom_fichier;
}

int main()
{
    std::string nom { "" };
    std::string prenom { "" };
    std::string sexe { "" };
    int age { 0 };

    demander_infos(nom, prenom, sexe, age);
    auto nom_fichier = enregistrer_infos(nom, prenom, sexe, age);
    std::cout << std::endl << "Ces données seront enregistrées dans le fichier " << nom_fichier << std::endl;

    return 0;
}

Analyse de l’exercice

On a réussi à mener à bien l’exercice, mais on peut remarquer des pistes d’amélioration :

  • Les fonctions demander_infos et enregistrer_infos prennent beaucoup de paramètres. Mais, à la limite, c’est du détail.
  • Plus grave, si on ajoute une information sur une personne, il faudra modifier les prototypes de toutes nos fonctions ! Cela porte gravement atteinte à l’évolutivité de nos programmes.
  • Les données que l’on manipule sont liées et pourraient s’utiliser en tant qu’ensemble.

Introduction aux structures

La solution est justement d’utiliser une structure. Cela va nous permettre de créer un type, que l’on va par exemple appeler InformationsPersonnelles, regroupant l’intégralité des informations que l’on souhaite enregistrer. La syntaxe de création est la suivante.

struct identifiant
{
    *membres*
};
  • L’identifiant de la structure suit les mêmes règles de nommage que les identifiants de variables et de fonctions.
  • En termes de convention, nous suivrons une convention appelée CamelCase : on colle les mots en commençant chaque mot par une majuscule. Il en existe d’autres, mais nous utiliserons celle-là car elle permet facilement de distinguer les variables et les types.
  • La définition d’une structure doit se terminer par un point virgule. Il est fréquent de l’oublier.

Par exemple, une structure représentant les données personnelles d’une personne, dont on pourrait se servir dans l’exercice précédent, peut être définie comme suit.

struct InformationsPersonnelles
{
    std::string prenom;
    std::string nom;
    std::string sexe;
    int age;
};

Initialisation

Pour initialiser une structure, nous disposons de plusieurs façons de faire, qui ne vont pas vous surprendre, puisque nous les connaissons déjà pour les variables « classiques ».

// Initialisation par défaut.
InformationsPersonnelles infos {};

// Initialisation à des valeurs choisies.
InformationsPersonnelles infos { "Clem", "Lagrume", "Fruit", 4 };

// Autre syntaxe, utilisant le signe = comme en C.
InformationsPersonnelles infos = { "Clem", "Lagrume", "Fruit", 4 };

Notez que, lorsqu’on initialise avec des valeurs choisies, il faut les donner dans l’ordre dans lequel elles sont définies dans la structure. On ne peut pas donner un entier comme première valeur, si celle-ci est déclarée dans la définition comme étant une chaîne de caractères.

Voici les membres

Pour manipuler un membre, c’est-à-dire une variable appartenant à la structure, il suffit d’utiliser la syntaxe structure.membre, qui fonctionne tant en lecture qu’en écrire.

#include <iostream>
#include <string>

struct InformationsPersonnelles
{
    std::string prenom;
    std::string nom;
    std::string sexe;
    int age;
};

int main()
{
    InformationsPersonnelles info_clem { "Clem", "Lagrume", "Fruit", 5 };

    // Modification.
    info_clem.age = 4;
    // Utilisation en lecture.
    std::cout << "Je m'appelle " << info_clem.prenom << " " << info_clem.nom << " et j'ai " << info_clem.age << " ans." << std::endl;

    return 0;
}
Je m'appelle Clem Lagrume et j'ai 4 ans.

Bien entendu, comme toujours, la modification d’un membre n’est possible que si la variable n’est pas déclarée comme étant const.

Exercice

Sans plus attendre, modifions le code de l’exercice précédent pour utiliser une structure. C’est simple, modifiez-le pour utiliser une structure au lieu de se trimballer plein de variables.

Correction
#include <fstream>
#include <iostream>
#include <limits>
#include <string>


template<typename T>
void entree_securisee(T & variable)
{
    while (!(std::cin >> variable))
    {
        std::cout << "Entrée invalide. Recommence." << std::endl;
        std::cin.clear();
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }
}

template <typename T, typename Predicat>
void entree_securisee(T & variable, Predicat predicat)
{
    while (!(std::cin >> variable) || !predicat(variable))
    {
        std::cout << "Entrée invalide. Recommence." << std::endl;
        std::cin.clear();
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }
}

struct InformationsPersonnelles
{
    std::string prenom;
    std::string nom;
    std::string sexe;
    int age;
};

InformationsPersonnelles demander_infos()
{
    InformationsPersonnelles infos {};
    std::cout << "Nom ? ";
    entree_securisee(infos.nom);
    std::cout << "Prénom ? ";
    entree_securisee(infos.prenom);
    std::cout << "Sexe ? ";
    entree_securisee(infos.sexe);
    std::cout << "Age ? ";
    entree_securisee(infos.age, [](int & age) { return age >= 0; });

    return infos;
}

std::string enregistrer_infos(InformationsPersonnelles const & infos)
{
    std::string nom_fichier { infos.prenom + "." + infos.nom + ".csv" };
    std::ofstream fichier { nom_fichier };

    fichier << infos.nom << ',' << infos.prenom << ',' << infos.sexe << ',' << infos.age;

    return nom_fichier;
}

int main()
{
    auto infos = demander_infos();
    auto nom_fichier = enregistrer_infos(infos);
    std::cout << std::endl << "Ces données seront enregistrées dans le fichier " << nom_fichier << std::endl;

    return 0;
}

Et voilà ! Le code est plus lisible et plus évolutif. Vous pouvez essayer d’ajouter une information à enregistrer, par exemple la couleur préférée ou la date de naissance, et vous verrez que vous aurez uniquement des ajouts à faire. C’est un critère important d’évolutivité du code. En particulier, les prototypes des fonctions ne changeront pas, seules les implémentations changeront. Du point de vue de l’utilisation, c’est transparent, on ne voit rien de changé, tout le code les utilisant n’aura donc pas à être réécrit.

Raccourci

Remarquez que, maintenant qu’on peut directement renvoyer le résultat de demander_infos, on n’est plus obligé de prendre en paramètres des références vers les variables à modifier. Cela permet donc d’écrire, non sans élégance :

auto infos = demander_infos();

  1. En total accord avec le RGPD.

std::tuple — Une collection hétérogène

Les structures ne sont pas le seul moyen de représenter un ensemble de données de types variés. Il existe un autre outil nommé std::tuple, qui est une collection hétérogène de taille fixée. Hétérogène, car on peut stocker des informations de types différents (comme struct), mais dont la taille ne varie pas (comme std::array).

Fichier à inclure

Pour utiliser les tuples, il faut inclure le fichier <tuple>.

Déclaration

Pour préciser les types des différents éléments, on utilise une syntaxe bien connue. Par exemple, si on veut créer un tuple pour contenir des informations personnelles, comme dans l’exercice précédent, c’est très simple.

using namespace std::literals;
std::tuple { "Clem"s, "Lagrume"s, "Fruit"s, 4 };
N’oubliez pas le s

Je vous rappelle qu’avec les littéraux, pour que le type déduit soit bien std::string, vous devez rajouter le s après chaque littéral (ainsi que la ligne using namespace std::literals;). C’est ici obligatoire pour que l’on crée un std::tuple contenant des std::string et non des chaînes héritées du C.

On a aussi une fonction std::make_tuple permettant de créer un tuple en déduisant les types.

using namespace std::literals;
auto infos = std::make_tuple("Clem"s, "Lagrume"s, "Fruit"s, 4);

Accès aux éléments

Comme pour toute collection, il faut aussi être capable d’accéder aux éléments. Pour cela, on utilise la fonction std::get. Celle-ci prend entre chevrons l’indice de l’élément auquel on veut accéder.

#include <iostream>
#include <string>
#include <tuple>

int main()
{
    using namespace std::literals;
    auto informations = std::make_tuple("Clem"s, "Lagrume"s, "Fruit"s, 4);

    // Accès en lecture.
    std::cout << "Prénom : " << std::get<0>(informations) << std::endl;
    std::cout << "Âge : " << std::get<3>(informations) << std::endl;

    // Accès en écriture.
    std::get<3>(informations) += 1; // Clem a maintenant 5 ans !
    std::cout << "Âge maintenant : " << std::get<3>(informations) << std::endl;

    return 0;
}
Prénom : Clem
Âge : 4
Âge maintenant : 5

Dans le cas où tous les éléments d’un std::tuple ont un type unique, et seulement dans ce cas, on peut aussi y accéder en donnant à std::get le type de l’élément désiré.

#include <iostream>
#include <string>
#include <tuple>

int main()
{
    using namespace std::literals;
    // Prénom et salaire.
    auto informations = std::make_tuple("Clem"s, 50000);

    std::cout << "Prénom : " << std::get<std::string>(informations) << std::endl;
    std::cout << "Salaire : " << std::get<int>(informations) << "€" << std::endl;
         
    return 0;
}
Prénom : Clem
Salaire : 50000€

Si vous essayez d’utiliser cette syntaxe alors qu’il y a plusieurs éléments de même type, le code ne compilera tout simplement pas.

#include <iostream>
#include <string>
#include <tuple>

int main()
{
    using namespace std::literals;
    auto identite = std::make_tuple("Clem"s, "Lagrume"s);
    // Ne compile pas car il y a deux éléments de même type. Comment choisir ?
    std::get<std::string>(identite);
         
    return 0;
}

std::tuple et fonctions

On peut tout à fait créer une fonction qui renvoie un std::tuple. C’est même une astuce qu’on utilise pour contourner la limite qu’impose C++ de ne pouvoir retourner qu’une seule valeur à la fois. Il suffit de déclarer que la fonction renvoie un std::tuple et de préciser, entre chevrons, les types de ses éléments.

Notez, dans l’exemple suivant, la syntaxe alternative et concise pour renvoyer un std::tuple, introduite depuis C++17.

// Ligne nécessaire pour Visual Studio afin d'accéder à M_PI, la valeur de pi.
#define _USE_MATH_DEFINES

#include <cmath>
#include <iostream>
#include <string>
#include <tuple>

std::tuple<int, std::string> f()
{
    using namespace std::literals;
    // On retourne un std::tuple qui contient un entier et une chaîne de caractères.
    return std::make_tuple(20, "Clem"s);
}

std::tuple<double, double> g(double angle)
{
    // On retourne un std::tuple qui contient deux flottants.
    // Notez la nouvelle syntaxe à base d'accolades.
    return { std::cos(angle), std::sin(angle) };
}

int main()
{
    std::tuple resultats_scolaires = f();
    std::cout << "Tu t'appelles " << std::get<std::string>(resultats_scolaires) << " et tu as obtenu " << std::get<int>(resultats_scolaires) << " / 20." << std::endl;

    std::tuple calculs = g(M_PI / 2.);
    std::cout << "Voici le cosinus de PI / 2 : " << std::get<0>(calculs) << std::endl;
    std::cout << "Voici le sinus de PI / 2 : " << std::get<1>(calculs) << std::endl;

    return 0;
}
Tu t'appelles Clem et tu as obtenu 20 / 20.
Voici le cosinus de PI / 2 : 0
Voici le sinus de PI / 2 : 1

Équations horaires

Vous voulez un exemple concret d’utilisation des std::tuple ? Vous aimez la physique ? Vous allez être servi. Nous allons coder une fonction retournant les coordonnées (x;y)(x;y) d’un objet lancé à une vitesse v0v_0 et à un angle α\alpha, en fonction du temps tt.

Point de vocabulaire

C’est ce qu’on appelle l’équation horaire de l’objet. Cette notion est abordée, en France, au lycée en Terminale. Ne vous inquiétez pas si vous ne connaissez pas, nous n’allons pas du tout rentrer dans les détails.

Un cours de physique vous expliquera qu’on obtient la position de l’objet en fonction du temps tt grâce à deux équations.

{x(t)=v0.cosα.ty(t)=g.t22+v0.sinα.t\left\{\begin{aligned} x(t) &= v_0 \,.\, cos \, \alpha \,.\, t \\ y(t) &= -g \,.\, \dfrac{t^2}2 + v_0 \,.\, sin \, \alpha \,.\, t \end{aligned}\right.

Donc, si on traduit tout ça en C++, on obtient quelque chose comme ça.

// Ligne nécessaire pour Visual Studio afin d'accéder à M_PI, la valeur de pi.
#define _USE_MATH_DEFINES

#include <cmath>
#include <iostream>
#include <string>
#include <tuple>

std::tuple<double, double> equations_mouvement_temps(double vitesse_initiale, double angle, double t)
{
    // Accélération sur Terre.
    double const g { 9.80665 };
    double const x { vitesse_initiale * std::cos(angle) * t };
    double const y { (-g * (t * t) / 2.) + (vitesse_initiale * std::sin(angle) * t) };

    return { x, y };
}

int main()
{
    // Vitesse de 8 mètres par seconde.
    double const vitesse_initiale { 8.0 };
    // On tire à un angle de pi / 4, soit 45°.
    double const angle { M_PI / 4 };

    // On simule sur 10 secondes, avec un calcul toutes les 100 millisecondes.
    for (double t { 0.0 }; t < 10; t += 0.1)
    {
        std::tuple coordonnees { equations_mouvement_temps(vitesse_initiale, angle, t) };

        if (std::get<1>(coordonnees) < 0)
        {
            // On ne continue plus la simulation dès que y est au niveau du sol.
            break;
        }

        std::cout << "À l'instant t = " << t << ", on a : " << std::endl;
        std::cout << "x = " << std::get<0>(coordonnees) << std::endl;
        std::cout << "y = " << std::get<1>(coordonnees) << std::endl << std::endl;
    }

    return 0;
}

Pourquoi s’encombrer des tuples ? Que dois-je choisir ?

Il est vrai que std::tuple semble présenter plus d’inconvénients qu’autres choses. Le code n’est pas très lisible avec tous ces std::get. De plus, contrairement à une structure dont l’accès à un élément est clair (comme informations.prenom), il ne saute pas aux yeux que std::get<1>(informations) représente potentiellement un prénom.

En fait, chaque solution a ses avantages et ses inconvénients, et on va donc choisir en conséquence selon les situations.

  • Le tuple permet de rapidement avoir une collection hétérogène sans avoir à définir un nouveau type. Il est particulièrement utile lorsque l’on a besoin d’une collection hétérogène uniquement pour une portée locale, dans le corps d’une fonction par exemple. Par contre, la syntaxe d’utilisation, notamment pour l’accès aux éléments, est peu lisible.
  • La structure permet une plus grande expressivité, notamment par le fait que les éléments ont des noms. Elle est particulièrement adaptée pour une utilisation sur une portée plus globale.

En fait, le tuple est à la structure ce que la lambda est à la fonction, finalement. C++ vous laisse libre, c’est vous qui choisirez en fonction des cas.

std::unordered_map — Une table associative

Depuis le début de ce cours, nous avons vu les conteneurs std::vector, std::array et std::string. Nous avons également, très brièvement, survolé std::list. Maintenant, j’aimerais vous en présenter d’autres, qui sont un peu différents, mais très utiles.

Le premier conteneur se nomme std::unordered_map. Ce nom peut être traduit par « tableau associatif », « table associative » ou « carte associative », car son principe est d’associer une valeur à une clé. Ce principe, nous le connaissons déjà avec std::vector, qui associe une valeur quelconque à une clé entière. Ainsi, quand vous faites tableau[4], vous utilisez une clé de type entier et qui vaut 4. Grâce à std::unordered_map, nous avons le choix du type de la clé.

Fichier à inclure

Pour utiliser ce nouveau conteneur, pensez à inclure le fichier <unordered_map>.

Un dictionnaire de langue Zestienne

Imaginez que vous vouliez créer un dictionnaire. Comme pour la version papier, nous voulons associer un mot à un ensemble de phrases. En C++, on peut traduire ça par une std::unordered_map dont la clé est de type std::string, ainsi que la valeur. On précise le type de la clé et de la valeur entre chevrons, car notre conteneur utilise les templates.

#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    using namespace std::literals;

    // Notez que chaque élément ajouté est lui-même entre accolades {}.
    std::unordered_map<std::string, std::string> dictionnaire
    {
        // Ajout d'une clé 'Clem' avec sa valeur 'La mascotte du site Zeste de Savoir, toute gentille et tout mignonne.'
        { "Clem"s, "La mascotte du site Zeste de Savoir, toute gentille et toute mignonne."s },
        { "mehdidou99"s, "Un des auteurs du tutoriel C++."s },
        { "informaticienzero"s, "Un des auteurs du tutoriel C++."s },
        { "Taurre"s, "Un super validateur !"s },
        { "Arius"s, "Un membre super sympa mais qui mord."s },
        { "Gants de vaisselle"s, "Objets présents sur le site et dont personne ne sait pourquoi."s }
    };

    return 0;
}

Pour afficher le contenu de notre conteneur, on va récupérer les éléments un par un. On peut faire ça avec une simple boucle for, comme on en a l’habitude. Chaque élément est un std::pair<T, U>, où T est de même type que la clé et U de même type que la valeur. Ce type n’est rien d’autre qu’un cas particulier de tuple à deux valeurs uniquement.

Ce type fournit deux propriétés qui nous intéressent, qui sont first et second, renvoyant respectivement la clé et la valeur récupérée dans la std::unordered_map. On a donc maintenant toutes les informations pour écrire la boucle et afficher les éléments de notre tableau associatif.

#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    using namespace std::literals;

    std::unordered_map<std::string, std::string> dictionnaire
    {
        { "Clem"s, "La mascotte du site Zeste de Savoir, toute gentille et toute mignonne."s },
        { "mehdidou99"s, "Un des auteurs du tutoriel C++."s },
        { "informaticienzero"s, "Un des auteurs du tutoriel C++."s },
        { "Taurre"s, "Un super validateur !"s },
        { "Arius"s, "Un membre super sympa mais qui mord."s },
        { "Gants de vaisselle"s, "Objets présents sur le site et dont personne ne sait pourquoi."s }
    };

    for (auto const & paire : dictionnaire)
    {
        std::cout << "Clé : " << paire.first << std::endl;
        std::cout << "Valeur : " << paire.second << std::endl << std::endl;
    }

    return 0;
}
Clé : mehdidou99
Valeur : Un des auteurs du tutoriel C++.

Clé : Clem
Valeur : La mascotte du site Zeste de Savoir, toute gentille et toute mignonne.

Clé : informaticienzero
Valeur : Un des auteurs du tutoriel C++.

Clé : Taurre
Valeur : Un super validateur !

Clé : Arius
Valeur : Un membre super sympa mais qui mord.

Clé : Gants de vaisselle
Valeur : Objets présents sur le site et dont personne ne sait pourquoi.
Petite précision

Je vous ai expliqué ce qu’est std::pair, mais j’ai utilisé auto à la place. Le code est ainsi plus court et plus lisible. Vous êtes néanmoins libre d’écrire explicitement std::pair<std::string, std::string> si vous le souhaitez.

Toujours plus de clés

Bien entendu, si notre conteneur n’est pas déclaré comme const, il est possible de le modifier, lui ajouter ou lui supprimer des éléments. Voyez par vous-mêmes plusieurs exemples ci-dessous.

#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    using namespace std::literals;

    std::unordered_map<std::string, std::string> dictionnaire
    {
        { "Clem"s, "La mascotte du site Zeste de Savoir, toute gentille et toute mignonne."s },
        { "mehdidou99"s, "Un des auteurs du tutoriel C++."s },
        { "informaticienzero"s, "Un des auteurs du tutoriel C++."s },
        { "Taurre"s, "Un super validateur !"s },
        { "Arius"s, "Un membre super sympa mais qui mord."s },
        { "Gants de vaisselle"s, "Objets présents sur le site et dont personne ne sait pourquoi."s }
    };

    // Insertion avec la fonction 'insert'.
    dictionnaire.insert({ "C++"s, "Le langage que vous apprennez."s });

    // Plusieurs valeurs en même temps. Notez les doubles accolades {}.
    dictionnaire.insert({ { "Pacman++"s, "C'est un des avatars de mehdidou99."s }, { "Un truc"s, "Personne ne sait ce que c'est."s } });

    // Ajout d'une nouvelle paire avec les crochets.
    dictionnaire["nohar"] = "Un lama ancestral."s;

    // Utilisation des crochets pour modifier la valeur associée à une clé existante.
    dictionnaire["Taurre"] = "Un validateur vraiment cool !"s;
    // Accès en lecture.
    std::cout << "Qui est Taurre ? " << dictionnaire["Taurre"] << std::endl << std::endl;

    // Suppression par clé.
    dictionnaire.erase("Un truc"s);

    for (auto const & paire : dictionnaire)
    {
        std::cout << "Clé : " << paire.first << std::endl;
        std::cout << "Valeur : " << paire.second << std::endl << std::endl;
    }

    return 0;
}
Qui est Taurre ? Un validateur vraiment cool !

Clé : mehdidou99
Valeur : Un des auteurs du tutoriel C++.

Clé : C++
Valeur : Le langage que vous apprennez.

Clé : Clem
Valeur : La mascotte du site Zeste de Savoir, toute gentille et toute mignonne.

Clé : informaticienzero
Valeur : Un des auteurs du tutoriel C++.

Clé : Taurre
Valeur : Un validateur vraiment cool !

Clé : Arius
Valeur : Un membre super sympa mais qui mord.

Clé : Pacman++
Valeur : C'est un des avatars de mehdidou99.

Clé : Gants de vaisselle
Valeur : Objets présents sur le site et dont personne ne sait pourquoi.

Clé : nohar
Valeur : Un lama ancestral.

Cette clé est unique !

Abordons maintenant un point important de std::unordered_map, mais que j’ai passé sous silence. Il s’agit de l’unicité de la clé. Il ne peut y avoir qu’une seule valeur associée à une seule clé. Dit autrement, on ne peut pas assigner plusieurs valeurs à une même clé.

Quand on ajoute une nouvelle paire, il ne se passe rien de visible dans le cas où la clé existe déjà. C’est un peu gênant pour signaler l’erreur. Heureusement, la fonction insert retourne un std::pair contenant deux informations qui nous intéressent.

  • L’élément first est un itérateur sur l’élément inséré si la clé n’existait pas au préalable, ou sur l’élément correspondant à la clé si elle existe déjà. Cet itérateur est lui-même un std::pair, donc on accède à la clé avec first et à la valeur avec second.
  • L’élément second est un booléen indiquant si l’élément a été inséré (true) ou non (false).
#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    using namespace std::literals;

    std::unordered_map<std::string, double> constantes
    {
        { "pi"s, 3.14159 },
        { "e"s, 2.71828 }
    };

    auto paire_phi = constantes.insert({ "phi"s, 1.61803 });
    if (paire_phi.second)
    {
        std::cout << "La valeur de " << paire_phi.first->first << " a bien été ajoutée." << std::endl;
    }

    auto paire_pi = constantes.insert({ "pi"s, 3.0 });
    if (!paire_pi.second)
    {
        std::cout << "La clé " << paire_pi.first->first << " existe déjà et vaut " << paire_pi.first->second << "." << std::endl;
    }

    return 0;
}
La valeur de phi a bien été ajoutée.
La clé pi existe déjà et vaut 3.14159.

Dans le cas où vous souhaitez ajouter une valeur si elle n’existe pas, ou bien mettre à jour la valeur associée à une clé si celle-ci existe, utilisez la fonction insert_or_assign, qui fonctionne presque pareil. Elle renvoie une paire semblable, avec toujours le booléen signalant l’insertion (true) ou la mise à jour (false).

#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    using namespace std::literals;

    std::unordered_map<std::string, double> constantes
    {
        { "pi"s, 3.14159 },
        { "e"s, 2.0 }
    };

    auto paire_e = constantes.insert_or_assign("e"s, 2.71828);
    if (paire_e.second)
    {
        std::cout << "La valeur a bien été ajoutée." << std::endl;
    }
    else
    {
        std::cout << "La valeur a bien été mise à jour." << std::endl;
    }

    for (auto const & paire : constantes)
    {
        std::cout << "La constante " << paire.first << " vaut " << paire.second << "." << std::endl;
    }

    return 0;
}
La valeur a bien été mise à jour.
La constante pi vaut 3.14159.
La constante e vaut 2.71828.

Cherchez un élément

Comme l’accès à un élément par les crochets permet également d’ajouter une nouvelle paire clé / valeur, l’utiliser peut parfois être délicat. Voyez par vous-mêmes l’exemple suivant.

#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    using namespace std::literals;

    std::unordered_map<std::string, std::string> membres
    {
        { "mehdidou99"s, "Un auteur du cours C++."s },
        { "informaticienzero"s, "Un auteur du cours C++."s }
    };

    // Notez l'accent.
    std::string const pseudo { "informaticienzéro" };
    // ah, ça ne va pas afficher ce que vous attendiez.
    std::cout << "Qui est informaticienzero ? " << membres[pseudo] << std::endl;

    return 0;
}
Qui est informaticienzero ? 

Il existe heureusement une fonction find, qui attend une clé et qui renvoie un itérateur sur l’élément concerné si la clé existe, ou bien un itérateur sur la fin de la collection sinon.

#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    using namespace std::literals;

    std::unordered_map<std::string, std::string> membres
    {
        { "mehdidou99"s, "Un auteur du cours C++."s },
        { "informaticienzero"s, "Un auteur du cours C++."s }
    };

    // Notez l'accent.
    std::string const pseudo { "informaticienzéro" };
    if (membres.find(pseudo) != std::end(membres))
    {
        // On a trouvé le membre.
        std::cout << "Qui est informaticienzero ? " << membres[pseudo] << std::endl;
    }
    else
    {
        std::cout << "Ce membre n'existe pas." << std::endl;
    }

    return 0;
}
Ce membre n'existe pas.

Un exemple concret

Grâce à ce que nous savons, nous pouvons faire un petit programme qui compte les occurrences de chaque mot au sein d’une phrase. Il suffit d’avoir un tableau associatif avec std::string pour clé et int pour valeur.

#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>

void occurrences_mots(std::string const & phrase)
{
    std::istringstream iss { phrase };
    std::string mot {};

    std::unordered_map<std::string, int> occurences {};
    while (iss >> mot)
    {
        ++occurences[mot];
    }

    for (auto const & paire : occurences)
    {
        std::cout << "Le mot '" << paire.first << "' apparait " << paire.second << " fois." << std::endl;
    }
}

int main()
{
    occurrences_mots("Bonjour, ceci est un test avec une phrase qui est longue et est une phrase en français.");
    return 0;
}
Le mot 'Bonjour,' apparait 1 fois.
Le mot 'ceci' apparait 1 fois.
Le mot 'est' apparait 3 fois.
Le mot 'un' apparait 1 fois.
Le mot 'une' apparait 2 fois.
Le mot 'test' apparait 1 fois.
Le mot 'qui' apparait 1 fois.
Le mot 'avec' apparait 1 fois.
Le mot 'français.' apparait 1 fois.
Le mot 'phrase' apparait 2 fois.
Le mot 'longue' apparait 1 fois.
Le mot 'et' apparait 1 fois.
Le mot 'en' apparait 1 fois.

std::unordered_set — Représenter un ensemble

Le deuxième conteneur se nomme std::unordered_set. C’est la représentation en C++ d’un ensemble au sens mathématique du terme, c’est-à-dire un ensemble d’éléments du même type, où chacun n’est présent qu’une seule et unique fois. C’est un peu comme une table associative dans laquelle il n’y aurait que des clés et pas de valeur.

Fichier à inclure

Pour utiliser ce conteneur, il faut inclure le fichier d’en-tête <unordered_set>.

Inscription sur Zeste de Savoir

Sur le présent site, vous pouvez vous inscrire, mais il faut que votre pseudo soit unique. Vous ne pouvez donc pas réutiliser le pseudo de quelqu’un d’autre. On pourrait donc imaginer stocker les pseudos dans un std::unordered_set. Vous allez voir que l’utilisation de ce conteneur ressemble fortement à celle de std::unordered_map.

#include <iomanip>
#include <iostream>
#include <string>
#include <unordered_set>

void ajouter_membre(std::unordered_set<std::string> & membres, std::string const & pseudo)
{
    auto it = membres.insert(pseudo);
    if (it.second)
    {
        std::cout << "Bienvenu sur Zeste de Savoir, " << pseudo << "." << std::endl;
    }
    else
    {
        std::cout << "Désolé, le pseudo " << std::quoted(pseudo) << " est déjà pris." << std::endl;
    }
}

int main()
{
    std::unordered_set<std::string> pseudos { "mehdidou99", "informaticienzero" };

    // Ajouts.
    pseudos.insert("Dwayn");
    pseudos.insert("artragis");
    pseudos.insert("Taurre");

    ajouter_membre(pseudos, "gbdivers");
    ajouter_membre(pseudos, "informaticienzero");

    // Suppression.
    pseudos.erase("Dwayn");

    // Parcours for.
    for (auto const & cle : pseudos)
    {
        std::cout << cle << std::endl;
    }

    // Recherche de membres.
    if (pseudos.find("Taurre") != std::end(pseudos))
    {
        std::cout << "Taurre est un membre." << std::endl;
    }

    if (pseudos.find("Gabbro") == std::end(pseudos))
    {
        std::cout << "Le pseudo " << std::quoted("Gabbro") << " est libre." << std::endl;
    }

    return 0;
}

Comme vous le voyez, l’utilisation est très proche. La différence se trouve simplement dans l’absence de valeurs liées aux clés. Pour choisir entre les deux conteneurs, il faut simplement réfléchir à ce que vous voulez stocker. Un ensemble de clés uniques ? Choisissez std::unordered_set. Si vous devez associer à ces clés des valeurs, alors partez sur std::unordered_map.

Un peu d'ordre, voyons !

Ces deux conteneurs sont très utiles, mais comme vous l’avez remarqué, ils ne sont pas ordonnés. Si, par exemple, vous avez un std::unordered_set de chaînes de caractères, vous verrez qu’elles ne sont pas affichées dans l’ordre alphabétique.

#include <iostream>
#include <string>
#include <unordered_set>

int main()
{
    std::unordered_set<std::string> const mots { "Archive", "Base", "Conduite", "Développement", "Entrain" };

    for (auto const & mot : mots)
    {
        std::cout << mot << std::endl;
    }

    return 0;
}
Développement
Archive
Entrain
Conduite
Base

En interne, les clés sont ordonnées et triées, mais selon leur « hash ». Non, je n’ai pas fait de faute de français. Un hash est le résultat d’une fonction de hachage. En très bref, c’est une fonction qui transforme une donnée quelconque en une donnée de taille fixée. Pour notre conteneur, cela signifie qu’il ne va plus travailler avec des chaînes de caractères ou autres clés potentiellement grosses, mais avec une version de taille fixe et plus petite, ce qui est beaucoup plus rapide.

Il existe une version alternative des conteneurs std::unordered_map et std::unordered_set, qui n’ordonne pas les éléments selon le hash des clés mais directement avec les clés. Ces nouveaux conteneurs se nomment, respectivement, std::map et std::set.

Fichier à inclure

Pour les utiliser, il faut respectivement inclure les fichiers <map> et <set>.

En remplaçant std::unordered_set par sa version triée par clé dans l’exemple précédent, on obtient bien un affichage par ordre alphabétique.

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

int main()
{
    std::set<std::string> const mots { "Archive", "Base", "Conduite", "Développement", "Entrain" };

    for (auto const & mot : mots)
    {
        std::cout << mot << std::endl;
    }

    return 0;
}
Archive
Conduite
Base
Développement
Entrain

Du coup, la seule différence, c’est une question d’affichage et d’ordre ?

La structure interne et les algorithmes employés pour ajouter, supprimer ou chercher des éléments ne sont pas les mêmes. De manière générale, les versions non ordonnées sont plus rapides d’utilisation et ce sont celles qui sont utilisées dans 90% des cas. Les 10% restants se répartissent en deux points.

  • On veut conserver l’ordre des clés.
  • On a vraiment énormément de données (de l’ordre du million d’éléments), auquel cas la version non ordonnée est moins rapide que la version ordonnée, de part leur structure interne.

Leur utilisation est très semblable à leurs cousins non ordonnés, vous n’aurez donc aucun de mal à les manipuler. :)


En résumé

  • Les structures sont des agrégats de données permettant de lier et de manipuler plus aisément des données liées entre elles.
  • Les tuples sont des collections hétérogènes et fixées, qui permettent de lier des données entre elles sans créer pour autant de nouveau type.
  • Grâce aux tuples et aux structures, nous sommes en mesure de retourner plusieurs variables d’un coup.
  • Les std::unordered_map sont des tables associatives, qui permettent d’associer une clé de type quelconque à une valeur de type quelconque.
  • Les std::unordered_set sont des ensembles au sens mathématique du terme et permettent de stocker un ensemble de clés uniques.
  • Il existe des versions triées par clé de ces conteneurs, std::map et std::set, mais qui sont beaucoup plus lentes.