Pourquoi std::sort n'appelle-t-il pas ma fonction d'échange personnalisée pour les petites plages ?

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

Question :

Dans le code suivant, pourquoi la fonction d'échange personnalisée n'est-elle pas appelée lorsque std::sort est exécuté avec une plage plus petite (n=4), même si elle est appelée pour une plage plus grande (n=20) ?

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

namespace my_space
{

struct A
{
    double  a;
    double* b;
    bool operator<(const A&amp; rhs) const
    {
        return this->a < rhs.a;
    }
};

void swap(A&amp; lhs, A&amp; 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";
}

Réponse :

Pour les petites plages, les implémentations std::sort dans stdlibc de GCC (et d'autres implémentations de bibliothèques standard) utilisent le tri par insertion pour des raisons de performances. Le tri par insertion n'utilise pas std::swap pour échanger des éléments. Au lieu de cela, il déplace des plages entières de valeurs à la fois, ce qui permet d'économiser potentiellement des performances.

Le code pertinent dans l'implémentation du tri par insertion de GCC (bits/stl_algo.h:2187, GCC 4.7.2) est :

<code class="cpp">typename iterator_traits<_RandomAccessIterator>::value_type
  __val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);</code>

Ce code déplace la valeur à la position actuelle (__i) vers un stockage temporaire, déplace toutes les valeurs précédentes de __first à __i d'une unité vers le haut, puis réinsère la valeur temporaire à __first. Ce faisant, il effectue n échanges en une seule opération plutôt que d'avoir à déplacer n valeurs individuellement.

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!