C ++ se bloque dans une boucle ‘for’ avec une expression négative

Le code suivant bloque C ++ avec une erreur d’exécution:

#include  using namespace std; int main() { ssortingng s = "aa"; for (int i = 0; i < s.length() - 3; i++) { } } 

Bien que ce code ne plante pas:

 #include  using namespace std; int main() { ssortingng s = "aa"; int len = s.length() - 3; for (int i = 0; i < len; i++) { } } 

Je ne sais pas comment l’expliquer. Quelle pourrait être la raison de ce comportement?

s.length() est un type entier non signé. Lorsque vous soustrayez 3, vous le rendez négatif. Pour un unsigned , cela signifie très gros .

Une solution de contournement (valable tant que la chaîne est longue jusqu’à INT_MAX) serait de faire comme ceci:

 #include  using namespace std; int main() { ssortingng s = "aa"; for (int i = 0; i < static_cast (s.length() ) - 3; i++) { } } 

Qui n’entrerait jamais dans la boucle.

Un détail très important est que vous avez probablement reçu un avertissement “comparant la valeur signée et la valeur non signée”. Le problème est que si vous ignorez ces avertissements, vous entrez dans le champ très dangereux de la “conversion entière” implicite (*) , qui a un comportement défini, mais difficile à suivre: le mieux est de ne jamais ignorer ces avertissements.


(*) Vous pourriez également être intéressé par la “promotion de l’entier” .

Tout d’abord: pourquoi ça tombe en panne? Parcourons votre programme comme le ferait un débogueur.

Remarque: je suppose que votre corps de boucle n’est pas vide, mais accède à la chaîne. Si ce n’est pas le cas, la cause de la panne est un comportement indéfini par dépassement d’entier. Voir Richard Hansens répond à cela.

 std::ssortingng s = "aa";//assign the two-character ssortingng "aa" to variable s of type std::ssortingng for ( int i = 0; // create a variable i of type int with initial value 0 i < s.length() - 3 // call s.length(), subtract 3, compare the result with i. OK! {...} // execute loop body i++ // do the incrementing part of the loop, i now holds value 1! i < s.length() - 3 // call s.length(), subtract 3, compare the result with i. OK! {...} // execute loop body i++ // do the incrementing part of the loop, i now holds value 2! i < s.length() - 3 // call s.length(), subtract 3, compare the result with i. OK! {...} // execute loop body i++ // do the incrementing part of the loop, i now holds value 3! . . 

On s'attendrait à ce que la vérification i < s.length() - 3 échoue tout de suite, car la longueur de s est deux (on lui a seulement donné une longueur au début et ne l’a jamais modifiée) et 2 - 3 est -1 , 0 < -1 est faux. Cependant, nous obtenons un "OK" ici.

C'est parce que s.length() n'est pas 2 . C'est 2u . std::ssortingng::length() a le type de retour size_t qui est un entier non signé. Donc, revenons à la condition de la boucle, nous obtenons d'abord la valeur de s.length() , donc 2u , maintenant soustraire 3 . 3 est un littéral entier et interprété par le compilateur en tant que type int . Le compilateur doit donc calculer 2u - 3 , deux valeurs de types différents. Les opérations sur les types primitifs ne fonctionnent que pour les mêmes types, il faut donc les convertir dans l'autre. Il y a des règles ssortingctes, dans ce cas, unsigned "wins" unsigned , donc 3 sont convertis en 3u . Dans les entiers non signés, 2u - 3u ne peut pas être -1u car un tel nombre n'existe pas (enfin, car il a bien sûr un signe!). Au lieu de cela, il calcule chaque opération modulo 2^(n_bits) , où n_bits est le nombre de bits de ce type (généralement 8, 16, 32 ou 64). Donc, au lieu de -1 nous obtenons 4294967295u (en supposant 32 bits).

Donc maintenant, le compilateur est fait avec s.length() - 3 (bien sûr, c'est beaucoup plus rapide que moi ;-)), passons maintenant à la comparaison: i < s.length() - 3 . Mettre les valeurs: 0 < 4294967295u . Encore une fois, différents types, 0 devient 0u , la comparaison 0u < 4294967295u est évidemment vraie, la condition de la boucle est vérifiée positivement, nous pouvons maintenant exécuter le corps de la boucle.

Après l'incrémentation, la seule chose qui change dans ce qui précède est la valeur de i . La valeur de i sera à nouveau convertie en un unsigned int, comme le nécessite la comparaison.

Donc nous avons

 (0u < 4294967295u) == true, let's do the loop body! (1u < 4294967295u) == true, let's do the loop body! (2u < 4294967295u) == true, let's do the loop body! 

Voici le problème: que faites-vous dans le corps de la boucle? Vous avez probablement access au i^th personnage de votre chaîne, n'est-ce pas? Même si ce n'était pas votre intention, vous n'avez pas seulement accédé au premier et au zéro, mais aussi au deuxième! Le second n'existe pas (votre chaîne ne contenant que deux caractères, le zeroth et le premier), vous accédez à la mémoire que vous ne devriez pas utiliser, le programme fait ce qu'il veut (comportement non défini). Notez que le programme n'est pas obligé de se bloquer immédiatement. Cela peut sembler fonctionner correctement pendant encore une demi-heure, alors ces erreurs sont difficiles à détecter. Mais il est toujours dangereux d’accéder à la mémoire au-delà des limites, c’est là que viennent la plupart des accidents.

Donc, en résumé, vous obtenez une valeur différente de s.length() - 3 partir de laquelle vous vous attendez, cela se traduit par une vérification de condition de boucle positive, ce qui conduit à une exécution répétitive du corps de la boucle, qui lui-même accède à la mémoire. ne devrait pas.

Voyons maintenant comment éviter cela, c'est-à-dire comment dire au compilateur ce que vous vouliez dire dans votre condition de boucle.


Les longueurs de chaînes et les tailles des conteneurs sont insortingnsèquement non signées . Vous devez donc utiliser un entier non signé dans les boucles.

Puisque unsigned int est assez long et donc indésirable pour écrire encore et encore dans les boucles, utilisez simplement size_t . C'est le type que chaque conteneur de la STL utilise pour stocker la longueur ou la taille. Vous devrez peut-être inclure cstddef pour affirmer l'indépendance de la plate-forme.

 #include  #include  using namespace std; int main() { ssortingng s = "aa"; for ( size_t i = 0; i + 3 < s.length(); i++) { // ^^^^^^ ^^^^ } } 

Comme a < b - 3 est mathématiquement équivalent à a + 3 < b , nous pouvons les échanger. Cependant, a + 3 < b empêche que b - 3 soit une valeur énorme. Rappelons que s.length() retourne un entier non signé et que les entiers non signés effectuent les opérations module 2^(bits) où bits est le nombre de bits du type (généralement 8, 16, 32 ou 64). Par conséquent, avec s.length() == 2 , s.length() - 3 == -1 == 2^(bits) - 1 .


Sinon, si vous souhaitez utiliser i < s.length() - 3 pour votre préférence personnelle, vous devez append une condition:

 for ( size_t i = 0; (s.length() > 3) && (i < s.length() - 3); ++i ) // ^ ^ ^- your actual condition // ^ ^- check if the string is long enough // ^- still prefer unsigned types! 

En fait, dans la première version, vous faites une boucle très longue, car vous comparez i à un entier non signé contenant un très grand nombre. La taille d’une chaîne est (en effet) identique à celle de size_t qui est un entier non signé. Lorsque vous soustrayez le 3 de cette valeur, il se développe et devient une grande valeur.

Dans la deuxième version du code, vous affectez cette valeur non signée à une variable signée et vous obtenez ainsi la valeur correcte.

Et ce n’est pas vraiment la condition ou la valeur qui provoque le crash, il est plus probable que vous indexiez la chaîne hors limites, un cas de comportement indéfini.

En supposant que vous ayez omis du code important dans la boucle for

La plupart des gens ici semblent incapables de reproduire le plantage, y compris moi-même, et il semble que les autres réponses reposent sur l’hypothèse que vous avez omis du code important dans le corps de la boucle for et que le code manquant est à l’origine du problème. votre crash

Si vous utilisez i pour accéder à la mémoire (vraisemblablement des caractères dans la chaîne) dans le corps de la boucle for , et que vous avez laissé ce code hors de votre question pour tenter de fournir un exemple minimal, le crash s’explique facilement par le fait que s.length() - 3 a la valeur SIZE_MAX raison de l’arithmétique modulaire sur les types entiers non signés. SIZE_MAX est un très grand nombre, donc i continuerai à grossir jusqu’à ce qu’il soit utilisé pour accéder à une adresse qui déclenche une erreur de segmentation.

Cependant, votre code pourrait théoriquement tomber tel quel, même si le corps de la boucle for est vide. Je ne suis au courant d’aucune implémentation qui tomberait en panne, mais peut-être que votre compilateur et votre CPU sont exotiques.

L’explication suivante ne suppose pas que vous avez omis le code dans votre question. Il faut croire que le code que vous avez posté dans votre question se bloque tel quel; qu’il ne s’agit pas d’un remplacement abrégé d’un autre code qui se bloque.

Pourquoi votre premier programme plante

Votre premier programme se bloque car il s’agit de sa réaction à un comportement indéfini dans votre code. (Lorsque j’essaie d’exécuter votre code, il se termine sans planter car c’est la réaction de mon implémentation au comportement indéfini.)

Le comportement indéfini provient du débordement d’un int . Le standard C ++ 11 dit (dans [expr] clause 5 paragraphe 4):

Si, lors de l’évaluation d’une expression, le résultat n’est pas défini mathématiquement ou ne figure pas dans la plage des valeurs représentables pour son type, le comportement n’est pas défini.

Dans votre exemple de programme, s.length() renvoie un size_t avec la valeur 2. size_t soustrayez 3, vous obtiendrez un 1 négatif, à l’exception de size_t est un type entier non signé. La norme C ++ 11 dit (dans la clause 3.9.1 paragraphe 4 de [basic.fundamental]):

Les entiers non signés, déclarés unsigned , doivent obéir aux lois de l’arithmétique modulo 2 nn est le nombre de bits de la représentation des valeurs de la taille entière entière. 46

46) Cela implique que l’arithmétique non signée ne déborde pas car un résultat qui ne peut pas être représenté par le type entier non signé résultant est réduit modulo par le nombre supérieur à la plus grande valeur pouvant être représentée par le type entier non signé résultant.

Cela signifie que le résultat de s.length() - 3 est un size_t avec la valeur SIZE_MAX . C’est un très grand nombre, plus grand que INT_MAX (la plus grande valeur représentable par int ).

Parce que s.length() - 3 est si grand, l’exécution tourne dans la boucle jusqu’à ce que INT_MAX à INT_MAX . Lors de la prochaine itération, quand il essaiera d’incrémenter i , le résultat serait INT_MAX + 1 mais ce n’est pas dans la plage des valeurs représentables pour int . Ainsi, le comportement est indéfini. Dans votre cas, le comportement est de tomber en panne.

Sur mon système, le comportement de mon implémentation lorsque i incrémenté après INT_MAX est de boucler (définir i sur INT_MIN ) et continuer. Une fois que j’atteins -1, les conversions arithmétiques habituelles (C ++ [expr], clause 5, paragraphe 9) provoquent que SIZE_MAX donc la boucle se termine.

L’une ou l’autre réaction est appropriée. C’est le problème du comportement non défini: il peut fonctionner comme vous le souhaitez, il risque de tomber en panne, de formater votre disque dur ou d’annuler Firefly. On ne sait jamais.

Comment votre deuxième programme évite le crash

Comme pour le premier programme, s.length() - 3 est un type size_t avec la valeur SIZE_MAX . Cependant, cette fois, la valeur est affectée à un int . La norme C ++ 11 indique (dans la clause 4.7, paragraphe 3, de [conv.integral]):

Si le type de destination est signé, la valeur rest inchangée si elle peut être représentée dans le type de destination (et la largeur du champ binary); sinon, la valeur est définie par l’implémentation.

La valeur SIZE_MAX est trop grande pour être représentable par un int , donc len obtient une valeur définie par l’implémentation (probablement -1, mais peut-être pas). La condition i < len sera finalement vraie quelle que soit la valeur assignée à len , donc votre programme se terminera sans rencontrer de comportement indéfini.

Le type de s.length () est size_t avec une valeur de 2, donc s.length () – 3 est aussi un type non signé size_t et il a la valeur SIZE_MAX qui est définie par l’implémentation (18446744073709551615 si sa taille est 64 bit). Il est au moins de type 32 bits (peut être 64 bits dans les plates-formes 64 bits) et ce nombre élevé signifie une boucle indéfinie. Pour éviter ce problème, vous pouvez simplement s.length() en int :

 for (int i = 0; i < (int)s.length() - 3; i++) { //..some code causing crash } 

Dans le second cas, len est -1 car c'est un signed integer et il n'entre pas dans la boucle.

En ce qui concerne les crashs, cette boucle "infinie" n'est pas la cause directe du crash. Si vous partagez le code dans la boucle, vous pouvez obtenir des explications supplémentaires.

Comme s.length () est un type unsigned, lorsque vous faites s.length () – 3, il devient négatif et les valeurs négatives sont stockées sous la forme de valeurs positives importantes (dues aux spécifications de conversion non signées) et la boucle devient infinie et se bloque .

Pour que cela fonctionne, vous devez transcrire le s.length () comme:

static_cast (s.length ())

Le problème que vous rencontrez provient de la déclaration suivante:

 i < s.length() - 3 

Le résultat de s.length () est du type unsigned size_t. Si vous imaginez la représentation binary de deux:

0 ... 010

Et vous en substituez alors trois, vous enlevez effectivement 1 trois fois, à savoir:

0 ... 001

0 ... 000

Mais ensuite, vous avez un problème, en supprimant le troisième chiffre qu’il contient, car il tente d’obtenir un autre chiffre de la gauche:

1 ... 111

C'est ce qui arrive peu importe si vous avez un type non signé ou signé , mais la différence est que le type signé utilise le bit le plus significatif (ou MSB) pour représenter si le nombre est négatif ou non. Lorsque l'undeflow se produit, il représente simplement un négatif pour le type signé .

D'autre part, size_t n'est pas signé . Lorsqu'il est en cours, il représente désormais le plus grand nombre que size_t peut représenter. Ainsi, la boucle est pratiquement infinie (en fonction de votre ordinateur, cela affecte le maximum de size_t).

Pour résoudre ce problème, vous pouvez manipuler le code que vous avez de différentes manières:

 int main() { ssortingng s = "aa"; for (size_t i = 3; i < s.length(); i++) { } } 

ou

 int main() { ssortingng s = "aa"; for (size_t i = 0; i + 3 < s.length(); i++) { } } 

ou même:

 int main() { ssortingng s = "aa"; for(size_t i = s.length(); i > 3; --i) { } } 

Les points importants à noter sont que la substitution a été omise et que l'ajout a été utilisé ailleurs avec les mêmes évaluations logiques. Les deux premiers changent la valeur de i disponible dans la boucle for alors que la seconde la conservera.

J'ai été tenté de fournir ceci comme exemple de code:

 int main() { ssortingng s = "aa"; for(size_t i = s.length(); --i > 2;) { } } 

Après reflection, j'ai réalisé que c'était une mauvaise idée. L'exercice des lecteurs consiste à déterminer pourquoi!

La raison est la même que int a = 1000000000; long long b = a * 100000000; donnerait erreur. Lorsque compilateurs multiplie ces nombres, il les évalue en ints, car un littéral 1000000000 étant ints, et 10 ^ 18 étant beaucoup plus volumineux que la limite supérieure de int, cela donnera une erreur. Dans votre cas, nous avons s.length () – 3, car s.length () est unsigned int, il ne peut pas être négatif, et puisque s.length () – 3 est évalué comme unsigned int et que sa valeur est -1, ça donne aussi une erreur ici.