Problème : std::string et Segfault

**TNT89** · 13/01/2010, 17h33

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

Merci pour votre aide,

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

**koala01** · 13/01/2010, 19h09

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

**TNT89** · 13/01/2010, 19h26

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

:

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?

Blague mise à part, j'essaie d'apprendre par moi même donc la meilleure solution est quand même de réussir à faire...

**TNT89** · 13/01/2010, 19h35

Bon ok je me suis planté...
Rien à voir avec un problème de std::string...

Le code suivant ne fonctionne pas non plus :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

**Cheps** · 13/01/2010, 20h29

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.

**TNT89** · 13/01/2010, 20h40

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

**koala01** · 13/01/2010, 20h41

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

**TNT89** · 13/01/2010, 21h17

Ok!

Merci du conseil...

**Arzar** · 13/01/2010, 21h56

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.

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.

On quitte la boucle while du destructeur dès le deuxième tour, n est NULL...