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 swap
nicht aufgerufen.
- Ich verwende MSVC ++ 2019 auf x64.
- Wann wird
swap
angerufen und wann nicht und warum? Vielen Dank! - Ich habe bei der Kopierzuweisung nicht
swap
nur verwendet, um zwischen dem Aufruf und der Sortierung vom Kopierzuweisungsoperator zu unterscheiden.
std::sort
greift auf die Einfügesortierung zurück, wenn die Anzahl der Elemente 32 oder weniger beträgt, und verwendet andernfalls die schnelle Sortierung.while (_ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal)
wo_ISORT_MAX
wird der Wert 32 angegeben. Zeile 3447 der<algorithm>
Verwendung von VS 16.5.0Antworten:
Die Microsoft-
std::sort
Implementierung sieht folgendermaßen aus :Wenn der zu sortierende Bereich 32 Elemente oder weniger enthält, wird
Sort
die Einfügesortierung verwendet. Die Einfügesortierung wirdswap
in ihrer Implementierung nicht verwendet . Andernfalls wird die schnelle Sortierung zum Teilen und Erobern verwendet. In der Implementierung ruft esiter_swap
(innenUnguarded_partition
) auf, was wiederum Folgendes aufruftswap
:All dies sind Implementierungsdetails. Sie variieren von einer Standardbibliotheksimplementierung zur anderen.
quelle