Mengapa swap dipanggil oleh std :: sortir hanya jika wadah saya memiliki lebih dari 32 elemen?

13

Halo Saya punya pertanyaan sederhana:

class A 
{
public:
    A(int);
    A(const A&);
    A& operator=(const A&);
    ~A();
private:
    int* ptr_;

    friend bool operator<(const A&, const A&);
    friend void swap(A&, A&);
};

A::A(int x) : 
    ptr_(new int(x))
{}

A::A(const A& rhs) :
    ptr_(rhs.ptr_ ? new int(*rhs.ptr_) : nullptr)
{}

A& A::operator = (const A & rhs)
{
    int* tmp = rhs.ptr_ ? new int(*rhs.ptr_) : nullptr;
    delete ptr_;
    ptr_ = tmp;

    return *this;
}

A::~A()
{
    delete ptr_;
}

bool operator<(const A& lhs, const A& rhs)
{
    cout << "operator<(const A&, const A&)" << endl;
    return *lhs.ptr_ < *rhs.ptr_;
}

void swap(A& lhs, A& rhs)
{
    cout << "swap(A&, A&)" << endl;
    using std::swap;
    swap(lhs.ptr_, rhs.ptr_);
}

int main()
{

    std::vector<A> v{ 33,32,31,30,29,28,27,26,25,24,23,22, 21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5, 4,3,2,1 };
    std::sort(v.begin(), v.end());

}

Dengan lebih dari 32 elemen, panggilan semacam itu swap. Dengan 32 elemen atau kurang, elemen-elemen tersebut masih diurutkan tetapi swaptidak disebut.

  • Saya menggunakan MSVC ++ 2019 pada x64.
  • Kapan swapdipanggil dan kapan tidak dan mengapa? Terima kasih!
  • Saya tidak menggunakan swapdalam penugasan salinan hanya untuk membedakan antara panggilan untuk itu dari mengurutkan dari operator penugasan salinan.
Maestro
sumber
6
std::sortmenggunakan sortasi penyisipan jika jumlah elemen 32 atau kurang, dan menggunakan sort cepat.
Evg
@ Evg Apakah itu persyaratan atau penjelasan untuk konteks khusus ini?
François Andrieux
2
@ FrançoisAndrieux, ini adalah detail implementasi perpustakaan standar Microsoft. Dugaan saya adalah bahwa ini adalah alasan perilaku yang diamati oleh OP. Saat ini saya sedang mencari kode sumber untuk mendapatkan lebih banyak detail.
Evg
1
Bagian yang relevan dari sumbernya adalah: di while (_ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal)mana _ISORT_MAXdiberi nilai 32. Baris 3447 <algorithm>menggunakan VS 16.5.0
ChrisMM
Quicksort nyata tidak digunakan di perpustakaan standar modern dalam bahasa apa pun. Semua menggunakan versi campuran yang dimodifikasi yang hanya merupakan quicksort ketika jumlah elemen cukup besar. Misalnya Java dan Python menggunakan Timsort sementara .NET framework dan pustaka C ++ GCC menggunakan Introsort . libstdc ++ dan libc ++ juga menggunakan jenis penyisipan untuk urutan pendek. Lihat Algoritma apa yang digunakan dalam C ++ 11 std :: sortir dalam implementasi STL yang berbeda?
phuclv

Jawaban:

14

std::sortImplementasi Microsoft terlihat seperti ini:

const int ISORT_MAX = 32;  // maximum size for insertion sort

template<class RanIt, class Diff, class Pr>
void Sort(RanIt First, RanIt Last, Diff Ideal, Pr Pred)
{
    Diff Count;
    for (; ISORT_MAX < (Count = Last - First) && 0 < Ideal; )
    {   // divide and conquer by quicksort
        pair<RanIt, RanIt> Mid = Unguarded_partition(First, Last, Pred);

        // ...
    }

    if (ISORT_MAX < Count)
    {   // heap sort if too many divisions
        Make_heap(First, Last, Pred);
        Sort_heap(First, Last, Pred);
    }
    else if (1 < Count)
        Insertion_sort(First, Last, Pred);  // small
}

Saat rentang yang akan diurutkan memiliki 32 elemen atau kurang, Sortgunakan jenis penyisipan. Jenis penyisipan tidak digunakan swapdalam implementasinya . Jika tidak, sortir dan taklukkan quick sort digunakan. Dalam implementasinya ia memanggil iter_swap(di dalam Unguarded_partition), yang pada gilirannya memanggil swap:

template<class FwdIt1, class FwdIt2>
void iter_swap(FwdIt1 Left, FwdIt2 Right)
{   // swap *Left and *Right
    swap(*Left, *Right);
}

Semua ini adalah detail implementasi. Mereka berbeda dari satu implementasi standar perpustakaan ke yang lain.

Evg
sumber
1
libcxx menggunakan semacam penyisipan untuk urutan panjang lebih kecil dari 6 atau 30 tergantung pada jenisnya. libstd ++ melakukan itu untuk urutan 16 elemen atau kurang. Algoritma apa yang digunakan dalam C ++ 11 std :: sort dalam implementasi STL yang berbeda?
phuclv