Ce numéro est l'occasion de traiter des structures de données mises à disposition par la librairie standard du C++, les conteneurs.
Nous aborderons ensuite l'utilisation des itérateurs, qui permettent de "visiter" les conteneurs puis deux cas particuliers de conteneurs, les vector et les map.
Pour pouvoir présenter les exemples, il faut d'abord aborder la théorie. Rassurez vous, comme d'habitude, je ne serai pas long sur cette partie pour pouvoir rapidement passer à la pratique.
Comme promis, je vais dans cet article vous présenter les vector et les maps. Je vous montrerai la méthode utilisée pour en parcourir les éléments, basée sur l'utilisation des itérateurs. Je vous décrirai ensuite l'application d'algorithmes courants. C'est pourquoi, avant de donner les exemples je dois vous expliquer succintement ce que l'on appelle un conteneur et un itérateur.
Un conteneur est un objet dont le rôle est d'en contenir d'autres, comme son nom l'indique. Il existe deux types de conteneurs, les conteneurs de séquences (listes, queues, files, piles), et les conteneurs associatifs (tableaux, tables de hachage).
On trouve parmi les conteneurs de séquences les vecteurs, conteneurs génériques, les listes, optimisées pour l'ajout et la suppression d'éléments et les queues optimisées pour les opérations en début et fin de séquence.
Des adaptations de ces conteneurs existent également mais ne font que reprendre une partie des caractéristiques de ces derniers. Nous avions par exemple vus lors du premier article sur le C++ les classes stack et queue qui sont en fait des adaptations d'une queue à double entrée (deque).
Les conteneurs associatifs sont les map et les set. Ils sont optimisés pour permettre l'accès à leur données par le biais de clés.
Les conteneurs partagent plusieurs caractéritiques communes dont la plus appréciable à mon sens est qu'ils se chargent eux mêmes de gérer la mémoire nécessaire aux objets qu'ils contiennent, ça vous permet de faire fi de vos soucis de malloc, realloc, et autres free dont la mauvaise utilisation peut vous faire passer de nombreuses heures sur du débogage fastidieux.
D'autre part, les conteneurs fournissent un ensemble d'opérations permettant d'ajouter des objets, de les consulter, de les modifier mais chacun d'entre eux est spécialisé pour s'adapter à une tâche. A titre d'exemple, citons les maps dont les données sont stockées dans une structure arborescente pour accélérer les temps d'accès à ces dernières. Elles sont réparties selon leur index. Pour créer un arbre, la donnée utilisée comme clé doit fournir un opérateur de comparaison(en fait pour résumer et en simplifiant, elle doit fournir un operator<). Le plus souvent, on utilise une chaîne de caractères ou un nombre en guise d'index mais pour utiliser des types de clés différents, vous devez fournir cet opérateur s'il n'existe pas. Nous verrons dans l'exemple plus loin une implémentation de map utilisant des adresses sur 48bits comme clé.
Pour pouvoir s'adapter à tout type de contenu, les conteneurs sont bâtis à partir de patrons (cf. linuxmag n°45). Ils peuvent donc contenir des objets de classes que vous définissez vous mêmes comme nous le verrons dans les exemples.
Pour parcourir les objets stockés dans un conteneur, on pourrait utiliser un bête pointeur. On utilise en fait des itérateurs. On peut se représenter un itérateur comme un "objet pointeur", qui mérite alors le nom de pointeur intelligent.
Un itérateur permet de manipuler les objets des conteneurs sans connaître leur type à l'avance.
On utilise le plus souvent les itérateurs de façon simple : on "obtient" un itérateur puis on le "déplace", à l'aide des opérateurs ++ et -- ou on accède aux objets précédants ou suivants grâce à des expressions du type begin+3 ou end-2. Attention, cette notation (begin+3, end-2, ...) ne peut pas toujours être employée, cela dépend du conteneur et du type d'itérateur qu'il offre. Pour obtenir l'itérateur, on utilise les méthodes fournies par les conteneurs. Il s'agit, entre autres, de begin, end, rbegin ou rend.
begin correspond au premier objet contenu. end correspond lui, comme son nom l'indique à la fin du conteneur, pas au dernier élément mais à la fin du conteneur. Cet itérateur sert généralement à signaler une erreur, par exemple dans le cas d'une recherche, on renvoit un itérateur end si l'objet n'est pas trouvé. rbegin ou rend représentent la même chose mais en prenant le conteneur à l'envers. rbegin correspond au dernier élément. Il s'agit de reverse_iterator. C'est à dire que les opérateurs ont des actions inverses du cas des itérateurs "normaux". Si begin+1 correspond au deuxième objet, rbegin+1 correspond, lui, à l'avant dernier objet du conteneur.
On accède à l'objet à partir d'un itérateur grâce à l'opérateur *, comme dans le cas des pointeurs. Par exemple *(conteneur.begin()) donne accès à l'objet situé au début du conteneur conteneur.
On trouve enfin des const_iterator qui ne permettent que la consultation des objets du conteneur, alors que les iterateurs "basiques" permettent de les modifier.
Les maps sont généralement appelés tables de hashage ou hashtables. Le but de ce conteneur est de faire correspondre une donnée d'un type quelconque à une autre, également d'un type quelconque (un autre ou le même). On parle de clés et de valeurs, les premières permettant de retrouver les secondes. Pour vous faire "percuter" l'utilité de la chose, je vais vous donner l'un des exemples type que l'on cite pour l'utilisation des maps. Nous verrons ensuite un exemple plus original destiné à stocker des périphériques bluetooth.
Pour créer un map on peut écrire :
map<c, v> m;
Cette ligne crée un map dont les clés sont des objets de type c et les valeurs, des objets de type v. Bien sûr, pour celà, il ne faut pas oublier d'inclure l'entête <map>.
/* ex_7_1.c++ */
#include <iostream>
#include <string>
#include <map>
using namespace std;
typedef map<char, string> char_string_map;
int main(void) {
char_string_map m;
m.insert(char_string_map::value_type('0', "zéro"));
m.insert(char_string_map::value_type('1', "un"));
m.insert(char_string_map::value_type('2', "deux"));
m.insert(char_string_map::value_type('3', "trois"));
m.insert(char_string_map::value_type('4', "quatre"));
m.insert(char_string_map::value_type('5', "cinq"));
m.insert(char_string_map::value_type('6', "six"));
m.insert(char_string_map::value_type('7', "sept"));
m.insert(char_string_map::value_type('8', "huit"));
m.insert(char_string_map::value_type('9', "neuf"));
string s = "";
while (s!="x") {
cout << "Saisissez un nombre (ou x pour quitter) : ";
cin >> s;
for (int i=0; i<s.length(); ++i) {
if ((s[i]>='0') && (s[i]<='9')) {
cout << m[s[i]] << " ";
}
}
cout << endl;
}
return 0;
}
Cet exemple sert à savoir quels chiffres composent votre nombre. Autant dire à rien, si ce n'est de vous montrer un premier usage des maps.
Un map stocke des paires d'objets. On doit donc informer le conteneur du type d'objets qu'il va contenir. Ceci crée donc un nouveau type que l'on définit comme char_string_map. Les types des objets de la paire sont passés via les paramètres du patron map.
Les paires sont du type char_string_map::value_type. On voit, après la déclaration du map, son remplissage. Il y a plusieurs façons de faire. J'ai utilisé celle qui consiste à créer des paires et à les insérer dans le map. On peut toutefois utiliser une spécificité des maps pour ce faire. Si on prend l'exemple du map m, en écrivant m['5'] on obtient la chaîne correspondant à la clé '5'. Si cette valeur n'existe pas, elle est créée. Le bloc d'insertions peut donc être remplacé par :
m['0'] = "zéro"; m['1'] = "un"; m['2'] = "deux"; m['3'] = "trois"; m['4'] = "quatre"; m['5'] = "cinq"; m['6'] = "six"; m['7'] = "sept"; m['8'] = "huit"; m['9'] = "neuf";
La réservation d'espace mémoire est automatiquement faite par le map. C'est la technique qui est employée page 240 de l'excellent "Thinking in C++ Volume 2" dont vous trouverez les références en fin d'article. Dans cet exmple l'auteur réalise un compteur de mots. Chaque mot différent est utilisé comme clé et la valeur correpondante est incrémentée à chaque apparition de ce dernier. Le c++ garantissant l'initialisation à 0 des entiers, ceci permet un algo simple :
déclarer une map avec des clés de type chaîne et des valeurs entières faire lire mot map[mot]++ tant que mot n'est pas un point Afficher tous les mots et leur nombre d'occurences
Ce qui se code basiquement de la façon suivante :
/* ex_7_3.c++ */
#include <iostream>
#include <string>
#include <map>
using namespace std;
typedef map<string, int> string_int_map;
int main(void) {
string_int_map m;
string texte;
cout << "Tapez du texte (ou rien pour quitter) :" << endl;
while (1) {
cin >> texte;
if (texte==".") break;
m[texte]++;
}
string_int_map::iterator it;
for (it = m.begin(); it != m.end(); it++) {
cout << (*it).first << " : " << (*it).second << " fois." << endl;
}
return 0;
}
Exécuté, voici ce que ça donne :
$ g++ -o ex_7_3 ex_7_3.cpp $ ./ex_7_3 Tapez du texte (ou rien pour quitter) : linux est beau linux est fort linux vaincra et voilà . beau : 1 fois. est : 2 fois. et : 1 fois. fort : 1 fois. linux : 3 fois. vaincra : 1 fois. voilà : 1 fois.
Cet exemple me permet de vous montrer l'utilisation d'un itérateur de map. Le type de l'iterateur se trouve de façon similaire au type de la paire. Il s'agit de votre_type_de_map::iterator. J'utilise ici l'iterateur dans une boucle for afin de parcourir l'intégralité du map. On part donc de begin() et on s'arrête sur end(). Je vous rappelle qu'il s'agit de la fin du conteneur et non du dernier élément.
Une fois qu'on a un itérateur, on obtient la paire correspondante en le déréférençant (*). Cet itérateur déréférencé est une paire, de type pair<string, int>, dont on accède aux éléments grâce à first et second.
Il nous reste une chose à voir à propos des maps en particulier mais des conteneurs en général : la libération des ressources. Comme le reste en C++, tout est libéré lorsque l'objet est hors de portée. On peut toutefois vouloir économiser des ressources tout de suite. Pour celà on utilise les méthodes erase. On passe en paramètre un iterateur, une clé ou deux itérateurs. Selon les cas on détruit la paire référencée par l'itérateur, la paire correspondant à la clé ou toutes les valeurs comprises entre les deux itérateurs. Par exemple, dans le code précédent, écrire m.erase(m.begin()) aurait effacé les occurences du mot "beau" et m.erase("linux") aurait supprimé le mot "linux" du comptage.
Pour être plus radical, on peut utiliser clear(), qui est équivalent à erase(begin(), end()).
Parmi les méthodes utiles, citons find qui renvoit un itérateur sur la valeur correspondante à la clé passée en paramètre ou end() si elle ne se trouve pas dans le conteneur. Par exemple à la fin de l'exemple précédent, pour connaître le nombre d'occurences du mot "est", on aurait pu écrire :
it = m.find("est");
if (it != m.end())
cout << "On vu le mot " << it->first << " " << it->second << " fois." << endl;
empty() renvoit un booléen indiquant si le conteneur est vide ou non.
size() renvoit le nombre d'éléments dans le conteneur.
Imaginons un map dans lequel on veut stocker des adresses bluetooth associées à leur identifiant de canal de communication (représenté ici par un short). On choisit d'utiliser l'adresse physique (sur 48bits) pour "ranger" les périphériques. On écrit donc le code suivant :
/* ex_7_4.c++ */
#include <iostream> #include <map>
using namespace std;
typedef unsigned char phy_addr[6];
class bt_addr {
phy_addr addr;
public:
bt_addr(const phy_addr& ba) {memcpy(addr, ba, sizeof(phy_addr));}
const phy_addr& get_phy_addr() const {return addr;}
};
typedef map<bt_addr, short> bt_dev_map;
int main(void) {
bt_dev_map m;
phy_addr a1 = { 1,1,1,1,1,1 };
m[a1] = 1;
phy_addr a2 = { 0,3,2,4,9,7 };
m[a2] = 2;
bt_dev_map::iterator it;
it = m.begin();
do {
cout << it->second << endl;
} while (++it != m.end());
return 0;
}
Vous allez vous faire insulter par le compilateur, qui va se plaindre de ne pas pouvoir comparer vos clés. Il faut donc ajouter l'opérateur < à votre classe pour pouvoir l'utiliser comme clé de map.
[...]
public:
bt_addr(const phy_addr& ba) {memcpy(addr, ba, sizeof(phy_addr));}
const phy_addr& get_phy_addr() const {return addr;}
bool operator< (const bt_addr& other) const;
};
bool bt_addr::operator< (const bt_addr& other) const {
return (memcmp(this->addr, other.get_phy_addr(), sizeof(phy_addr)) < 0);
}
typedef map<bt_addr, short> bt_dev_map;
[...]
Une exécution/compilation se passera alors normalement et vous confirmera que les périphériques sont bien agencés dans le conteneur suivant la comparaison des octets de leur adresse.
$ g++ -o ex_7_4 ex_7_4.cpp $ ./ex_7_4 2 1
On peut se les représenter comme des tableaux à taille variable, comme eux ils permettent l'accès aux données via l'opérateur []. Mais ils permettent également des opérations du type de celles que l'on retrouve dans les piles et les files, telles que l'ajout, la suppression et la consultation en début ou fin de vecteur.
Le vector est un conteneur primordial de la STL, ses itérateurs sont très souples et il offre de nombreuses méthodes permettant sa manipulation.
Créer un vecteur est quelque chose de simple. Il vous suffit d'écrire :
vector<T> v;
Vous avez alors un vecteur d'objets de type T, à condition de n'avoir pas fait l'impasse sur #include <vector>.
Un vecteur gère lui même la mémoire dont il a besoin en fonction des éléments que vous y ajoutez. Vous pouvez toutefois pour des raisons d'optimisation en modifier la taille vous mêmes, soit grâce à la méthode reserve(size_type n), soit resize(size_type n, T x = T()). Comme leurs noms l'indiquent, la première réserve de l'espace pour n objets alors que la seconde réserve l'espace et "remplit les cases". Le premier argument est, dans les deux cas la taille en objets que vous voulez attribuer à votre vecteur (et non en octets comme dans le cas de malloc). Dans le cas de resize(), le deuxième argument est la valeur à attribuer aux objets situés dans les "cases" nouvellement créées. Si vous ne spécifiez pas de valeur, on utilise le constructeur de votre objet.
Pour s'informer sur la taille d'un vecteur, on utilise les méthodes size(), capacity() et max_size(). La première renvoit le nombre d'éléments contenus dans le vecteur, la seconde renvoit le nombre d'objets que l'on peut stocker dans l'espace alloué au vecteur et la dernière renvoit le nombre maximum d'objets que ce vecteur saurait gérer. Attention, reserve réserve de l'espace mais ne change pas le nombre d'éléments renvoyé par size().
Vous pouvez vous posez la question : "Pourquoi j'irais gérer moi même la mémoire alors que le vector le fait tout seul ?". C'est juste ! Mais il existe une bonne raison à cela. Les vecteurs sont codés de manière à assurer que les objets qu'il contient soient stockés de façon contigue dans la mémoire. C'est à dire qu'en grossissant, l'implémentation doit réattribuer un plus gros bloc de mémoire au vecteur. Si vous réservez de l'espace au préalable, il n'y aura pas de déplacement des données du vecteur et votre application sera plus rapide.
Il existe plusieurs façons d'ajouter des éléments dans un vecteur. On peut utiliser resize et se servir de l'opérateur d'indexation :
/* ex_7_5.c++ */
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> int_vector;
int main(void) {
int_vector v;
v.resize(5);
v[0] = 1;
v[1] = 7;
v[2] = 5;
v[3] = 13;
v[4] = 4;
for (int i = 0; i < v.size(); ++i)
cout << v[i] << endl;
return 0;
}
On peut également utiliser la méthode push_back(const T& x), qui ajoute l'élément x en queue de vecteur. Notre programme devient alors :
/* ex_7_6.c++ */
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> int_vector;
int main(void) {
int_vector v;
v.push_back(1);
v.push_back(7);
v.push_back(5);
v.push_back(13);
v.push_back(4);
for (int i = 0; i < v.size(); ++i)
cout << v[i] << endl;
return 0;
}
Après compilation, ces deux programmes ont la même sortie :
$ ./ex_7_5 1 7 5 13 4
On peut également utiliser une des méthodes insert, les deux plus utilisées étant insert(iterator it, const T& x = T()) et insert(iterator it, size_type n, const T& x = T()). Ces deux méthodes ajoutent x ou n fois x avant l'objet référencé par l'itérateur it. Par exemple, l'ajout de des deux lignes suivantes avant la boucle for d'un des deux programmes précédent :
v.insert(v.begin()+3, 333); v.insert(v.end()-1, 2, 222);
produit l'affichage suivant :
$ ./ex_7_7 1 7 5 333 13 222 222 4
On remarque le 333 inséré avant la quatrième place (begin()+3) et les deux 222 insérés avant l'avant dernier élément (end()-1)
On vient de voir ci-dessus une méthode de consultation des valeurs stockées dans un vector : on peut accéder à ces dernières grâce à l'opérateur []. On peut également utiliser la méthode at() qui prend en paramètre une position, comme []. La différence réside dans le fait que at() provoque une exception si l'on essaye d'accéder à une position invalide. Nous reverrons celà dans l'article sur les exceptions.
Une autre solution consiste à utiliser un itérateur. Nous aurions pu écrire la boucle for ainsi :
int_vector::iterator it; for (it = v.begin(); it != v.end(); ++it) cout << *it << endl;
On aurait obtenu la même fonctionnalité.
Enfin, on peut accéder aux éléments de bouts de vecteur grâce aux méthodes front et back, qui renvoient respectivement le premier et le dernier élément du vecteur.
On retrouve ici les méthodes clear et erase, comme dans le cas des maps. Un vector offre également pop_back(), pour supprimer le dernier élément du tableau. Combinée à la méthode empty(), elle permet par exemple une vidange/affichage inversé du vecteur. Il suffit d'ajouter avant le return 0; dans notre exemple précédent, ces quelques lignes :
cout << "A l'envers !" << endl;
while (!v.empty()) {
cout << v.back() << endl;
v.pop_back();
}
On obtient alors l'affichage suivant (à la fin de la boucle, le vecteur est vide):
$ ./ex_7_9 1 7 5 333 13 222 222 4 A l'envers ! 4 222 222 13 333 5 7 1
Utiliser des conteneurs comme ça, c'est sympa ;-) mais généralement, les conteneurs sont intégrés à des classes. L'utilisateur de ces classes manipule indirectement les conteneurs mais sans le savoir. Ceci permet au concepteur de la classe de protéger ses données et d'adapter les conteneurs à ses besoins propres. Cette technique présente en plus l'avantage de permettre au concepteur de la classe de changer le type de conteneur utilisé de façon transparente pour l'utilisateur de la classe, à condition qu'il maintienne une interface de classe identique.
Si on prend l'exemple de la modélisation d'un bus, on pourrait choisir d'utiliser un vecteur pour représenter les gens assis à telle ou telle place, ces dernières étant numérotées de 1 à 50.
La classe fournirait une interface comportant une méthode permettant d'ajouter un passager, ce qui retournerai son numéro de place ou 0 s'il ne reste plus de place disponible et une méthode permettant de connaître la personne assise à la place portant un numéro connu.
Si un jour, la compagnie de bus décide d'indéxer ses places selon les noms des dieux de l'olympe, l'interface restera la même mis à part le type retourné pour identifier la place mais en interne, au lieu d'un vecteur de personnes, il y a de grandes chances que l'on choisisse d'utiliser un map de personnes indéxées par des string représentant les dieux de l'olympe.
Pour l'utilisateur rien n'aura changé, il utilisera toujours ses deux mêmes méthodes. En revanche, en interne, la classe aura été profondément modifiée. Si le programme avait directement utilisé un vecteur, il aurait dû être entièrement réécrit, alors que dans le cas de l'utilisation d'une classe gérant le conteneur, il n'y a que la classe à réécrire.
Pour en savoir plus, consultez les références. Je vous ai cité au cours du premier article et de celui-ci les conteneurs stack, queue, map et vector. Je vous ai brièvement présenté les iterateurs. Si j'ai atteint le but que je m'étais fixé, vous devez à présent être à même, en ayant recours à des sources annexes, d'utiliser les conteneurs standards dans vos projets. Par ailleurs, cette présentation vous permettra de vous familiariser rapidement avec leur homologues dans des bibliothèques comme Qt (QMap, QVector, ...).
Il existe par ailleurs des conteneurs que je ne vous ai pas présenté comme les multimap, semblables au maps mais autorisant des valeurs différentes à avoir la même clé, les list (vous comprenez, j'en suis sûr), les deque (des queues à double entrée ou une sorte de stack également utilisable comme une queue), les set et multiset, les priority queue (des queues avec gestion de priorité comme leur nom l'indique, utiles pour gérer différents types de messages de logs), etc... . Chaque conteneur est optimisé pour un type d'opération ou pour être pratique, tout simplement. Je vous renvoie une nouvelle fois au livre de Bruce Eckel, "Thinking in C++ Volume 2", Chapitre 4, qui présente de façon complète les divers conteneurs de la STL (lui, il a 116 pages pour ça ...). Sachez par exemple que les list et les deque offrent une méthode équivalente à push_back() pour ajouter des éléments à l'autre extrémité du conteneur (vous aurez deviné qu'elle s'appelle push_front()).
Un dernier point que j'avoue avoir négligé est la présentation des divers constructeurs offerts par les conteneurs. Je vous ai toutefois présenté leur utilisation la plus courante et vous laisse regarder de votre côté comment initialiser les conteneurs plus intelligemment en spécifiant directement la taille ou en faisant une copie d'un conteneur existant par exemple.
Dans le prochain numéro, je vous montrerai comment utiliser les exceptions. D'ici là, bon été.
@+
Xavier Garreau - <xavier@xgarreau.org>
http://www.xgarreau.org/
Ingénieur de recherche PRIM'TIME TECHNOLOGY
http://www.prim-time.fr/
Membre fondateur du ROCHELUG
http://www.rochelug.org/
| Précédent | Index | Suivant |
a+
