• Главная
• Контакты
• Нашёл ошибку
• Прислать материал
• Добавить в избранное

Нравится нам это или нет, но функции и представляющие их объекты (функторы) занимают важное место в STL. Они используются ассоциативными контейнерами для упорядочения элементов, управляют работой алгоритмов типа

find_if

for_each

transform

not1

bind2nd

Да, функторы и классы функторов встречаются в STL на каждом шагу. Встретятся они и в ваших программах. Умение создавать правильно работающие функторы абсолютно необходимо для эффективного использования STL, поэтому большая часть этой главы посвящена одной теме — как добиться того, чтобы функторы работали именно так, как им положено работать в STL. Впрочем, один совет посвящен другой теме и наверняка пригодится тем, кто задумывался о необходимости включения в программу вызовов

ptr_fun

mem_fun

mem_fun_ref

Ни C, ни C++ не позволяют передавать функции в качестве параметров других функций. Вместо этого разрешается передавать указатели на функции. Например, объявление стандартной библиотечной функции

qsort

void qsort(void *base, size_t nmemb, size_t size,

 int (*cmpfcn)(const void*, const void*));

В совете 46 объясняется, почему вместо функции

qsort

sort

cmpfcn

qsort

cmpcfn

qsort

Объекты функций STL создавались по образцу указателей на функции, поэтому в STL также действует правило, согласно которому объекты функций передаются по значению (то есть копируются). Вероятно, это правило лучше всего демонстрирует приведенное в Стандарте объявление алгоритма

for_each

template<class InputIterator, class Function>

Function // Возврат по значению

for_each(InputIterator first, InputIterator last,

 Function f);// Передача по значению

Честно говоря, передача по значению не гарантирована полностью, поскольку вызывающая сторона может явно задать типы параметров в точке вызова. Например, в следующем фрагменте

for_each

class DoSomething:

 public unary_function<int, void>{ // Базовый класс описан

 void operator()(int x){…}         // в совете 40

};

typedef deque<int>::iterator DequeIntIter; // Вспомогательное определение

deque<int> di;

…

DoSomething d; // Создать объект функции

…

for_each<DequeIntIter,    // Вызвать for_each с типами

 DoSomethng&>(di.begin(), // параметров DequeIntIter

 di.end(),                // и DoSomething&; в результате

 d);                      // происходит передача

                          // и возврат по ссылке.

Пользователи STL почти никогда не используют эту возможность, а в некоторых реализациях алгоритмов STL при передаче объектов функций по ссылке программы даже не компилируются. В продолжение этого совета будем считать, что объекты функций всегда передаются по значению, поскольку на практике это почти всегда так.

Поскольку объекты функций передаются и возвращаются по значению, вы должны позаботиться о том, чтобы объект функции правильно работал при передаче подобным способом (то есть копированием). Для этого необходимо соблюдение двух условий. Во-первых, объекты функций должны быть небольшими, в противном случае копирование обойдется слишком дорого. Во-вторых, объекты функций должны быть мономорфными (то есть не полиморфными), поэтому в них не могут использоваться виртуальные функции. Второе требование связано с тем, что при передаче по значению объектов производных классов в параметрах базового класса происходит отсечение: в процессе копирования удаляются специализированные составляющие (другой пример проблемы отсечения в STL приведен в совете 3).

Бесспорно, эффективность является важным фактором, и предотвратить отсечение тоже необходимо, однако не все функторы малы и мономорфны. Одно из преимуществ объектов функций перед обычными функциями заключается в отсутствии ограничений на объем информации состояния. Некоторые объекты функций от природы «упитанны», и очень важно, чтобы они могли передаваться алгоритмам STL так же просто, как и их «тощие» собратья.

Столь же нереалистичен и запрет на полиморфные функторы. Иерархическое наследование и динамическое связывание относятся к числу важнейших особенностей C++, и при проектировании классов функторов они могут принести такую же пользу, как и в других областях. Что такое классы функторов без наследования? C++ без «++». Итак, необходимы средства, которые бы позволяли легко передавать большие и/или полиморфные объекты функций с соблюдением установленного в STL правила о передаче функторов по значению.

Такие средства действительно существуют. Достаточно взять данные и/или полиморфные составляющие, которые требуется сохранить в классе функтора, перенести их в другой класс и сохранить в классе функтора указатель на этот новый класс. Рассмотрим пример создания класса полиморфного функтора с большим количеством данных:

template<typename T>       // BPFC = "Big Polymorphic

class BPFC:                //         Functor class"

 public                    // Базовый класс описан

 unary_function<T, void> { // в совете 40

private:

 Widget w; // Класс содержит большой объем

 int х;    // данных, поэтому передача

 …         // по значению

           // была бы неэффективной

public:

 virtual void operator()(const T& val) const; // Виртуальная функция.

 …                                            // создает проблему

};                                            // отсечения

Мы выделяем все данные и виртуальные функции в класс реализации и создаем компактный, мономорфный класс, содержащий указатель на класс реализации:

template<typename T> //Новый класс реализации

class BPFCImpl {     //для измененного BPFC.

private:

 Widget w; // Все данные, ранее находившиеся

 int х;    // в BPFC, теперь размещаются

 …         // в этом классе,

 virtual ~BPFCImpl(); // В полиморфных классах нужен

                      // виртуальный деструктор,

 virtual void operator()(const T& val) const;

 friend class BPFC<T>; // Разрешить BPFC доступ к данным

};

template<typename T>

class BPFC: // Компактная, мономорфная версия

 public unary_function<T, void> {

private:

 BPFCImpl<T>* pImpl; // Все данные BPFC

public:

 void operator()(const T& val) const; // Функция не является

 {                                    // виртуальной; вызов передается

  plImpl->operator()(val);            // BPFCImpl

 }

};

Реализация

BFPC::operator()

BPFC

BPFCImpl

BPFC

Материал изложен довольно кратко, поскольку описанные базовые приемы хорошо известны в кругах C++. В книге «Effective C++» этой теме посвящен совет 34. В книге «Приемы объектно-ориентированного проектирования» [6] соответствующая методика называется «паттерн Bridge». Саттер в своей книге «Exceptional C++» [8] использует термин «идиома

Pimpl

С позиций STL прежде всего необходимо помнить о том, что классы функторов, использующие данную методику, должны поддерживать соответствующий механизм копирования. Если бы вы были автором приведенного выше класса

BPFC

BPFCImpl

shared_ptr

Boost

В сущности, копирующий конструктор

BPFC

Для начала разберемся с основными терминами.

• Предикатом называется функция, возвращающая тип

bool

bool

find_if

• «Чистой» функцией называется функция, возвращаемое значение которой зависит только от параметров. Если

f

x

y

f(x, y)

В C++ все данные, используемые «чистыми» функциями, либо передаются в виде параметров, либо остаются постоянными на протяжении всего жизненного цикла функции (естественно, такие постоянные данные объявляются с ключевым словом const). Если бы данные, используемые «чистой» функцией, могли изменяться между вызовами, то вызов этой функции в разные моменты времени с одинаковыми параметрами мог бы давать разные результаты, что противоречит определению «чистой» функции.

Из сказанного должно быть понятно, что нужно сделать, чтобы предикаты были «чистыми» функциями. Мне остается лишь убедить читателя в том, что эта рекомендация обоснована. Для этого придется ввести еще один термин.

• Предикатным классом называется класс функтора, у которого функция

operator()

true

false

Обещаю, что новых терминов больше не будет. Теперь давайте разберемся, почему следует выполнять рекомендацию данного совета.

В совете 38 объяснялось, что объекты функций передаются по значению, поэтому при проектировании необходимо позаботиться о возможном копировании. Для объектов функций, являющихся предикатами, существует и другой аргумент в пользу специальной поддержки копирования. Алгоритмы могут создавать копии функторов и хранить их определенное время перед применением, причем некоторые реализации алгоритмов этим активно пользуются. Важнейшим следствием этого факта является то, что предикатные функции должны быть «чистыми».

Предположим, вы нарушили это ограничение. Ниже приведен плохо спроектированный класс предиката, который независимо от переданных аргументов возвращает

true

false

class BadPredicate:                   // Базовый класс описан

 public unary_function<Widget, bool>{ // в совете 40

public:

 BadPredicate(): timesCalles(0) {} // Переменная timesCalled

                                   // инициализируется нулем

bool operator()(const Widget&) {

 return ++timesCalled = 3;

}

private:

 size_t timesCalled;

};

Предположим, класс

BadPedicate

Widget

vector<Widget>

vector<Widget> vw; // Создать вектор и заполнить его

…                  // объектами Widget

vww.erase(remove_if(vw.begin(), // Удалить третий объект Widget.

 vw.end(),                      // связь между erase и remove_if

 BadPredcate()),                // описана в совете 32

 vw.end());

Программа выглядит вполне разумно, однако во многих реализациях STL из вектора

vw

Чтобы понять, почему это происходит, необходимо рассмотреть один из распространенных вариантов реализации

remove_if

template<typename FwdIterator, typename Predicate>

FwdIterator remove_if(FwdIterator begin, FwdIterator end, Predicate p) {

 begin = find_if(begin, end, p);

 if (begin==end) return begin;

 else {

  FwdIterator next=begin;

  return remove_copy_if(++next, end, begin, p);

 }

}

Подробности нас сейчас не интересуют. Обратите внимание: предикат 

p

find_if

remove_copy_if

p

Первый вызов

remove_if

vw

BadPredcate

timesCalled

remove_if

p

find_if

find_if

BadPredicate

timesCalled

find_if

true

find_if

remove_if

Remove_if

remove_copy_if

p

timesCalled

p

find_if

p

p

remove_copy_if

true

remove_if

Widget

Чтобы обойти эту лингвистическую ловушку, проще всего объявить функцию

operator()

const

class BadPredicate:

 public unary_function<Widget, bool> {

public:

 bool operator()(const Widget&) const {

  return ++timesCalled == 3; // Ошибка! Изменение локальных данных

 }                           // в константной функции невозможно

};

Из-за простоты этого решения я чуть было не озаглавил этот совет «Объявляйте

operator()

mutablе

operator()

operator()

operator()

Ранее в этом совете уже упоминалось о том, что всюду, где STL ожидает получить предикатную функцию, может передаваться либо реальная функция, либо объект предикатного класса. Этот принцип действует в обоих направлениях. В любом месте, где STL рассчитывает получить объект предикатного класса, подойдет и предикатная функция (возможно, модифицированная при помощи

ptr_fun

operator()

BadPredcate

bool anotherBadPredicate(const Widget&, const Widget&) {

 static int timesCalled = 0; // Нет! Нет! Нет! Нет! Нет! Нет!

 return ++timesCalled == 3;  // Предикаты должны быть "чистыми"

}                            // функциями, а "чистые" функции

                             // не имеют состояния

Как бы вы ни программировали предикаты, они всегда должны быть «чистыми» функциями.

Предположим, у нас имеется список указателей

Widget*

Widget

list<Widget*> WidgetPtrs;

bool isInteresting(const Widget *pw);

Если потребуется найти в списке первый указатель на «интересный» объект

Widget

list<Widget*>::iterator i = find_if(widgetPts.begin(), widgetPts.end(),

 isIntersting);

if (i != widgetPts.end()) {

 … // Обработка первого "интересного"

}  // указателя на Widget

С другой стороны, если потребуется найти первый указатель на «неинтересный» объект

Widget

list<Widget*>::iterator i = find_if(widgetPtrs.begin(), widgetPtrs.end(),

 not1(isInteresting)); // Ошибка! He компилируется

Перед

not1

isInteresting

ptr_fun

list<Widget*>::iterator i =

 find_if(widgetPtrs.begin(), widgetPtrs.end(),

 not1(ptr_fun(isInteresting))); // Нормально

if (i != widgetPtrs.end()) { // Обработка первого

 …                           // "неинтересного" указателя

}                            //на Widget

При виде этого решения невольно возникают вопросы. Почему мы должны применять

ptr_fun

not1

ptr_fun

Ответ оказывается весьма неожиданным. Вся работа

ptr_fun

not1

not1

ptr_fun

not1

isInteresting

isInteresting

not1

Впрочем,

not1

not1

not2

bind1st

bind2nd

Наверное, вместо туманного выражения «некоторые определения типов» вы бы предпочли иметь точный список? Речь идет об определениях

argument_type

first_argument_type

second_argument_type

result_type

operator()

std::unary_function

operator()

std::binary_function

Впрочем, не совсем так.

unary_function

binary_function

unary_function

operator()

binary_function

operator()

Пара примеров:

template<typename T>

class MeetsThreshold: public std::unary_function<Widget, bool> {

private:

 const T threshold;

public:

 Meets Threshold(const T& threshold);

 bool operator()(const WidgetS) const;

 …

};

struct WidgetNameCompare:

 std::binary_function<Widget, Widget, bool> {

 bool operator()(const Widget& lhs, const Widget& rhs) const;

};

В обоих случаях типы, передаваемые

unary_function

binary_function

operator()

operator()

unary_function

binary_function

Возможно, вы заметили, что

MeetsTheshold

WidgetNameCompare

MeetsTheshold

threshold

WidgetNameCompare

public

operator()

less<T>

plus<T>

Вернемся к определению WidgetNameCompare:

struct WidgetNameCompare:

 std::binary_function<Widget, Widget, bool> {

 bool operator()(const Widget& lhs, const Widget& rhs) const;

};

Хотя аргументы

operator()

Widget&

binary_function

Widget

unary_function

binary_function

const

Если

operator()

WidgetNameCompare

Widget*

struct PtrWidgetNameCompare:

 std::binary_function<const Widget*, const Widget*, bool> {

 bool operator()(const Widget* lhs, const Widget* rhs) const;

};

В этом случае типы, передаваемые

binary_function

operator()

unary_function

binary_function

operator()

Помните, что базовые классы

unary_function

binary_function

list<Widget> widgets;

…

list<Widget>::reverse_iterator i1 =        // Найти последний объект

 find_if(widgets.rbegin(), widgets.rend(), // Widget, не соответствующий

 not1(MeetsThreshold<int>(10)));           // пороговому критерию 10

                                           //(что бы это ни означало)

Widget w(аргументы конструктора);        // Найти первый объект Widget.

list<Widget>::iterator i2 =              // предшествующий w в порядке

 find_if(widgets.begin(), widgets.end(), // сортировки, определенном

 bind2nd(WidgetNameCompare(), w));       // WidgetNameCompare

Если бы классы функторов не определялись производными от

unary_function

binary_function

not1

bind2nd

Объекты функций STL построены по образцу функций C++, а функции C++ характеризуются единственным набором типов параметров и одним типом возвращаемого значения. В результате STL неявно подразумевает, что каждый класс функтора содержит единственную функцию

operator()

unary_function

binary_function

WidgetnNameCompare

PtrWidgetCompare

operator()

binary_function

Иногда в классе функтора бывает разумно определить несколько форм вызова, тем самым отказавшись от адаптируемости (примеры таких ситуаций приведены в советах 7, 20, 23 и 25), но это скорее исключение, а не правило. Адаптируемость важна, и о ней следует помнить при разработке классов функторов.

Загадочные функции

ptr_fun/mem_fun/mem_fun_ref

Действительно, имена выглядят довольно странно, но функции

ptr_fun

mem_fun

mem_fun_ref

В C++ существуют три варианта синтаксиса вызова функции

f

x

f(x); // Синтаксис 1: f не является функцией класса

      //(вызов внешней функции)

x.f(); // Синтаксис 2: f является функцией класса, а х

       // является объектом или ссылкой на объект

p->f(); // Синтаксис 3: f является функцией класса,

        // а р содержит указатель на х

Рассмотрим гипотетическую функцию, предназначенную для «проверки» объектов

Widget

void test(Widget& w); // Проверить объект w. Если объект не проходит

                      // проверку, он помечается как "плохой"

Допустим, у нас имеется контейнер объектов

Widget

vector<Widget> vw; // vw содержит объекты Widget

Для проверки всех объектов

Widget

vw

for_each

for_each(vw.begin(), vw.end(), test); // Вариант 1 (нормально компилируется)

Но представьте, что

test

Widget

Widget

class Widget {

public:

 …

 void test(); // Выполнить самопроверку. Если проверка

 …            // завершается неудачей, объект помечается

};            // как "плохой"

В идеальном мире мы могли бы воспользоваться

for_each

Widget::test

vw

for_each(vw.begin(), vw.end(),

 &Widget::test); // Вариант 2 (не компилируется!)

Более того, если бы наш мир был действительно идеальным, алгоритм

for_each

Widget::test

Widget*

list<Widget*> lpw; // Список lpw содержит указатели

                   // на объекты Widget

for_each(lpw.begin(), lpw.end(), // Вариант 3 (не компилируется!)

 &widget::test);

Но подумайте, что должно было бы происходить в этом идеальном мире. Внутри функции

for_each

for_each

for_each

for_each

В реальном мире существует только одна версия

for_each

template<typename InputIterator, typename Function>

Function for_each(InputIterator begin, InputIterator end, Function f) {

 while (begin != end) f(*begin++);

}

Жирный шрифт используется для выделения того, что при вызове

for_each

for_each

Теперь понятно, для чего нужны функции

mem_fun

mem_fun_ref

Принцип работы

mem_fun

mem_fun_ref

mem_fun

mem_fun_ref

template<typename R, typename C> // Объявление mem_fun для неконстантных

 mem_fun_t<R, C>                 // функций без параметров. С - класс.

mem_fun(R(C::*pmf)()); // R - тип возвращаемого значения функции.

                       // на которую ссылается указатель

Функция

mem_fun

pmf

mem_fun_t

operator()

operator()

list<Widget*> lpw; // См. ранее

…

for_each(lpw.begin(), lpw.end(),

 mem_fun(&Widget::test)); // Теперь нормально компилируется

При вызове

for_each

mem_fun_t

Widget::test

Widget*

lpw

for_each

mem_fun_t

Widget::test

Widget*

В целом

mem_fun

Widget::test

Widget*

for_each

mem_fun_t

mem_fun_ref

mem_fun_ref_t

Объекты, создаваемые функциями

mem_fun

mem_fun_ref

ptr_fun

for_each(vw.begin(), vw.end(), test); // См. ранее, вариант 1.

                                      // Нормально компилируется

компилируется, а следующие конструкции не компилируются:

for_each(vw.begin(), vw.end(), &Widget::test); // См. ранее, вариант 2.

                                               // Не компилируется.

for_each(lpw.begin(), lpw.end(), &Widget::test); // См. ранее, вариант 3.

                                                 // Не компилируется

При первом вызове (вариант 1) передается настоящая функция, поэтому адаптация синтаксиса вызова для

for_each

for_each

ptr_fun

test

ptr_fun

for_each(vw.begin(), vw.end(), ptr_fun(test)); // Компилируется и работает,

                                               // как вариант 1.

Если вы забываете, когда функция

ptr_fun

ptr_fun

Существует и другой подход — использовать

ptr_fun

С

mem_fun

mem_fun_ref

Остается лишь разобраться со странными именами адаптеров. Перед нами самый настоящий пережиток прошлого STL. Когда впервые возникла необходимость в адаптерах, разработчики STL ориентировались на контейнеры указателей (с учетом недостатков таких контейнеров, описанных в советах 7, 20 и 33, это может показаться странным, но не стоит забывать, что контейнеры указателей поддерживают полиморфизм, а контейнеры объектов — нет). Когда понадобился адаптер для функций классов (MEMber FUNctions), его назвали

mem_fun

mem_fun_ref

Допустим, объект класса

Widget

weight

maxSpeed

class Widget {

public:

 …

 size_t weight() const;

 size_t maxSpeed() const;

 …

}

Будем считать, что естественная сортировка объектов

Widget

weight

<

bool operator<(const Widget& lhs, const Widget& rhs) {

 return lhs.weight()<rhs.weight();

}

Предположим, потребовалось создать контейнер

multiset<Widget>

Widget

maxSpeed

multiset<Widget>

less<Widget>

operator<

Widget

multiset<Widget>

maxSpeed

less<Widget>

operator<

less<Widget>

maxSpeed

template<>                // Специализация std::less

struct std::less<Widget>: // для Widget: такой подход

 public                   // считается крайне нежелательным!

 std::binаry_function<Widget,

Widget, // Базовый класс описан

  bool> { // в совете 40

 bool operator() (const Widget& lhs, const Widget& rhs) const {

  return lhs.maxSpeed() < rhs.maxSpeed();

 }

};

Поступать подобным образом не рекомендуется, но, возможно, совсем не по тем причинам, о которых вы подумали. Вас не удивляет, что этот фрагмент вообще компилируется? Многие программисты обращают внимание на то, что в приведенном фрагменте специализируется не обычный шаблон, а шаблон из пространства имен

std

std

Вообще говоря, попытки модификации компонентов

std

std

std::less

shared_ptr

Boost

namespace std {

 template<typename T>                // Специализация std::less

 struct less<boost::shared_ptr<T> >: // для boost::shared_ptr<T>

 public                              // (boost - пространство имен)

 binary_function<boost::shared_ptr<T>,

  boost::shared_ptr<T>, // Базовый класс описан

  bool> {               // в совете 40

  bool operator()(const boost::shared_ptr<T>& a,

   const boost::shared_ptr<T>& b) const {

   return less<T*>()(a.get(), b.get()); // shared_ptr::get возвращает

  }                                     // встроенный указатель

 };                                     // из объекта shared_ptr

}

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

less

Widget

Программисты C++ часто опираются на предположения. Например, они предполагают, что копирующие конструкторы действительно копируют (как показано в совете 8, невыполнение этого правила приводит к удивительным последствиям). Они предполагают, что в результате взятия адреса объекта вы получаете указатель на этот объект (в совете 18 рассказано, что может произойти в противном случае). Они предполагают, что адаптеры

bind1st

not2

+

string

-

==

less

operator<

В действительности

operator<

less

less

less

operator<

В STL нет ни одного случая использования

less

multiset<Widget>

maxSpeed

less

struct MaxSpeedCompare:

 public binary_function<Widget, Widget, bool> {

 bool operator()(const Widget& lhs, const Widget& rhs) const {

  return lhs.maxSpeed() < rhs.maxSpeed();

 }

};

При создании контейнера

multiset

MaxSpeedCompare

less<Widget>

multiset<Widget, MaxSpeedCompare> widgets;

Смысл этой команды абсолютно очевиден: мы создаем контейнер

multiset

Widget

MaxSpeedCompare

multiset<Widget> widgets;

В нем создается контейнер

multiset

Widget

less<Widget>

operator<

less

less

operator<