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 operatora  vec(n);
    for (int i = 0; i <p><strong>Réponse :</strong></p>
<p>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.</p>
<p>Le code pertinent dans l'implémentation du tri par insertion de GCC (bits/stl_algo.h:2187, GCC 4.7.2) est :</p>
<pre class="brush:php;toolbar:false"><code class="cpp">typename iterator_traits<_randomaccessiterator>::value_type
  __val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);</_randomaccessiterator></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!