Книга: Эффективное использование STL

Совет 39. Реализуйте предикаты в виде «чистых» функций

Совет 39. Реализуйте предикаты в виде «чистых» функций

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

• Предикатом называется функция, возвращающая тип bool (или другое значение, которое может быть автоматически преобразовано к bool). Предикаты широко используются в STL. В частности, функции сравнения в стандартных ассоциативных контейнерах представляют собой предикаты. Предикатные функции часто передаются в виде параметров таким алгоритмам, как find_if, и различным алгоритмам сортировки (обзор алгоритмов сортировки приведен в совете 31).

• «Чистой» функцией называется функция, возвращаемое значение которой зависит только от параметров. Если f — «чистая» функция, а x и y — объекты, то возвращаемое значение f(x, y) может измениться только в случае изменения х или у.

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

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

• Предикатным классом называется класс функтора, у которого функция operator() является предикатом, то есть возвращает true или false. Как и следует ожидать, во всех случаях, когда STL ожидает получить предикат, может передаваться либо настоящий предикат, либо объект предикатного класса.

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

В совете 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 передается по значению — то есть копируется (теоретически возможны исключения, но на практике дело обстоит именно так; за подробностями обращайтесь к совету 38).

Первый вызов remove_if (расположенный в клиентском коде, удаляющем третий элемент из vw) создает анонимный объект BadPredcate с внутренней переменной timesCalled, равной 0. Этот объект, известный в remove_if под именем p, затем копируется в find_if, поэтому find_if тоже получает объект BadPredicate с переменной timesCalled, равной 0. Алгоритм find_if «вызывает» этот объект, пока тот не вернет true; таким образом, объект вызывается три раза. Затем find_if возвращает управление remove_if. Remove_if продолжает выполняться и в итоге вызывает remove_copy_if, передавая в качестве предиката очередную копию p. Но переменная timesCalled объекта p по-прежнему равна 0! Ведь алгоритм 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 — см. совет 41). Теперь вы знаете, что функции operator() в предикатных классах должны быть «чистыми» функциями, поэтому ограничение распространяется и на предикатные функции. Следующая функция также плоха в качестве предиката, как и объекты, созданные на основе класса BadPredcate:

bool anotherBadPredicate(const Widget&, const Widget&) {
 static int timesCalled = 0; // Нет! Нет! Нет! Нет! Нет! Нет!
 return ++timesCalled == 3;  // Предикаты должны быть "чистыми"
}                            // функциями, а "чистые" функции
                             // не имеют состояния

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

Оглавление книги