**Ruft std::sort immer benutzerdefinierte Swap-Funktionen für kleine Bereiche auf?**

std::sort ohne benutzerdefinierte Swaps für kleine Bereiche

Beim Arbeiten mit der Funktion std::sort in C wird allgemein erwartet, dass dies der Fall ist Während des Sortiervorgangs werden vom Programmierer bereitgestellte benutzerdefinierte Swap-Funktionen aufgerufen. In bestimmten Szenarien ist dies jedoch möglicherweise nicht der Fall. Insbesondere für kleine Datenbereiche können einige Implementierungen von std::sort, wie sie beispielsweise in stdlibc von GCC zu finden sind, Einfügungssortierung zur Leistungsoptimierung verwenden.

Einfügesortierungsoptimierung

Einfügungssortierung verwendet im Gegensatz zu den standardmäßigen Schnell- oder Einführungssortierungsalgorithmen von std::sort keine expliziten Swaps. Stattdessen werden Blöcke von Datenelementen verschoben, um die sortierte Reihenfolge zu erreichen. Dieser Ansatz ist schneller als einzelne Swaps in kleinen Bereichen.

In der internen Implementierung der Einfügungssortierung (zu finden in bits/stl_algo.h in GCC 4.7.2) wird die Datenverschiebung mit GLIBCXX_MOVE und _GLIBCXX_MOVE_BACKWARD3 durchgeführt Funktionen. Diese Funktionen entsprechen std::move und std::move_backward in C 11. Sie können jedoch auf Kopieren statt auf Verschieben zurückgreifen, wenn das Makro __GXX_EXPERIMENTAL_CXX0X nicht definiert ist.

Auswirkungen auf Benutzerdefiniert Swaps

Aufgrund der durch die Einfügungssortierung verwendeten Optimierungen dürfen vom Programmierer definierte benutzerdefinierte Swap-Funktionen beim Sortieren kleiner Datenbereiche nicht aufgerufen werden. Dies kann besonders besorgniserregend sein, wenn die benutzerdefinierte Swap-Funktion rechenintensiv ist.

Beispiel

Betrachten Sie den folgenden Code, in dem eine benutzerdefinierte Swap-Funktion und ein Strukturvektor implementiert sind A ist sortiert:

<code class="c++">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 = 4;
    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>

Für einen kleinen Bereich wie n=4 wird die benutzerdefinierte Swap-Funktion nicht aufgerufen, obwohl das Array korrekt sortiert ist. Dies liegt daran, dass eine Einfügungssortierung verwendet wird, die keine expliziten Swaps erfordert.

Fazit

Es ist wichtig zu beachten, dass std::sort möglicherweise nicht immer benutzerdefinierte Swaps verwendet für kleine Datenbereiche aufgrund algorithmischer Optimierungen. Dies kann Auswirkungen haben, wenn mit teuren benutzerdefinierten Swap-Funktionen gearbeitet wird.

Das obige ist der detaillierte Inhalt von**Ruft std::sort immer benutzerdefinierte Swap-Funktionen für kleine Bereiche auf?**. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!