Это статья для начинающих. Рассматривается использование простых функторов в алгоритмах. Рассказано про копирующий конструктор. Основная цель, это исследование количества создаваемых объектов функторов и простых методов как это можно сделать. Программа-пример последовательно усложняется. Некоторые шаги могут показаться неверными и лишними, но это типичный процесс исследования и отладки. Такой подход выбран сознательно. Обычный способ, когда делаются только разумные шаги, далек от реальности. И еще, чтобы заинтриговать, скажу, что в конце статьи получаем очень неожиданный результат.
Итак, начнем.
Для простоты считаем, что пространство имен 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
Автор: varerysan
