Problème : std::string et Segfault

Version imprimable

Bonjour,

Un petit bout de code vaut mieux qu'un long discours alors c'est parti! :

Ma classe de liste et ses itérateurs (j'adore réinventer la roue...)

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
92
template<typename T>
        struct List
        {
            /// Data
                T        Data;
                List<T>* Next;
                List<T>* Previous;
 
            /// Iterators
                struct Iterator
                {
                    private :
                        List<T>* l;
                    public :
                        Iterator(void)  {l = NULL;}
 
                        Iterator(List<T>* _l) {l = _l;}
 
                        Iterator(List<T>& _l) {l = &(_l);}
 
                        bool isNull(void) {return l==NULL;}
 
                        void next(void)
                        {
                            if(l!=NULL)
                                l = l->Next;
                        }
 
                        void previous(void)
                        {
                            if(l!=NULL)
                                l = l->Previous;
                        }
 
                        void push(const T& dat)
                        {
                            if(l!=NULL)
                                l->push(dat);
                        }
 
                        void pushAndMove(const T& dat)
                        {
                            if(l!=NULL)
                            {
                                while(l->Next!=NULL) l = l->Next; //go to the end
 
                                l->push(dat); // push element
 
                                l = l->Next; // move to it
                            }
                            else
                                std::cout << "accessing NULL data" << std::endl;
                        }
                };
 
            /// Constructors
                List(void) : Data()
                {
                    Next = NULL;
                    Previous = NULL;
                }
 
                List(const T& data, List<T>* prev = NULL, List<T>* next = NULL) : Data(data)
                {
                    Next     = next;
                    Previous = prev;
                }
 
                ~List(void)
                {
                    if(Next!=NULL)
                    {
                        Next->Previous = NULL; //eviter de revenir sur cet élément (this)
                        delete Next;
                    }
                    if(Previous!=NULL)
                    {
                        Previous->Next = NULL;  //eviter de revenir sur cet élément (this)
                        delete Previous;
                    }
                }
 
            /// Methods
                void push(const T& data)
                {
                    List<T>* it = this;
 
                    while(it->Next!=NULL) it = it->Next; //tant qu'il y a du monde derrière
 
                    it->Next = new List<T>(data, it, NULL);
                }
    };

et le code qui fait tout planter... (un joli Segmentation Fault apparaît après "done" et avant la fin du programme...)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int main()
{
    List<std::string>* mylist = new List<std::string>;
    List<std::string>::Iterator it(mylist);
 
     mylist->Data = "Hello World";
 
     for(unsigned int i = 0; i<1000000; i++)
         it.pushAndMove("a b c d");
 
     std::cout << "done" << std::endl;
 
     delete mylist;
 
     return 0;
}

gdb me trouve un SIGSEGV sur la ligne de delete dans le cas de Next!=NULL du destructeur ~List.

:aie:

Merci pour votre aide,

PS : Petite indication : ce code se déroule bien pour 104822 éléments mais pas pour un de plus...

13/01/2010, 19h09
koala01

Salut,

Une question peut-être idiote, mais, si l'idée est de créer une liste de chaines de caractères, pourquoi ne pas, tout simplement, utiliser... std::list :question:
13/01/2010, 19h26
TNT89

C'est déjà écrit dans le premier message :roll: :

Citation:

j'adore réinventer la roue...

Et si c'était si facile que ça, alors pour quoi suis-je incapable de trouver pourquoi ce code ne fonctionne pas?

:aie::aie::aie:

Blague mise à part, j'essaie d'apprendre par moi même donc la meilleure solution est quand même de réussir à faire...
:lol:
13/01/2010, 19h35
TNT89
Bon ok je me suis planté...
Rien à voir avec un problème de std::string...

Le code suivant ne fonctionne pas non plus :
Code:

1 2 3 4 5 6 7 8 List<int*>* mylist = new List<int*>(NULL); List<int*>::Iterator it(mylist); for(unsigned int i = 0; i<1000000; i++) it.pushAndMove(NULL); delete mylist;
Ce que je pense : je fais trop d'allocation dans le tas (chaque maillon est créé avec new) quel est la taille maximum d'allocation dans le tas? nombre maximum d'allocations dans le tas?
13/01/2010, 20h29
Cheps

Comme ta liste est créee avec new, elle n'est pas sur la pile mais bel et bien sur le tas. Un vecteur de 1 million d'eléments ça fait 4mo en 32bits donc ça doit pas être le problème sur une config récente.

Effectivement... c'et cela... J'ai modifié légèrement le code et du coup il attaque bien ce qu'il faut (et il attaque le swap pour des grosses quantités : 1 000 000 000 d'éléments (int)...)

Bon en fait j'ai testé le code suivant :

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
 
struct bidule
        {
            bidule* p;
            bidule* n;
            int d;
 
            bidule(void) { p = n = NULL;}
 
            void push(int _d)
            {
                bidule* t = this;
 
                while(t->n!=NULL) t = t->n;
 
                t->n = new bidule();
                t->n->p = t;
                t->n->d = _d;
            }
 
            ~bidule(void)
            {
                if(n!=NULL) delete n;
            }
        };

Avec :

Code:

1
2
3
4
5
6
7
8
9
10
11
 
bidule* a = new bidule();
        bidule* t = a;
 
        for(unsigned int i = 0; i<10000000; i++)
        {
            t->push(0);
            t = t->n;
        }
 
        delete a;

Et ça plante...

Par contre ce code ne plante pas : (avec le même appel, voire plus d'éléments...)

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
 
struct bidule
        {
            bidule* p;
            bidule* n;
            int d;
 
            bidule(void) { p = n = NULL;}
 
            void push(int _d)
            {
                bidule* t = this;
 
                while(t->n!=NULL) t = t->n;
 
                t->n = new bidule();
                t->n->p = t;
                t->n->d = _d;
            }
 
            void remnext(void)
            {
                if(n!=NULL)
                {
                    bidule* tmp = n;
                    n = n->n;
                    tmp->n = NULL;
                    delete tmp;
                }
            }
 
            ~bidule(void)
            {
                while(n!=NULL) remnext();
            }
        };

Je pense que c'est dû à une profondeur limite de récursivité... Dans le premier cas les destructeurs s'enchaînent en profondeur, dans le second ce n'est pas le cas!

Est-ce vrai?

En fait, il faut savoir que ce n'est pas la liste qui sert d'élément mais... une structure paticulière...

En gros, il faut compter trois à quatre types de données:

Le type que tu souhaite placer dans la liste
le "maillon" qui permet... de relier les différents éléments d'une même liste entre eux
l'itérateur, qui permet de parcourir les différents maillons d'une même liste,et, enfin,
la liste elle même qui... représente la collections de données.

Il y aura des différences avec la STL, mais une liste pourrait très bien prendre la forme 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
template <typename T>
class List /* une liste (4) contenant des objets de type T (1)*/
{
    /* le maillon de la chaine (2)
     * ... a usage interne uniquement
     */
    struct item
    {
        item(T const & v):value(v),next(0){}
        T value;
        item * next;
    };
   public:
   /* quelques alias de type pour la facilité */
    typedef T const & constrefype;
    typedef T * ptrtype;
    typedef T & reftype;
       class iterator /* le type qui permet le parcours de la liste (3)
                       * les gens n'ont aucun besoin de savoir comment
                       * la machinerie interne fonctionne :D
                       */
       {
 
           public:
               iterator& operator++()
               {
                   ptr_=ptr_->next;
                   return (*this);
               }
               reftype operator *(){return ptr_->value;}
               ptrtype operator->(){return &(ptr_->value);}
               bool operator==(iterator const & it)const
               {
                   return ptr_==it->ptr_;
               }
               bool operator!=(iterator it)
               {
                   return ptr_!=it.ptr_;
               }
 
            private:
            friend class List; //seule la liste peut créer un itérateur :D
               iterator(item * v):ptr_(v){}
               item * ptr_;
       };
       /* prévoir un itérateur constant sur le même principe ;) */
       List():f_(0),l_(0){}
       ~List()
       {
           clear();
       }
       void push_back(constrefype v)
       {
           item* toadd = new  item(v);
           if(f_==0)
           {
               f_=toadd;
           }
           if(l_)
           {
               l_->next=toadd;
           }
           l_=toadd;
       }
       void push_front(constrefype v)
       {
           item* toadd=new  item(v);
           toadd->next = f_;
           f_=toadd;
       }
       /* on pourrait prévoir insert, voire, des variante prenant...
        * un iterateur de debut et de fin (y compris pour le constructeur ;)
        */
       iterator begin(){return iterator(f_);}
       iterator end(){return iterator(0);}
       void clear()
       {
           while(f_!=0)
           {
               item* temp=f_->next;
               delete f_;
               f_=temp;
           }
       }
       /* les autres fonctions "sympa" (calcul de la taille, ...) */
    private:
        item * f_; // le premier maillon
        item * l_; // le dernier maillon (pour permettre l'ajout en fin en
                   // temps constant)
};

et fonctionnera sans aucun problème avec tout type copiable:

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
#include <string>
#include <iostream>
using namespace std;
int main()
{
    List<int> l;
    for(int i=0;i<10;++i)
        l.push_back(i);
    List<int>::iterator it=l.begin();
    for(List<int>::iterator it=l.begin();it!=l.end();++it)
    {
        cout<<(*it)<<endl;
    }
    List<string> ls;
    ls.push_back("bonjour");
    ls.push_back("le");
    ls.push_back("monde");
    ls.push_back("...");
    ls.push_back("koala01");
    ls.push_back("vous");
    ls.push_back("salue");
 
    for(List<string>::iterator it=ls.begin();it!=ls.end();++it)
    {
        cout<<(*it)<<" ";
    }
    return 0;
}

13/01/2010, 21h17
TNT89

Ok!

Merci du conseil...
13/01/2010, 21h56
Arzar

Citation:

Envoyé par TNT89

Je pense que c'est dû à une profondeur limite de récursivité... Dans le premier cas les destructeurs s'enchaînent en profondeur, dans le second ce n'est pas le cas!

Est-ce vrai?

Oui c'est bien ça.
Si tu as un débuggeur, tu peux voir qu'il break dans le destructeur en affichant "Unhandled exception - stack overflow". (sous vs2010) Trop de récursivité finit par éclater la pile.

Citation:

Par contre ce code ne plante pas : (avec le même appel, voire plus d'éléments...)

Il ne plante peut être pas, mais il ne désalloue pas non plus. :mrgreen:
On quitte la boucle while du destructeur dès le deuxième tour, n est NULL...
13/01/2010, 22h04
TNT89

Effectivement y a une coquille!
Merci!!!