Mengapakah std::sort memanggil fungsi swap tersuai saya untuk julat kecil?

std::sort Tidak Sentiasa Memanggil std::swap

Soalan:

Dalam kod berikut, mengapakah fungsi swap tersuai tidak dipanggil apabila std::sort dilaksanakan dengan julat yang lebih kecil (n=4), walaupun ia dipanggil untuk julat yang lebih besar (n=20)?

<code class="cpp">#include <algorithm>
#include <iostream>
#include <vector>

namespace my_space
{

struct A
{
    double  a;
    double* b;
    bool operator<(const A&amp; rhs) const
    {
        return this->a < rhs.a;
    }
};

void swap(A&amp; lhs, A&amp; 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";
}

Jawapan:

Untuk julat kecil, std::isih pelaksanaan dalam stdlibc GCC (dan pelaksanaan perpustakaan standard lain) menggunakan isihan sisipan atas sebab prestasi. Isihan sisipan tidak menggunakan std::swap untuk menukar elemen. Sebaliknya, ia menggerakkan keseluruhan julat nilai pada satu masa, yang berpotensi menjimatkan prestasi.

Kod yang berkaitan dalam pelaksanaan isihan sisipan GCC (bits/stl_algo.h:2187, GCC 4.7.2) ialah:

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

Kod ini mengalihkan nilai pada kedudukan semasa (__i) ke storan sementara, mengalihkan semua nilai sebelumnya daripada __first ke __i satu ke atas, dan kemudian memasukkan semula nilai sementara pada __first. Dengan berbuat demikian, ia melakukan n swap dalam satu operasi dan bukannya perlu memindahkan n nilai secara individu.

Atas ialah kandungan terperinci Mengapakah std::sort memanggil fungsi swap tersuai saya untuk julat kecil?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!