Dlaczego swd jest wywoływany przez std :: sort tylko wtedy, gdy mój kontener ma więcej niż 32 elementy?

13

Witam mam proste pytanie:

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

}

Z ponad 32 elementami sortowanie wywołuje swap. Przy 32 elementach lub mniej elementy są nadal sortowane, ale swapnie są wywoływane.

  • Używam MSVC ++ 2019 na x64.
  • Kiedy się swapnazywa, a kiedy nie i dlaczego? Dziękuję Ci!
  • Nie użyłem swapprzy przypisaniu kopii tylko po to, aby odróżnić wywołanie od sortowania od operatora przypisania kopii.
Maestro
źródło
6
std::sortstosuje sortowanie wstawiane, jeśli liczba elementów wynosi 32 lub mniej, aw przeciwnym razie używa szybkiego sortowania.
Evg
@Evg Czy to wymóg, czy jest to wyjaśnienie dla tego konkretnego kontekstu?
François Andrieux
2
@ FrançoisAndrieux, jest to szczegół implementacji standardowej biblioteki Microsoft. Domyślam się, że jest to powód zachowania zaobserwowanego przez OP. Obecnie szukam kodu źródłowego, aby uzyskać więcej szczegółów.
Evg
1
Istotną częścią źródła jest: while (_ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal)gdzie _ISORT_MAXpodano wartość 32. Wiersz 3447 <algorithm>użycia VS 16.5.0
ChrisMM
Żaden prawdziwy szybki przegląd nie jest używany w żadnych współczesnych standardowych bibliotekach w żadnym języku. Wszystkie używają zmodyfikowanych wersji mieszanych, co jest szybkim sortowaniem tylko wtedy, gdy liczba elementów jest wystarczająco duża. Na przykład Java i Python używają Timsort, podczas gdy .NET Framework i biblioteka C ++ GCC używają Introsort . libstdc ++ i libc ++ również używają sortowania wstawiania dla krótkich sekwencji. Zobacz Jakie algorytmy są używane w C ++ 11 std :: sort w różnych implementacjach STL?
phuclv,

Odpowiedzi:

14

std::sortImplementacja Microsoft wygląda następująco:

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
}

Gdy zakres do sortowania ma 32 elementy lub mniej, Sortużywa sortowania wstawianego. Sortowanie wstawiania nie jest używane swapw jego implementacji . W przeciwnym razie stosuje się szybkie sortowanie z podziałem i zwycięstwem. W implementacji wywołuje iter_swap(wewnątrz Unguarded_partition), co z kolei wywołuje swap:

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

Wszystko to są szczegóły implementacji. Różnią się one od jednej standardowej implementacji biblioteki do drugiej.

Evg
źródło
1
libcxx używa sortowania wstawiania dla sekwencji o długości mniejszej niż 6 lub 30, w zależności od typu. libstd ++ robi to dla sekwencji 16 elementów lub mniej. Jakie algorytmy są używane w C ++ 11 std :: sort w różnych implementacjach STL?
phuclv,