Pourquoi `std::sort` n'appelle-t-il pas toujours `std::swap` pour les petites plages ?

std::sort n'appelle pas toujours std::swap

Dans certains cas, std::sort peut ne pas appeler le swap personnalisé fonction définie pour un type de données donné. Ce comportement a été observé dans l'implémentation stdlibc de GCC et est particulièrement apparent lorsque vous travaillez avec de petites plages d'éléments.

Pour des raisons d'efficacité des performances, l'implémentation std::sort de GCC utilise le tri par insertion pour les plages inférieures à une certaine taille. En effet, le tri par insertion est plus rapide que le tri rapide ou le tri par introduction pour les petits ensembles de données. Cependant, le tri par insertion n'utilise pas la fonction d'échange définie. Au lieu de cela, il effectue un déplacement direct de toute la plage d'éléments pour obtenir des performances plus rapides.

Ce comportement est illustré dans l'extrait de code ci-dessous :

<code class="cpp">#include <algorithm>
#include <iostream>
#include <vector>

namespace my_space
{

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";
    std::swap(lhs.a, rhs.a);
    std::swap(lhs.b, rhs.b);
}

}

int main()
{
    const int n = 20;
    std::vector<my_space::A> vec(n);
    for (int i = 0; i < n; ++i) {
        vec[i].a = -i;
    }

    for (int i = 0; i < n; ++i) {
        std::cerr << vec[i].a << " ";
    }
    std::cerr << "\n";
    std::sort(vec.begin(), vec.end());
    for (int i = 0; i < n; ++i) {
        std::cerr << vec[i].a << " ";
    }
    std::cerr << "\n";
}</code>

Lorsque n est défini sur 20, le La fonction d'échange personnalisée est appelée et le tableau est trié correctement. Cependant, si n est réduit à 4, la fonction d'échange personnalisée n'est pas invoquée, mais le tableau est toujours correctement trié.

Ce comportement peut devenir problématique lorsque vous travaillez avec des objets coûteux à copier. Pour atténuer ce problème, envisagez d'utiliser une implémentation de std::sort qui appelle toujours la fonction swap fournie. De plus, vous souhaiterez peut-être signaler ce comportement aux développeurs de GCC pour une optimisation ultérieure.

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!