Conteneurs exotiques Boost

Introduction du cours

Boost fournit un grand nombre de conteneurs : nous en présenterons certains, plus ou moins inconnus, mais parfois fort utiles.

Des tuples en C++

Le tuple est l'association de plusieurs éléments, structurellement semblable à un struct. On peut par exemple y stocker une relation élément/attribut ({objet : "Ballon", nombre: 4}), une position ({abscisse : 349, ordonne : 89, profondeur : 2}) ...

Ainsi ils peuvent contenir plusieurs sorte de données, et cette association forme un type, là ou un tableau ne peut en contenir qu'un, et ne précise pas leur nombre. De plus, par rapport à une structure anonyme utilisé en plusieurs endroits, un tuple sera toujours compatible avec d'autres tuples de même caractéristique, puisqu'il s'agit d'un type unique.

Utiliser les tuples

Vous n'avez pas besoin de librairie à lier, mais vous devez inclure les en-têtes suivants :

#include <boost/tuple/tuple.hpp> // Base #include <boost/tuple/tuple_comparison.hpp> // Opérateurs de comparaison #include <boost/tuple/tuple_io.hpp> // Tuples et IO

Pour créer un tuple, vous devez spécifier les types de ses éléments, puis éventuellement les initialiser :

boost::tuple<int, int, double> monTuple(1,2,3.14);

Cependant, cette notation est pénible en cela qu'elle oblige à écrire chaque type. Pour pallier ce problème, Boost met à notre disposition une fonction permettant de créer des tuples.

monTuple = make_tuple(1, 2, 3, 4);

Si le tuple que vous essayez de créer doit contenir une référence, il faut le spécifier, autrement l'élément pointé sera copié : ref() pour forcer une référence, cref() pour forcer une référence constante.

Si vous utilisez ref() , comme dans le 5éme exemple, sur une référence constante, l'attribut const ne sera pas perdu.

MaClasse1 a; MaClasse2 b; const MaClasse1 ca = a; make_tuple(cref(a), b); // Résultat : tuple<const MaClasse1&, MaClasse2> make_tuple(ref(a), b); // Résultat : tuple<MaClasse1&, MaClasse2> make_tuple(ref(a), cref(b)); // Résultat : tuple<MaClasse1&, const MaClasse2&> make_tuple(cref(ca)); // Résultat : tuple<const MaClasse1&> make_tuple(ref(ca)); // Résultat : tuple<const MaClasse1&>

Vous pouvez accéder au contenu du tuple de deux manières :

• Via la fonction boost::get<NumeroElement>(tuple);

• Via la méthode tuple.get<NumeroElement>();

Ce qui donne par exemple :

tuple <int, int> t(1,2); get<0>(t) = 10; // t vaut 10|2 std::cout << t.get<1>(); // Le programme affiche 2

Notez d'ailleurs que vous n'aurez pas de mauvaise surprise : les accès à des données inexistantes (par exemple, t.get<3>() pour un tuple à 2 valeurs) sont détectés à la compilation, grâce à l'utilisation de template.

les indices commencent comme d'habitude à zéro et non pas à un

Comparaisons

Les tuples ont des opérateurs de comparaison (== , > ,< , ...) : le premier élément du tuple A sera comparé au premier élément du tuple B, le second au second, et ainsi de suite. Les tuples sont égaux si tous les éléments les constituants sont égaux un à un.

Flux

Vous pouvez imprimer un tuple sous la forme (1 2 3 Orly) en utilisant l'opérateur << :

tuple<int,int,int,std::string> t(1,2,3,std::string("Orly")); std::cout << t;

Pour obtenir un tuple depuis l'entrée standard, faites de même :

cin >> a

L'entrée devra être formatée comme la sortie (exemple : "(1 2 3 Aaa)")

Si vous le souhaitez, vous pouvez changer les délimiteurs, tant pour la sortie que pour l'entrée :

• set_open(char) défini le caractère de début.

• set_close(char) défini le caractère de fin.

• set_delimiter(char) défini le délimiteur

Le code suivant aura pour sortie [1,2,3,Aaa]

std::cout << tuples::set_open('[') << tuples::set_close(']') << tuples::set_delimiter(',') << t;

Avec le compilateur MS Visual C++, il est possible que, malgré la conformance aux standards du code des tuples, les références ne puissent être utilisés dans les tuples (les fonctions ref() et cref() ne fonctionnant pas.)

Tampon circulaire

Un tampon circulaire ("Circular buffer", que j'abrègerais TC) est un conteneur générique, qui fonctionne de manière très similaire à un std::vector à ceci près qu'il possède une taille et que les éléments inscrits une fois que le TC est plein seront écrits par-dessus les premiers éléments.

Un seul include pour les TC :

#include <boost/circular_buffer.hpp>

Le constructeur est tout ce qu'il y a de plus simple; par exemple, le code suivant créera un TC de 3 items contenant des int :

boost::circular_buffer<int> cb(3);

On peut ensuite insérer, comme dans un vector, des éléments à la fin:

cb.push_back(1); cb.push_back(2); cb.push_back(3);

L'état du TC est donc 1|2|3. Nous pouvons modifier les éléments qu'il contient comme un std::vector :

int a = cb[0]; // a vaut 1 a = cb.at(1); // a vaut 2 cb[2] = 1; // le TC est maintenant 1|2|1

Si malgré que le TC soit plein, on continue d'appeler push_back :

// t est un TC défini comme ceci: 1|2|3|4|5|6. Il est rempli t.push_back(0); // t == 0|2|3|4|5|6 t.push_back(9); // t == 0|9|3|4|5|6

On peut enlever des items depuis le début et la fin du buffer (cf. le schéma précédent) :

// t est un TC défini comme ceci: 1|2|3|4|5|6. Il est rempli t.pop_back(); // t == 1|2|3|4|5** t.pop_front(); // t == **2|3|4|5**

Quelques autres méthodes notables sont fournies :

bool t.full(); // Plein ? bool t.empty(); // Vide ? size_t t.reserve(); // Nombre d'item non rempli ? size_t t.capacity(); // Nombre d'item maximal ? void t.set_capaxity(size_t); // Changement capacité

Attention ! Les changements de capacité affectent grandement les performances lorsque le buffer s'étend. Quand il est réduit, les derniers éléments sont retirés.

Vous trouverez la totalité de la documentation ici.

Un TC peut par exemple être utilisé dans :

• Un système de cache avec n éléments maximum.

• Une queue qui retire automatiquement les éléments trop anciens.

• Un tampon avec frontière (bounded buffer en anglais) qui peut servir quand un thread produit des données, et qu'un autre les traitent. Voir cette implémentation.

N'utilisez jamais un TC pour des objets alloués dynamiquement : si le TC vient à devenir plein, les anciens éléments seront effacés, et vous ne pourrez plus les libérer. Cela conduira à des fuites de mémoire.

Tableau revisité

Les std::vector sont parfaits quand il s'agit de tableau dynamique. Mais ne sont d'aucune utilité dans le cas de tableau réellement statique (nombre de cases défini, et immuable). Cependant, ils fournissent un certain confort, comme les itérateurs, l'accès sécurisé via at() , la taille du tableau via size() ,... C'est-à-dire une interface dans le style de la librairie standard. C'est pour cette raison que l'équipe Boost a créé boost.array, des tableaux statiques dans une optique C++, avec les avantages précités.

Pour les utiliser, incluez l'header unique suivant :

#include <boost/array.hpp>

Construisez un array avec :

boost::array<int,4> a;

Ce code construit un array nommé a, contenant des int, de taille 4.

L'accès au contenu de l'array se fait de 2 manières :

a[0] = 1; a.at(0);

La deuxième méthode est considérée comme sûre car elle jette toujours une exception en cas d'accès hors de la plage de données, là où la première ne fait rien1

1

En vérité, la première méthode est protégée par une assertion :

// operator[] reference operator[](size_type i) { BOOST_ASSERT( i < N && "out of range" ); return elems[i]; }

Cependant, cela pose deux problèmes :

• Une assertion ratée conduit à la fermeture brutale du programme par un appel à abort()

• Dans le mode de compilation release, les assertions sont réduites à néant

Un accès sécurisé par [x] est cependant possible car la classe fournit explicitement une méthode size() .

Détails

Vous pouvez initialiser un tableau ainsi :

boost::array<int,4> a = { 1, 2, 3, 4 };

Si votre compilateur ne respecte pas les standard, et que le code ci-dessus ne marche pas, utilisez celui-ci :

boost::array<int,4> a = { { 1, 2, 3, 4 } }; Bimap

Qu'est ce qu'une map (dans la STL, il s'agit de std::map) ? Il s'agit de l'association d'une valeur, unique, appelée clé, avec un contenu, qui lui ne l'est pas forcément :

Exemple de map :

"Fraise" ==> "Bon" "Epinard" ==> "Mauvais" "Steak" ==> "Bon si saignant"

ou encore

3.23 ==> "Bon" 2.432 ==> "Mauvais" 1.09 ==> "Bon si saignant"

Vous associez la valeur de gauche à la valeur de droite. Cela correspond au schéma suivant issue de la documentation Boost :

Une bimap fait la même chose, mais dans les deux sens : les deux coté sont des clés : cela signifie premièrement que l'on peut accéder aux données depuis la gauche, ou depuis la droite, et secondement, contrairement à une map, que les doublons sont prohibés, car conduiraient à une situation incohérente où une recherche renverrait 2 résultats.

Utilisation

Incluez le header :

#include <boost/bimap.hpp>

On définit ensuite un type pour notre map (ce n'est pas obligatoire, mais c'est plus lisible). Dans l'exemple suivant, la bimap aura une coté int et un coté string :

typedef boost::bimap< int, std::string > int_string;

Nous créons ensuite un objet bimap:

int_string a;

C'est vide. Il nous faut insérer des relations:

a.insert( int_string::value_type(1, "un" ) ); a.insert( int_string::value_type(2, "deux" ) ); a.insert( int_string::value_type(3, "trois" ) );

Notre bimap est donc maintenant :

1 <=> "un" 2 <=> "deux" 3 <=> "trois"

Nous pouvons par exemple afficher chaque relation à l'aide d'une boucle et des itérateurs fourni :

for( int_string::const_iterator iter = a.begin(), iend = a.end(); iter != iend; ++iter ) { std::cout << iter->left << " <--> " << iter->right << std::endl; }

C'est ultra intuitif si l'on garde le schéma de nos relations en tête : left est la gauche de nos relation, right la droite !

La sortie de cette boucle sera:

1 <--> un 2 <--> deux 3 <--> trois

On peut utiliser chaque coté (gauche/droit) comme une map indépendante; ici la gauche :

typedef int_string::left_map::const_iterator left_const_iterator; // pour la lisibilité for( left_const_iterator left_iter = a.left.begin(), iend = a.left.end(); left_iter != iend; ++left_iter ) { std::cout << left_iter->first << " --> " << left_iter->second << std::endl; }

La sortie attendue sera :

1 --> un 2 --> deux 3 --> trois

On peut accéder directement aux vue gauche et droite. Dans ce cas, nous avons affaire à 2 maps simples (une bimap étant la combinaison de ces deux maps) :

std::cout << a.left(1); // affiche "un" std::cout << a.right("un"); // affiche 1 a.left.erase(3); // efface 3<=>"trois"

Pour résumer les différentes méthodes d'accès, voici un schéma issue de la documentation :

On voit que l'accès du coté gauche donne une map inverse à celle correspondante à gauche.

Le tutoriel long et officiel est celui ci. Il mène aussi à la documentation.

Pour aller...