Faire varier le format de stockage d'un tableau/vecteur

Bonjour,

je dispose d'une classe générique Vector qui ressemble à ceci sans les fonctions membres :

Code:

---

1 2 3 4 5 6 7 8

template<typename precision> class Vector { private: size_t _length; // longueur du vecteur precision *_values; // valeurs du vecteur };

---

J'aimerais modifier cette classe pour qu'elle admette deux formats de stockage possibles. Celui déjà défini dans ma classe est le format "dense" classique. J'aimerais également un format "creux" qui permette de ne stocker que les valeurs non nulles de mon vecteur. Par contre, je veux n'avoir qu'une seule et unique classe Vector. Si j'avais implémenté ma classe avec le format creux, j'aurais écrit ceci :

Code:

---

1 2 3 4 5 6 7 8 9

template<typename precision> class Vector { private: size_t _length; // longueur du vecteur size_t _nnz; // nombre de valeurs non nulles precision *_values; // valeurs (non nulles) du vecteur };

---

Je me suis pas mal documenté sur les classes de trait et de politique parce que j'ai pensé que ça correspondait assez à ce que je souhaite. Cependant, je maîtrise encore assez mal ces techniques et j'ai besoin de votre aide. J'ai essentiellement deux questions :

1. pour les formats de stockage, faut-il préférer des structures ou des classes?
2. comment gérer le fait que mon constructeur va être différent selon le format de stockage?

Pour un format dense, il me suffit de fournir la longueur souhaitée du vecteur pour initialiser mes données membres. Pour un format creux, je dois préciser la longueur ET le nombre de valeurs non nulles.

Merci pour votre aide!

1 - C'est pareil.
2 - Je ne sais pas. Est-ce qu'il faut qu'un vecteur plein bascule automatiquement en vecteur creux si on en modifie le contenu pour mettre des 0, et réciproquement ?

Si oui, le basculement entre les deux représentations doit être dynamique, et une stratégie type lettre-enveloppe semble appropriée.

Si non, une autre solution plus statique consisterait à définir deux classe sans aucun rapport, mais avec une interface compatible, et templatiser le code client en fonction de cette interface.S'il y a pas mal de code en commun entre les deux versions (ou si d'autres choix de ce type vont apparaître plus tard, et que tu veux faire la combinatoire des possibilités), l'utilisation de classe de politique peut être utile, sinon, deux classes séparées sont plus simples.

Pour le constructeur, pas de problème : S'il y a un endroit unique où tu connais précisément le type exact de ta classe, c'est généralement le constructeur... Un constructeur permettant de reprendre les paramètres d'un vector de même type peut aussi s'avérer utile.

PS : Je pense que tu ne donnes pas assez d'info pour ton vecteur creux, par exemple où sont les données, où sont les trous.

Merci pour ta réponse JolyLoic.

Pour la différence entre structures et classes c'est noté. Au départ, je voulais aboslument préciser dans le paramètre template qu'il faut fournir un "VectorFormat" sous forme de classe ou de structure. Avec les classes, cela me conduit à un héritage où les fils de VectorFormat sont DenseVectorFormat et SparseVectorFormat mais j'essaie d'éviter d'utiliser des fonctions virtuelles autant que possible. Avec les structures templates, je n'ai pas reçu à trouver une syntaxe correcte pour faire des typedefs. Je crois que je vais me passer de tout ça et accepter n'importe quel type de structure en paramètre.

Citation:

---

Est-ce qu'il faut qu'un vecteur plein bascule automatiquement en vecteur creux si on en modifie le contenu pour mettre des 0, et réciproquement ?

---

Non, jamais.

Citation:

---

Si non, une autre solution plus statique consisterait à définir deux classe sans aucun rapport, mais avec une interface compatible, et templatiser le code client en fonction de cette interface.S'il y a pas mal de code en commun entre les deux versions (ou si d'autres choix de ce type vont apparaître plus tard, et que tu veux faire la combinatoire des possibilités), l'utilisation de classe de politique peut être utile, sinon, deux classes séparées sont plus simples.

---

Je ne veux qu'une seule classe et faire de la spécialisation partielle quand c'est utile : le but est d'éviter d'appeler des fonctions membres virtuelles mais de pouvoir passer un 'Vector' dans d'autres fonctions de manière aveugle, quel que soit le format de stockage. Je ne spécialise que dans la classe Vector.

Code:

---

1 2	Pour le constructeur, pas de problème : S'il y a un endroit unique où tu connais précisément le type exact de ta classe, c'est généralement le constructeur... Un constructeur permettant de reprendre les paramètres d'un vector de même type peut aussi s'avérer utile.

---

Désolé, ça a l'air simple mais je ne vois pas. Pour le constructeur par copie, pas de problème mais c'est tout. Imaginons que j'ai réussi à faire tout le reste, alors j'aurais une classe commune pour les deux formats qui ressemblerait à ceci (je fais la syntaxe à l'oeil, il peut y avoir des coquilles) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

template<template<typename precision>class VectorFormat> class Vector { public: Vector(Vector<VectorFormat<precision>>const&); Vector<VectorFormat<precision>>& operator=(Vector<VectorFormat<precision>>const&); public: friend Vector<VectorFormat<precision>> operator+<>(Vector<VectorFormat<precision> const&,Vector<VectorFormat<precision> const&> // idem pour operateurs -,*,/ et le produit scalaire dot private: VectorFormat* _format; }

---

Par contre, pour le format dense, j'aimerais un constructeur du type

Code:

---

1 2	Vector(size_t const& length=0);

---

alors que pour le format creux j'aimerais plutôt

Code:

---

1 2	Vector(size_t const& length=0,size_t const& nnz=0);

---

Citation:

---

Je pense que tu ne donnes pas assez d'info pour ton vecteur creux, par exemple où sont les données, où sont les trous.

---

C'est de ma faute. Dans la précipitation, j'ai oublié de mettre le vecteur des indices pour le format creux. Le format creux doit donc ressembler à ceci

Code:

---

1 2 3 4 5 6 7

struct { size_t _length; // longueur size_t _nnz; // nombre de non zeros size_t* _indices; // indices des non zeros precision* _values; // valeurs des non zeros

---

Par exemple, pour stocker le vecteur {10, 0, 11, 0, 0, 12, 0, 0} de longueur 8, j'ai la structure de données suivante :

Code:

---

1 2 3 4 5

_length = 8; _nnz = 3; // c'est le nombre de valeurs non nulles _indices = {0,2,5} // indices des valeurs non nulles _values = {10,11,12} // valeurs non nulles

---

Citation:

---

Envoyé par Aleph69

Par contre, pour le format dense, j'aimerais un constructeur du type

Code:

---

1 2	Vector(size_t const& length=0);

---

alors que pour le format creux j'aimerais plutôt

Code:

---

1 2	Vector(size_t const& length=0,size_t const& nnz=0);

---

---

Qu'est-ce qui t'empêche de mixer les deux ?
Bon, tu peux oublier les paramètres par défaut, mais avec des constructeurs de signatures différentes, tu sais exactement quel genre de vector on veux créer : dense si on appelle le premier, creux si on appelle le second.
Je pense que c'est que qu'il voulait dire :

Citation:

---

Envoyé par JolyLoic

Pour le constructeur, pas de problème : S'il y a un endroit unique où tu connais précisément le type exact de ta classe, c'est généralement le constructeur... Un constructeur permettant de reprendre les paramètres d'un vector de même type peut aussi s'avérer utile.

---

Si cela ne te convient pas, tu peux toujours utiliser le design pattern « fabrique » (ou « usine », je ne me souviens jamais).

Si tu ne veux absolument qu'une seule classe, tu pourrais utiliser quoi qu'il arrive les quatre champs définis pour ta classe de vecteur creux, en ajoutant un champ binaire indiquant le type de vecteur (dense ou creux).

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

class Vector {   enum type {DENSE, SPARSE};   type _type; // type de vecteur size_t _length; // longueur size_t _nnz; // nombre de non zeros size_t* _indices; // indices des non zeros precision* _values; // valeurs des non zeros   };

---

Quoi qu'il arrive, tu stockes toutes les valeurs, et tu conserves les indices de valeurs non nulles.
Si tu as besoin d'un vecteur dense, tu parcours _values.
Si tu as besoin d'un vecteur creux, tu parcours _indices.
Passer de l'un à l'autre ne devrait pas être très compliqué… :P

Bonjour,

désolé mais je ne vois toujours pas. Je suis bien d'accord avec le fait que je sais quel type de vecteur je manipule en fonction de la signature du constructeur appelé mais je ne vois pas comment en profiter pour résoudre mon problème.

Pour l'instant, la seule solution qui fonctionnerait serait de spécialiser de façon globale (j'ai enlevé le paramètre template precision pour simplifier la syntaxe) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

template<typename Format> class Vector;   template<> class Vector<DenseFormat> { Vector(size_t const&); };   template<> class Vector<SparseFormat> { Vector(size_t const&,size_t const&); };

---

Le problème avec cette approche est que je vais pratiquement recopier deux fois ma classe Vector car beaucoup de fonctions membres risquent d'être totalement identiques (accesseurs et mutateurs entre autres).

Et comme ça, c'est plus clair ?

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

Vector::Vector(size_t const& length) : _length(length), _nnz(), // si nécessaire... _indices(), // si nécessaire... _values(...) { // Initialisation du vecteur dense (...)   init(); }     Vector::Vector(size_t const& length, size_t const& nnz) : _length(length), _nnz(nnz), _indices(...), _values(...) { // Initialisation du vecteur creux (...)   init(); }     // Code nécessaire au deux constructeurs, quel que soit le type de vecteur void Vector::init(...) { (...) }

---

En plus, si tu as un champ qui te permet de savoir quel type de vecteur tu manipules (ou un autre moyen), tu peux l'initialiser dans la partie spécifique du constructeur.

Pour ce qui est de ta version templatée, tu peux peux-être définir une classe (abstraite) dans laquelle tu définis tout ce qui est commun aux deux types de vecteur, puis tu la fais dériver par ta classe (toujours templatée) Vector, pour laquelle tu ne définit rien.
Les définitions auront lieu uniquement dans les classes spécialisées.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

template <typename Format> class _Vector_base {   // Tout ce qui est commun (...)   };   template <typename Format> class Vector : public/protected/private _Vector_base<Format> {};   template <> class Vector<DenseFormat> : ... _Vector_base<DenseFormat> {   // Ce qui est spécifique au format dense (...)   };   template <> class Vector<SparseFormat> : ... _Vector_base<SparseFormat> {   // Ce qui est spécifique au format creux (...)   };

---

En passant, ce ne serait pas mieux de faire quelque chose du genre :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

enum VectorFormat {DenseFormat, SparseFormat};     template <VectorFormat Format> class Vector {...};   template <> class Vector<DenseFormat> {...};   template <> class Vector<SparseFormat> {...};

---

La solution des deux constructeurs ne convient pas : si les deux constructeurs coexistent au sein de la classe Vector, je vais avoir beaucoup de mal à définir le comportement de ce type d'appel :

Code:

---

1 2	Vector<DenseFormat> vec(8,3);

---

Cela n'a pas de sens de construire un vecteur dense en lui précisant une longueur et un nombre de valeurs non nulles.

Je ne veux surtout pas passer par une classe abstraite (~fonctions virtuelles pures) car la perte en vitesse de calcul est trop importante avec certains compilateurs (g++ par ex.).

Si je comprends bien, la meilleure solution reste de faire une classe générique et de passer par de la spécialisation partielle pour gérer les différents formats. Pour les vecteurs, ça va encore mais pour les matrices je vais m'amuser étant donné le nombre de formats de stockage possibles... Merci quand même pour votre aide!

Citation:

---

Envoyé par Aleph69

Cela n'a pas de sens de construire un vecteur dense en lui précisant une longueur et un nombre de valeurs non nulles.

---

Justement !
Si tu précises au constructeur le nombre de valeurs non nulle, c'est que forcément tu veux créer un vecteur creux.
Si à l'inverse tu ne le précises pas, c'est que forcément tu veux créer un vecteur dense.
Ils peuvent coexister car ils ne créent aucune ambigüité !
Bien au contraire ! :ccool:

Citation:

---

Envoyé par Aleph69

Je ne veux surtout pas passer par une classe abstraite (~fonctions virtuelles pures) car la perte en vitesse de calcul est trop importante avec certains compilateurs (g++ par ex.).

---

Rien ne t'oblige à écrire des fonctions virtuelles, pures ou non.
Si tu déclares les constructeurs et le destructeur de la classe de base « protected », c'est comme si elle était abstraite (d'un point de vue extérieur en tout cas).

Tu peux même déclarer toutes tes fonctions membres comme protégées ou privées, et augmenter leur visibilité à l'aide de la directive « using ».
De cette manière, depuis l'extérieur on n'aura aucune visibilité sur la classe de base, excepté son nom.
Donc on la connaîtra, mais on ne pourra strictement rien en faire.

Si en plus tu fais un héritage protégé ou privé… :roll: ;)

Citation:

---

Envoyé par Steph_ng8

Justement !
Si tu précises au constructeur le nombre de valeurs non nulle, c'est que forcément tu veux créer un vecteur creux.
Si à l'inverse tu ne le précises pas, c'est que forcément tu veux créer un vecteur dense.
Ils peuvent coexister car ils ne créent aucune ambigüité !
Bien au contraire ! :ccool:

---

Sur le principe, je suis d'accord mais je ne vois pas ce qui empêche l'utilisateur d'appeler des mauvaises combinaisons format/constructeur comme dans l'exemple que j'ai donné.

Citation:

---

Envoyé par Steph_ng8

Rien ne t'oblige à écrire des fonctions virtuelles, pures ou non.
Si tu déclares les constructeurs et le destructeur de la classe de base « protected », c'est comme si elle était abstraite (d'un point de vue extérieur en tout cas).

---

Oui, je comprend bien ce point de vue. On commence à se rapprocher des classes de politique pour faire partager une interface commune aux deux types de format de stockage. En fait, c'est vraiment à la construction que j'ai un problème. Le reste est plutôt clair ensuite.

Citation:

---

Envoyé par Aleph69

Sur le principe, je suis d'accord mais je ne vois pas ce qui empêche l'utilisateur d'appeler des mauvaises combinaisons format/constructeur comme dans l'exemple que j'ai donné.

---

Ah bah c'est sûr que si l'utilisateur fait n'importe quoi, aussi… :|
Dans ce cas, tu peux tourner vers le design pattern « fabrique » :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Vector {   public: static Vector * createDenseVector(size_t length = 0) { return new Vector(length); }   static Vector * createSparseVector(size_t length = 0, size_t nnz = 0) { return new Vector(length, nnz); }     private: // Crée un vecteur dense Vector(size_t length);   // Crée un vecteur creux Vector(size_t length, size_t nnz);   };

---

Ceci dit, rien n'empêche l'utilisateur d'appeler « createSparseVector() » alors qu'il veut créer un vecteur dense…
Sauf éventuellement le bon sens ; mais si ta classe est bien documentée (et qu'il fait l'effort de lire la documentation), s'il a du bon sens il ne se trompera pas.

Citation:

---

Envoyé par Aleph69

Oui, je comprend bien ce point de vue. On commence à se rapprocher des classes de politique pour faire partager une interface commune aux deux types de format de stockage. En fait, c'est vraiment à la construction que j'ai un problème. Le reste est plutôt clair ensuite.

---

Ok. :ccool:

Bonjour,

j'ai finalement trouvé la solution à mon problème dans le livre d'Alexandrescu. En fait, les classes de politique permettent permettent de résoudre le problème des constructeur. Il suffit de faire une classe de politique pour le format dense avec un constructeur prenant un size_t en paramètre, et une classe de politique pour le format creux avec un constructeur prenant deux size_t en paramètres. Ensuite, dans la classe Vector, on propose deux types de constructeurs, l'un prenant un size_t en paramètre et faisant appel au constructeur de la classe de politique dans la liste d'initialisation, l'autre prenant deux size_t en paramètres et faisant appel au constructeur de la classe de politique dans la liste d'initialisation. Ainsi, si on tente de construire un vecteur dense en passant deux size_t en paramètres, on a une erreur à la compilation. De même, si on tente de construire un vecteur creux en passant un seul size_t en paramètre, on a une erreur à la compilation.

Encore merci pour votre aide!