Classe Liste générique avec template

Version imprimable

Bonsoir,

Les Topics se suivent...mais ne se ressemble pas! J'ai un petit, bon d'accord un gros problème avec un bout de code qui concerne une liste générique doublement chaînée lorsque je l'utilise avec des vecteurs (pas ceux de la STL...).
Le problème est une fuite mémoire assez bizarroïde (c'est le propre d'une fuite mémoire?) qui se passe quand je lance le programme et qui freeze DrWatson (le débugeur post-mortem qui arrive après le crash de l'application) une 30aine de seconde...Donc réflexe, je lance le débugueur de C::B et là.... PATATRAAAAA, ça fonctionne au poil...

Du côté liste :

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
  template<typename TYPE, unsigned int nb_cur>
  struct LIST
    {
        ///Data level
        struct ELMT
        {
            ELMT* prev;
            TYPE data;
            ELMT* next;
 
            ELMT(ELMT* p, TYPE& dat) : data(dat)
            {
                prev = p;
            }
        };
 
        ///Data
        unsigned int length;
        ELMT *fst;
        ELMT *cur[nb_cur];
        ELMT *lst;
 
        LIST()
        {
            unsigned int i;
 
            length = 0;
 
            fst = NULL;
            lst = NULL;
 
            for(i=0; i<nb_cur; i++)
                cur[i]=NULL;
 
            return ;
        }
 
        unsigned int push(TYPE& data)
        {
            //Data problem
            if( fst==NULL )
            {
                fst = new ELMT(NULL, data);
                lst = fst;
            }
            else
            {
                lst->next = new ELMT(lst, data);
                lst = lst->next;
            }
 
            length++;
            return length;
        }
    };

Du côté vecteur (dim étant un entier, non signé, prédéfini)

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
32
 
      struct VECTOR
        {
            float* data;
 
            VECTOR()
            {
                data = new float(dim);
                return ;
            }
 
            VECTOR(VECTOR& v)
            {
                unsigned int i;
                data = new float(dim);
 
                for(i=0; i<dim; i++)
                    *(data+i) = *(v.data+i);
 
                return ;
            }
 
            VECTOR& operator= (const VECTOR& v)
            {
                unsigned int i;
 
                for(i=0; i<dim; i++)
                    *(data+i) = *(v.data+i);
 
                return *this;
            }
   };

(bien entendu j'ai allégé un peu le code...)

et pour le test :

Code:

1
2
3
4
 
VECTOR a;
LIST<VECTOR,1> lst;
lst.push(a);

(dois-je aussi utiliser plutôt memcpy et memset pour mes opérations sur des tableaux???)

Voili, voilou, je vous remercie de m'aider.

09/05/2009, 01h15
JolyLoic

Tu n'as pas de destructeurs dans ton code ?
Ensuite, que se passe-t-il si l'utilisateur essaye de copier un objet de type LIST ?
A part ça, il est plus courant d'avoir comme signature pour un constructeur de copie : VECTOR(VECTOR const & v) au lieu de VECTOR(VECTOR& v)
09/05/2009, 03h51
Arzar

Ce code

Code:

data = new float(dim);

alloue un float dans le tas, lui affecte la valeur "dim" et renvoie un pointeur dessus.
Je suppose que tu souhaites plutôt allouer un tableau de 10 float :

Code:

data = new float[dim];

(Attention à bien utiliser delete[] au lieu de delete dans le destructeur)

Merci beaucoup pour vos réponses :D...

En fait je n'ai pas publié les destructeurs mais ils sont dans le code compilé (et dans leurs classes respectives)...
Pour List :

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
 
        ~LIST()
        {
            while(length>0) drop();
        }
 
        unsigned int drop(void)
        {
            if( lst!=NULL )
            {
                if( lst->prev!=NULL )
                {
                    lst = lst->prev;
                    delete lst->next;
                }
                else
                {
                    fst = NULL;
                    delete lst;
                }
                length--;
            }
 
            return length;
        }

Pour Vector :

Code:

1
2
3
4
5
 
            ~VECTOR()
            {
                delete[] data;
            }

Par contre je n'ai pas encore implémenté la copie de LIST...
Merci, pour l'erreur du new (() au lieu de []) que je n'avais pas vu :aie:...

Petite question 1 : est-il plus propre d'utiliser les memset et memcpy que des boucles for?
Petite question 10 : sur l'utilisation du mot clé const, j'ai repéré cette adresse. Faut-il toujours suivre ces conseils comme des idiomes de programmation???

Merci de votre aide.

09/05/2009, 13h36
hiura

Citation:

Envoyé par TNT89

Petite question 10 : sur l'utilisation du mot clé const, j'ai repéré cette adresse. Faut-il toujours suivre ces conseils comme des idiomes de programmation???

Je ne vois aucune raison valide de ne pas produire du code correcte au niveau des const.

Salut,

A vrai dire, il y a un certain nombre de chose que je ne comprend pas vraiment...

Par exemple, l'usage que tu peux avoir du membre (tableau de pointeur de type ELEM) cur...

Typiquement, les listes chainées sont utilisée, justement, pour ne pas devoir recourir à un tableau contigu d'éléments (même s'il doit s'agir d'un tableau de pointeurs) pour en gérer le contenu...

D'autent plus que chaque élément a une référence vers l'élément qui le suit, et comme nous parlons d'une liste doublement chainée, une référence vers l'élément qui le précède...

L'idée générale d'une liste simplement chainée est donc de n'allouer qu'un seul élément à chaque fois, et "sur demande" (au moment où l'on décide de rajouter un élément)

De plus, comme pour tout élément de n'importe quelle structure dynamique (pile, file, liste, arbre binaire), la création d'un élément doit être simplifiée au maximum:
tu alloue l'espace mémoire pour l'élément, tu initialise l'objet qu'il contient, et tu initialise les références vers les éléments "adjacents" à NULL.

C'est en effet du seul role de la structure dynamique d'aller "chipoter" à ces références pour l'insérer... dans la structure dynamique.

(au fait, évite de choisir des noms tout en majuscules pour tes structures... c'est généralement réservé aux définitions préprocesseur ;))

Au final, ta structure devrait prendre (hors template) une forme proche de

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class Liste
{
    public:
        class Element
        {
            public:
                Element(Type const& value):value(value),prev(0),next(0){}
                ~Element(){/* rien à faire */}
                /* les acces aux éléments précédents et suivants */
                Element* operator++(){return next;}
                Element* operator--(){return prev;}
                Element const * operator++ const{return next;}
                Element const * operator-- const{return prev;}
                /* les acces a la valeur contenue */
                Type & operator*(){return value;}
                Type const & operator*() const{return value;}
                Type & operator->(){return value;}
                Type const & operator() const{return value;}
            private:
                Type value;
                Element* prev;
                Element* next;
                /* la liste doit pouvoir accéder aux pointeurs privés */
                friend class Liste;
        }
        Liste():msize(0),first(0),last(0){}
        /* les fonctions suivantes ne devraient pas être inline
         * Si elles le sont, c'est juste par flegme...
         */
        ~Liste()
        {
            while(first)
            {
                Element* temp=first->next;
                delete first;
                first=temp;
            }
        }
        void push_back(Type const& value)
        {
            Element* temp=new Element(value);
            if(!first)
                first=temp;
            temp->prev=last;
            if(last)
                last->next=temp;
            last = temp;
        }
        void insert(Element* prev, Type const & value)
        {
            if(prev == last || (prev==0 && last==0))
                push_back(value);
            else
            {
                ASSERT(prev!=0);
                Element* temp=new Element(value);
                if(prev->next)
                {
                    temp->next = prev->next;
                    prev->next->prev = temp;
                }
                prev->next = temp;
                temp->prev = prev;
            }
        }
        size_t size() const
        {
            if (!first)
                return 0;
            size_t ret=0;
            Element* temp=first;
            while(temp)
            {
                ++ret;
                 tem=temp->next;
            }
            return ret;
        }
        /* il faudrait aussi de quoi supprimer un élément et, pourquoi pas,
         * un ensemble d'éléments adjacents
         * les fonctions suivantes peuvent être inline 
         */
        bool empty() const{return first!=0;}
        Element* begin(){return first;}
        Element* end(){return 0;}
        Element const * begin() const{return first;}
        Element const * end() const{return 0;}
    private:
        Element* first;
        Element* last;
};

(code créé "from scratch", non testé, mais normalement correct ;))

09/05/2009, 14h23
TNT89

Le tableau de pointeurs 'cur' me sert pour définir un ensemble de curseurs pointant donc vers certains éléments du tableau...Cela me permet de faire des traitements propre à chaque liste en se souvenant de certaines caractéristiques (d'où un tableau de taille fixée)...
Enfin après il y a surement possibilité de faire mieux...(mais le mieux est l'ennemi du bien :lol:)...
09/05/2009, 14h33
koala01

Citation:

Envoyé par TNT89

Le tableau de pointeurs 'cur' me sert pour définir un ensemble de curseurs pointant donc vers certains éléments du tableau...Cela me permet de faire des traitements propre à chaque liste en se souvenant de certaines caractéristiques (d'où un tableau de taille fixée)...

Sauf que cela n'entre pas dans les responsabilités de la liste...

La seule responsabilité de la liste, c'est de maintenir l'ensemble des éléments en un tout cohérent, et c'est déjà amplement suffisant.

Si tu veux disposer, pour un usage particulier, d'une structure qui permette de garder un index de certains éléments de la liste sur lesquelles certaines actions ont été effectuées, ca doit être de la responsabilité d'autre chose, qui disposera d'une liste et d'un tableau d'éléments ;)
09/05/2009, 14h56
TNT89

c'est plutôt philosophique donc...J'avais envie d'en-capsuler ces deux objets car je n'ai pas besoin de listes au sens classique du terme...et ce n'est pas destiné à être une librairie... :(

Je vous remercie de vos remarques : :king:
09/05/2009, 15h14
koala01

Ce n'est absolument pas "philosophique"...

C'est la seule manière de s'assurer que l'on évite des problèmes qui apparaitront systématiquement du fait que tu en demande trop à une seule et unique chose...

De plus, cela permet de "modulariser" beaucoup mieux ton programme ;)