為什麼'std::sort”避免為小範圍呼叫自訂'swap”函數？

std::sort 可以避免std::swap 以提高效率

問題：

考慮以下使用使用者定義類型A 和自訂交換函數的程式碼：

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

當n 設定為20 時，使用自訂交換函數並對陣列進行排序。然而，當 n 設定為 4 時，自訂交換函數不會被呼叫。

答案：

對於小範圍（例如當n 為4)，GCC 的stdlibc 中的std::sort 實作（以及其他標準函式庫實作）出於效能原因切換到插入排序。

插入排序最佳化：

GCC 實作中的插入排序使用不同的交換方法：

1. 它一次移動整個值範圍，內部使用std::move_backward。
2. 如果未啟用編譯器的實驗性 C 11 功能，std::move_backward 可能會使用複製而不是移動。

此最佳化透過避免不必要的交換來提高效能。不是單獨交換元素，而是移動數組的一部分，從而在一次操作中有效地執行多次交換。

結論：

對小數組進行排序時，std:: sort 可以使用插入排序來避免呼叫自訂交換函數。這種最佳化可以提高效能，但在複製物件成本高時應考慮。

以上是為什麼'std::sort”避免為小範圍呼叫自訂'swap”函數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！