std :: sort non sempre chiamare std :: Swap

Question

Si consideri il seguente codice:

#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"; 
} 

Se uso n=20, la funzione di scambio personalizzato è chiamato e l'array è ordinato. Ma se utilizzo n=4, la matrice è ordinata correttamente, ma la funzione di scambio personalizzato è chiamata. Perché? E se fosse davvero costoso copiare i miei oggetti?

Per questo test, stavo usando gcc 4.5.3.

Answer 1

Per piccoli intervalli, std::sort implementazioni in stdlibc del GCC++ (e altre implementazioni della libreria standard) ricorre per insertion sort per motivi di prestazioni (è più veloce di quicksort/introsort su piccole gamme).

L'implementazione di ordinamento inserzione di GCC a sua volta non si scambia tramite std::swap - sposta invece interi intervalli di valori alla volta, invece di scambiare singolarmente, risparmiando potenzialmente le prestazioni. La parte pertinente è qui (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 è uguale std::move da C++ 11 e _GLIBCXX_MOVE_BACKWARD3 è std::move_backward - tuttavia, questo è solo il caso se __GXX_EXPERIMENTAL_CXX0X__ è definita; in caso contrario, queste operazioni ricorrono alla copia anziché al movimento!

Quello che fa è spostare il valore nella posizione corrente (__i) per una memorizzazione temporanea, quindi spostare tutti i valori precedenti da __first a __i uno, e poi reinserire il valore temporaneo __first. Quindi questo esegue n swap in una sola operazione invece dover spostare n valori in una posizione temporanea:

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

Ho modificato il codice per essere più dettagliato. L'ordinamento di 20 elementi utilizza molti swap, utilizza la copia finale dell'assegnazione. L'ordinamento di 4 elementi utilizza solo l'assegnazione e la copia. Non so delle specifiche, ma potrebbe essere qualcosa su cui andare avanti.

#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"; 
} 

uscite

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

E

=== 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

seconda del tipo, scambiando può essere più costoso di un movimento assegnazione (in C++ 98 un compito semplice). La libreria standard non ha alcun modo per rilevare questi casi. Almeno in C++ 11 la soluzione è chiara: implementare un operatore di assegnazione del movimento per tutte le classi in cui si implementa lo swap.