Warum ruft „std::sort“ für kleine Bereiche nicht immer „std::swap“ auf?

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

In bestimmten Fällen ruft std::sort den benutzerdefinierten Swap möglicherweise nicht auf Funktion, die für einen bestimmten Datentyp definiert ist. Dieses Verhalten wurde in der stdlibc-Implementierung von GCC beobachtet und tritt besonders deutlich bei der Arbeit mit kleinen Elementbereichen auf.

Aus Gründen der Leistungseffizienz verwendet die std::sort-Implementierung von GCC eine Einfügungssortierung für Bereiche unterhalb einer bestimmten Größe. Dies liegt daran, dass die Einfügungssortierung bei kleinen Datensätzen schneller ist als die Schnellsortierung oder die Introsortierung. Allerdings nutzt die Einfügungssortierung nicht die definierte Swap-Funktion. Stattdessen wird eine direkte Verschiebung des gesamten Elementbereichs durchgeführt, um eine schnellere Leistung zu erzielen.

Dieses Verhalten wird im folgenden Codeausschnitt veranschaulicht:

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

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 = 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";
}</code>

Wenn n auf 20 eingestellt ist, wird das Die benutzerdefinierte Swap-Funktion wird aufgerufen und das Array wird korrekt sortiert. Wenn n jedoch auf 4 reduziert wird, wird die benutzerdefinierte Swap-Funktion nicht aufgerufen, aber das Array ist immer noch korrekt sortiert.

Dieses Verhalten kann problematisch werden, wenn mit Objekten gearbeitet wird, die teuer zu kopieren sind. Um dieses Problem zu entschärfen, sollten Sie die Verwendung einer Implementierung von std::sort in Betracht ziehen, die immer die bereitgestellte Swap-Funktion aufruft. Darüber hinaus möchten Sie dieses Verhalten möglicherweise den GCC-Entwicklern zur weiteren Optimierung melden.

Das obige ist der detaillierte Inhalt vonWarum ruft „std::sort“ für kleine Bereiche nicht immer „std::swap“ auf?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!