Warum wird swap nur von std :: sort aufgerufen, wenn mein Container mehr als 32 Elemente enthält?

13

Hallo, ich habe eine einfache Frage:

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());

}

Mit mehr als 32 Elementen wird die Sortierung aufgerufen swap. Bei 32 Elementen oder weniger werden die Elemente weiterhin sortiert, aber swapnicht aufgerufen.

  • Ich verwende MSVC ++ 2019 auf x64.
  • Wann wird swapangerufen und wann nicht und warum? Vielen Dank!
  • Ich habe bei der Kopierzuweisung nicht swapnur verwendet, um zwischen dem Aufruf und der Sortierung vom Kopierzuweisungsoperator zu unterscheiden.
Maestro
quelle
6
std::sortgreift auf die Einfügesortierung zurück, wenn die Anzahl der Elemente 32 oder weniger beträgt, und verwendet andernfalls die schnelle Sortierung.
Evg
@Evg Ist das eine Anforderung oder ist das eine Erklärung für diesen speziellen Kontext?
François Andrieux
2
@ FrançoisAndrieux, dies ist ein Implementierungsdetail der Microsoft-Standardbibliothek. Ich vermute, dass dies der Grund für das von OP beobachtete Verhalten ist. Ich schaue gerade in den Quellcode, um mehr Details zu erhalten.
Evg
1
Relevanter Teil der Quelle ist: while (_ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal)wo _ISORT_MAXwird der Wert 32 angegeben. Zeile 3447 der <algorithm>Verwendung von VS 16.5.0
ChrisMM
In modernen Standardbibliotheken in keiner Sprache wird eine echte Quicksortierung verwendet. Alle verwenden modifizierte gemischte Versionen, die nur dann schnell verfügbar sind, wenn die Anzahl der Elemente groß genug ist. Beispielsweise verwenden Java und Python Timsort, während .NET Framework und die C ++ - Bibliothek von GCC Introsort verwenden . libstdc ++ und libc ++ verwenden auch die Einfügesortierung für kurze Sequenzen. Siehe Welche Algorithmen werden in C ++ 11 std :: sort in verschiedenen STL-Implementierungen verwendet?
Phuclv

Antworten:

14

Die Microsoft- std::sortImplementierung sieht folgendermaßen aus :

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
}

Wenn der zu sortierende Bereich 32 Elemente oder weniger enthält, wird Sortdie Einfügesortierung verwendet. Die Einfügesortierung wird swapin ihrer Implementierung nicht verwendet . Andernfalls wird die schnelle Sortierung zum Teilen und Erobern verwendet. In der Implementierung ruft es iter_swap(innen Unguarded_partition) auf, was wiederum Folgendes aufruft swap:

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

All dies sind Implementierungsdetails. Sie variieren von einer Standardbibliotheksimplementierung zur anderen.

Evg
quelle
1
libcxx verwendet die Einfügesortierung für Sequenzen mit einer Länge von weniger als 6 oder 30, je nach Typ. libstd ++ macht das für Sequenzen von 16 Elementen oder weniger. Welche Algorithmen werden in C ++ 11 std :: sort in verschiedenen STL-Implementierungen verwendet?
Phuclv