**Est-ce que std::sort appelle toujours des fonctions d'échange personnalisées pour les petites plages ?**

std::sort sans échanges personnalisés pour les petites plages

Lorsque vous travaillez avec la fonction std::sort en C, on s'attend généralement à ce que les fonctions d'échange personnalisées fournies par le programmeur seront appelées pendant le processus de tri. Cependant, dans certains scénarios, cela peut ne pas être le cas. Plus précisément, pour les petites plages de données, certaines implémentations de std::sort, telles que celles trouvées dans stdlibc de GCC, peuvent utiliser le tri par insertion pour optimiser les performances.

Optimisation du tri par insertion

Le tri par insertion, contrairement aux algorithmes de tri rapide ou d'introduction par défaut utilisés par std::sort, n'utilise pas d'échanges explicites. Au lieu de cela, il fonctionne en déplaçant des blocs d’éléments de données pour obtenir l’ordre de tri. Cette approche est plus rapide que les échanges individuels sur de petites plages.

Dans l'implémentation interne du tri par insertion (trouvée dans bits/stl_algo.h dans GCC 4.7.2), le mouvement des données est effectué à l'aide de GLIBCXX_MOVE et _GLIBCXX_MOVE_BACKWARD3. fonctions. Ces fonctions correspondent à std::move et std::move_backward en C 11. Cependant, elles peuvent recourir à la copie au lieu de déplacer si la macro __GXX_EXPERIMENTAL_CXX0X n'est pas définie.

Impact sur la personnalisation Swaps

En raison des optimisations utilisées par le tri par insertion, les fonctions d'échange personnalisées définies par le programmeur ne peuvent pas être appelées lors du tri de petites plages de données. Cela peut être particulièrement préoccupant si la fonction d'échange personnalisée est coûteuse en calcul.

Exemple

Considérez le code suivant dans lequel une fonction d'échange personnalisée est implémentée et un vecteur de struct A est trié :

<code class="c++">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 = 4;
    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>

Pour une petite plage comme n=4, la fonction d'échange personnalisée n'est pas appelée même si le tableau est correctement trié. Cela se produit parce que le tri par insertion est utilisé, ce qui ne nécessite pas d'échanges explicites.

Conclusion

Il est important de savoir que std::sort peut ne pas toujours utiliser des échanges personnalisés. pour les petites plages de données grâce à des optimisations algorithmiques. Cela peut avoir des implications lorsque vous travaillez avec des fonctions d'échange personnalisées coûteuses.

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!