Warum ruft std::sort meine benutzerdefinierte Swap-Funktion für kleine Bereiche nicht auf?

std::sort ruft nicht immer std::swap auf

Frage:

Warum wird im folgenden Code die benutzerdefinierte Swap-Funktion nicht aufgerufen, wenn std::sort mit einem kleineren Bereich (n=4) ausgeführt wird, obwohl sie für einen größeren Bereich (n=20) aufgerufen wird?

<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";
}

Antwort:

Für kleine Bereiche verwenden std::sort-Implementierungen in der stdlibc von GCC (und anderen Standardbibliotheksimplementierungen) aus Leistungsgründen die Einfügungssortierung. Die Einfügungssortierung verwendet std::swap nicht zum Austauschen von Elementen. Stattdessen werden ganze Wertebereiche auf einmal verschoben, wodurch möglicherweise Leistung gespart wird.

Der relevante Code in der Einfügungssortierungsimplementierung von GCC (bits/stl_algo.h:2187, GCC 4.7.2) lautet:

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

Dieser Code verschiebt den Wert an der aktuellen Position (__i) in einen temporären Speicher, verschiebt alle vorherigen Werte von __first nach __i um eins nach oben und fügt dann den temporären Wert bei __first wieder ein. Auf diese Weise werden n Swaps in einem Vorgang durchgeführt, anstatt n Werte einzeln verschieben zu müssen.

Das obige ist der detaillierte Inhalt vonWarum ruft std::sort meine benutzerdefinierte Swap-Funktion für kleine Bereiche nicht auf?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!