Boost.PropertyMap ou comment associer des objets « clé » à des objets « valeur »

Matthieu Brucher

Les Property Maps de Boost sont un moyen d'utiliser dans des algorithmes des propriétés différentes. Par exemple, dans les algorithmes de graphes, les Property Maps permettent de donner à ceux-ci les capacités des arcs. ♪

- Titre : Boost.PropertyMap ou comment associer des objets « clé » à des objets « valeur »

- Auteur : Matthieu Brucher

- Parution : 4 décembre 2006

- Licence : Copyright ® 2006 Matthieu Brucher. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- Introduction

- I. Les concepts

- I-A. Readable Property Map

- I-B. Writable Property Map

- I-C. Read/Write Property Map

- I-D. Lvalue Property Map

- II. Les classes template de Property Map

- II-A. identity_property_map

- II-B. iterator_property_map<RandomAccessIterator, OffsetMap, T, R>

- II-C. associative_property_map<UniquePairAssociativeContainer>

- II-D. const_associative_property_map<UniquePairAssociativeContainer>

- II-E. vector_property_map<T, IndexMap = identity_property_map>

- II-F. Transformer un pointeur en Property Map

- III. Conclusion

Introduction

Boost.PropertyMap implémente quatre concepts à l'aide de plusieurs classes template. Chacune de ces classes implémente les concepts nécessaires à leur utilisation dans des algorithmes complexes, et ceci de manière interchangeable, qu'elles soient stockées au départ dans des std::map ou de simples tableaux.

I - Les concepts

Au nombre de quatre, ces concepts proposent une interface aux classes qui les implémentent, selon leurs capacités.

I-A - Readable Property Map

Cette Property Map peut être lue à l'aide de la fonction get(). Outre cette fonction, plusieurs types sont indispensables, dépendant de PMap, le type de la Property Map.

Type

Code correspondant

Explication

Type de valeur

boost::property_traits<PMap>::value_type

Type de la propriété

Type de référence

boost::property_traits<PMap>::reference

Type qui peut se convertir en un type de valeur

Type de clé

boost::property_traits<PMap>::key_type

Type permettant d'effectuer une recherche d'une valeur. Peut valoir void si le type de clé est template

Catégorie

boost::property_traits<PMap>::category

Type de la catégorie, doit pouvoir se convertir en readable_property_map_tag

Une seule fonction doit être définie.

Nom

Expression

Type de retour

Description

Get Property Value

get(pmap, key)

reference

Retourne la valeur dans la Property Map pmap associée à la clé key

I-B - Writable Property Map

Cette Property Map est capable d'associer à une clé une valeur grâce à la fonction put(). Plusieurs types sont aussi indispensables.

Type

Code correspondant

Explication

Type de valeur

boost::property_traits<PMap>::value_type

Type de la propriété

Type de clé

boost::property_traits<PMap>::key_type

Type permettant d'effectuer une recherche d'une valeur. Peut valoir void si le type de clé est template

Catégorie

boost::property_traits<PMap>::category

Type de la catégorie, doit pouvoir se convertir en writable_property_map_tag

Une seule fonction doit être définie.

Nom

Expression

Type de retour

Description

Put Property Value

put(pmap, key, val)

void

Affecte dans la Property Map pmap la valeur val à la clé key

I-C - Read/Write Property Map

Ce concept hérite des deux précédents, avec une petite différence pour le type de catégorie.

Type

Code correspondant

Explication

Catégorie

boost::property_traits<PMap>::category

Type de la catégorie, doit pouvoir se convertir en lvalue_property_map_tag

I-D - Lvalue Property Map

Une telle Property Map peut hériter de Readable Property Map ou de Read/Write Property Map selon qu'elle soit constante ou non - mutable -. On peut accéder à une référence indexée par une clé grâce à une interface particulière.

Type

Code correspondant

Explication

Type de référence

boost::property_traits<PMap>::reference

Type qui peut se convertir en un type de valeur

Catégorie

boost::property_traits<PMap>::category

Type de la catégorie, doit pouvoir se convertir en writable_property_map_tag

Une fonction d'accesseur particulier doit être définie.

Nom

Expression

Type de retour

Description

Access Property Value

pmap[key]

value_type& pour mutable, const value_type& sinon

Retourne une référence vers l'objet indexé par la clé key

II - Les classes template de Property Map

II-A - identity_property_map

Cette Property Map est une Readable Property Map qui retourne la clé donnée en entrée.

Code

Description

boost::property_traits<identity_property_map>::value_type

Ce type est void, les fonctions de la Property Map sont templatées

boost::property_traits<identity_property_map>::key_type

Ce type est void, les fonctions de la Property Map sont templatées

boost::property_traits<identity_property_map>::category

Vaut readable_op_bracket_tag

Quelques fonctions membres indispensables sont utilisables.

Membre

Description

identity_property_map()

Constructeur par défaut

identity_property_map(const identity_property_map& x)

Constructeur par recopie

template <class T> T operator[](T x) const

Retourne une copie de l'élément x

template <class T> T get(const identity_property_map& pmap, T x)

Fonction non membre retournant une copie de x

II-B - iterator_property_map<RandomAccessIterator, OffsetMap, T, R>

Cette classe implémente le concept de Lvalue Property Map. À partir d'un itérateur à accès aléatoire, on peut accéder à n'importe quel élément avec un entier - comme pour un itérateur sur des vecteurs standards, on peut l'avancer ou le reculer à l'aide des additions, ici, c'est la même chose -. Le deuxième élément indispensable est un outil pour convertir la clé en cet entier qu'on va utiliser. Les autres paramètres ont des valeurs par défaut décrites dans le tableau suivant.

Paramètre

Description

Valeur par défaut

Iterator

Modèle d'itérateur à accès aléatoire

OffsetMap

Modèle de Readable Property Map et la valeur associée doit pouvoir être convertie en type de différence pour l'itérateur précédent

T

Type de valeur de l'itérateur

std::iterator_traits<RandomAccessIterator>::value_type

R

Type de référence de l'itérateur

std::iterator_traits<RandomAccessIterator>::reference

Et voici les membres associés à cette Property Map :

Membre

Description

property_traits<iterator_property_map>::value_type

Vaut std::iterator_traits<Iterator>::value_type

iterator_property_map(Iterator i)

Constructeur, OffsetMap est construit par défaut

iterator_property_map(Iterator i, OffsetMap m)

Constructeur

reference operator[](difference_type v)

Retourne une référence selon la différence donnée

II-C - associative_property_map<UniquePairAssociativeContainer>

Cet adaptateur permet de transformer des objets répondants aux critères des conteneurs associatifs à paires - une paire clé/valeur - et des conteneurs associatifs à clé unique, comme std::map pour les transformer en Lvalue Property Map.

Paramètre

Description

Valeur par défaut

UniquePairAssociativeContainer

Type répondant aux critères des conteneurs associatifs à paires et à clé unique

Et voici les membres associés à cette Property Map :

Membre

Description

property_traits<associative_property_map>::value_type

Vaut UniquePairAssociativeContainer::data_type

associative_property_map()

Constructeur par défaut

associative_property_map(UniquePairAssociativeContainer& c

Constructeur

data_type& operator[](const key_type& k) const

Retourne une référence selon la différence donnée. Les types sont dérivés de UniquePairAssociativeContainer

II-D - const_associative_property_map<UniquePairAssociativeContainer>

Cet adaptateur diffère du précédent en ne proposant qu'un accesseur retournant un élément constant.

Membre

Description

const data_type& operator[](const key_type& k) const

Retourne une référence selon la différence donnée. Les types sont dérivés de UniquePairAssociativeContainer

II-E - vector_property_map<T, IndexMap = identity_property_map>

Cette classe particulière se trouve entre une Property Map associative et une Property Map itérative. À la différence de cette dernière, le nombre d'éléments stockés peut varier. En fait, les données stockées sous la forme d'un vecteur qui croît à la demande. C'est à nouveau une implémentation du modèle Lvalue Property Map.

Paramètre

Description

Valeur par défaut

T

Le type de valeur

IndexMap

Implémente le modèle de Readable Property Map et doit être convertible en std::vector<T>::size_type

identity_property_map

Et voici les membres associés à cette Property Map :

Membre

Description

vector_property_map(const IndexMap& index = IndexMap())

Constructeur pouvant prendre une IndexMap en paramètre

vector_property_map(unsigned initial_size, const IndexMap& index = IndexMap())

Constructeur prenant en plus la taille initiale de la Property Map

vector_property_map(const vector_property_map&)

Constructeur par recopie

vector_property_map& operator=(const vector_property_map&)

Opérateur d'assignation

reference operator[](const key_type& v) const

Opérateur d'accès

std::vector<T>::iterator storage_begin()
std::vector<T>::iterator storage_end()
std::vector<T>::const_iterator storage_begin()
std::vector<T>::const_iterator storage_end()

Récupération d'itérateurs sur la Property Map

void reserve(unsigned size)

Permet de réserver une taille pour éviter les changements de taille coûteux

II-F - Transformer un pointeur en Property Map

Afin d'utiliser un pointeur T*, des fonctions put et get existent pour palier l'absence naturelle de ces fonctions pour les pointeurs, ainsi qu'une spécialisation de property_traits afin de répondre aux nécessités d'une Read/Write Property Map.

III - Conclusion

Chaque Property Map, sauf identity_property_map, peut être construite à l'aide d'un make_xxx où xxx est le type à construire. Ces classes sont utilisées couramment dans Boost.Graph que nous étudierons par la suite, mais vous pouvez les utiliser dès que vous voulez utiliser des propriétés associées à un type de données.