станд :: сортировки не всегда называют станд :: своп

Question

Рассмотрим следующий код:

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

Если я использую n=20, функция пользовательской замены называется и массив отсортирован. Но если я использую n=4, массив сортируется правильно, но пользовательская функция свопинга - , а не. Почему это? Что делать, если мне действительно дорого копировать мои объекты?

Для этого теста я использовал gcc 4.5.3.

Answer 1

Для малых диапазонов std::sort реализации в stdlibc GCC в ++ (и другие стандартные реализации библиотеки) рецидивирует для вставки рода для повышения производительности (это быстрее, чем quicksort/introsort на небольших диапазонах).

Вставка сортировки вставки GCC, в свою очередь, не сворачивается через std::swap - вместо этого она перемещает целые диапазоны значений за раз, вместо того, чтобы менять их индивидуально, что потенциально позволяет сэкономить производительность. Соответствующая часть здесь (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 такое же, как std::move от C++ 11 и _GLIBCXX_MOVE_BACKWARD3 является std::move_backward - однако, это только в том случае, если __GXX_EXPERIMENTAL_CXX0X__ определяется; если нет, то эти операции прибегают к копированию, а не к движению!

Что это делает переместить значение в текущей позиции (__i) на временное хранение, а затем переместить все предыдущие значения от __first до __i одного до, а затем повторно вставьте временное значение в __first. Таким образом, это выполняет п свопы в одну операцию вместо того, чтобы, чтобы двигаться п значения во временное местоположение:

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

Я изменил код, чтобы быть более подробным. Сортировка для 20 элементов использует много свопов, использует конечную копию назначения. Сортировка для 4 элементов использует только назначение и копирование. Не знаю о спецификациях, но это может быть что-то еще.

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

Выходы

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

И

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

В зависимости от типа, замена может быть более дорогим, чем двигаться присваивания (в C++ 98 простое назначение). Стандартная библиотека не имеет способа обнаружить эти случаи. По крайней мере, в C++ 11 решение понятно: реализуйте оператор присваивания move для всех классов, где вы реализуете swap.