Qu'est-ce qui fait que std::sort() accède à une adresse hors plage

Question

Je comprends que pour utiliser std::sort(), la fonction de comparaison doit être d'ordre strict et faible, sinon elle plantera en raison d'un accès à l'adresse hors des limites.(https://gcc.gnu.org/ml/gcc-bugs/2013-12/msg00333.html)

Cependant, pourquoi std::sort() accéderait-il à une adresse hors limite alors que la fonction de comparaison n'est pas un ordre strict et faible ?Qu'est-ce qu'il essaie de comparer ?

Je me demande également s'il existe d'autres pièges en STL dont je devrais être conscient.

Answer 1

La première chose est qu'appeler l'algorithme avec un comparateur qui ne respecte pas les exigences est un comportement indéfini et tout est permis...

Mais à part cela, je suppose que vous souhaitez savoir quel type d'implémentation pourrait finir par accéder hors des limites si le comparateur est mauvais. L'implémentation ne devrait-elle pas vérifier les limites avant d'accéder aux éléments en premier lieu ?c'est à dire.avant d'appeler le comparateur

La réponse est la performance, et ce n’est qu’un des éléments possibles pouvant conduire à ce type de problèmes.Il existe différentes implémentations d'algorithmes de tri, mais le plus souvent, std::sort est construit sur une variante de tri rapide qui dégénérera sur un algorithme de tri différent comme le tri par fusion pour éviter les pires performances de tri rapide.

L'implémentation du tri rapide sélectionne un pivot, puis partitionne l'entrée autour du pivot, puis trie indépendamment les deux côtés.Il existe différentes stratégies pour la sélection du pivot, mais une stratégie courante est la médiane de trois :l'algorithme obtient les valeurs du premier, du dernier et du milieu élément, sélectionne la médiane des trois et l'utilise comme valeur pivot.

Conceptuellement, la partition part de la gauche jusqu'à ce qu'elle trouve un élément qui n'est pas plus petit que le pivot, elle part ensuite de la droite en essayant de trouver un élément qui est plus petit que le pivot.Si les deux curseurs se rencontrent, partition terminée.Si des éléments déplacés sont trouvés, les valeurs sont permutées et le processus continue dans la plage déterminée par les deux curseurs.La boucle partant de la gauche pour trouver l’élément à échanger ressemblerait à :

while (pos < end && value(pos) < pivot) { ++pos; }

Bien qu'en général, la partition ne puisse pas supposer que la valeur du pivot sera comprise dans la plage, le tri rapide sait C'est vrai, après tout, il a sélectionné le pivot parmi les éléments de la gamme.Une optimisation courante dans ce cas consiste à échanger la valeur de la médiane pour qu'elle se trouve dans le dernier élément de la boucle.Ceci garantit que value(pos) < pivot sera vrai avant pos == end (pire cas: pos == end - 1).L'implication ici est que nous pouvons supprimer le contrôle pour la fin de la plage et utiliser un unchecked_partition (choisissez votre choix de nom) avec une condition plus simple et plus rapide :

while (/*pos < end &&*/ value(pos) < pivot) ++pos;

Tout va bien, sauf que < s'écrit comparator(value(pos), pivot).Maintenant, si le comparator est mal implémenté, vous pourriez vous retrouver avec comparator(pivot,pivot) == true et le curseur dépassera les limites.

Notez qu'il ne s'agit que d'un exemple d'optimisation de l'algorithme qui peut supprimer les limites du contrôle des performances :en supposant une commande valide, c'est impossible pour sortir du tableau dans la boucle ci-dessus si le tri rapide définit le pivot sur le dernier élément avant appeler cette partition modifiée.

Revenons à la question :

L'implémentation ne devrait-elle pas vérifier les limites avant d'accéder aux éléments en premier lieu ?c'est à dire.avant d'appeler le comparateur

Non, pas s'il supprime la vérification des limites en prouvant qu'il ne sortira pas du tableau, mais cette preuve repose sur le principe que le comparateur est valide.

Answer 2

std::sort nécessite en effet que le comparateur donné établisse un ordre strict et faible, sinon le tri n'a pas vraiment de sens.

En ce qui concerne l'accès hors de portée, le lien que vous avez publié renvoie à un rapport de bug, c'est-à-direce n'est pas censé faire ça.Les compilateurs, comme tout autre logiciel, peuvent avoir et auront des bugs.Comme l'a noté Adam, ce rapport de bug particulier a été rejeté car il ne s'agit pas vraiment d'un bug.

Ce qui se passe exactement lorsque vous n'avez pas d'ordre faible strict n'est pas défini par la norme, cela n'a pas de sens de le faire et est donc laissé de côté par la norme.Il est donc indéfini par omission. Indéfini signifie que tout peut arriver, même un accès hors de portée.

Quant à éviter les « pièges », soyez simplement conscient des exigences des algorithmes et des fonctions que vous utilisez.Pour le C++, il existe un joli site de référence que j'utilise habituellement : cppréférence

Lequel sur la page de std::sort dit:

comp - objet de fonction de comparaison (c'est-à-direun objet qui satisfait aux exigences de Compare) qui renvoie true si le premier argument est inférieur à (c'est-à-direest commandé avant) le deuxième.

Avec un lien vers la description de Comparer