Discussion :

[Zéli]

Bonjour,

J'ai 2 set<const char *> pour lesquels je cherche à savoir si ils ont des valeurs communes.
Je fais donc un set_intersection sur ces deux ensembles, mais lors de l'exécution j'ai l'erreur

Debug Assertion Failed

...

Expression : sequence not ordered

Voici le bout du code où se situe l'erreur, dites moi s'il vous en faut plus.

Code :

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

1
2
3
4
5
6
7
8
9
 set<const char*,ltstr> *** tmpCluster; // stocke les objets de la colocation classés par caracteristique/cluster/caracteristique associée
tmpCluster = new set <const char *, ltstr>**[itCand->size()];
for (j=0;j<itCand->size();j++) 
{
     tmpCluster[j] = new set <const char *, ltstr>*[(*freqFeatures->find((*itCand)[j])).second.nbCluster];
      for (i=0 ; i<(*freqFeatures->find((*itCand)[j])).second.nbCluster ; i++) {
           tmpCluster[j][i] = new set <const char *, ltstr>[itCand->size()];
       }
}

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
vector<const char*> outSet;
set<const char*,ltstr> tmpSet;
set<const char*,ltstr>::iterator it;
for (i=0;i<(*freqFeatures->find((*itCand)[caracClusterMax])).second.nbCluster;i++)
{
    for (k=i+1;k<(*freqFeatures->find((*itCand)[caracClusterMax])).second.nbCluster;k++) 
    {
	for (int l=0;l<itCand->size();l++) 
	{
		set_intersection (tmpCluster[caracClusterMax][i][l].begin(),tmpCluster[caracClusterMax][i][l].end(),
					tmpCluster[caracClusterMax][k][l].begin(),tmpCluster[caracClusterMax][k][l].end(),
					back_inserter( outSet )
					);
		// cluster adaptation
		if (outSet.size() != 0 )
		{
			...
		}
	}
}

Je ne trouve pas le message "sequence not ordered" très parlant étant donné que les éléments du tableau tmpCluster sont de type set et donc ordonnés.

en débuggant le programme au pas à pas, j'ai trouvé que l'erreur venait peut être du fait que tmpCluster.end() (ainsi que begin parfois) me retournent un pointeur incorrect (0xcdcdcdcd), mais la mémoire est allouée donc je ne comprends pas d'où cela peut venir.

Je vous remercie d'avance de votre aide.

Elise

[3DArchi]

Bonjour,
Outre que tous ces pointeurs me piquent les yeux (tu ne pouvais pas encapsuler dans des structures plus abstraites et avec des std::vector ?), quelques remarques :
1/std::set<Type*> ordonnera les objets selon la valeur de leur adresse et non selon la valeur de l'objet.
2/si find échoue, il te retourne un itérateur invalide dont le dé-référencement doit avoir un comportement indéterminé. Donc ton for, devrait tester que find retourne un itérateur valide (!=freqFeatures->end()).
3/si tu ne modifies pas ton set, pourquoi faire l'appel de find à chaque étape ? Ne peux-tu pas le faire au début de la fonction une fois pour toutes tes boucles.
4/ end() retourne toujours un itérateur invalide qu'il ne faut pas dé-référencer. end() ne désigne pas le dernier élément.
5/ begin() peut renvoyer un itérateur invalide pour un conteneur vide. On a alors begin()==end(), ce qui est un moyen de tester si le conteneur est vide.

Après ton problème ne me saute pas aux yeux. Peut être un problème de pointeur mal initialisé/déjà libéré ?

[Zéli]

Bonjour,

Pour les pointeurs, je l'ai fait parce que je connais d'avance la taille, j'ai donc pensé que cela me ferait un gain de place et de temps de réallocation et d'accès, même si je sais que ce n'est pas très très lisible.

1/std::set<Type*> ordonnera les objets selon la valeur de leur adresse et non selon la valeur de l'objet.

D'accord, ce qui veut dire que je ne peux pas utiliser les set dans la fonction set_intersection qui demande des ensembles ordonnés ? Ou alors je dois les ordonner moi même ?
Pourtant ils semblent ordonnés quand je fais le débug, fait du hasard?

2/si find échoue, il te retourne un itérateur invalide dont le dé-référencement doit avoir un comportement indéterminé. Donc ton for, devrait tester que find retourne un itérateur valide (!=freqFeatures->end()).

Pour freqFeature, je sais exactement ce qu'il y a dedans, et quand je fais le find je suis sure de demander quelque-chose qu'il va trouver.

3/si tu ne modifies pas ton set, pourquoi faire l'appel de find à chaque étape ? Ne peux-tu pas le faire au début de la fonction une fois pour toutes tes boucles.

En fait c'est l'objet demandé qui est modifié mais dans une boucle encore extérieure, donc je devrais en effet le faire au début pour toutes les boucles.

4/ end() retourne toujours un itérateur invalide qu'il ne faut pas dé-référencer. end() ne désigne pas le dernier élément.
5/ begin() peut renvoyer un itérateur invalide pour un conteneur vide. On a alors begin()==end(), ce qui est un moyen de tester si le conteneur est vide.

D'accord donc le fait qu'il me retourne un itérateur invalide est normal. Ce qui n'est pas normal c'est juste qu'il me fasse un debug assertion failed

en fait c'est à cet endroit là :

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
template<class _InIt1,
	class _InIt2,
	class _OutIt> inline
	_OutIt _Set_intersection(_InIt1 _First1, _InIt1 _Last1,
		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Range_checked_iterator_tag)
	{	// AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
	_DEBUG_ORDER(_First1, _Last1);
	_DEBUG_ORDER(_First2, _Last2);
	_DEBUG_POINTER(_Dest);
	for (; _First1 != _Last1 && _First2 != _Last2; )
		if (_DEBUG_LT(*_First1, *_First2))
			++_First1;
		else if (*_First2 < *_First1)
			++_First2;
		else
			*_Dest++ = *_First1++, ++_First2;
	return (_Dest);
	}

Voire même là :

Code :

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

1
2
3
4
5
6
7
template<class _InIt> inline
	void __CLRCALL_OR_CDECL _Debug_order(_InIt _First, _InIt _Last,
		const wchar_t *_File, unsigned int _Line)
	{	// test is range is ordered by operator<
	_DEBUG_RANGE2(_First, _Last, _File, _Line);
	_Debug_order2(_First, _Last, _File, _Line, _Iter_cat(_First));
	}

Donc je suppose que ça doit être dû au fait que le set n'est pas ordonné ?
Pourtant j'ai vu plein d'exemples avec des sets sur internet ?

[koala01]

Salut

Bonjour,

Pour les pointeurs, je l'ai fait parce que je connais d'avance la taille, j'ai donc pensé que cela me ferait un gain de place et de temps de réallocation et d'accès, même si je sais que ce n'est pas très très lisible.

Une chance que tu a utilisé le terme pensé et non le terme cru, sinon je t'aurais dit qu'il faut laisser croire les béguines...

Mais non... tu ne gagnera absolument rien ni en terme de taille ni en terme de vitesse d'allocation de mémoire:

Un std::set n'est rien de plus qu'un arbre binaire, et n'est absolument pas implémenté sous la forme (ce que tu pensais visiblement) d'un tableau que l'on garderait ordonné...

tmpCluster peut, effectivement, être un tableau "C style" alloué par new ou créé sur base d'une taille définie à la compilation, mais il ne sert strictement à rien de passer par un tableau de pointeurs vers des std::set...

D'accord, ce qui veut dire que je ne peux pas utiliser les set dans la fonction set_intersection qui demande des ensembles ordonnés ? Ou alors je dois les ordonner moi même ?

Les std::set sont, par nature, ordonnés... Mais, visiblement, pas sur la bonne chose...

Je m'explique: un pointeur représente, tu le sais surement, l'adresse mémoire à laquelle on va trouver une variable donnée.

La seule donnée sur laquelle le set puisse se baser pour ordonner les pointeurs est donc... cette adresse qui est... unique pour chaque variable...

Si tu remplis successivement deux sets différents avec un nombre identique de pointeurs vers des variables allouées dynamiquement, tous les pointeurs des deux set pointeront fatalement vers... des adresses différentes...

Dés lors, comment veux tu pouvoir trouver une adresse se trouvant dans les deux conteneurs en même temps, et à plus forte raison plusieurs

Pourtant ils semblent ordonnés quand je fais le débug, fait du hasard?

Sans doute si, pour une raison ou une autre tu te base, non pas sur l'adresse pointée mais sur une valeur membre de l'objet pointé...

Il est fort vraisemblable, l'allocation dynamique étant ce qu'elle est, que si tu alloue dynamiquement la mémoire pour trois objets différents "coup sur coup", l'adresse du premier soit plus basse que celle du deuxième qui sera, elle-même, plus basse que le troisième, bien que ce ne soit absolument pas certain...

Si, parce que tu fais un test, tu fais en sorte que ces trois allocations s'effectue dans une boucle en donnant à chaque objet la valeur du compteur de la boucle, il y a donc effectivement beaucoup de chances pour que l'adresse de l'élément que tu identifiera par 1 soit... plus basse que l'adresse de l'élément que tu identifiera par 2 et que celle-ci soit elle-même plus basse que l'élément que tu identifiera par 3, et donc, au final, que ton set te semble ordonné...

Mais, si tu écris le test "à la main" en veillant, justement, à ne pas introduire les éléments dans l'ordre (ce qui est sans doute ce qui risque d'arriver en production), tu a de fortes chances de remarquer que ton set n'est plus ordonné

Pour freqFeature, je sais exactement ce qu'il y a dedans, et quand je fais le find je suis sure de demander quelque-chose qu'il va trouver.

Ici et maintenant, pour la durée de tes tests...

Mais qu'en sera-t-il une fois en production

Surtout si la clé doit être introduite par un utilisateur (ou avoir comme origine l'introduction d'un utilisateur)...

Il faut bien te dire que 90% des bugs trouvent leur origine entre la chaise et le clavier, et qu'il est "de bon ton" de considérer, par défaut, que l'utilisateur (ce peut être toi ou moi, d'ailleurs, je ne suis pas meilleur qu'un autre) est un imbécile distrait...

Si, un jour, l'utilisateur oublie un chiffre ou a une touche qui "passe mal" sur son clavier (pour l'instant, je dois particulièrement insister sur le k pour qu'il passe... une chance que ce ne soit pas une lettre couramment utilisée ), tu te prépare à foncer droit dans le mur...

En fait c'est l'objet demandé qui est modifié mais dans une boucle encore extérieure, donc je devrais en effet le faire au début pour toutes les boucles.

Ouh là là, danger...

Pour l'instant, il n'y a pas "trop" de problème dans le sens où tes objets sont ordonnés sur base de l'adresse mémoire à laquelle ils se trouvent, et qu'elle risque *moins* d'être modifiée...

Mais, comme je l'ai fait transparaitre durant toute cette réponse, je soupçonne fortement que ce n'est pas forcément ce que tu souhaite en fait...

De plus, tu as de la chance que ton set manipule des pointeurs, qui laissent facilement "filer" une constance, car, normalement, les éléments récupérés depuis un set sont... constant, et donc manipulables uniquement au travers de leurs fonctions membres constantes...

Et la raison en est bien simple: c'est l'objet lui-même qui sert de clé de tri.

si un set venait à laisser modifier l'objet auquel on accède, nous risquerions de... nous retrouver avec un objet dont la position dans le set ne correspond pas avec la position qu'il devrait avoir après modification, et donc, avec un set non trié... un comble quand on sait que le fait d'être intrincèquement trié est une des qualités principales de ce conteneur

Peut être devrais tu te tourner vers un conteneur pour lequella clé est indépendante de la valeur rerpésentée (une std::map)

D'accord donc le fait qu'il me retourne un itérateur invalide est normal. Ce qui n'est pas normal c'est juste qu'il me fasse un debug assertion failed

Si tu es en mode débug, non...

Debug assertion failed signifie, simplement, que quelque part dans le code tu as un code proche de

Code :

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

assert(<quelquechose><comparaision><valeur>);

(qui est d'ailleurs, pour le cas qui nous intéresse écrit sous la forme de _DEBUG_POINTER(_Dest);) "planqué" quelque part dans les fonctions de la classes set...

C'est ca le gros avantage de la STL en mode debug: comme tu ne prend pas la précaution élémentaire de vérifier la validité des données obtenues, tu as, par chance, quelqu'un qui a pensé à un moyen de la vérifier pour toi...

Si tu prenais la peine de tester si le résultat de la fonction find est différent de end() avant d'aller plus loin, tu n'aurais très certainement plus le problème...

Donc je suppose que ça doit être dû au fait que le set n'est pas ordonné ?
Pourtant j'ai vu plein d'exemples avec des sets sur internet ?

sur le fait que le set n'est, très certainement, pas ordonné sur ce que tu crois, en l'occurence

[Arzar]

Au fait, comment est implémenté le prédicat ltstr() ?
Une erreur qui revient fréquemment et qui peut se manifester par ce genre d'assert il me semble, c'est de ne pas respecter la relation d'ordre strict demandée par la STL.

Par exemple ce prédicat est faux:

Code :

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

1
2
3
4
bool ltstr(int i1, int i2)
{
   return (i1 <= i2);
}

Il faut utiliser un inférieur strict '<'.

[Zéli]

Tout d'abord, merci pour le temps passé à me répondre !!

Pour répondre à Arzar, mon ltstr :

Code :

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

1
2
3
4
5
6
7
struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

Pour freqFeature, je sais exactement ce qu'il y a dedans, et quand je fais le find je suis sure de demander quelque-chose qu'il va trouver.

Ici et maintenant, pour la durée de tes tests...

Mais qu'en sera-t-il une fois en production

Surtout si la clé doit être introduite par un utilisateur (ou avoir comme origine l'introduction d'un utilisateur)...

Oui mais la que ce soit freqFeature ou la clé que je recherche, tout est créé par le programme à partir de la même base de données, m'enfin pour plus de sécurité, je vais faire une vérification.


Ensuite pour le reste de la réponse, je vais commencer par expliquer pourquoi la structure choisie est un set.
La priorité du set qui m'importe le plus ici est l'unicité des clés, en effet, ces sets sont remplis à partir de requêtes SQL où les valeurs peuvent être un nombre indéterminé de fois, mais je ne veux travailler dans cette partie du code que sur les valeurs distinctes. Je peux, par exemple (sur la base de données test) passer de 17000 valeurs à une centaine de valeurs distinctes.

J'ai donc bien compris que le set est ordonné selon l'adresse des pointeurs et non sur la valeur de la clé (ce qui ne m'arrange pas franchement du coup ). Mais quelle est alors la meilleure solution ?

1. Trouver une structure autre que le set qui me permettrait tout à la fois de ne pas avoir 17000 mais 100 lignes et en plus de les avoir ordonnées comme je le souhaite ... ça existe ?
2. Ordonner moi même le set selon les valeurs de la clé.
3. Trouver une autre méthode que set_intersection pour chercher un point commun entre 2 sets ... je n'ai personnellement pas trouvé ... mais ça existe peut être ?
4. Une autre solution que je ne vois pas ...

Si tu prenais la peine de tester si le résultat de la fonction find est différent de end() avant d'aller plus loin, tu n'aurais très certainement plus le problème...

Attention, je crois que tu confonds (ou peut être est-ce moi ?).
Le debug assertion failed est causé par set_intersection, pas par un find. Dû au fait (vu vos réponses) que les sets que je lui fournis ne sont pas ordonnés.