std :: sort nie zawsze zadzwonić std :: Swap

Question

Rozważmy następujący kod:

#include <algorithm> 
#include <iostream> 
#include <vector> 

namespace my_space 
{ 

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

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

Jeśli używam n=20 zwyczaj swap nazywa i tablica jest posortowana. Ale jeśli używam n=4, tablica jest posortowana poprawnie, ale niestandardowa funkcja wymiany to , a nie. Dlaczego? A co, jeśli kopiowanie moich obiektów jest naprawdę kosztowne?

Do tego testu użyłem gcc 4.5.3.

Answer 1

Dla małych zakresach, std::sort implementacje w stdlibc GCC++ (i inne implementacje biblioteki standardowej) powraca do wstawiania rodzaju ze względu na wydajność (jest to szybciej niż quicksort/introsort na małych zakresach).

Implementacja sortowania wstawek GCC z kolei nie zamienia się za pomocą std::swap - zamiast tego przesuwa całe zakresy wartości naraz, zamiast zamieniać się pojedynczo, co potencjalnie oszczędza wydajność. Odpowiednia część jest tu (bits/stl_algo.h:2187 GCC 4.7.2)

typename iterator_traits<_RandomAccessIterator>::value_type 
    __val = _GLIBCXX_MOVE(*__i); 
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); 
*__first = _GLIBCXX_MOVE(__val); 

_GLIBCXX_MOVE jest taka sama jak std::move z C++ 11 i _GLIBCXX_MOVE_BACKWARD3 jest std::move_backward - jest to jednak miejsce tylko w przypadku __GXX_EXPERIMENTAL_CXX0X__ jest określony; jeśli nie, to te operacje odwołują się do kopiowania zamiast poruszania się!

Co to jest przenieść wartość w aktualnej pozycji (__i) do czasowego składowania, a następnie przenieść wszystkie poprzednie wartości z __first do __i jednej góry, a następnie ponownie wstawić wartość tymczasową na __first. Tak więc zamiast tego przeprowadza n swapy w jednej operacji konieczności przemieszczania n wartości tymczasowego położenia:

first   i 
+---+---+---+---+---+---+ 
| b | c | d | e | a | f | 
+---+---+---+---+---+---+ 
        | 
    <---------------+ 


    first   i 
+---+---+---+---+---+---+ 
| --> b-> c-> d-> e-> f | 
+---+---+---+---+---+---+ 


    first   i 
+---+---+---+---+---+---+ 
| a | b | c | d | e | f | 
+---+---+---+---+---+---+ 
^

Answer 2

Zmodyfikowałem kod, aby był bardziej szczegółowy. Sortowanie dla 20 elementów wykorzystuje wiele zamian, używa końcowej kopii zadania. Sortowanie dla 4 elementów wykorzystuje tylko przypisanie i kopiowanie. Nie wiem o specyfikacjach, ale może to być coś, co można dalej robić.

#include <algorithm> 
#include <iostream> 
#include <vector> 

namespace my_space 
{ 

struct A 
{ 
    double a; 
    double* b; 
    A() 
     : a(0) 
     , b(NULL) 
    { } 
    A(const A &rhs) 
     : a(rhs.a) 
     , b(rhs.b) 
    { 
     std::cerr << "copy" << std::endl; 
    } 
    A& operator=(A const &rhs) 
    { 
     if(this==&rhs) 
       return *this; 
     a = rhs.a; 
     b = rhs.b; 
     std::cerr << "=" << std::endl; 
     return *this; 
    } 
    bool operator<(const A& rhs) const 
    { 
     return this->a < rhs.a; 
    } 
}; 

void swap(A& lhs, A& rhs) 
{ 
    std::cerr << "My swap.\n"; 
    std::swap(lhs.a, rhs.a); 
    std::swap(lhs.b, rhs.b); 
} 

} // namespace my_space 

int main() 
{ 
    const int n = 20; 

     std::cerr << "=== TEST CASE: n = " << n << std::endl; 
    std::cerr << "=== FILL ===" << std::endl; 
    std::vector<my_space::A> vec(n); 
    for (int i = 0; i < n; ++i) { 
     vec[i].a = -i; 
    } 

    std::cerr << "=== PRINT ===" << std::endl; 
    for (int i = 0; i < n; ++i) { 
     std::cerr << vec[i].a << " "; 
    } 
    std::cerr << "\n"; 

    std::cerr << "=== SORT ===" << std::endl; 
    std::sort(vec.begin(), vec.end()); 

    std::cerr << "=== PRINT ===" << std::endl; 
    for (int i = 0; i < n; ++i) { 
     std::cerr << vec[i].a << " "; 
    } 
    std::cerr << "\n"; 
} 

Wyjścia

=== TEST CASE: n = 4 
=== FILL === 
copy 
copy 
copy 
copy 
=== PRINT === 
0 -1 -2 -3 
=== SORT === 
copy 
= 
= 
copy 
= 
= 
= 
copy 
= 
= 
= 
= 
=== PRINT === 
-3 -2 -1 0 

I

=== TEST CASE: n = 20 
=== FILL === 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
copy 
=== PRINT === 
0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 
=== SORT === 
copy 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
My swap. 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
copy 
= 
copy 
= 
copy 
= 
copy 
= 
copy 
= 
=== PRINT === 
-19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 

Answer 3

W zależności od rodzaju, ciężkich może być droższy niż do przełączenia przypisania (C++ 98 proste zadanie). Standardowa biblioteka nie ma żadnego sposobu na wykrycie tych przypadków. Przynajmniej w C++ 11 rozwiązanie jest jasne: zaimplementuj operator przeniesienia przypisania dla wszystkich klas, w których implementujesz swap.