Warum vermeidet „std::sort' den Aufruf einer benutzerdefinierten „swap'-Funktion für kleine Bereiche?

std::sort kann std::swap für Effizienz vermeiden

Frage:

Betrachten Sie den folgenden Code unter Verwendung des benutzerdefinierten Typs A mit benutzerdefinierter Swap-Funktion:

<code class="cpp">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"; // Custom swap function
}</code>

Wenn n auf 20 gesetzt ist, wird die benutzerdefinierte Swap-Funktion verwendet und das Array sortiert. Wenn n jedoch auf 4 gesetzt ist, wird die benutzerdefinierte Swap-Funktion nicht aufgerufen.

Antwort:

Für kleine Bereiche (z. B. wann n ist 4), std::sort-Implementierungen in GCCs stdlibc (und anderen Standardbibliotheksimplementierungen) wechseln Sie aus Leistungsgründen zur Einfügungssortierung.

Einfügungssortierungsoptimierung:

Einfügesortierung in der GCC-Implementierung verwendet einen anderen Ansatz zum Austauschen:

1. Es verschiebt ganze Wertebereiche gleichzeitig, indem es intern std::move_backward verwendet.
2. Wenn die experimentellen C 11-Funktionen des Compilers nicht aktiviert sind, verwendet std::move_backward möglicherweise Kopieren statt Verschieben.

Diese Optimierung verbessert die Leistung, indem unnötige Swaps vermieden werden. Anstatt Elemente einzeln auszutauschen, wird ein Teil des Arrays verschoben, wodurch effektiv mehrere Auslagerungen in einem Vorgang durchgeführt werden.

Schlussfolgerung:

Beim Sortieren kleiner Arrays gilt std:: sort kann die Einfügungssortierung verwenden, um den Aufruf der benutzerdefinierten Swap-Funktion zu vermeiden. Diese Optimierung kann die Leistung verbessern, sollte jedoch in Betracht gezogen werden, wenn das Kopieren von Objekten kostspielig ist.

Das obige ist der detaillierte Inhalt vonWarum vermeidet „std::sort' den Aufruf einer benutzerdefinierten „swap'-Funktion für kleine Bereiche?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!