** std::sort 是否總是呼叫小範圍的自訂交換函式？

std::sort 沒有小範圍的自訂交換

在C 中使用std::sort 函數時，通常期望排序過程中將呼叫程式設計師提供的自訂交換函數。然而，在某些情況下，情況可能並非如此。具體來說，對於小資料範圍，std::sort 的某些實作（例如 GCC 的 stdlibc 中的實作）可能會利用插入排序來進行效能最佳化。

插入排序最佳化

插入排序與 std::sort 使用的預設快速或介紹排序演算法不同，不使用明確交換。相反，它透過移動資料元素區塊來實現排序順序。這種方法比小範圍內的單獨交換更快。

在插入排序的內部實作中（在 GCC 4.7.2 中的 bits/stl_algo.h 中找到），使用 GLIBCXX_MOVE 和 _GLIBCXX_MOVE_BACKWARD3 執行資料移動功能。這些函數對應於 C 11 中的 std::move 和 std::move_backward。但是，如果未定義 __GXX_EXPERIMENTAL_CXX0X 宏，它們可能會訴諸複製而不是移動。

對自訂的影響交換

由於插入排序採用的最佳化，在小資料範圍排序期間可能不會呼叫程式設計師定義的自訂交換函數。如果自訂交換函數的計算成本很高，這可能會特別令人擔憂。

範例

考慮以下程式碼，其中實作了自訂交換函數和結構體向量A 已排序：

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

對於像n =4 這樣的小範圍，即使陣列已正確排序，也不會呼叫自訂交換函數。發生這種情況是因為採用了插入排序，不需要明確交換。

結論

重要的是要注意 std::sort 可能並不總是使用自訂交換由於演算法優化，適用於小資料範圍。當使用昂貴的自訂交換函數時，這可能會產生影響。

以上是** std::sort 是否總是呼叫小範圍的自訂交換函式？的詳細內容。更多資訊請關注PHP中文網其他相關文章！