Pourquoi `std::sort` évite-t-il d'appeler une fonction `swap` personnalisée pour les petites plages ?

std::sort peut éviter std::swap pour plus d'efficacité

Question :

Considérez le code suivant utilisant le type A défini par l'utilisateur avec la fonction d'échange personnalisée :

<code class="cpp">struct A {
    double a;
    double* b;
    bool operator<(const A& rhs) const {
        return this->a < rhs.a;
    }
};

void swap(A& lhs, A& rhs) {
    std::cerr << "My swap.\n"; // Custom swap function
}</code>

Lorsque n est défini sur 20, la fonction d'échange personnalisée est utilisée et le tableau est trié. Cependant, lorsque n est défini sur 4, la fonction d'échange personnalisée n'est pas appelée.

Réponse :

Pour les petites plages (comme lorsque n est 4), implémentations std::sort dans stdlibc de GCC (et d'autres implémentations de bibliothèques standard) passer au tri par insertion pour des raisons de performances.

Optimisation du tri par insertion :

Le tri par insertion dans l'implémentation de GCC utilise une approche différente de l'échange :

1. Il déplace des plages entières de valeurs à la fois, en utilisant std::move_backward en interne.
2. Si les fonctionnalités expérimentales C 11 du compilateur ne sont pas activées, std::move_backward peut utiliser la copie au lieu du déplacement.

Cette optimisation améliore les performances en évitant les échanges inutiles. Au lieu d'échanger des éléments individuellement, une partie du tableau est décalée, effectuant ainsi plusieurs échanges en une seule opération.

Conclusion :

Lors du tri de petits tableaux, std :: sort peut utiliser le tri par insertion pour éviter d'invoquer la fonction d'échange personnalisée. Cette optimisation peut améliorer les performances mais doit être prise en compte lorsque la copie d'objets est coûteuse.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!