Pourquoi `std::sort` évite-t-il `std::swap` pour les petits ensembles de données ?

Std::sort évite std::swap avec de petits ensembles de données

Dans cet extrait de code, un tableau d'objets personnalisés est créé et passé à std::sort.

<code class="cpp">std::vector<my_space::A> vec(n);
for (int i = 0; i < n; ++i) {
  vec[i].a = -i;
}

std::sort(vec.begin(), vec.end());

La fonction d'échange personnalisée dans my_space est définie comme :

<code class="cpp">namespace my_space
{
struct A
{
  double a;
  double* b;
};

void swap(A& lhs, A& rhs)
{
  std::cerr << "My swap.\n";
  std::swap(lhs.a, rhs.a);
  std::swap(lhs.b, rhs.b);
}
}  

Lors de l'exécution, le phénomène suivant est observé : lorsque n est défini sur 20 , la fonction d'échange personnalisée est appelée et le tableau est trié avec succès. Cependant, lorsque n est défini sur 4, le tableau est trié sans appeler la fonction d'échange personnalisée.

Ce comportement découle de l'utilisation par std::sort du tri par insertion pour les petites plages. Dans l'implémentation stdlibc de GCC, le tri par insertion est utilisé pour des raisons de performances. Voici ce qui se passe en interne :

<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>

Cette opération imite n swaps en une seule action rapide. Par conséquent, la fonction d'échange personnalisée n'est pas appelée.

Il est à noter que _GLIBCXX_MOVE invoquera std::move uniquement si GXX_EXPERIMENTAL_CXX0X est défini. Sinon, il copiera par défaut les valeurs.

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!