[Из песочницы] Небольшое исследование по использованию функторов в стандартной библиотеке STL С++
Это статья для начинающих. Рассматривается использование простых функторов в алгоритмах. Рассказано про копирующий конструктор. Основная цель, это исследование количества создаваемых объектов функторов и простых методов как это можно сделать. Программа-пример последовательно усложняется. Некоторые шаги могут показаться неверными и лишними, но это типичный процесс исследования и отладки. Такой подход выбран сознательно. Обычный способ, когда делаются только разумные шаги, далек от реальности. И еще, чтобы заинтриговать, скажу, что в конце статьи получаем очень неожиданный результат.Итак, начнем.Для простоты считаем, что пространство имен std добавлено:
using namespace std;
Допустим, у нас есть контейнер с объектами. В нашем случае это вектор с интами.
vector
class Print
{
public:
void operator () (int value)
{
cout<<"value="< using namespace std; class Print
{
public:
void operator () (int value)
{
cout<<"value="< int main ()
{
vector 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()"< ~Print ()
{
cout<<"Print::~Print()"< using namespace std; class Print
{
public:
Print ()
{
cout<<"Print::Print()"< Print (const Print& print)
{
cout<<"Print::Print(const Print& )"< ~Print ()
{
cout<<"Print::~Print()"< Mul (const Mul& muk)
{
cout<<"Mul::Mul(const Mul& )"< ~Mul ()
{
cout<<"Mul::~Mul()"< Compare (const Compare& compare)
{
cout<<"Compare::Compare(const Compare& )"< ~Compare ()
{
cout<<"Compare::~Compare()"< int main ()
{
vector 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 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 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="< return 0;
}
Вывод программы:
rate=1.4582
Для массивов из миллиона элементов, значение примерно такое же. Честно говоря, для меня это было большим сюрпризом. То есть в среднем, на каждый элемент сортировочного массива создается полтора функтора! Хорошо, что сложность линейная и это не так сильно сказывается на общем времени работы алгоритма. Какие выводы? Если ваш функтор содержит много данные и имеет сложный копирующий конструктор, то это может привести к потери производительности.Литература:1. Герб Саттер, Андрей Александреску. Стандарты программирования на С++.: Пер. с англ. — М.: Изд. дом «Вильямс», 2005.2. www.cplusplus.com
