crash inexpliqué avec sort()

Bonjour,
Je cherche desesperemment à debugger un crash inexpliqué avec l'algo sort() de la STL. Ca fait 2 jours que je suis dessus, et je craque...

Outils: code::blocks avec mingw

Le contexte (je ne met que ce qui est pertinent dans les classes):
J'ai une classe (CRule) qui contient un conteneur "map", plus d'autres trucs (dont un Id unique, assigné par incrémentation d'une variable statique dans tous les contructeurs. Cet Id n'a de rôle que en phase "debug")

Code:

---

1 2 3 4 5 6

class CRule { private: std::map<uchar, uchar> set; uint Id; };

---

Cette classe est utilisée dans une autre, sous la forme d'un "vector":

Code:

---

1 2 3 4 5

class CRuleBase { private: std::vector<CRule>* rule_set; }

---

L'allocation est faite en dynamique de façon tout à fait classique dans le constructeur de cette classe:

Code:

---

1 2 3 4

CRuleBase::CRuleBase() { rule_set = new vector<CRule>; }

---

(c'est fait en dynamique, parce qu'il y a un traitement qui extrait de la liste principale une liste constituée des éléments pertinents, et ceci se fait en allouant et remplissant un nouveau vector, puis en faisant un delete de l'ancien, puis en assignant le pointeur sur le nouveau vector)

J'ai une méthode de tri, qui ne fait qu'appeler le "sort()":

Code:

---

1 2 3 4 5

void CRuleBase::Sort() { cerr << "Nb Elem = "<<distance(rule_set->begin(), rule_set->end() )<<endl; sort( rule_set->begin(), rule_set->end() ); }

---

Or, quand je veux trier ce vecteur, pour 1000 élements: aucun problème, mais si je passe à 1500, j'ai un crash (SIGSEGV, segmentation fault, me dit gdb)

J'ai tracé l'utilisation de mon opérateur "<" de CRule (affichage de l'Id de chaque CRule manipulé, et de son contenu), et j'observe des comportements incohérents avant le crash: genre, après une série de comparaison normales, on a d'un coup 549 comparaisons successives identiques entre le CRule N°0 (1-qui n'existe pas, j'ai la trace de sa destruction !, 2-qui est vide), et l'objet CRule n°5894 (qui lui est tout à fait cohérent)

Bref, tout ça ressemble fort à de la corruption mémoire, mais je ne vois vraiment pas où est mon erreur... Y a-t-il des précautions particulières à prendre avec sort() ? Dois-je utiliser un mécanisme d'allocation mémoire particulier? Là, je suis un peu coincé, je ne me vois pas trop comment aller fouiller dans la fonction sort()...

Ou alors un problème d'allocation méméoire ? Mais c'est normalement géré de façon automatique, non ? Comment depister un tel problème ?

Merci d'avance pour vos conseils et idées !

Salut,

Quelques remarques déjà sur ton code :

Code:

---

std::vector<CRule>* rule_set;

---

Je ne comprends pas pourquoi tu as un pointeur sur un vecteur. Ton explication ne me semble pas obliger d'avoir un pointeur. Il te suffit de créer ton autre vecteur avec les éléments que tu veux, puis de faire un swap. C'est rapide et c'est beaucoup plus propre...

Code:

---

1 2 3 4 5 6

std::vector<CRule> monNouveauVector;   // Tu le remplis   rule_set.swap (monNouveauVector);

---

Code:

---

cerr << "Nb Elem = "<<distance(rule_set->begin(), rule_set->end() )<<endl;

---

<=> cerr << "Nb Eleme = " << rule_set.size() << endl;


Pour le problème en lui-même, effectivement il n'y a aucune raison que ça crash pour 1500 éléments seulement... Tu peux nous montrer ta surcharge de l'opérateur < ? Que cherches-tu à comparer exactement ? Les ID des objets CRule ?

Citation:

---

Envoyé par Bakura

Salut,
Je ne comprends pas pourquoi tu as un pointeur sur un vecteur. Ton explication ne me semble pas obliger d'avoir un pointeur. Il te suffit de créer ton autre vecteur avec les éléments que tu veux, puis de faire un swap. C'est rapide et c'est beaucoup plus propre...

Code:

---

1 2 3 4

std::vector<CRule> monNouveauVector; // Tu le remplis rule_set.swap (monNouveauVector);

---

---

A la rigueur, oui, je pourrais faire ça. Je vais même essayer tout de suite, je suis plus à ça près !
Mais sur le fond, je ne pense pas que ça change grand chose, non ? A partir du moment ou l'allocation et la désallocation sont faites correctement, ça ne devrait pas influencer le comportement.

Code:

---

1 2 3 4 5 6 7 8

CRuleBase::CRuleBase() { rule_set = new vector<CRule>; } CRuleBase::~CRuleBase() { delete rule_set; }

---

et la fonction qui recherche les "bons":

Code:

---

1 2 3 4 5 6 7 8 9

CRuleBase::Traitement() { vector<CRule>* new_rule_set = new vector<CRule>   // ici on empile dans new_rule_set avec new_rule_set->push_back( );   delete rule_set; rule_set = new_rule_set; }

---

Citation:

---

Code:

---

cerr << "Nb Elem = "<<distance(rule_set->begin(), rule_set->end() )<<endl;

---

<=> cerr << "Nb Eleme = " << rule_set.size() << endl;

---

Oh là, oui, ça, c'est débile en effet. Désolé pour la pollution !

Citation:

---

Pour le problème en lui-même, effectivement il n'y a aucune raison que ça crash pour 1500 éléments seulement... Tu peux nous montrer ta surcharge de l'opérateur < ? Que cherches-tu à comparer exactement ? Les ID des objets CRule ?

---

Ci-dessous:

Code:

---

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

bool CRule::operator < ( const CRule& r ) const { uint Nb1 = set.size(); uint Nb2 = r.set.size();   if( Nb1 == 0 ) // if no rules, then allways smaller return true;   if( Nb1 != Nb2 ) // if the rule don't have the same number of terms, return ( Nb1 < Nb2 ); // then, the one with the lowest nb of rules will be "lower"   RULE_TYPE::const_iterator it2 = r.set.begin(); for( RULE_TYPE::const_iterator it1 = set.begin(); it1 != set.end(); it1++, it2++ ) { uint v1 = (*it1).second; uint v2 = (*it2).second; if( v1 != v2 ) return ( v1 < v2 ); } return true; }

---

avec un typedef pour RULE_TYPE:

Code:

---

typedef std::map<uchar, uchar> RULE_TYPE;

---

Citation:

---

A la rigueur, oui, je pourrais faire ça. Je vais même essayer tout de suite, je suis plus à ça près !

---

Euh bien sûr, mais le but de la STL est quand même de limiter au maximum l'usage des pointeurs...

Concernant ta fonction, si je me trompe pas dans la compréhension, dans un premier temps tu compares d'abord le nombre d'éléments dans la map, et si ces deux valeurs sont différentes, tu retournes vrai si Nb1 < Nb2.

Et ensuite, tu parcours les deux maps de chaque objet et cette fois-ci tu compares les valeurs A L'INTERIEUR de ces maps c'est bien ça ?

J'avoue ne pas voir pourquoi ça platnerait, comme ça la fonction m'a l'air correcte :/.

salut,
es-tu sûr que ton operator< est correct ?
c.à.d. que :
- si A=B est vrai alors A<B est faux;
- si A<B est vrai alors B<A est faux;
- si A<B et B<C sont vrai alors A<C.

Code:

---

1 2 3 4 5 6

bool CRule::operator < ( const CRule& r ) const { uint Nb1 = set.size(); uint Nb2 = r.set.size(); if( Nb1 == 0 ) // if no rules, then allways smaller return true;

---

Et si Nb2 == 0 aussi ? il faudrait retourner false.

A la fin de la fonction tu retourne true alors qu'il me semble que si on arrive jusqu'à là c'est que les 2 objets sont égaux, il faudrait retourner false.

a+
jmv

+1 Bakura pour la STL.
Sinon un opérateur de comparaison à cette forme:

Code:

---

bool operator/*...*/(const Class &, const Class &);

---

edit: Tiens, on dirais que le colorateur du fofo ne fait pas la différence "class"/"Class".

Citation:

---

Envoyé par jmv

es-tu sûr que ton operator< est correct ?
A la fin de la fonction tu retourne true alors qu'il me semble que si on arrive jusqu'à là c'est que les 2 objets sont égaux, il faudrait retourner false.

---

Bravo à jmv, c'était effectivement ce point qui posait problème. Et évidemment, ce n'est qu'après passé des heures à mettre en oeuvre tout un système de traçage des allocation mémoires et des différents objets crées, puis à afficher l'occupation mémoire, que j'ai simplement, pour voir..., essayer de remplacer ce true par false... Et, là, miracle, plus de plantage.
J'avais même essayé d'utiliser qsort(), mais les résultats n'étaient vraiment pas concluants, pas de plantage... mais pas de tri non plus !

Ce que je ne m'explique pas, c'est pourquoi cette inversion true/false fait planter sort(). Car enfin, c'est quand même à moi de dire comment on doit comparer mes 2 objets ! En quoi cette fonction, qui ne renvoie que true ou false, peut provoquer une corruption mémoire ? C'est encore mystérieux pour moi.
Ca fera l'objet d'une investigation plus approfondie...quand j'aurais le temps!

Et sinon, Bakura, j'ai suivi ton conseil: supprimé le pointeur, et utilisé swap(). Bon, ça n'a pas changé grand chose, mais c'est peut-être effectivement plus conforme à "l'esprit STL" (venant du C, je suis toujours grand utilisateur de pointeurs...)

Citation:

---

Envoyé par Chlab_lak

Sinon un opérateur de comparaison à cette forme:
Code :

Code:

---

bool operator/*...*/(const Class &, const Class &);

---

---

Ca, c'est quand on le définit sous la forme d'une fonction amie, non ? Ici, je l'ai implémenté sous la forme d'une méthode de classe. On peut faire les deux, mais perso, je n'utilise des fonctions amies qu'en "dernier" recours.

Merci à tous en tout cas de vous être penché sur mon problème !
A+

Citation:

---

Envoyé par sebkramm

Ca, c'est quand on le définit sous la forme d'une fonction amie, non ? Ici, je l'ai implémenté sous la forme d'une méthode de classe. On peut faire les deux, mais perso, je n'utilise des fonctions amies qu'en "dernier" recours.

---

Seul l'op<() et l'op==() doivent être amis (les autres opérateurs pouvant être implémentés à partir de op<() et de op==()), mais seulement si il n'y a pas d'accès public aux données (accesseurs). L'avantage des opérateurs de comparaison écrits comme ça (forme canonique je crois) c'est qu'il y a une symétrie. Genre tu peux écrire:

Code:

---

1 2 3 4 5

Class C(195); Class C2(16); C != C2; C == 195; 16 == C2; // ici une forme de comparaison impossible avec des fonctions membres

---

Citation:

---

Envoyé par Chlab_lak

Seul l'op<() et l'op==() doivent être amis (les autres opérateurs pouvant être implémentés à partir de op<() et de op==()), mais seulement si il n'y a pas d'accès public aux données (accesseurs).

---

Formellement oui, il n'y a effectivement pas besoin de déclarer systématiquement l'amitié. Mais en pratique, si on veut pouvoir l'écrire de la même façon qu'une fonction membre, on déclare l'amitié de façon à, justement, pouvoir se passer d'utiliser les accesseurs, qui apportent souvent une lourdeur d'écriture.

Citation:

---

L'avantage des opérateurs de comparaison écrits comme ça (forme canonique je crois) c'est qu'il y a une symétrie. Genre tu peux écrire:

Code:

---

1 2 3 4 5

Class C(195); Class C2(16); C != C2; C == 195; 16 == C2; // ici une forme de comparaison impossible avec des fonctions membres

---

---

Ah, effectivement, ça, ça m'avait échappé !
Merci, a+