Небольшое исследование по использованию функторов в стандартной библиотеке STL С++

Это статья для начинающих. Рассматривается использование простых функторов в алгоритмах. Рассказано про копирующий конструктор. Основная цель, это исследование количества создаваемых объектов функторов и простых методов как это можно сделать. Программа-пример последовательно усложняется. Некоторые шаги могут показаться неверными и лишними, но это типичный процесс исследования и отладки. Такой подход выбран сознательно. Обычный способ, когда делаются только разумные шаги, далек от реальности. И еще, чтобы заинтриговать, скажу, что в конце статьи получаем очень неожиданный результат.

Итак, начнем.
Для простоты считаем, что пространство имен std добавлено:
using namespace std;

Допустим, у нас есть контейнер с объектами. В нашем случае это вектор с интами.
vector<int> mas;
for( int k = 1; k < 10; k++ )
{
    mas.push_back(k*10);
}

И мы хотим его распечатать. Можно сделать так:
for( int curr = 0; curr < mas.size(); curr++ )
{
    cout<<"value="<<mas[curr]<<endl;
}

или лучше с итераторами:
for( vector<int>::iterator iter = mas.begin(); iter != mas.end(); iter++ )
{
    cout<<"value="<<*iter<<endl;
}

более правильно, но длиннее.

Но лучше не использовать обычный цикл for, а взять алгоритм for_each, который сам перебирает элементы контейнера и вызывает для каждого заданную функцию. Это позволит писать более наглядный код. Алгоритм for_each принимает на вход начало и конец диапазона и функцию.
В качестве такой функции будем использовать функтор, который будет делать вывод. Функтор это объект, который используется как функция. Звучит страшно, но на самом деле просто. В данном случае, функтор представляет собой класс в котором реализован оператор скобки operator().
class Print
{
public:
    void operator() (int value)
    {
      cout<<"value="<<value<<endl;
    }
};

Оператор будет принимать в качестве параметра объект для обработки. Теперь алгоритм можно вызвать так:
for_each( mas.begin(), mas.end(), Print() );

Красиво и аккуратно. Что при этом происходит? Мы создаем безымянный объект Print, который передаем в функцию for_each, которая перебирает элементы с первого до последнего и передает их функции operator().
Вся программа будет выглядеть так:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Print
{
public:
    void operator() (int value)
    {
      cout<<"value="<<value<<endl;
    }
};

int main()
{
    vector<int> mas;

    for( int k = 1; k < 10; k++ )
    {
        mas.push_back(k*10);
    }

    for_each( mas.begin(), mas.end(), Print() );
    return 0;
}

Всё просто. А вот теперь вопрос, сколько объектов класса Print будет создано? Можно предположить, что один, при создании безымянного объекта командой Print().
Добавляем конструктор, деструктор и отладочный вывод, чтобы увидеть процесс создания и удаления объектов. Теперь класс будет выглядеть так:
class Print
{
public:
    
    Print()
    {
      cout<<"Print::Print()"<<endl;
    }

    ~Print()
    {
      cout<<"Print::~Print()"<<endl;
    }
  
    void operator() (int value)
    {
      cout<<"value="<<value<<endl;
    }
};

Запускаем:
Print::Print()
value=10
value=20
value=30
value=40
value=50
value=60
value=70
value=80
value=90
Print::~Print()
Print::~Print()

Как интересно. Один конструктор, и два деструктора. Как так может быть? Если вызвать деструктор для уже удаленного объекта, будет непредсказуемое поведение. Такого не может быть. Попробуем разобраться. И вот тут надо вспомнить, что объект может быть создан не только обычным образом, но и с использованием копирующего конструктора. Это конструктор, который создаёт новый объект, как копию переданного.
Print(const Print& print)
{
  cout<<"Print::Print(const Print& )"<<endl;
}

В данном случае наш объект не содержит никаких данных, поэтому мы ничего не копируем. Но надо помнить, если мы замещает стандартный копирующий конструктор своим, то вся ответственность ложится на нас.
Весь код:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Print
{
public:
    
    Print()
    {
      cout<<"Print::Print()"<<endl;
    }

    Print(const Print& print)
    {
      cout<<"Print::Print(const Print& )"<<endl;
    }

    ~Print()
    {
      cout<<"Print::~Print()"<<endl;
    }
  
    void operator() (int value)
    {
      cout<<"value="<<value<<endl;
    }
};

int main()
{
    vector<int> mas;

    for( int k = 1; k < 10; k++ )
    {
        mas.push_back(k*10);
    }

    for_each( mas.begin(), mas.end(), Print() );

    return 0;
}

Вывод:
Print::Print()
value=10
value=20
value=30
value=40
value=50
value=60
value=70
value=80
value=90
Print::Print(const Print& )
Print::~Print()
Print::~Print()

Ну вот, стало лучше, два конструктора, два деструктора. Но вот почему объектов два? Про первый объект понятно, он создается в нашем коде. В вот второй создается даже после того, как отрабатывает весь вывод. Зачем?
Посмотрим описание функции for_each:
Function for_each(InputIterator first, InputIterator last, Function fn);

Вот, функция возвращает функтор, который мы никак не использовали. Добавим получение результата.
Print p = for_each( mas.begin(), mas.end(), Print() );


Запускаем.

Print::Print()
value=10
value=20
value=30
value=40
value=50
value=60
value=70
value=80
value=90
Print::Print(const Print& )
Print::~Print()
Print::~Print()

Вывод совсем не изменился. То есть это и была невидимая переменная, которую нам передавали, но мы игнорировали.
Давайте сделаем нечто похожее, но с алгоритмом transform. Это алгоритм перебирает элементы одного контейнера, преобразует их и помещает в другой контейнер. Мы сделаем умножение на 10 и результат поместим обратно в исходный контейнер.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Mul
{
public:
    
    Mul()
    {
      cout<<"Mul::Mul()"<<endl;
    }

    Mul(const Mul& muk)
    {
      cout<<"Mul::Mul(const Mul& )"<<endl;
    }

    ~Mul()
    {
      cout<<"Mul::~Mul()"<<endl;
    }
  
    int operator() (int value)
    {
      cout<<"value="<<value<<endl;
      return value*10;
    }
};

int main()
{
    vector<int> mas;

    for( int k = 1; k < 10; k++ )
    {
        mas.push_back(k);
    }

    transform( mas.begin(), mas.end(), mas.begin(), Mul() );

    return 0;
}

Вывод:

Mul::Mul()
value=1
value=2
value=3
value=4
value=5
value=6
value=7
value=8
value=9
Mul::~Mul()

Ну, всё понятно, transform не возвращает никаких функторов, поэтому создается только один временный объект.
А вот теперь самое интересное:
Алгоритм sort
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Вопрос, сколько объектов типа Compare будет создано? Один? А вот и нет. Сделаем вектор из трех элементов и отсортируем. Нам надо будет создать функтор, который осуществляет сравнение двух объектом, это оператор меньше operator<, который принимает на вход два объекта и возвращает true если первый считаем меньше второго.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Compare
{
public:
    
    Compare()
    {
      cout<<"Compare::Compare()"<<endl;
    }

    Compare(const Compare& compare)
    {
      cout<<"Compare::Compare(const Compare& )"<<endl;
    }

    ~Compare()
    {
      cout<<"Compare::~Compare()"<<endl;
    }
  
    bool operator() (int v1, int v2)
    {
      cout<<"compare "<<v1<<" "<<v2<<endl;
      return v1 < v2;
    }
};

int main()
{
    vector<int> mas;

    for( int k = 1; k <= 3; k++ )
    {
        mas.push_back( rand() );
    }

    sort( mas.begin(), mas.end(), Compare() );

    return 0;
}


Вывод:
Compare::Compare()
Compare::Compare(const Compare& )
Compare::~Compare()
Compare::Compare(const Compare& )
Compare::Compare(const Compare& )
compare 18467 41
Compare::Compare(const Compare& )
compare 18467 41
Compare::~Compare()
compare 6334 41
Compare::Compare(const Compare& )
compare 6334 18467
compare 6334 41
Compare::~Compare()
Compare::~Compare()
Compare::~Compare()
Compare::~Compare()

Вот так сюрприз, пять сравнений и шесть созданных функторов!
Ну, один наш при вызове функции, а остальные использует сортировка. Почему они там? Скорее всего из-за рекурсивности алгоритма сортировки, где при каждом рекурсивном вызове создается новая копия, которая должна быть передана в функцию.
А теперь давайте подсчитаем сколько будет в среднем таких объектов при сортировке больших массивов. Добавим счетчик и уберем весь вывод. Счетчик реализуем как статический член класса, который будет один на все создаваемые экземпляры.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Compare
{
public:

    static int num;

    Compare()
    {
      num++;
    }

    Compare(const Compare& compare)
    {
      num++;
    }

    ~Compare()
    {
    }
  
    bool operator() (int v1, int v2)
    {
      return v1 < v2;
    }
};
int Compare::num = 0;

int main()
{
    vector<int> mas;

    int size = 10000;
    for( int k = 1; k <= size; k++ )
    {
        mas.push_back( rand() );
    }

    sort( mas.begin(), mas.end(), Compare() );

    float rate = (float)Compare::num/(float)size;

    cout<<"rate="<<rate<<endl;

    return 0;
}

Вывод программы:

rate=1.4582

Для массивов из миллиона элементов, значение примерно такое же. Честно говоря, для меня это было большим сюрпризом. То есть в среднем, на каждый элемент сортировочного массива создается полтора функтора! Хорошо, что сложность линейная и это не так сильно сказывается на общем времени работы алгоритма. Какие выводы? Если ваш функтор содержит много данных и имеет сложный копирующий конструктор, то это может привести к потере производительности.

Литература:
1. Герб Саттер, Андрей Александреску. Стандарты программирования на С++.: Пер. с англ. — М.: Изд. дом «Вильямс», 2005.
2. www.cplusplus.com

Комментарии 44

    0
    А оптимизация никак не может на этот рейт влиять?
      0
      У меня на тестах, при оптимизации O1 и O3 результаты по rate одинаковые. Параметры передаются по значению и скорее всего компилятор не может с этим ничего поделать.
        0
        Почему-то так я и подумал. Спасибо!
          +7
          Компилятор не может с этим ничего поделать, поскольку у вас в конструкторах/деструкторах код, который влияет на результат вычислений (программы). Пустые конструкторы/деструкторы компилятор вполне мог бы вырезать. Надо объектный код смотреть.
            +1
            Когда конструкторы и деструкторы пустые, можно и не волноваться. А когда они есть, и в них что-то сложное, тогда всё только ухудшается. И компилятор ничего не сделает, да и функции дорогие. :-)
            0
            rate зависит от степени отсортированности массива, это видно, если наполнять массив разными данными.
            Я, честно говоря, ожидал увидеть логарифмическую зависимость, но пока её наблюдать не приходится.
            Код
            #include <iostream>
            #include <vector>
            #include <algorithm>
            #include <iomanip>
            
            using namespace std;
            
            class Compare
            {
            public:
            
                static int num;
            
                Compare()
                {
                  num++;
                }
            
                Compare(const Compare& compare)
                {
                  num++;
                }
            
                ~Compare()
                {
                }
              
                bool operator() (int v1, int v2)
                {
                  return v1 < v2;
                }
            };
            int Compare::num = 0;
            
            int main()
            {
                vector<int> mas;
                
                for(int step = 1; step <= 3; ++step){
                
                  cout << "---- step " << step << endl;
            
                  for(int size = 1; size < 1e7; size *= 2){
                    
                    mas.resize(size);
                    for( int k = 0; k < size; k++ ) mas[k] = rand();
            
                    Compare::num = 0;
                    sort( mas.begin(), mas.end(), Compare() );
            
                    cout << setw(7) << size << setw(7) << setprecision(4) << ((float)Compare::num/(float)size) << endl;
                  }
                }
            
                return 0;
            }
            

            Результат выполнения: размер массива - rate
            >g++ habrasort.cpp -o habrasort && habrasort
            ---- step 1
                  1      4
                  2      2
                  4      1
                  8      1
                 16  1.125
                 32  1.313
                 64  1.422
                128  1.422
                256  1.477
                512  1.441
               1024  1.431
               2048  1.452
               4096  1.448
               8192  1.456
              16384  1.451
              32768  1.442
              65536  1.437
             131072  1.428
             262144  1.413
             524288   1.39
            1048576   1.38
            2097152  1.367
            4194304  1.362
            8388608  1.359
            ---- step 2
                  1      4
                  2    2.5
                  4    1.5
                  8  1.125
                 16 0.9375
                 32   1.25
                 64  1.391
                128  1.469
                256  1.406
                512  1.443
               1024  1.454
               2048  1.444
               4096   1.45
               8192   1.46
              16384  1.456
              32768  1.449
              65536  1.438
             131072  1.434
             262144  1.412
             524288   1.39
            1048576   1.38
            2097152  1.368
            4194304  1.362
            8388608  1.359
            ---- step 3
                  1      4
                  2      2
                  4    1.5
                  8  1.375
                 16  1.063
                 32  1.219
                 64  1.359
                128  1.391
                256  1.395
                512  1.486
               1024  1.449
               2048  1.462
               4096  1.446
               8192  1.465
              16384  1.448
              32768  1.443
              65536  1.438
             131072  1.428
             262144  1.413
             524288   1.39
            1048576  1.381
            2097152  1.367
            4194304  1.362
            8388608  1.359
            
            >g++ habrasort.cpp -o habrasort -O3 && habrasort
            ---- step 1
                  1      4
                  2      2
                  4      1
                  8      1
                 16  1.125
                 32  1.313
                 64  1.422
                128  1.422
                256  1.477
                512  1.441
               1024  1.431
               2048  1.452
               4096  1.448
               8192  1.456
              16384  1.451
              32768  1.442
              65536  1.437
             131072  1.428
             262144  1.413
             524288   1.39
            1048576   1.38
            2097152  1.367
            4194304  1.362
            8388608  1.359
            ---- step 2
                  1      4
                  2    2.5
                  4    1.5
                  8  1.125
                 16 0.9375
                 32   1.25
                 64  1.391
                128  1.469
                256  1.406
                512  1.443
               1024  1.454
               2048  1.444
               4096   1.45
               8192   1.46
              16384  1.456
              32768  1.449
              65536  1.438
             131072  1.434
             262144  1.412
             524288   1.39
            1048576   1.38
            2097152  1.368
            4194304  1.362
            8388608  1.359
            ---- step 3
                  1      4
                  2      2
                  4    1.5
                  8  1.375
                 16  1.063
                 32  1.219
                 64  1.359
                128  1.391
                256  1.395
                512  1.486
               1024  1.449
               2048  1.462
               4096  1.446
               8192  1.465
              16384  1.448
              32768  1.443
              65536  1.438
             131072  1.428
             262144  1.413
             524288   1.39
            1048576  1.381
            2097152  1.367
            4194304  1.362
            8388608  1.359
            


            UPD: Заполнил массив как for( int k = 0; k < size; k++ ) mas[k] = 1e7 - k; — получил число, стремящееся к 5.
              0
              Кстати, 1.359*2 = 2.718. Я тоже сначала думал о логарифмической зависимости, но получалось константа. Возможно, тут получается сумма какого-то рада из логарифмов, значение которого e/2.
                0
                К UPD про rate=5. Сложность алгоритма sort в среднем O(N*logN), а в худшем случае O(N^2). Тут похоже эффект от «плохого» массива.
                  0
                  До квадрата дело тут не дошло. 8 миллионов элементов так быстро бы не отсортировалось.
                  0
                  Запустил ваш код в 2013 студии с полной оптимизацией.

                  Результат
                  ---- step 1
                        1      2
                        2      2
                        4      1
                        8    0.5
                       16   0.25
                       32  0.125
                       64 0.4375
                      128 0.3594
                      256 0.3438
                      512 0.3652
                     1024  0.373
                     2048 0.3711
                     4096 0.4006
                     8192 0.3885
                    16384 0.3855
                    32768 0.3741
                    65536 0.3645
                   131072 0.3445
                   262144 0.3098
                   524288 0.2511
                  1048576 0.1682
                  2097152 0.1093
                  4194304 0.05469
                  8388608 0.02734
                  
                  ---- step 2
                        1      2
                        2      2
                        4      1
                        8    0.5
                       16   0.25
                       32  0.125
                       64 0.2969
                      128 0.3359
                      256 0.3906
                      512 0.3789
                     1024 0.3701
                     2048 0.3916
                     4096 0.3936
                     8192 0.3824
                    16384 0.3782
                    32768 0.3759
                    65536 0.3668
                   131072 0.3447
                   262144 0.3085
                   524288 0.2512
                  1048576 0.1682
                  2097152 0.1093
                  4194304 0.05469
                  8388608 0.02734
                  
                  ---- step 3
                        1      2
                        2      2
                        4      1
                        8    0.5
                       16   0.25
                       32  0.125
                       64 0.2969
                      128 0.3828
                      256 0.4375
                      512 0.3652
                     1024  0.373
                     2048  0.396
                     4096  0.395
                     8192  0.385
                    16384 0.3817
                    32768 0.3804
                    65536 0.3666
                   131072 0.3458
                   262144 0.3095
                   524288 0.2514
                  1048576  0.168
                  2097152 0.1093
                  4194304 0.05469
                  8388608 0.02734
                  

                    0
                    У меня нет под рукой VS 2013. Попробуйте заменить rand() на rand()*32768+rand().
                      0
                      Заменил, вот результат:
                      Результат с rand()*32768+rand()
                      ---- step 1
                            1      2
                            2      2
                            4      1
                            8    0.5
                           16   0.25
                           32  0.125
                           64 0.3438
                          128 0.4531
                          256 0.4141
                          512 0.3535
                         1024 0.3877
                         2048 0.3799
                         4096 0.3833
                         8192 0.3851
                        16384  0.383
                        32768 0.3881
                        65536 0.3911
                       131072 0.3884
                       262144 0.3914
                       524288 0.3899
                      1048576 0.3899
                      2097152 0.3896
                      4194304 0.3901
                      8388608 0.3901
                      ---- step 2
                            1      2
                            2      2
                            4      1
                            8    0.5
                           16   0.25
                           32  0.125
                           64 0.2969
                          128 0.3359
                          256 0.3555
                          512  0.377
                         1024 0.4082
                         2048 0.3843
                         4096 0.3877
                         8192 0.3982
                        16384 0.3973
                        32768   0.39
                        65536 0.3889
                       131072 0.3894
                       262144 0.3907
                       524288 0.3897
                      1048576 0.3899
                      2097152 0.3902
                      4194304 0.3901
                      8388608 0.3899
                      ---- step 3
                            1      2
                            2      2
                            4      1
                            8    0.5
                           16   0.25
                           32  0.125
                           64 0.3438
                          128 0.3594
                          256 0.3438
                          512 0.3945
                         1024  0.376
                         2048 0.3828
                         4096  0.396
                         8192 0.3813
                        16384  0.389
                        32768 0.3897
                        65536 0.3906
                       131072 0.3906
                       262144 0.3899
                       524288 0.3908
                      1048576 0.3903
                      2097152 0.3904
                      4194304 0.3897
                      8388608 0.3899
                      


                      Скорее всего это связано с тем что в С++ 11 поменяли реализацию, об этом указано на en.cppreference.com/w/cpp/algorithm/sort
                      а именно:

                      Complexity
                      until C++11: O(N·log(N)), where N = std::distance(first, last) comparisons on average.

                      since C++11: O(N·log(N)), where N = std::distance(first, last) comparisons.
                      0
                      Интересно… Можно отличать по этому признаку компиляторы (до их первого обновления).

                      На данный момент в gcc 4.8.1 такие результаты (с флагом -std=c++11 не меняются):
                      размер | rate       | массив M
                      -------+------------+------------------------
                           1 |          4 | любой
                        >> 1 |       1.25 | M[i] == M[j]
                        >> 1 |       1.33 | M[i] < M[i+1]
                        >> 1 |          5 | M[i] > M[i+1]
                        >> 1 | около 1.39 | M[i] == i % 2 ? 10 : 11
                        >> 1 | около 1.34 | M[i] == i % 3 ? 10 : 11
                      

                      («около» — значит нельзя уверенно сказать, что значение к чему-то стремится)
                      Попробуйте для интереса тоже забить константу/возрастающую/убывающую последовательность.
                0
                >> for_each( mas.begin(), mas.end(), Print() );
                Странно я всегда полагал что Print() создаcт анонимный объект, а при заходе в for_each произойдет его копирование. Это какой — то результат оптимизации, что с++ анонимные объекты передает принудительно по ссылке или стандарт?
                  0
                  А зачем создавать объект и делать его копирование, если он никому больше, как в самой функции, не нужен? Можно сразу там его один раз и создать.
                    0
                    Я могу согласиться что в этом нет смысла, но С++ не всегда делает то, что кажется нам разумным.
                      0
                      В C++ есть правило «as if» — компилятор может делать все, что угодно, если наблюдаемое поведение соответствует семантике стандарта. Если у вас нет кода, в котором можно наблюдать разницу между копированием и его отсутствием, то оптимизатор вправе заменить одно на другое.
                        0
                        Но в статье то как раз такой код, где можно наблюдать разницу (иначе бы мы и не смогли её пронаблюдать).
                    +3
                    Это стандарт. Оптимизация copy elision. Работает только с анонимными объектами или при возвращении значений из функции. (http://en.cppreference.com/w/cpp/language/copy_elision)
                    +6
                    Во-первых, функторы — это из теории категорий. А то, что в статье описано — это функциональные объекты.

                    Во-вторых, в статье напрашивается рассмотреть move семантику и перемещающие конструкторы.

                    Ну и в-третьих, писать свои функциональные объекты — это довольно унылое занятие, когда есть bind и лямбды, а печать так вообще делается как

                    std::copy(mas.cbegin(), mas.cend(), std::ostream_iterator<int>(std::cout, " "));
                    
                      0
                      Согласен, но не хотелось затрагивать С++11. Думаю, начинающим надо давать материал постепенно и попроще. Такая запись
                      std::ostream_iterator<int>(std::cout, " ")
                      

                      многих отпугнет.
                        +1
                        Для начинающих C++11 как раз проще, там не надо особо объяснять, как работают лямбды, да и граблей меньше. А в компиляторах они уже во всех есть несколько лет как.
                        +1
                        В рамках C++, «functors» — это таки вполне устоявшееся название, пусть и неудачное.
                          +2
                          Стандарт их называет функциональными объектами (function objects). В статье, я считаю, нужно писать правильно.
                            0
                            И отучать русских программистов от неудачного сленга. Кто-то в дремучем году ляпнул (не Александреску ли?), и понеслось.
                          0
                          К сожалению, «функтор» — чертовски перегруженное слово в русском языке.

                          В С++ ими традиционно обзывают классы с оператором (); не всякие функциональные объекты, а именно классы; потому что указатели на свободные функции, а также синтаксическое замыкание указателя на объект и указателя на функцию-член (ptr->*member), — не являются функторами.
                          Вслед за плюсами — функторами обзывают функциональные объекты и в других языках.
                          В теоркате — отображения категорий с определённой аксиоматикой (выполняется ковариантность)
                          В хаскелле — тайпкласс Functor — интерфейс, воспроизводящий теоркатовские функторы. Ну и реализации этого тайпкласса для параметризованных типов.
                          В окамле — параметризованные модули — отображения типов и модулей (по сути, категорий) вообще как бог на душу положит.
                          0
                          Интересный момент про создание копий функторов, не знал об этом. Пишут что это проблема библиотечного хидера algorithm в целом. В принципе она зависит от имплементации (некоторые версии STL могут быть свободны от этого косяка), но в большинстве имплементаций создаются копии.

                          В общем случае проблема лечится использованием std::reference_wrapper

                          Compare sort_criterion; sort( mas.begin(), mas.end(), std::cref(sort_criterion) );
                            0
                            Сортировка же зачастую рекурсивный алгоритм, логично предположить, что ваш функциональный объект будет передан в следующий рекурсивный вызов. Поскольку объект принимается по значению, то он копируется до тех пор, пока вы явно не попросите этого не делать. Здесь в игру и вступает reference_wrapper.
                            0
                            А как в этом случае себя будут вести лямбда функции?
                              0
                              Надо полагать, что как указатели на функции, если ничего не захватывают из области видимости, откуда создаются; и как объекты с конструкторами по умолчанию в другом лсучае.
                                +1
                                Во-первых, в C++ нет никаких лямбда-функций, есть лямбда-выраженин, и генерируемые из них замыкания.
                                Если лямбда выражение без захвата, то у типа-замыкания определён non-explicit оператор приведения к указателю на функцию с соответствующей сигнатурой.
                                Поскольку алгоритмы принимают действие с выводом типов, приведение к указателю на функцию в них происходить не может, происходит обычное копирование объекта, но поскольку он пустой, это в целом равносильно копированию указателя на функцию.
                                  0
                                  Помимо вышесказанного, за счёт встраивания копирования в результате вообще может не быть, и в этом можно убедиться, сравнив машинный код для обычного for по итератору, для range-based for и для std::for_each с замыканием.
                                  Если бы это было не так, то алгоритмы вроде for_each никто бы не использовал из-за abstraction penalty.
                                0
                                Кстати, при использовани libc++ (это реализация стандартной библиотеки в Clang), rate получается очень маленьким.
                                  0
                                  Укажите компилятор, только из изучения комментариев понял что у вас vs2013. «починили» стандартную библиотеку? надо посмотреть в код, а то раньше там параметр шаблона не передавался по цепочке вложенному вызову, что приводило к забавным результатам
                                    0
                                    Нет, не vs2013, у меня gcc 4.7.1.
                                    0
                                    Попробуйте добавить const это укажет компилятору что вызов метода не изменит передаваемый экземпляр функтора и копировать его нет необходимости, он ведь все равно не изменится :)

                                    void operator() (int value) const

                                    ПС: Я не проверял, просто гипотеза
                                      0
                                      Не работает, я проверял :)
                                        0
                                        Добавил const для случая с сортировкой — результат сохраняется как и у 0serg. Скорее всего компилятор и так понял нас правильно.
                                        Для интереса решил дело усложнить, добавив в operator() счётчик его вызовов. Количество вызовов конструктора осталось прежним. Количество вызовов operator() — O(NlnN), ничего противоестественного не произошло.
                                        Графики
                                        ctr_rate — вызовы конструктора на один элемент, cmp_rate — вызовы operator() на один элемент.

                                        Сортировка убывающей последовательности:


                                        Сортировка массива из нулей:


                                        Сортировка случайного массива:
                                        0
                                        Из этой статьи, на примере for_each, я узнал, что в шаблон в качестве класса можно передавать функцию. Это всегда так было?
                                          0
                                          Нет, в качестве класса можно только передать класс-функтор, обычно у которого переопределён оператор (). Но в качестве параметра шаблона может быть не только класс, но и любое скалярное значение, включая функцию.
                                            0
                                            Точнее, указатель на неё.
                                              0
                                              Это одно и то же :)

                                              #include <iostream>
                                              using namespace std;
                                              void foo()
                                              {
                                              	std::cout << "bar\n";
                                              }
                                              
                                              int main() {
                                              	(*&**&**&*&****&*foo)();
                                              	return 0;
                                              }
                                              
                                                +1
                                                Это не одно и то же, читайте что такое function-to-pointer conversion в ISO CPP.
                                                Простой пример:
                                                using function_type = void();
                                                function_type a[10]; // compile-time error, cannot declare array of function type
                                                function_type* a[10];
                                                0
                                                Действительно, параметром шаблона может быть функция, а не только указатель на неё. Не знал.

                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                          Самое читаемое