Cours de C/C++
Précédent	Chapitre 17. Les conteneurs	Suivant

17.3. Les conteneurs associatifs

Contrairement aux séquences, les conteneurs associatifs sont capables d'identifier leurs éléments à l'aide de la valeur de leur clef. Grâce à ces clefs, les conteneurs associatifs sont capables d'effectuer des recherches d'éléments de manière extrêmement performante. En effet, les opérations de recherche se font généralement avec un coût logarithmique seulement, ce qui reste généralement raisonnable même lorsque le nombre d'éléments stockés devient grand. Les conteneurs associatifs sont donc particulièrement adaptés lorsqu'on a besoin de réaliser un grand nombre d'opération de recherche.

La librairie standard distingue deux types de conteneurs associatifs : les conteneurs qui différencient la valeur de la clef de la valeur de l'objet lui-même et les conteneurs qui considèrent que les objets sont leur propre clef. Les conteneurs de la première catégorie constituent ce que l'on appelle des associations car ils permettent d'associer des clefs aux valeurs des objets. Les conteneurs associatifs de la deuxième catégorie sont appelés quant à eux des ensembles, en raison du fait qu'ils servent généralement à indiquer si un objet fait partie ou non d'un ensemble d'objets. On ne s'intéresse dans ce cas pas à la valeur de l'objet, puisqu'on la connaît déjà si on dispose de sa clef, mais plutôt à son appartenance ou non à un ensemble donné.

Si tous les conteneurs associatifs utilisent la notion de clef, tous ne se comportent pas de manière identique quant à l'utilisation qu'ils en font. Pour certains conteneurs, que l'on qualifie de conteneurs « à clefs uniques », chaque élément contenu doit avoir une clef qui lui est propre. Il est donc impossible d'insérer plusieurs éléments distincts avec la même clef dans ces conteneurs. En revanche, les conteneurs associatif dits « à clefs multiples » permettent l'utilisation d'une même valeur de clef pour plusieurs objets distincts. L'opération de recherche d'un objet à partir de sa clef peut donc, dans ce cas, renvoyer plus d'un seul objet.

La librairie standard fournit donc quatre types de conteneurs au total, selon que ce sont des associations ou des ensembles, et selon que ce sont des conteneurs associatifs à clefs multiples ou non. Les associations à clefs uniques et à clefs multiple sont implémentées respectivement par les classes template map et multimap, et les ensembles à clefs uniques et à clefs multiples par les classes template set et multiset. Cependant, bien que ces classes se comportent de manière profondément différentes, elles fournissent les mêmes méthodes permettant de les manipuler. Les conteneurs associatifs sont donc moins hétéroclites que les séquences, et leur manipulation en est de beaucoup facilitée.

Les sections suivantes présentent les différentes fonctionnalités des conteneurs associatifs dans leur ensemble. Les exemples seront donnés en utilisant la plupart du temps la classe template map, car c'est certainement la classe la plus utilisée en pratique en raison de sa capacité à stocker et à retrouver rapidement des objets identifiés de manière unique par un identifiant. Cependant, certains exemples utiliseront des conteneurs à clefs multiples afin de bien montrer les rares différences qui existent entre les conteneurs à clefs uniques et les conteneurs à clefs multiples.

17.3.1. Généralités et propriétés de base des clefs

La contrainte fondamentale que les algorithmes des conteneurs associatifs imposent est qu'il existe une relation d'ordre pour le type de donnée utilisé pour les clefs des objets. Cette relation peut être définie soit implicitement par un opérateur d'infériorité, soit par un foncteur que l'on peut spécifier en tant que paramètre template des classes des conteneurs.

Alors que l'ordre de la suite des éléments stockés dans les séquences est très important, ce n'est pas le cas avec les conteneurs associatifs, car ceux-ci se basent exclusivement sur l'ordre des clefs des objets. En revanche, la librairie standard C++ garantit que le sens de parcours utilisé par les itérateurs des conteneurs associatifs est non décroissant sur les clefs des objets itérés. Cela signifie que le test d'infériorité strict entre la clef de l'élément suivant et la clef de l'élément courant est toujours faux, ou, autrement dit, l'élément suivant n'est pas plus petit que l'élément courant.

Note : Attention, cela ne signifie aucunement que les éléments sont classés dans l'ordre croissant des clefs. En effet, l'existence d'un opérateur d'infériorité n'implique pas forcément celle d'un opérateur de supériorité d'une part, et deux valeurs comparables par cet opérateur ne le sont pas forcément par l'opérateur de supériorité. L'élément suivant n'est donc pas forcément plus grand que l'élément courant. En particulier, pour les conteneurs à clefs multiples, les clefs de deux éléments successifs peuvent être égales.
En revanche, le classement utilisé par les itérateurs des conteneurs à clefs uniques est plus fort, puisque dans ce cas, on n'a pas à se soucier des clefs ayant la même valeur. La séquence des valeurs itérées est donc cette fois strictement croissante, c'est-à-dire que la clef de l'élément courant est toujours strictement inférieure à la clef de l'élément suivant.

Comme pour tous les conteneurs, le type des éléments stockés par les conteneurs associatifs est le type value_type. Cependant, contrairement aux séquences, ce type n'est pas toujours le type template par lequel le conteneur est paramétré. En effet, ce type est une paire contenant le couple de valeurs formé par la clef et par l'objet lui-même pour toutes les associations (c'est-à-dire pour les map et les multimap). Dans ce cas, les méthodes du conteneur qui doivent effectuer des comparaisons sur les objets se basent uniquement sur le champ first de la paire encapsulant le couple (clef, valeur) de chaque objet. Autrement dit, les comparaisons d'objets sont toujours définies sur les clefs, et jamais sur les objets eux-mêmes. Bien entendu, pour les ensembles, le type value_type est strictement équivalent au type template par lequel ils sont paramétrés.

Pour simplifier l'utilisation de leurs clefs, les conteneurs associatifs définissent quelques types complémentaires de ceux que l'on a déjà présentés dans la Section 17.1.2. Le plus important de ces types est sans doute le type key_type qui, comme son nom l'indique, représente le type des clefs utilisées par ce conteneur. Ce type constitue donc, avec le type value_type, l'essentiel des informations de typage des conteneurs associatifs. Enfin, les conteneurs définissent également des types de prédicats permettant d'effectuer des comparaisons entre deux clefs et entre deux objets de type value_type. Il s'agit des types key_compare et value_compare.

17.3.2. Construction et initialisation

Les conteneurs associatifs disposent de plusieurs surcharges de leurs constructeurs qui permettent de les créer et de les initialiser directement. De manière générale, ces constructeurs prennent tous deux paramètres afin de laisser au programmeur la possibilité de définir la valeur du foncteur qu'ils doivent utiliser pour comparer les clefs, ainsi qu'une instance de l'allocateur à utiliser pour les opérations mémoire. Comme pour les séquences, ces paramètres disposent de valeurs par défaut, si bien qu'en général il n'est pas nécessaire de les préciser.

Hormis le constructeur de copie et le constructeur par défaut, les conteneurs associatifs fournissent un troisième constructeur permettant de les initialiser à partir d'une série d'objets. Ces objets sont spécifiés par deux itérateurs, le premier indiquant le premier objet à insérer dans le conteneur et le deuxième l'itérateur référençant l'élément suivant le dernier élément à insérer. L'utilisation de ce constructeur est semblable au constructeur du même type défini pour les séquences et ne devrait donc pas poser de problème particulier.

Exemple 17-9. Construction et initialisation d'une association simple

#include <iostream>
#include <map>
#include <list>

using namespace std;

int main(void)
{
    typedef map<int, char *> Int2String;
    // Remplit une liste d'éléments pour ces maps :
    typedef list<pair<int, char *> > lv;
    lv l;
    l.push_back(lv::value_type(1, "Un"));
    l.push_back(lv::value_type(2, "Deux"));
    l.push_back(lv::value_type(5, "Trois"));
    l.push_back(lv::value_type(6, "Quatre"));
    // Construit une map et l'initialise avec la liste :
    Int2String i2s(l.begin(), l.end());
    // Affiche le contenu de la map :
    Int2String::iterator i = i2s.begin();
    while (i != i2s.end())
    {
        cout << i->second << endl;
        ++i;
    }
    return 0;
}

Note : Contrairement aux séquences, les conteneurs associatifs ne disposent pas de méthode assign permettant d'initialiser un conteneur avec des objets provenant d'une séquence ou d'un autre conteneur associatif. En revanche, ils disposent d'un constructeur et d'un opérateur de copie.

17.3.3. Ajout et suppression d'éléments

Du fait de l'existence des clefs, les méthodes d'insertion et de suppression des conteneurs associatifs sont légèrement différentes de celles des séquences. De plus, elles n'ont pas tout à fait la même signification. En effet, les méthodes d'insertion des conteneurs associatifs ne permettent pas, contrairement à celles des séquences, de spécifier l'emplacement où un élément doit être inséré puisque l'ordre des éléments est imposé par la valeur de leur clef. Les méthodes d'insertion des conteneurs associatifs sont présentées ci-dessous :

iterator insert(iterator i, const value_type &valeur): Insère la valeur valeur dans le conteneur. L'itérateur i indique l'emplacement probable dans le conteneur où l'insertion doit être faite. Cette méthode peut donc être utilisée pour les algorithmes qui connaissent déjà plus ou moins l'ordre des éléments qu'ils insèrent dans le conteneur afin d'optimiser les performances du programme. En général, l'insertion se fait avec une complexité de ln(N) (où N est le nombre d'éléments déjà présents dans le conteneur). Toutefois, si l'élément est inséré après l'itérateur i dans le conteneur, la complexité est constante. L'insertion se fait systématiquement pour les conteneurs à clefs multiples, mais peut ne pas avoir lieu si un élément de même clef que celui que l'on veut insérer est déjà présent pour les conteneurs à clefs uniques. Dans tous les cas, la valeur retournée est un itérateur référençant l'élément inséré ou l'élément ayant la même clef que l'élément à insérer.
void insert(iterator premier, iterator dernier): Insère les éléments de l'intervalle défini par les itérateurs premier et dernier dans le conteneur. La complexité de cette méthode est n×ln(n+N) en général, où N est le nombre d'éléments déjà présents dans le conteneur et n est le nombre d'éléments à insérer. Toutefois, si les éléments à insérer sont classés dans l'ordre de l'opérateur de comparaison utilisé par le conteneur, l'insertion se fait avec un coût proportionnel au nombre d'éléments à insérer.
pair<iterator, bool> insert(const value_type &valeur): Insère ou tente d'insérer un nouvel élément dans un conteneur à clefs uniques. Cette méthode renvoie une paire contenant l'itérateur référençant cet élément dans le conteneur et un booléen indiquant si l'insertion a effectivement eu lieu. Cette méthode n'est définie que pour les conteneurs associatifs à clefs uniques (c'est-à-dire les map et les set). Si aucun élément du conteneur ne correspond à la clef de l'élément passé en paramètre, cet élément est inséré dans le conteneur et la valeur renvoyée dans le deuxième champ de la paire vaut true. En revanche, si un autre élément utilisant cette clef existe déjà dans le conteneur, aucune insertion n'a lieu et le deuxième champ de la paire renvoyée vaut alors false. Dans tous les cas, l'itérateur stocké dans le premier champ de la valeur de retour référence l'élément inséré ou trouvé dans le conteneur. La complexité de cette méthode est logarithmique.
iterator insert(const value_type &valeur): Insère un nouvel élément dans un conteneur à clefs multiples. Cette insertion se produit qu'il y ait déjà ou non un autre élément utilisant la même clef dans le conteneur. La valeur retournée est un itérateur référençant le nouvel élément inséré. Vous ne trouverez cette méthode que sur les conteneurs associatifs à clefs multiples, c'est-a-dire sur les multimap et les multiset. La complexité de cette méthode est logarithmique.

Comme pour les séquences, la suppression des éléments des conteneurs associatifs se fait à l'aide des surcharges de la méthode erase. Les différentes versions de cette méthode sont indiquées ci-dessous :

void erase(iterator i): Permet de supprimer l'élément référencé par l'itérateur i. Cette opération a un coût amorti constant car aucune recherche n'est nécessaire pour localiser l'élément.
void erase(iterator premier, iterator dernier): Supprime tous les éléments de l'intervalle défini par les deux itérateurs premier et dernier. La complexité de cette opération est ln(N)+n, où N est le nombre d'éléments du conteneur avant suppression et n est le nombre d'éléments qui seront supprimés.
size_type erase(key_type clef): Supprime tous les éléments dont la clef est égale à la valeur passée en paramètre. Cette opération a pour complexité ln(N)+n, où N est le nombre d'éléments du conteneur avant suppression et n est le nombre d'éléments qui seront supprimés. Cette fonction retourne le nombre d'éléments effectivement supprimés. Ce nombre peut être nul si aucun élément ne correspond à la clef fournie en paramètre, ou valoir 1 pour les conteneurs à clefs uniques, ou être supérieur à 1 pour les conteneurs à clefs multiples.

Les conteneurs associatifs disposent également, tout comme les séquences, d'une méthode clear permettant de vider complètement un conteneur. Cette opération est réalisée avec un coût proportionnel au nombre d'éléments se trouvant dans le conteneur.

Exemple 17-10. Insertion et suppression d'éléments d'une association

#include <iostream>
#include <map>

using namespace std;

typedef map<int, char *> Int2String;

void print(Int2String &m)
{
    Int2String::iterator i = m.begin();
    while (i != m.end())
    {
        cout << i->second << endl;
        ++i;
    }
    return ;
}

int main(void)
{
    // Construit une association Entier -> Chaîne :
    Int2String m;
    // Ajoute quelques éléments :
    m.insert(Int2String::value_type(2, "Deux"));
    pair<Int2String::iterator, bool> res =
        m.insert(Int2String::value_type(3, "Trois"));
    // On peut aussi spécifier un indice sur
    // l'emplacement où l'insertion aura lieu :
    m.insert(res.first,
        Int2String::value_type(5, "Cinq"));
    // Affiche le contenu de l'association :
    print(m);
    // Supprime l'élément de clef 2 :
    m.erase(2);
    // Supprime l'élément "Trois" par son itérateur :
    m.erase(res.first);
    print(m);
    return 0;
}

17.3.4. Fonctions de recherche

Les fonctions de recherche des conteneurs associatifs sont puissantes et nombreuses. Ces méthodes sont décrites ci-dessous :

iterator find(key_type clef): Renvoie un itérateur référençant un élément du conteneur dont la clef est égale à la valeur passée en paramètre. Dans le cas des conteneurs à clefs multiples, l'itérateur renvoyé référence un des éléments dont la clef est égale à la valeur passée en paramètre. Attention, ce n'est pas forcément le premier élément du conteneur vérifiant cette propriété. Si aucun élément ne correspond à la clef, l'itérateur de fin du conteneur est renvoyé.
iterator lower_bound(key_type clef): Renvoie un itérateur sur le premier élément du conteneur dont la clef est égale à la valeur passée en paramètre. Les valeurs suivantes de l'itérateur référenceront les éléments suivants dont la clef est supérieure ou égale à la clef de cet élément.
iterator upper_bound(key_type clef): Renvoie un itérateur sur l'élément suivant le dernier élément dont la clef est égale à la valeur passée en paramètre. S'il n'y a pas de tel élément, c'est-à-dire si le dernier élément du conteneur utilise cette valeur de clef, renvoie l'itérateur de fin du conteneur.
pair<iterator, iterator> equal_range(key_type clef): Renvoie une paire d'itérateurs égaux respectivement aux itérateurs renvoyés par les méthodes lower_bound et upper_bound. Cette paire d'itérateurs référence donc tous les éléments du conteneur dont la clef est égale à la valeur passée en paramètre.

Exemple 17-11. Recherche dans une association

#include <iostream>
#include <map>

using namespace std;

int main(void)
{
    // Déclare une map à clefs multiples :
    typedef multimap<int, char *> Int2String;
    Int2String m;
    // Remplit la map :
    m.insert(Int2String::value_type(2, "Deux"));
    m.insert(Int2String::value_type(3, "Drei"));
    m.insert(Int2String::value_type(1, "Un"));
    m.insert(Int2String::value_type(3, "Three"));
    m.insert(Int2String::value_type(4, "Quatre"));
    m.insert(Int2String::value_type(3, "Trois"));
    // Recherche un élément de clef 4 et l'affiche :
    Int2String::iterator i = m.find(4);
    cout << i->first << " : " << i->second << endl;
    // Recherche le premier élément de clef 3 :
    i = m.lower_bound(3);
    // Affiche tous les éléments dont la clef vaut 3 :
    while (i != m.upper_bound(3))
    {
        cout << i->first << " : " << i->second << endl;
        ++i;
    }
    // Effectue la même opération, mais de manière plus efficace
    // (upper_bound n'est pas appelée à chaque itération) :
    pair<Int2String::iterator, Int2String::iterator> p =
        m.equal_range(3);
    for (i = p.first; i != p.second; ++i)
    {
        cout << i->first << " : " << i->second << endl;
    }
    return 0;
}

Note : Il existe également des surcharges const pour ces quatre méthodes de recherche afin de pouvoir les utiliser sur des conteneurs constants. Ces méthodes retournent des valeurs de type const_iterator au lieu des itérateurs classiques, car il est interdit de modifier les valeurs stockées dans un conteneur de type const.
La classe template map fournit également une surcharge pour l'opérateur d'accès aux membres de tableau []. Cet opérateur renvoie la valeur de l'élément référencé par sa clef et permet d'obtenir directement cette valeur sans passer par la méthode find et un déréférencement de l'itérateur ainsi obtenu. Cet opérateur insère automatiquement un nouvel élément construit avec la valeur par défaut du type des éléments stockés dans la map si aucun élément ne correspond à la clef fournie en paramètre. Contrairement à l'opérateur [] des classes vector et deque, cet opérateur ne renvoie donc jamais l'exception out_of_range.

Enfin, les conteneurs associatifs disposent d'une méthode count qui renvoie le nombre d'éléments du conteneur dont la clef est égale à la valeur passée en premier paramètre. Cette méthode retourne donc une valeur du type size_type du conteneur, valeur qui peut valoir 0 ou 1 pour les conteneurs à clefs uniques et n'importe quelle valeur pour les conteneurs à clefs multiples. La complexité de cette méthode est ln(N)+n, où N est le nombre d'éléments stockés dans le conteneur et n est le nombre d'éléments dont la clef est égale à la valeur passée en paramètre. Le premier terme provient en effet de la recherche du premier élément disposant de cette propriété, et le deuxième des comparaisons qui suivent pour compter les éléments désignés par la clef.

Note : Les implémentations de la librairie standard utilisent généralement la structure de données des arbres rouges et noirs pour implémenter les conteneurs associatifs. Cette structure algorithmique est une forme d'arbre binaire équilibré, dont la hauteur est au plus le logarithme binaire du nombre d'éléments contenus. Ceci explique les performances des conteneurs associatifs sur les opérations de recherche.

Précédent	Sommaire	Suivant
Les séquences	Niveau supérieur	Les algorithmes