為什麼對於小資料集，`std::sort` 避免使用 `std::swap`？-C++-PHP中文網

為什麼對於小資料集，`std::sort` 避免使用 `std::swap`？

Barbara Streisand

發布： 2024-10-25 17:41:02

原創

1037 人瀏覽過

Why Does `std::sort` Avoid `std::swap` for Small Datasets?

std::sort 在小資料集上避免std::swap

在此程式碼片段中，建立了一個自訂對象數組，並傳遞給std::sort。

<code class="cpp">std::vector<my_space::A> vec(n);
for (int i = 0; i < n; ++i) {
  vec[i].a = -i;
}

std::sort(vec.begin(), vec.end());

登入後複製

my_space 中的自訂交換函數定義為：

<code class="cpp">namespace my_space
{
struct A
{
  double a;
  double* b;
};

void swap(A& lhs, A& rhs)
{
  std::cerr << "My swap.\n";
  std::swap(lhs.a, rhs.a);
  std::swap(lhs.b, rhs.b);
}
}

登入後複製

執行時，觀察到以下現象：當n 設定為20 時，呼叫自訂交換函數且陣列成功排序。但是，當 n 設定為 4 時，陣列將在不呼叫自訂交換函數的情況下進行排序。

此行為源自於 std::sort 對小範圍使用插入排序。在 GCC 的 stdlibc 實作中，出於效能原因採用插入排序。以下是內部發生的情況：

<code class="cpp">typename iterator_traits<RandomAccessIterator>::value_type
  __val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);</code>

登入後複製

此操作在一個快速操作中模擬 n 次交換。因此，不會呼叫自訂交換函數。

值得注意的是，只有在定義了 GXX_EXPERIMENTAL_CXX0X 時，_GLIBCXX_MOVE 才會呼叫 std::move。否則，它將預設複製值。

以上是為什麼對於小資料集，`std::sort` 避免使用 `std::swap`？的詳細內容。更多資訊請關注PHP中文網其他相關文章！