Un espace si dense
C++ STL

Conteneurs map et multimap

dimanche 18 juin 2006 par guillaume

La STL, standard template library est assez connue dans le monde du C++, pourtant, son utilisation est assez complexe (son débuggage assez horrible).

Bref, c’est un magnifique sujet de TROLL.

Pourtant, certaines fonctions optimisées en N Log(N) font l’unanimité.

Ici, je traiterais des conteneurs ’map’ assez proches des ’array’ du PHP

Le conteneur MAP

Map permet des associations clef-valeur.

ATTENTION : LES CLEFS de MAP sont UNIQUES (c’est l’idée que l’on s’en fait si on travaille avec des tableaux de type PHP)

L’itérateur

Dans le cas d’un vector, l’itérateur peut être avantageusement remplacé par un entier : on peut faire un :

au lieu de :

(c’est quand même moins simple et moins clair non ?).

Par contre, dans le cas des map, on est bien obligé d’y passer.

Le plus simple est de définir une fonction foreach qui sera utilisee par tout le monde :

C’est bien, mais pas avec un map, donc on va faire le notre

Néammoins, ce n’est pas sans poser de problèmes. Considérons ce qu’il faut faire avec une classe TXT, qui renvoit par défaut un wstring. (Ce qui ne marche pas quand la classe est constante ) :

Les fonctions internes de map

  • Opérateur [] :
    • Opérateur d’accès aux éléments val=truc[i]
    • Efficacité : O(N log(N))
  • find(clef)
    • Permet de trouver une clef associé à une valeur : truc.find(val) renvoit i
    • Renvoit end() si rien n’est trouvé : faire attention
    • Un conseil : faites une fonction pour vérifier que end() ou non la valeur
  • insert (élément ou intervalle d’une autre map)
  • erase (élément ou intervalle)

Multimap Multipap fonctionne comme map, mais les ensembles clefs-valeurs ne sont pas uniques. On est donc obligé d’utiliser la fonction make_pair() ;

Erase : efface toutes les clefs,mais ont peut utiliser un effacement d’un itérateur (par exemple après find)

Noter aussi l’existence de upper_bound et lower_bound (+ equal_range) pour la recherche


Accueil du site | Contact | Plan du site | Espace privé | visites : 37371

RSS RSSfr

Site réalisé avec SPIP 1.8.3 + ALTERNATIVES