STL: conteneur hétérogène

STL: conteneur hétérogène - C++ - Programmation

Marsh Posté le 03-04-2005 à 17:11:44    

Je souhaite faire un conteneur hétérogène. Dans mon cas, il s'agit d'une pile.
 
Voic mes classes:

Code :
  1. class cRoot; // classe vide
  2. class cNumber: public cRoot; // un nombre
  3. class cString: public cRoot; // un string


 
1ère tentative:

Code :
  1. stack<cRoot *> s;
  2. s.push(new cString("bonjour!" ));
  3. s.push(new cNumber(3.1415926535));
  4. s.top()->Disp(); s.pop();
  5. s.top()->Disp(); s.pop();


Résultat:  
3.1415926535bonjour!
ça marche. Seulement, il m'a fallu appeler l'opérateur new une fois par élément ajouté. Dans mon cas, c'est inacceptable.
 
2ème tentative:

Code :
  1. stack<cRoot> s;
  2. s.push(cString("bonjour!" ));
  3. s.push(cNumber(3.1415926535));
  4. s.top().Disp(); s.pop();
  5. s.top().Disp(); s.pop();


Au début ça ne compilait pas. J'ai muni les classes cString et cNumber un constructeur de copie, ainsi que l'opérateur =.
À présent ça compile, mais ça ne fonctionne pas (Bleme).
Source exact (que vous pouvez tester):

Code :
  1. #include <stack>
  2. #include <iostream>
  3. #include <string>
  4. using namespace std;
  6. class cRoot
  7. {
  8. public:
  9. virtual void Disp() { cout<<"Bleme";};
  10. };
  12. class cNumber : public cRoot
  13. {
  14. public:
  15. double n;
  16. cNumber()    { n=0; }
  17. cNumber(double n_)   { n=n_; }
  18. cNumber(const cNumber &n_)  { n=n_.n; }
  19. cNumber & operator= (cNumber &n_)
  20. {
  21.  n=n_.n;
  22.  return (*this);
  23. }
  24. void Disp() { cout<<n; }
  25. };
  27. class cString : public cRoot
  28. {
  29. public:
  30. string str;
  31. cString()   { str=""; }
  32. cString(string str_)  { str=str_; }
  33. cString(const cString &str_) { str=str_.str; }
  35. cString & operator= (cString &s)
  36. {
  37.  str=s.str;
  38.  return *this;
  39. }
  40. void Disp() { cout<<str; }
  41. };
  43. void main()
  44. {
  45. stack<cRoot> s;
  47. s.push(cString("bonjour" ));
  48. s.push(cNumber(3.1415926535));
  50. (&s.top())->Disp(); s.pop();
  51. (&s.top())->Disp(); s.pop();
  53. puts("" );
  54. }


 
Je me doute que les constructeurs bien de copie cNumber et cString ne sont même pas invoqués. Comment palier cela ?
 

Reply

Marsh Posté le 03-04-2005 à 17:11:44   

Reply

Marsh Posté le 03-04-2005 à 17:42:12    

si tu veux du polymorphisme, tu es forcé de passer par des pointeurs ou des références ...

Reply

Marsh Posté le 03-04-2005 à 18:05:25    

theshockwave a écrit :

si tu veux du polymorphisme, tu es forcé de passer par des pointeurs ou des références ...


Dans ce cas, je repose ma question différemment: est-il possible en C++ de faire appel à un constructeur, ou a un constructeur de copie sur un emplacement spécifique de la mémoire?
 
Exemple (qui ne marche pas systématiquement):

Code :
  1. #define MAXSIZE 4096
  2. class MyStack
  3. {
  4. public:
  5. char *tmp;
  6. int tmp_;
  7. MyStack();
  8. ~MyStack();
  9. void Push(cRoot *r); // empile physiquement l'objet
  10. void Pop();
  11. cRoot * Top();
  12. };
  13. MyStack::MyStack()
  14. {
  15. tmp=new char[MAXSIZE];
  16. tmp_=MAXSIZE;
  17. }
  18. MyStack::~MyStack()
  19. {
  20. delete tmp;
  21. }
  22. void MyStack::Push(cRoot *r)
  23. {
  24. cRoot *t;
  25. tmp_-=r->size();
  26. t=(cRoot *)&tmp[tmp_];  //cast violent
  27. (*t)=(*r); // je fais appel à l'opérateur=, ça ne marche pas systématiquement (par exemple avec STL string)
  28. }
  30. void MyStack::Pop()
  31. {
  32. cRoot *t;
  33. t=(cRoot *)&tmp[tmp_];
  34. tmp_+=t->size();
  35. }
  37. cRoot *MyStack::Top()
  38. {
  39. cRoot *t;
  40. t=(cRoot *)&tmp[tmp_];
  41. return t;
  42. }
  44. void main()
  45. {
  46. MyStack s;
  47. s.Push(&cString("bonjour" ));
  48. s.Push(&cNumber(3.1415926535));
  50. s.Top()->Disp(); s.Pop();
  51. s.Top()->Disp(); s.Pop();
  52. }


C'est tordu, mais ça m'éviterait de faire des new.  

Reply

Marsh Posté le 03-04-2005 à 18:48:07    

new (emplacement) T
 
après c'est toi qui te fous des limites à la con : j'aime bien le "c'est inacceptable" ... quand on voit la daube que tu veux utiliser en  tentative de remplacement ... allez, commence par mettre des warnings à ton compilateurs et reviens jouer plus tard.
 
NB : c'est la pire daube que j'ai jamais vu, je sais pas comment tu oses dire que ça marche.

Reply

Marsh Posté le 03-04-2005 à 18:51:42    

cRoot n'a pas la taille d'un char, donc déjà, quand tu stockes un CRoot à l'emplacement tmp[1], tu écrases une partie des données de tmp[0] (c'est typiquement ce qui se passe quand tu mets ton cNumber dans ta pile après avoir mis ta cString)
enfin bon, dans le principe, tu dois être forcé de faire des new pour allouer tes objets, oui. (évidemment, passer tmp au type cRoot ne résoudrait pas les problèmes puisque tu écraserais les portions des objets qui sont spécifiques aux classes cNumber et cString)
 
=> tu passes ton tmp en cRoot *, tu lui alloues la taille pour stocker tes 4096 pointeurs sur cRoot et tu passes des objets construits par new dans tes fonctions ... je pense que c'est ce qu'il y a de mieux à faire

Reply

Marsh Posté le 03-04-2005 à 18:59:40    

euh non, c'est pas pire, mais pas vraiment meilleur. c'est un problème insoluble. Soit tu fais du polymorphisme, ce qui est génial, soit tu maintiens 3 conteneurs pour tes 3 types, soit tu réécris un allocateur mémoire ce qui serait complètement stupide mais pourtant tu essaies d'en bricoler un.

Reply

Marsh Posté le 03-04-2005 à 19:04:21    

Taz a écrit :

euh non, c'est pas pire, mais pas vraiment meilleur. c'est un problème insoluble. Soit tu fais du polymorphisme, ce qui est génial, soit tu maintiens 3 conteneurs pour tes 3 types, soit tu réécris un allocateur mémoire ce qui serait complètement stupide mais pourtant tu essaies d'en bricoler un.


 
 
j'ai foiré ma double étoile :o .... Je voulais dire de passer tmp en " cRoot ** " (vu le reste de la phrase, c'est assez clair, remarque) ce qui revient à faire un conteneur et utiliser le polymorphisme.
 
 
(Edit : l'idée de l'allocateur m'avait traversé l'esprit, mais je ne suis pas encore assez à l'aise pour en parler  :whistle: )


Message édité par theshockwave le 03-04-2005 à 19:05:55
Reply

Marsh Posté le 03-04-2005 à 19:21:52    

faudrait arrêter la branlette intellectuelle quand -- à ce que je vois, -- y a des bases niveau pointeurs qui sont manquantes.
 
Reprenons depuis le début.
 
Pourquoi 'inacceptable' ?

Reply

Marsh Posté le 03-04-2005 à 20:27:14    

Taz a écrit :

faudrait arrêter la branlette intellectuelle quand -- à ce que je vois, -- y a des bases niveau pointeurs qui sont manquantes.
 
Reprenons depuis le début.
 
Pourquoi 'inacceptable' ?


 
Tout d'abord, t'es pas obligé de me pourrir la gueule lorsque tu réponds :)
 
Bon je raconte mon histoire.  
J'ai réalisé une machine virtuelle. Ma pile<pRoot> (pRoot= smart pointer sur cRoot*) peut contenir des cString, cNumber, cFunction, cLValue etc... Le tout est 100% objet, malloqué en temps réel, et utilisant les smart pointer ainsi que les STL.  
Seul problème: ça rame.
 
En regardant de plus près, je me suis aperçu que c'était essentiellement du à la fonction pop() de ma pile "système". En effet, push() et pop() utilisent directement ou non new et delete. Moralité: je fais en moyenne 1 à 2 new et 1 delete par cycle instruction. Je tourne à peu près à 50 000 cycle/s (en release) ce qui est très faible, même si mon Athlon 1.2 GHz commence à se faire vieux.
 
Je me suis dit qu'on pourrait gagner en vitesse en copiant physiquement les objets dans la pile. En effet, dans ce cas précis, pas besoin d'utiliser new et delete puisqu'on est capable de prévoir quand et où un objet doit être construit/détruit. Dans les autres cas, on peut continuer à utiliser new et delete, car ils sont beaucoup moins souvent utilisés.
 
Pour ceux qui ont déjà réalisé des moteurs en C, le problème ne se pose pas puisqu'on utilise des structures, et que push() et pop() peuvent s'écrire avec des macros du genre:

Code :
  1. #define PUSH(valeur) (*pile++)=valeur
  2. #define POP() (*--pile)


En revanche, en C , on se trimbale des struct {char type, union{ valeurs }} , des switch(type), et pleins d'autres trucs pas vraiment sexy.
 
 
Bref, j'avais vu que STL stack<> n'utilisait pas d'opérateur new et remplissait la pile en faisant des affectations (constructeur de copie). Je me suis dit que mon problème pouvait être résolu en utilisant le STL stack<>.
 
Apparemment je vais devoir gruger en utilisant explicitement le constructeur de copie (et le detructeur), sur l'emplacement mémoire de mon choix, en écrivant un truc du style (par exemple pour cString):

Code :
  1. void CopyTo(cString *s, char *ptr)
  2. {
  3. ((cString*)ptr)->cString::cString(*s);
  4. }


 
TAZ: Je vais voir si new(emplacement)T va résoudre mon problème.  
      Merci quand même et promets d'être un peu plus poli la prochaine fois :)
 
Shockwave: C'est pour ça que j'incrémente en faisant tmp+=size() (size étant une fonction à moi retournant le sizeof de la classe courante).


Message édité par joek-mel le 03-04-2005 à 20:46:04
Reply

Marsh Posté le 03-04-2005 à 20:50:17    

tu ne voudrais pas faire une méthode push template, plutôt ?
 
Edit : mouais, en fait, ca ne résoudrait pas tous les pbs ...


Message édité par theshockwave le 03-04-2005 à 20:51:28
Reply

Marsh Posté le 03-04-2005 à 20:50:17   

Reply

Marsh Posté le 03-04-2005 à 21:09:04    

theshockwave a écrit :

tu ne voudrais pas faire une méthode push template, plutôt ?
 
Edit : mouais, en fait, ca ne résoudrait pas tous les pbs ...


 
Je sais pas encore comment je vais implémenter tout ça. Le void CopyTo est un exemple, mais bon, c'est pas très "classe" d'utiliser ça comme ça :)
 
De même qu'il faut que je regarde comment se comporte new(emplacement)T : si celui-ci ne fait qu'appeler le constructeur de copie sans chercher à allouer une seconde fois cet emplacement, alors ça peut être cool. Et inversement, si le delete associé ne se contente que d'appeler le destructeur sans chercher à libérer cet emplacement, alors ça peut être doublement cool :)
 
Vala.
 
TAZ: t'as autre chose à ajouter? (poliment :) )


Message édité par joek-mel le 03-04-2005 à 21:10:39
Reply

Marsh Posté le 03-04-2005 à 21:12:46    

Si le bottle-neck est l'allocation / destruction (et que tu en es sur), peut etre peux tu envisager de manipuler l'allocateur standard directement.  
 
Mais bon, Taz n'a pas tord, ton C++ est maladroit, et je ne suis pas convaincu qu'il n'y ait rien d'autre à optimiser que l'allocation.

Reply

Marsh Posté le 03-04-2005 à 21:13:52    

ton void CopyTo me fait plus penser à un problème de conception qu'à autre chose, en fait.
Tu mets en place une interface pour manipuler tes variables empilables et au final, tu ne peux pas l'utiliser à 100% :/

Reply

Marsh Posté le 03-04-2005 à 21:19:13    

++fab a écrit :

Si le bottle-neck est l'allocation / destruction (et que tu en es sur), peut etre peux tu envisager de manipuler l'allocateur standard directement.


Dans ces cas là, Google est son ami.
 
Nan, pas Google le moteur de recherche: Google la société.
    http://sourceforge.net/projects/goog-perftools/
 

Reply

Marsh Posté le 04-04-2005 à 01:26:33    

t'as le droit d'écrire un allocateur pour tes objets si tu trouves que ça rame. Ou de faire un cache (c'est à dire que plutot que de désallouer tes instances, tu en gardes quelques une sous la main). Genre trash stack.
 
 
Mais vu ton aisance avec les pointeurs, j'ai quand même bien envie de pencher pour un problème d'algorithmie ou de conception, en premier lieu.
 
 
Pour moi ton problème, c'est que tu veux jouer au warrior, sauf que ça prend pas. Tout problème peut se résoudre élégemment. Et avec de l'abstraction. Tu crois que le problème c'est l'allocation mémoire physique de tes objets, alors que c'est plus un problème de durée de vie.
 
(cString*)ptr)->cString::cString(*s);
 
je comprends même qpas ce que ça veut dire tellement c'est affreux.
 
new (ptr) cString(*s); c'est pourtant pas compliqué !
 
et puis je comprends ton obsession avec la pile. déjà que t'es entrain de nous montrer comment faire des pointeurs sur des variables temporaires ... La pile c'est plus rapide pour allouer, c'est tout. Une fois que tu as ton allocateur (même basé sur un pauvre vector) et ben ça fait la même performance à priori.
 
Il faudrait vraiment que tu apprennes un peu le C++, sinon ça va être un carnage vu tes notions sur les pointeurs et la POO en C++. Tu veux un exercice ? commence par écrire
 
template<typename T>
T** make(size_t d1, size_t d2);
 
qui alloue une matrice d1 x d2 de manière contigüe. C'est formatteur comme exercice.
 
Suis mon conseil : utilise un allocateur type pool (y en a chez boost) ou fais un petit cache.


Message édité par Taz le 04-04-2005 à 01:27:42
Reply

Marsh Posté le 04-04-2005 à 01:30:05    

juste un petite question... la machine virtuelle est censée interpreter quoi ?

Reply

Marsh Posté le 04-04-2005 à 14:23:53    

Taz a écrit :

t'as le droit d'écrire un allocateur pour tes objets si tu trouves que ça rame. Ou de faire un cache (c'est à dire que plutot que de désallouer tes instances, tu en gardes quelques une sous la main). Genre trash stack.
 
 
Mais vu ton aisance avec les pointeurs, j'ai quand même bien envie de pencher pour un problème d'algorithmie ou de conception, en premier lieu.
 
 
Pour moi ton problème, c'est que tu veux jouer au warrior, sauf que ça prend pas. Tout problème peut se résoudre élégemment. Et avec de l'abstraction. Tu crois que le problème c'est l'allocation mémoire physique de tes objets, alors que c'est plus un problème de durée de vie.
 
(cString*)ptr)->cString::cString(*s);
 
je comprends même qpas ce que ça veut dire tellement c'est affreux.
 
new (ptr) cString(*s); c'est pourtant pas compliqué !
 
et puis je comprends ton obsession avec la pile. déjà que t'es entrain de nous montrer comment faire des pointeurs sur des variables temporaires ... La pile c'est plus rapide pour allouer, c'est tout. Une fois que tu as ton allocateur (même basé sur un pauvre vector) et ben ça fait la même performance à priori.
 
Il faudrait vraiment que tu apprennes un peu le C++, sinon ça va être un carnage vu tes notions sur les pointeurs et la POO en C++. Tu veux un exercice ? commence par écrire
 
template<typename T>
T** make(size_t d1, size_t d2);
 
qui alloue une matrice d1 x d2 de manière contigüe. C'est formatteur comme exercice.
 
Suis mon conseil : utilise un allocateur type pool (y en a chez boost) ou fais un petit cache.


 
red faction: ma machine virtuelle est de type lisp. Les mots clés sont codés par d'autres personnes, qui me fournissent des DLLs. Tout ça pour dire que mon programme est très court, est qu'il ne fait qu'empiler, dépiler, et appeler des fonctions compilées.
 
Taz, Lam's: Je veux éviter au maximum les 3rd parties. Car si je les utilise, la personne qui développe une DLL devra les utiliser aussi (puisqu'on partage les mêmes piles, donc les mêmes données).
 
Taz:  

  • La différence entre ton new propre et mon constructeur de copie sale est que ton new propre impose d'écrire des opérateur new & delete au sein de la classe. C'est peut être ce que je devrais faire. Je regarde ça...
  • T'as déjà écrit un interpréteur?  

Reply

Marsh Posté le 05-04-2005 à 09:06:27    

joek-mel a écrit :

red faction:
Taz, Lam's: Je veux éviter au maximum les 3rd parties. Car si je les utilise, la personne qui développe une DLL devra les utiliser aussi (puisqu'on partage les mêmes piles, donc les mêmes données).


 
mouais enfin BOOST c'est du STL like hein ...  
 

joek-mel a écrit :

red faction:

  • T'as déjà écrit un interpréteur?

Ouais en 15mn montre en main avec :
http://www.boost.org/libs/spirit/index.html
 
mais bon , c'est vrai c'est du Third Party  [:everything4free] reinventez la roue c'est tellement plus hype  [:joel f]

Reply

Marsh Posté le 05-04-2005 à 09:45:11    

joek-mel a écrit :

red faction: ma machine virtuelle est de type lisp. Les mots clés sont codés par d'autres personnes, qui me fournissent des DLLs. Tout ça pour dire que mon programme est très court, est qu'il ne fait qu'empiler, dépiler, et appeler des fonctions compilées.
 
Taz, Lam's: Je veux éviter au maximum les 3rd parties. Car si je les utilise, la personne qui développe une DLL devra les utiliser aussi (puisqu'on partage les mêmes piles, donc les mêmes données).
 
Taz:  

  • La différence entre ton new propre et mon constructeur de copie sale est que ton new propre impose d'écrire des opérateur new & delete au sein de la classe. C'est peut être ce que je devrais faire. Je regarde ça...
  • T'as déjà écrit un interpréteur?


1) non
2) oui

Reply

Marsh Posté le 05-04-2005 à 11:26:25    

gniarf gniarf  
 

Code :
  1. #include <stack>
  2. #include <iostream>
  3. #include <string>
  4. using namespace std;
  5. class    cRoot
  6. {
  7. public:
  8. cRoot* subthis; //arf  
  9.     virtual void Disp() { //cout<<"Bleme";  
  10.       subthis->Disp();};
  11. void visit()
  12. {
  13.  subthis->iamvisited();
  14. }
  15. virtual void iamvisited() { cout<< " visiting croot " <<endl;}
  16. };
  17. class    cNumber : public cRoot
  18. {
  19. public:
  20.     double    n;
  21.     cNumber()                { n=0; subthis=this;}
  22.     cNumber(double n_)            { n=n_; subthis=this;}
  23.     cNumber(const cNumber &n_)        { n=n_.n; subthis=this;}
  24.     cNumber & operator= (cNumber &n_)
  25.     {
  26.         n=n_.n;
  27.  subthis=this;
  28.         return (*this);
  29.     }
  30. void iamvisited() { cout<< " visiting cnumber " <<endl;}
  31.     void    Disp()    {    cout<<n; }
  32. };
  33. class    cString : public cRoot
  34. {
  35. public:
  36.     string    str;
  37.     cString()            { str=""; subthis=this;}
  38.     cString(string str_)        { str=str_; subthis=this;}
  39.     cString(const cString &str_)    { str=str_.str; subthis=this;}
  40.    
  41.     cString & operator= (cString &s)
  42.     {
  43.  subthis=this;
  44.         str=s.str;
  45.         return *this;
  46.     }
  47. void iamvisited() { cout<< " visiting cstring " <<endl;}
  48.     void    Disp()    {    cout<<"string ["<<str<<"]"; }
  49. };
  52. void main()
  53. {
  54.   stack<cRoot>    s;
  55.     s.push(cString("bonjour" ));
  56.     s.push(cNumber(3.1415926535));
  57.     (&s.top())->Disp(); s.pop();
  58.     (&s.top())->Disp(); s.pop();
  59.     puts("" );
  61. }

Reply

Marsh Posté le 05-04-2005 à 11:29:54    

je quitte se topic, j'ai jamais vu autant de bêtises en si peu de code.

Reply

Marsh Posté le 05-04-2005 à 11:34:52    

Moi je trouve ca rigolo. salut grognon.  

Reply

Marsh Posté le 05-04-2005 à 11:45:42    

oh est puis quoi j ai rate le premier avril alors j'me ratrappe ;)

Reply

Marsh Posté le 05-04-2005 à 13:24:58    

:heink:


---------------
-( BlackGoddess )-
Reply

Marsh Posté le 05-04-2005 à 16:20:45    

Taz a écrit :

je quitte se topic, j'ai jamais vu autant de bêtises en si peu de code.


 
Merci pour les conseils. Quant à moi, je crois que je vais retourner à l'école :)

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed