首頁 > 後端開發 > C++ > 主體

為什麼'std::sort”並不總是為小範圍呼叫'std::swap”?

Linda Hamilton
發布: 2024-10-29 20:20:03
原創
551 人瀏覽過

Why Does `std::sort` Not Always Call `std::swap` for Small Ranges?

std::sort 並不總是調用std::swap

在某些情況下,std::sort 可能不會呼叫自訂交換為給定資料類型定義的函數。這種行為已在 GCC 的 stdlibc 實作中觀察到,並且在處理小範圍元素時尤其明顯。

為了提高效能效率,GCC 的 std::sort 實作對低於特定大小的範圍採用插入排序。這是因為對於小型資料集,插入排序比快速排序或內插排序更快。但是,插入排序不使用定義的交換函數。相反,它會直接移動整個元素範圍以實現更快的效能。

下面的程式碼片段說明了此行為:

<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>
登入後複製

當 n 設定為 20 時,呼叫自訂交換函數,並且陣列已正確排序。但是,如果 n 減少到 4,則不會呼叫自訂交換函數,但陣列仍然正確排序。

在處理複製成本高昂的物件時,此行為可能會出現問題。為了緩解此問題,請考慮使用始終呼叫提供的交換函數的 std::sort 實作。此外,您可能需要向 GCC 開發人員報告此行為以進行進一步優化。

以上是為什麼'std::sort”並不總是為小範圍呼叫'std::swap”?的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!